leetcode 22-04-05

发表于 更新于 分类于 阅读次数： 本文字数： 631 阅读时长 ≈ 2 分钟

今日份 leetcode

  • 1018. 可被 5 整除的二进制前缀
  • 1844. 将所有数字用字符替换
  • 299. 猜数字游戏
  • 1979. 找出数组的最大公约数

最近学校的作业有那么亿点点多，所以没太多时间刷题

1018. 可被 5 整除的二进制前缀

解题思路

通过左移加上二进制数组的元素再模 5，然后再判断是否等于 0 即可
但会有一个问题，那就是这个数会变得很大，不过根据平时的计算可以发现 5 的倍数跟其他位无关，只跟个位上的数有关，所以其余的位数可以舍去，只需要知道(个位数上的数 * 2 + 数组元素) % 5 是否等于 0 即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
// C
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 bool* prefixesDivBy5(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    bool * ans = (bool *) malloc (sizeof(bool) * numsSize);
    int n = 0;
    for(int i = 0; i < numsSize; i++){
        ans[i] = (n = ((n << 1) + nums[i]) % 5) == 0;
    }
    return ans;
 }

1844. 将所有数字用字符替换

解题思路

如果是字母直接保存，是 '0' - '9' 话就减去 '0'，因为减去 '0' 就可以得到本身的数字，然后让上一个字符加上这个数保存即可

代码

1
2
3
4
5
6
7
8
9
10
// C
char * replaceDigits(char * s){
    int len = strlen(s);
    char * res =  (char *) malloc (sizeof(char) * len + 1);
    for(int i = 0; i < len; i++){
        res[i] = (s[i] >= '0' && s[i] <= '9') ? s[i - 1] + s[i] - '0' : s[i];
    }
    res[len] = '\0';
    return res;
}

299. 猜数字游戏

解题思路

统计对应的个数，不对应的则分别记录出现次数，然后判断出现过的数的交集，因为交集且不对应的数才是 Cows，然后求出交集中每个数最小出现次数的和，因为每个位置不对的数只匹配一次

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// C
char * getHint(char * secret, char * guess){
    int len = strlen(secret);
    int As[10] = {0};
    int Bs[10] = {0};
    int A = 0,B = 0;
    char * res = (char *) malloc (sizeof(char) * 9);
    for(int i = 0; i < len; i++){
        if(secret[i] == guess[i]) A++;
        else{
            As[secret[i] - '0']++;
            Bs[guess[i] - '0']++;
        }
    }
    for(int i = 0; i < 10; i++){
        if(As[i] > 0 && Bs[i] > 0) B += As[i] > Bs[i] ? Bs[i] : As[i];
    }
    sprintf(res,"%dA%dB",A,B);
    return res;
}

1979. 找出数组的最大公约数

解题思路

先使用 qsort 对数组进行排序，然后利用辗转相除法求出最大公约数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C
int cmp(void * a, void * b){
    return * (int *) a - * (int *)b;
}
int findGCD(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    int max = nums[numsSize - 1];
    int min = nums[0];

    int n= max % min;
    while(n)
    {
        max = min;
        min = n;
        n= max % min;
    }
    return min;
}