美文网首页
009-牛客机试题2（通过测验）

009-牛客机试题2（通过测验）

作者: 千转军师 | 来源:发表于2021-04-07 17:10 被阅读0次

    1、IP地址统计问题

    注： 有些小细节会导致比较难排查的错误，例如ip字符串和mask字符串分离是否真确，即使一个字母，也会出错。

    #include <stdio.h>
#include <string.h>
#include <stdlib.h>
int toNum(char *str_p, unsigned char *out)//需要保证out为大于或等于4个元素的数组
{
    int i;
    int pos;
    int cnt;
    char tmp[128] = {0};
    char *tmp_p = tmp;
    i = 0;
    pos = 0;
    cnt = 0;
    while(str_p[i] != '\0')
    {
        if(str_p[i] == '.')
        {
            tmp_p = str_p + pos;
            tmp_p[i - pos] = '\0';
            out[cnt] = atoi(tmp_p);
            if(out[cnt] == 0 && tmp_p[0] != '0')
                return -1;
            pos = i + 1;
            cnt++;
            if(cnt >= 3)
                break;
        }   
        i++;
    }
    if(cnt != 3)
        return -1;
    tmp_p = str_p + pos;
    out[3] = atoi(tmp_p);
    return 0;
}
int maskIsOk(unsigned char *num_mask)
{
    int i, j;
    int mark;
    int one_num;
    mark = 0;
    one_num = 0;        //全部为1或者0的掩码为非法
    for(i = 0; i < 4; i++)
    {
        for(j = 0;j < 8; j++)
        {
            if((num_mask[i] & (1 << (7 - j))) != 0)
            {
                one_num++;
                if(mark == 1)
                {
                    return -1;
                }
            }       
            else if(mark == 0)
            {
                mark = 1;
                continue;
            }
        
        }
    }
    if(one_num == 0 || one_num >= 32)
    {
        return -1;
    }
    return 0;
}
int isIpPrivate(unsigned char *num_ip)
{
    int ip;
    int type;
    int i;
    ip = num_ip[0] << 24 | num_ip[1] << 16 | num_ip[2] << 8 | num_ip[3];
    const int start[] = 
    {
        10 << 24,
        172 << 24 | 16 << 16,
        192 << 24 | 168 << 16
    };
    const int end[] = 
    {
        10  << 24 | 255 << 16 | 255 << 8 |255,
        172 << 24 | 31 << 16 | 255 << 8 | 255 ,
        192 << 24 | 168 << 16 | 255 << 8 | 255 
    };
    for(i = 0; i < 3;  i++)
    {
        if(ip >= start[i] && ip <= end[i])
        {
            return 0;      
        }
    }
    return -1;
}
int ipType(unsigned char *num_ip)
{
    int ip;
    int type;
    int i;
    ip = num_ip[0] << 24 | num_ip[1] << 16 | num_ip[2] << 8 | num_ip[3];
    if(num_ip[0] == 0 || num_ip[0] == 127)
    {
        return 0;
    }
    
    const int start[] = 
    {
        1 << 24,
        128 << 24,
        192 << 24,
        224 << 24,
        240 << 24
    };
    const int end[] = 
    {
        126 << 24 | 255 << 16 | 255 << 8 |255,
        191 << 24 | 255 << 16 | 255 << 8 |255,
        223 << 24 | 255 << 16 | 255 << 8 |255,
        239 << 24 | 255 << 16 | 255 << 8 |255,
        255 << 24 | 255 << 16 | 255 << 8 |255
    };
    
    for(i = 0; i < 5;  i++)
    {
        if(ip > start[i] && ip < end[i])
        {
           return  (i + 1);     
        }
    }
    return -1;
}

int main(void)
{
    int i, j;
    char str_in[128] = {0};
    char str_ip[128] = {0};
    char str_mask[128] = {0};
    char *str_ip_p;
    char *str_mask_p;
    unsigned char num_ip[4] = {0};
    unsigned char num_mask[4] = {0};
    int a, b, c, d, e, error, pri;
    a = b = c = d = e = error = pri = 0;
    int ret, type;
    while(scanf("%s", str_in) != EOF)
    {
        strcpy(str_ip, str_in);
        strcpy(str_mask, str_in);
        i = 0;
        while(str_in[i] != '\0')
        {
            if(str_in[i] == '~')
            {
                str_ip_p = str_ip;
                str_ip_p[i] = '\0';
                str_mask_p = str_mask + i + 1;
                break;          
            }
            i++;
        }       
        ret = toNum(str_mask_p, num_mask);
        if(ret != 0)
        {
            error++;
            continue;
        }
        else if(maskIsOk(num_mask) != 0)
        {
            error++;
            continue;
        }
        
        ret = toNum(str_ip_p, num_ip);
        if(ret != 0)
        {
            error++;
            continue;
        }   
        else
        {
            type = ipType(num_ip);
            if(type == 1)
                a++;
            else if(type == 2)
                b++;
            else if(type == 3)
                c++;
            else if(type == 4)
                d++;
            else if(type == 5)
                e++;
            else if(type == 0)
                ;
            else
                {error++; continue;}
            if(isIpPrivate(num_ip) == 0)
                pri++;
        }
    }
    
    printf("%d %d %d %d %d %d %d\n", a, b, c, d, e, error, pri);
    return 0;
}

    2、密码验证合格程序

    
#include <stdio.h>
#include <string.h>
int main(void)
{
    char psswd[128] = {0};
    int len;
    int mark[4];
    int brk;
    int i, j;
    while(scanf("%s", psswd) != EOF)
    {
        //printf("----------------------->\n");
        len = strlen(psswd);
         if(len <= 8)
         {
             printf("%s\n", "NG"); 
             continue;
         }
         mark[0] = mark[1] = mark[2] = mark[3] =  0;
         for(i = 0; i < len; i ++)
         {
             if((psswd[i] >= 'a' && psswd[i] <= 'z'))
             {
                 mark[0] = 1;
             }
              else if((psswd[i] >= 'A' && psswd[i] <= 'Z'))
             {
                 mark[1] = 1;
             }
             else if((psswd[i] >= '0' && psswd[i] <= '9'))
             {
                 mark[2] = 1;
             }
             else
             {
                 mark[3] = 1; 
             } 
         }
        if((mark[0] + mark[1] + mark[2] + mark[3])  < 3)
        {
            printf("%s\n", "NG"); 
            continue;
        }   
        brk = 0;
        for(i = 0; i < len - 5; i ++)
        {
            if(brk == 1)
            {
                printf("%s\n", "NG");    
                break;
            }
            for(j = i + 3; j < len - 2; j++)
            {
                if(psswd[i] == psswd[j] && psswd[i + 1] == psswd[j + 1] && psswd[i + 2] == psswd[j + 2])             
                { 
                    brk = 1;
                    break;   
                }
            }
        }     
        if(brk == 1)
        {
            continue;
        }
        printf("%s\n", "OK");       
    }   
    return 0;
}

    3、求四则式子的数值

    前提： 输入的格式是正确的，不考虑对格式的判断
    例子： 1+2*10-(-2+3)

    /*注：（1）括号里的式子用递归解决；
*（2）存储+-符号用sybol[0]，存储* /符号用symbol[1]；存储第一个计数值用num[0]，第二个数值用num[1]，主要是为了解决乘除的优先级高于加减这个规则；
*（3）遇到符号时，对前面的数值计算；
*/
#include <stdio.h>
#include <string.h>
#define PRINT_EN 0
int mypow(int n, int cnt)
{
    int i;
    int ret = 1;
    for(i = 0; i < cnt; i++)
    {
        ret *= n;
    }
    return ret;
}
int calc(char *str_p, int set_pos)
{
    int symbol[2] = {0};
    int num[2] = {0};
    int tmp[16] = {0};
    int tmp_value, result;
    char ch;
    tmp_value = result = 0;
    static int pos = 0;  //位置
    if(set_pos == 1)
    {
        pos = 0;
    }
    int mark;
    mark = 0;
    while(1)
    {
        if(mark == 1)
           ch = '+';
        else if(str_p[pos] == '\0')//字符串末尾多个 +，执行最后操作
            ch = '+';
        else 
            ch = str_p[pos];
        
        if(ch >= '0' && ch <= '9')
        {
            tmp_value *= 10;
            tmp_value += ch - '0';
        }
        else if(ch == '+' || ch == '-')
        {
            if(symbol[1] == 1)//上一个为乘法
            {
                num[1] *= tmp_value;  
                if(symbol[0] == 1 || symbol[0] == 0)//上上个为加法
                {
                    num[0] += num[1]; 
                }
                else if(symbol[0] == 2)//上上个为减法法
                {
                    num[0] -= num[1]; 
                }
            }
            else if(symbol[1] == 2)//上一个为除法
            {
                if(tmp_value != 0)
                {
                    num[1] /= tmp_value;  
                }                
                if(symbol[0] == 1)//上上个为加法
                {
                    num[0] += num[1]; 
                }
                else if(symbol[0] == 2)//上上个为减法法
                {
                    num[0] -= num[1]; 
                }
            }
            else if(symbol[1] == 0 && (symbol[0] == 1 || symbol[0] == 0))
            {
                num[0] += tmp_value;             
            }
             else if(symbol[1] == 0 && symbol[0] == 2)
            {
                num[0] -= tmp_value;             
            }
            symbol[1] = 0;
            if(ch == '+')
            {
                if(PRINT_EN)printf("(+)===>num0=%d   num1=%d\n", num[0], num[1]);
                symbol[0] = 1;    
            }
            else if(ch == '-')
            {
                if(PRINT_EN)printf("(-)===>num0=%d   num1=%d\n", num[0], num[1]);
                symbol[0] = 2;
            }
            tmp_value = 0;          
        }
        else if(ch == '*' || ch == '/')
        {
            if(symbol[1] == 1)
            {
                num[1] *= tmp_value;
            }
            else if(symbol[1] == 2)
            {
                num[1] /= tmp_value;
            }
            else if(symbol[1] == 0 )
            {
                num[1] = tmp_value;
            }           
            if(ch == '*')
            {
                if(PRINT_EN)printf("(*)===>num0=%d   num1=%d\n", num[0], num[1]);
                symbol[1] = 1;    
            }
            else if(ch == '/')
            {
                if(PRINT_EN)printf("(/)===>num0=%d   num1=%d\n", num[0], num[1]);
                symbol[1] = 2;
            } 
            tmp_value = 0;
        }
       else if(ch == '(' || ch == '[' || ch == '{')
        {
            pos++;
            if(PRINT_EN)printf("(digui)------------------\n");
            tmp_value = calc(str_p, 0);
            if(PRINT_EN)printf("(digui)+++++++++++ str_p:%c  pos:%d  tmp_value:%d\n", *str_p, pos, tmp_value);
        }
        else if(ch == ')' || ch == ']' || ch == '}')
        {
            mark = 1;
            continue;
        }
        if(mark == 1)
            break;
         
        if(str_p[pos] == '\0')
            break;
        else
            pos++;       
    }
    return num[0];
}

int main(void)
{
    //char str[] = "-3-(5+6)*(3-1)";
    //char str[] = "3+1";
    
    char str[512] = {0};
    scanf("%s", str);
    printf("%d\n", calc(str, 1));
    
    return 0;
}

    参考

    #include <stdio.h>
#include <ctype.h>
int pos;
int compute(char* data)
{
    int len = strlen(data);
    int stack[1000];
    int top = -1;
    char flag = '+';
    int num = 0;
    
    while(pos < len)
    {
        if(data[pos] == '{' || data[pos] == '[' || data[pos] == '(')
        {
            pos++;
            num = compute(data);
        }
        
        while(pos < len && isdigit(data[pos]))
        {
            num = 10 * num + data[pos] - '0';
            pos++;
        }
        
        switch(flag)
        {
            case '+':
                stack[++top] = num;
                break;
            case '-':
                stack[++top] = -num;
                break;
            case '*':
                stack[top] *= num;
                break;
            case '/':
                stack[top] /= num;
                break;
        }
        
        num = 0;
        flag = data[pos];
        
        if(data[pos] == '}' || data[pos] == ']' || data[pos] == ')')
        {
            pos++;
            break;
        }
        pos++;
    }
    
    int res = 0;
    for(int i = 0; i <= top; i++)
    {
        res += stack[i];
    }
    return res;
}


int main()
{
    char data[1000];
    while(scanf("%s", data) != EOF)
    {
        pos = 0;
        int res = compute(data);
        printf("%d\n",res);
    }
    return 0;
}

    4、图片整理

    注：大小排序

    //冒泡法
#include <stdio.h>
#include <stdio.h>
int main(void)
{
    char buf[1024] = {0};
    
    int len;
    int i, j;
    while(scanf("%s", buf) != EOF)
    {
        len = strlen(buf);
        for(i = 0; i < len - 1; i++)
        {
            for(j = 0; j < (len - i - 1); j++)
            {
                if(buf[j] > buf[j + 1])
                {
                    buf[j] ^= buf[j + 1];
                    buf[j + 1] ^= buf[j];
                    buf[j] ^= buf[j + 1];
                }
            }              
        }
        printf("%s\n", buf);    
    } 
    return 0;
}

    快排法移植

    #include <stdio.h>
#include <string.h>
void swap(char *x, char *y) {
    char t = *x;
    *x = *y;
    *y = t;
}
void quick_sort_recursive(char arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(char arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}
int main(void)
{
    char buf[1024] = {0};  
    int len;
    int i, j;
    while(scanf("%s", buf) != EOF)
    {
        len = strlen(buf);
        quick_sort(buf, len);
        printf("%s\n", buf);    
    } 
    return 0;
}

    参考网友的：位图标记法

    #include <stdio.h>
#include <string.h>

int main(){
    char s[1025];
    while (scanf("%s", s)!= EOF){
        int a[1025] ={0};
        int len=strlen(s);
        for(int i=0; i< len; i++)
        {
            a[s[i]]++;
        }
        for(int i=0; i<1025; i++)
        {
            while(a[i]!=0){
                printf("%c",i);
                a[i]--;
            }
        }
        printf("\n");
    }
}

    5、蛇形矩阵

    #include <stdio.h>
int getNum(int num_start, int step_start, int idx)
{
    int i;
    int tmp, step;
    tmp = num_start;
    step = step_start;
    for(i = 0; i < idx; i++)
    {
        tmp += step;
        step++;        
    }
    return tmp;
}
int main(void)
{
    int i, j;
    int num;
    while(scanf("%d", &num) != EOF)
    {
        for(i = 0; i < num; i++)
        {
            for(j = 0; j < num - i; j++)
            {
                 printf("%d ", getNum(getNum(1, 1, i), 2 + i, j));
            }       
            printf("\n");
        }       
    }
    return 0;
}

    或者

    
#include <stdio.h>
int main(void)
{
    int i, j;
    int num;
    int step  = 1;
    int start = 1; 
    int start2 = 2; 
    int step3  = 2;
    int start3 = 1; 
    
    while(scanf("%d", &num) != EOF)
    {
        for(i = 0; i < num; i++)
        {                     
            for(j = 0; j < num - i; j++)
            {
                if(j == 0)
                {
                    printf("%d ", start3);    
                }
                else
                {
                    printf("%d ", start3 + step3);
                    start3 += step3;
                    step3++;
                }  
            }       
            printf("\n");
            start += step;
            step++;
            start3 = start;
            start2++;
            step3 = start2;                      
        }       
    }
    return 0;
}

    6、砝码称重

    6.1 未通过（原因超时；空间规模小的话，还可以计算）

    分析： 用的是穷举法，二进制为1代表数存在，0代表不存在，2的n次方遍历代表n个数的组合个数。我发现，最近刷的题用这种方法来解决总是耗时久，效率不好。

    //注： 遍历次数超过2 的 30 次方，耗时愈加明显，达到秒的级别
#include <stdio.h>
#include <stdlib.h>
#define MAX_GROUP_NUM 10
#define MAX_FAMA_NUM 6
#define MAXFAMA_WIGHT 2000
int strToNumArray(char *str, int *array, int *array_n, int max_num)
{
    int i, j, tmp, cnt;
    char buf[16] = {0};
    i = j = cnt = 0;
    while(str[i] != '\0')
    {
        if(str[i] == ' ')
        {
            i++;
            continue;
        }
        tmp = i;
        while(str[i] != ' ' && str[i] != '\0')
        {
            buf[i - tmp] = str[i];
            i++;
        }
        buf[i - tmp] = '\0';
        array[cnt] = atoi(buf);       
        if(array[cnt] == 0 && buf[0] != '0')
        {
             *array_n = cnt;   
             return -1;   
        }
        cnt++; 
        if(cnt >= max_num)
        {
            *array_n = cnt;   
             return -1;   
        }
    }
    *array_n = cnt;   
     return 0; 
}


int main(void)
{  
    long long long_i, long_j;
    int i, j;
    int val[MAX_GROUP_NUM] = {0};
    int num[MAX_GROUP_NUM] = {0};
    int val_all[MAX_FAMA_NUM * MAX_GROUP_NUM] = {0};
    int group, totle;   
    char str_val[64] = {0};
    char str_num[64] = {0};
    int val_n, num_n;
    int bit_map[MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1] = {0};
    int tmp, cnt;
    
    while(scanf("%d\n", &group) != EOF)
    {     
        gets(str_val);
        gets(str_num);

        strToNumArray(str_val, val, &val_n, MAX_GROUP_NUM);
        strToNumArray(str_num, num, &num_n, MAX_GROUP_NUM);
        totle = 0;
        for(i = 0; i < group; i ++)
        {
             for(j = 0; j < num[i]; j++)
             {
                 val_all[totle] = val[i];
                 totle++;           
             }
        }

       /* for(i = 0; i < group; i ++)
        {
            printf("%d ", val[i]);
        }
        printf("\n");
        for(i = 0; i < group; i ++)
        {
            printf("%d ", num[i]);
        }
        printf("\n");
        for(i = 0; i < totle; i ++)
        {
            printf("%d ", val_all[i]);
        }
        printf("\n");*/


        for(i = 0; i < MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1; i++)
            bit_map[i] = 0;
        for(long_i = 0; long_i < (((long long)1) << totle); long_i++)
        {
            tmp = 0;
            //printf("===>");
            for(j = 0; j < totle; j++)
            {
                if((long_i & ((long long)1 << j)) != 0)
                {
                    //printf("[j=%d]vla:%d ", j, val_all[j]);
                    tmp += val_all[j];     
                }
            }    
            //printf("<==i:0x%x  tmp:%d\n", long_i, tmp);
            bit_map[tmp] = 1;
        }   
        cnt = 0;
        for(i = 0; i < MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1; i++)
        {
            if(bit_map[i] == 1)
            {
                cnt++;
            }
        }
        printf("%d\n", cnt);
    }  
    return 0;
}

    6.2 通过：递归法，耗时110ms

    注：遇到错误的点：数组溢出

    #include <stdio.h>
#include <stdlib.h>
#define MAX_GROUP_NUM 10
#define MAX_FAMA_NUM 6
#define MAXFAMA_WIGHT 2000
int strToNumArray(char *str, int *array, int *array_n, int max_num)
{
    int i, j, tmp, cnt;
    char buf[16] = {0};
    i = j = cnt = 0;
    while(str[i] != '\0')
    {
        if(str[i] == ' ')
        {
            i++;
            continue;
        }
        tmp = i;
        while(str[i] != ' ' && str[i] != '\0')
        {
            buf[i - tmp] = str[i];
            i++;
        }
        buf[i - tmp] = '\0';
        array[cnt] = atoi(buf);       
        if(array[cnt] == 0 && buf[0] != '0')
        {
             *array_n = cnt;   
             return -1;   
        }
        cnt++; 
        if(cnt >= max_num)
        {
            *array_n = cnt;   
             return -1;   
        }
    }
    *array_n = cnt;   
     return 0; 
}

//多重循环
int record[100];
int bit_map[MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1] ;
int forLoop(int *end, int n, int top, int *data)
{
    int i;
    int tmp;
    if(end == NULL || data == NULL || top < n)return -1;
    if(n == 0)
    {        
        tmp = 0;
        for(i = 0; i < top - n; i++)
        {
            tmp += data[i] * record[i];    
        }
        bit_map[tmp] = 1;
    }
    else
    {
        for(i = 0; i <= end[top - n]; i++)
        {
            record[top - n] = i; 
            forLoop(end, n - 1, top, data);            
        }     
    }
         
    return 0;
}

int main(void)
{  
    int val[MAX_GROUP_NUM] = {0};
    int num[MAX_GROUP_NUM] = {0};
    char str_val[64] = {0};
    char str_num[64] = {0};
    int val_n, num_n, cnt, i, group;
    
    while(scanf("%d\n", &group) != EOF)
    {     
        gets(str_val);
        gets(str_num);
            
        strToNumArray(str_val, val, &val_n, MAX_GROUP_NUM);
        strToNumArray(str_num, num, &num_n, MAX_GROUP_NUM);
             
        for(i = 0; i < MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1; i++)
            bit_map[i] = 0;
        forLoop(num, group, group, val);
        cnt = 0;
        for(i = 0; i < MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1; i++)
        {
            if(bit_map[i] == 1)
            {
                cnt++;
            }
        }
        printf("%d\n", cnt);
 
    }     
    return 0;
}

    6.3 通过，类似于动态规划：利用前者的结果推导后面的结果，耗时10ms

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_GROUP_NUM 10
#define MAX_FAMA_NUM 6
#define MAXFAMA_WIGHT 2000
int strToNumArray(char *str, int *array, int *array_n, int max_num)
{
    int i, j, tmp, cnt;
    char buf[16] = {0};
    i = j = cnt = 0;
    while(str[i] != '\0')
    {
        if(str[i] == ' ')
        {
            i++;
            continue;
        }
        tmp = i;
        while(str[i] != ' ' && str[i] != '\0')
        {
            buf[i - tmp] = str[i];
            i++;
        }
        buf[i - tmp] = '\0';
        array[cnt] = atoi(buf);       
        if(array[cnt] == 0 && buf[0] != '0')
        {
             *array_n = cnt;   
             return -1;   
        }
        cnt++; 
        if(cnt >= max_num)
        {
            *array_n = cnt;   
             return -1;   
        }
    }
    *array_n = cnt;   
     return 0; 
}

int main(void)
{  
    int val[MAX_GROUP_NUM + 2] = {0};
    int num[MAX_GROUP_NUM + 2] = {0};
    char str_val[64] = {0};
    char str_num[64] = {0};
    int val_n, num_n, cnt, i, j, k, group;
    int bit_map[MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1] ;
    int bit_map_tmp[MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1] ;
    
    while(scanf("%d\n", &group) != EOF)
    {     
        gets(str_val);
        gets(str_num);
            
        strToNumArray(str_val, val, &val_n, MAX_GROUP_NUM);
        strToNumArray(str_num, num, &num_n, MAX_GROUP_NUM);
             
        for(i = 0; i < MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1; i++)
            bit_map[i] = 0;
        cnt = 0;
        for(i = 0; i < group; i++)
        {
            memcpy(bit_map_tmp, bit_map, sizeof(bit_map));
            for(j = 0; j < MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1; j++)
            {                
                if(bit_map_tmp[j] == 1)
                {
                    for(k = 0; k <= num[i]; k++)
                    {
                        bit_map[val[i] * k + j] = 1;
                    }
                }
            }
            for(j = 0; j <= num[i]; j++)
            {
                bit_map[val[i] * j] = 1;
            }           
        }
      
        for(i = 0; i < MAXFAMA_WIGHT * MAX_FAMA_NUM * MAX_GROUP_NUM + 1; i++)
        {
            if(bit_map[i] == 1)
            {
                cnt++;
            }
        }
        printf("%d\n", cnt);
 
    }     
    return 0;
}

    6.4 参考网友：只要3ms

    我的分析：
    （1）位图 1 代表存在， 0代表不存在
    （2）以上一个数的结果为基础，推导下一个数的结果，例如
    求{2， 2， 3， 3， 3} 和的不同情况：
    1）0放到位图，2放到位图===>[0,2]
    2）2放到位图，0+2放到位图；2+2放到位图===>[0,2,4]
    3） 3、0+3 、2+3、4+3 放到位图 ===>[0,2,4,3,5,7]
    以此类推，类似于数学的 “演绎推理”。

    #include <stdio.h>
 
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i,j,k,m[n],x[n],max=0,count=0;
        for(i=0;i<n;i++)
            scanf("%d",&m[i]);
        for(i=0;i<n;i++)
            scanf("%d",&x[i]);
        for(i=0;i<n;i++)
            max+=m[i]*x[i];
        int *array=(int *)malloc(sizeof(int)*(max+1));
        memset(array,0,sizeof(int)*(max+1));
        array[0]=1;
        for(i=0;i<n;i++)
            for(j=0;j<x[i];j++)
                for(k=max;k>=0;k--)
                    if(array[k]==1)
                        array[k+m[i]]=1;
        for(i=0;i<=max;i++)
            if(array[i]==1)
                count++;
        printf("%d\n",count);
    }
    return 0;
}

    7、学英文（英文数字）

    
#include <stdio.h>
#include <string.h>
const char name_of_num[][32]={
    "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
    "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen","eighteen", "nineteen" 
};
const char name_of_numplus[][32]={
     "aa", "aa", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"
};
const char name_key[][32]={
    "and", "hundred", "thousand", "million", "billon" 
};

void getNamePre(int num, char (*out_str)[32], int *pos)
{
    int tmp;
    if(num >= 1000) return ;
    tmp = num / 100;
    if(tmp >= 1)
    {
        strcpy(out_str[(*pos)++], name_of_num[tmp]);
        strcpy(out_str[(*pos)++], name_key[1]);
        strcpy(out_str[(*pos)++], name_key[0]);
    }
    tmp = num % 100;
    if(tmp == 0)
    {
         (*pos)--;
         return ;
    }
    tmp = num % 100;
    if((tmp / 10) == 1)
    {
        strcpy(out_str[(*pos)++], name_of_num[tmp]);
    }
    else if((tmp / 10) > 1)
    {
        strcpy(out_str[(*pos)++], name_of_numplus[tmp / 10]);
    } 
    tmp = num % 10;
    if(tmp != 0 && (((num % 100) / 10) != 1))
    {
        strcpy(out_str[(*pos)++], name_of_num[tmp % 10]);
    }           
}

int getName(int num, char (*out_str)[32], int *n)
{
    if(num >= 1000000000)return -1;
    int tmp;
    *n = 0;
    
    tmp = (num / 1000000) % 1000;
    if(tmp > 0)
    {
        getNamePre(tmp, out_str, n);   
        strcpy(out_str[(*n)++], name_key[3]);
    }
    tmp = (num / 1000) % 1000;
    if(tmp > 0)
    {
        getNamePre(tmp, out_str, n);   
        strcpy(out_str[(*n)++], name_key[2]);
    }
    getNamePre(num % 1000, out_str, n);   
    return 0;  
}

void test(int num)
{
    char buf[128][32] = {{0},};
    int n;
    getName(num, buf, &n);
    int i;
    for(i = 0; i < n; i++)
    {
        printf("%s ", buf[i]);
    }
    printf("\n");
}
int main(void)
{
    int num;
    while(scanf("%d", &num) != EOF)
          test(num);
    return 0;
}

    8、迷宫问题

    #include <stdio.h>
#include <string.h>

struct XYPOS{
    int x;
    int y;  
};
void printPath(struct XYPOS *p, int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        printf("(%d,%d)\n", p[i].y, p[i].x);
    }
    //printf("\n");
}

struct XYPOS record[128] = {0};
int record_pos = 0;
struct XYPOS tmp_record[128] = {0};
int tmp_pos;
int getPath(int *data, int x_top, int y_top, struct XYPOS now)
{
    int i, j;
    struct XYPOS xypos;
    int mark;
    //记录
    record[record_pos++] = now;   
    
    if((now.x >= 0 && now.x <= x_top) && (now.y >= 0 && now.y <= y_top))
    { 
        for(i = 0; i < 4; i++)
        {
            xypos = now;
            if(i == 0)
            {
                 xypos.x++;
            }
            else if(i == 1)
            {
                xypos.x--;
            }
            else if(i == 2)
            {
                xypos.y++;
            }
            else if(i == 3)
            {
                xypos.y--;
            }
            //禁止环路
            mark = 0;
            for(j = 0; j < record_pos; j++)
            {
                if(record[j].x == xypos.x && record[j].y == xypos.y)
                {
                    mark = 1;
                    break;
                }
            }
            if(mark == 1)continue;
            //越界
            if(!(xypos.x >= 0 && xypos.x <= x_top) && (xypos.y >= 0 && xypos.y <= y_top))
            {
                continue;
            }
            //遇 1 
            if(data[xypos.y * (1 + x_top) + xypos.x] == 1)
            {
                continue;
            }        
            //最终结果
            if(xypos.x == x_top && xypos.y == y_top)
            {               
                record[record_pos++] = xypos;                 
                if(tmp_pos > record_pos)//取最短路径
                {
                    tmp_pos = record_pos;
                    for(j = 0 ; j < record_pos; j++)
                    {
                        tmp_record[j] = record[j];
                    }                    
                }           
                //printPath(record, record_pos);
                record_pos--;              
                continue;
            }   
            //递归
            getPath(data, x_top, y_top, xypos);               
        }       
    }
    record_pos--;
    return 0;
}

int main(void)
{  
    int x, y, i, j;
    int data[100] = {0};
    while(scanf("%d %d", &y, &x) != EOF)
    {
        for(i = 0; i < y; i++)
        {
            for(j = 0; j < x; j++)
            {
                scanf("%d ",(data + i * x + j));
            }
            scanf("\n");
        }
        
        struct XYPOS now = {0, 0};
        record_pos = 0;
        tmp_pos = x*y;
        getPath(data, x - 1, y - 1, now);
        printPath(tmp_record, tmp_pos);       
    }
    return 0;
}

    9、数独问题
    （部分用例通过 2/6,，通过率30%）

    

#include <stdio.h>

#define TEST -1
int data[81] = {0};
int bit[81] = {0};
int stop = 0;
void printData(int *data)
{
    int i;
    for(i = 0; i < 81; i ++)
    {
        printf("%d ", *(data + i));
        if((i + 1) % 9 == 0)
        {
            printf("\n");
        }  
    }
}
int setnum(int n)
{
    int i, j, x, y, mark, tmp_data, tmp_bit;
    y = n / 9;
    x = n % 9;
    
    if(stop == 1)
    {
        return 0;
    }
    
    if(n >= 80)
    {
        //printf("OK\n");
        printData(data);
        //stop = 1;
        return 0;
    }
    if(data[n] == 0)
    {
        if(n == TEST)printf("TEST = %d is coming.............[0]\n", TEST);
        for(i = 0; i < 9; i++)
        {
            if(bit[y * 9 + i] == 0)
            {
                if(n == TEST)printf("==>[select] num=%d\n", i + 1);
                for(j = 0 ; j < 9 ; j ++)
                {
                     mark = 0;
                     
                     if(data[x + j * 9] == (i + 1) && y != j)
                     {
                         if(n == TEST)printf("==>[not ok](%d,%d) data=%d\n", j, x, i + 1);
                         mark = 1;
                         break;
                     }                    
                }
                if(mark == 1)
                    continue;
                if(n == TEST)printf("==>[ok] data=%d\n", i + 1);
                tmp_data = data[n];
                data[n] = i + 1;
                tmp_bit = bit[y * 9 + i];
                bit[y * 9 + i] = 1;
                setnum(n + 1);
                //回退
                data[n] = tmp_data;
                bit[y * 9 + i] = tmp_bit;
            }                        
        }  
    }
    else
    {
        if(n == TEST)printf("TEST = %d is coming.............[1]\n", TEST);
        setnum(n + 1);
    }
    return  0;
}

int main(void)
{
    int i;
    for(i = 0; i < 81; i ++)
        bit[i] = 0;
    for(i = 0; i < 81; i ++)
    {
        scanf("%d", data + i);
        if((i + 1) % 9 == 0)
            scanf("\n");    
        if(*(data + i) != 0)        
            bit[(i / 9) * 9 + (*(data + i) - 1)] = 1;
    }
    //printData(bit);
    
    stop = 0;
    setnum(0);
   
    return 0;
}

    10、漂亮数字
    python 例子（写代码速度确实更快，用到了现成的“轮子”）

    num = input()
while True:
    try:
        sum = 0
        mystr = input().strip().lower()
        str_len = len(mystr)
        l = [];
        value_a = ord('a')
        for i in range(26):
            tmp = mystr.count(chr(value_a + i))
            if tmp != 0:
                l.append(tmp)
        l = sorted(l, reverse=True)
        for i in range(len(l)):
            sum += l[i] * (26 - i)
        if(sum != 0):
            print(sum)      
    except:
        break

    c语言

    

#include <stdio.h>
#include <string.h>
/*思路
*统计字符出现的次数，然后排序，次数大的给数值26，次之给25，依次类推，最后求和
*/

void sort(int *p, int n)//冒泡排序
{
    int i, j;
    for(i = 0; i < n -1; i++)
        for(j = i + 1; j < n; j ++)
            if(p[i] < p[j])
                {p[i] ^= p[j];p[j] ^= p[i]; p[i] ^= p[j];}   
}

int main(void)
{
    int num, i, j, len, cnt, sum;
    int bit[26] = {0};
    int array[26] = {0};
    char buf[4096] = {0};
    while(scanf("%d", &num) != EOF)
    {
        for(i = 0; i < num; i++)
        {
            scanf("%s\n", buf);

            len = strlen(buf);
            for(j = 0; j < 26; j++)
                bit[j] = 0;
            for(j = 0; j < len; j++)
            {
                if(buf[j] >= 'a' && buf[j] <= 'z')
                    bit[buf[j] - 'a']++;
                else if(buf[j] >= 'A' && buf[j] <= 'Z')
                    bit[buf[j] - 'A']++;
            }
            cnt = 0;
            for(j = 0; j < 26; j++)
                if(bit[j] != 0)
                    array[cnt++] = bit[j];
            if(cnt == 0)
                continue;
            sort(array, cnt);
            sum = 0;
            for(j = 0; j < cnt; j++)
                sum += array[j] * (26 - j);
            printf("%d\n", sum);
        }  
    }
    return 0;
}

    11、链表

    
#include <stdio.h>
#include <stdlib.h>
struct myque{
    int val;
    struct myque *next;   
};
#define NEW_NODE (struct myque *)malloc(sizeof(struct myque));
#define NULL_THEN_RETURN do{if(head == NULL) return;}while(0);
void que_print(struct myque *head)
{
    NULL_THEN_RETURN;
    struct myque *prob = head;
    while(prob != NULL)
    {
        printf("%d ", prob->val);
        prob = prob->next;         
    }  
    printf("\n");
    
}
struct myque * que_init(int val)
{
    struct myque * q = NEW_NODE;
    q->val = val; 
    q->next = NULL;                                       
    return q;
}
void que_insert(struct myque *head, int pos, int val)
{
    NULL_THEN_RETURN;
    struct myque *prob = head;
    struct myque *tmp;
    if(pos == val)
        return;
    while(prob != NULL)
    {
        if(prob->val == pos)
        {
            tmp = prob->next; 
            prob->next = NEW_NODE;
            prob->next->val = val;
            prob->next->next = tmp;
            break;
        }
        prob = prob->next;         
    }
}
void que_del(struct myque *head, int val)
{
    NULL_THEN_RETURN;
    struct myque *prob = head;
    struct myque *last = head;
    struct myque *tmp;
    while(prob != NULL)
    {
        if(prob->val == val)
        {         
            if(prob == head)
            {
                tmp = head->next;
                *head = *(head->next);
                free(tmp);
                return;
            }
            last->next = prob->next;
            free(prob);
            return;
        }
        last = prob;
        prob = prob->next;         
    }  
}

int main(void)
{
    int num, head_v, i, val, pos, del_v;
    
    while(scanf("%d", &num) != EOF)
    {
        scanf("%d", &head_v);  
        struct myque *head = que_init(head_v);
        for(i = 0; i < num - 1; i++) 
        {
            scanf("%d %d", &val, &pos); 
            que_insert(head, pos, val); 
        }
        scanf("%d\n", &del_v); 
        que_del(head, del_v);
        que_print(head);       
    }
    return 0;
}

    相关文章

      网友评论

          本文标题：009-牛客机试题2（通过测验）

          本文链接：https://www.haomeiwen.com/subject/zgcukltx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|009-牛客机试题2（通过测验）|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！