力扣(LeetCode)定期刷题，每期 10 道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第 1 题：配对交换
试题要求如下：
解答思路：
分别取出 num 的偶数位与奇数位
然后让偶数位右移一位奇数位左移一位
让移位后的偶数与奇数异或即可得最终结果
回答（C 语言）：
int exchangeBits(int num){ int even_number = 0xaaaaaaaa; //1010 1010 ...... 取出偶数 int uneven_number = 0x55555555; //0101 0101 ...... 取出奇数 even_number = num & even_number; uneven_number = num & uneven_number; even_number = even_number >> 1; uneven_number = uneven_number << 1; return even_number | uneven_number;}
复制代码
运行效率如下所示：
第 2 题：比较字符串最小字母出现频次
试题要求如下：
解答思路：
回答（C 语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */#define NUM 26int QureySmallWord (char *str, int *hash){ memset(hash, 0, NUM * sizeof(int)); int len = strlen(str); int res = 0; for (int i = 0; i < len; i++) { // 统计字符串中各个字符出现的频次，已默认是字典序 hash[str[i] - 'a']++; } for (int i = 0; i < NUM; i++) { // 获取字符串中最小字母的出现频次，即hash表中第一个非零值 if (hash[i] > 0) { res = hash[i]; break; } } //printf("res %d\n", res); return res;}int* numSmallerByFrequency(char ** queries, int queriesSize, char ** words, int wordsSize, int* returnSize){ int *array_q = (int *)malloc(queriesSize * sizeof(int)); int *array_w = (int *)malloc(wordsSize * sizeof(int)); int *hash = (int *)malloc(NUM * sizeof(0)); // queries各个字符串（按字典序比较）最小字母的出现频次 for (int i = 0; i < queriesSize; i++) { array_q[i] = QureySmallWord(queries[i], hash); } // words各个字符串（按字典序比较）最小字母的出现频次 for (int i = 0; i < wordsSize; i++) { array_w[i] = QureySmallWord(words[i], hash); } // 依次查找queries中字符串满足f(queries[i]) < f(W[0..j])的个数 int *res = (int *)malloc(queriesSize * sizeof(int)); int count = 0; for (int i = 0; i < queriesSize; i++) { int temp = 0; for (int j = 0; j < wordsSize; j++) { //printf("array_q[%d] %d array_w[%d] %d", i, array_q[i], j, array_w[j]); if (array_q[i] < array_w[j]) { temp++; } } res[count++] = temp; } *returnSize = count; return res;}
复制代码
运行效率如下所示：
第 3 题：交替位二进制
试题要求如下：
解答思路：
每次用 n&1 位运算取出最后一位，并与上一次取出的最后一位比较，一样的话返回 false。
回答（C 语言）：
bool hasAlternatingBits(int n){ int pre = n & 1; n >>= 1; while (n != 0) { if ((n & 1) == pre) { return false; } pre = n & 1; n >>= 1; } return true;}
复制代码
运行效率如下所示：
第 4 题：二进制间距
试题要求如下：
解答思路：
1、利用 1 与数字 N 进行 &运算检查二进制第一位是否为 1；
2、逐步将数字二进制值向右移动一位:N = N>>1；
3、N <= 0 时终止。
回答（C 语言）：
int binaryGap(int N){ int distance = 0, max = 0,distanceon = 0; while (N > 0){ if((N & 1) != 0){ distanceon = 1; if(distance > max){ max = distance; } distance = 0; } distance+=(distanceon); N = N >> 1; } return max;}
复制代码
运行效率如下所示：
第 5 题：最后一块石头的重量
试题要求如下：
解答思路：
1、5 个石头撞四次 6 个石头撞 5 次 N 个石头撞 N-1 次；
2、降序，撞前两个。得到的新石头放回去，空缺位置置 0；
3、重复第二步；
4、最后剩下一个，就是答案。
回答（C 语言）：
int Cmp(const void* a, const void* b){ return *(int*)b - *(int*)a;} int lastStoneWeight(int* stones, int stonesSize){ int time = stonesSize - 1; int buf[30] = {0}; memcpy(buf, stones, stonesSize * sizeof(int)); while (time > 0) { qsort(buf, 30, sizeof(int), Cmp); buf[0] -= buf[1]; buf[1] = 0; time--; } return buf[0];}
复制代码
运行效率如下所示：
第 6 题：旋转数字
试题要求如下：
解答思路：
遍历从 1 到 N 的每个数字 X，判断 X 是否为好数。如果 X 中存在 3、4、7 这样的无效数字，则 X 不是一个好数。如果 X 中不存在 2、5、6、9 这样的旋转后会变成不同的数字，则 X 不是一个好数。否则，X 可以旋转成一个不同的有效数字。
回答（C 语言）：
/** 函数功能：检测是否是好数；是好数返回1，否则返回0 * 函数输入：当前检测的数num* 函数返回值：0或1*/int CheckDigits(int num){ int rest; int flag = 0; while(num > 0) { rest = num % 10; /* 遇到垃圾数直接返回0 */ if (rest == 3 || rest == 4 || rest == 7) { return 0; } /* 遇到有可能存在的好数先标记一下 */ if (rest == 2 || rest == 5 || rest == 6 || rest == 9) { flag = 1; } num = num / 10; } /* 如果不存在垃圾数，且有好数则统计加1 */ if (flag == 1) { return 1; } return 0;}int rotatedDigits(int N){ int ret = 0; for (int i = 1; i <= N; i++) { /* 逐个检测，好数就加1 */ ret += CheckDigits(i); } return ret;}
复制代码
运行效率如下所示：
第 7 题：十进制整数的反码
试题要求如下：
解答思路：
举个例子 6 是 110 那么他的反码是他与 111 异或得到的 001。所以找到比 N 大的每位都为 1 的数，与 N 进行异或。
回答（C 语言）：
int bitwiseComplement(int N){ int num = 1; while(num < N){ num = (num << 1) + 1; } return N ^ num;}
复制代码
运行效率如下所示：
第 8 题：连续子数组的最大和
试题要求如下：
解答思路：
动态规划：
回答（C 语言）：
int maxSubArray(int* nums, int numsSize){ int sum=nums[0],max=nums[0]; for(int i=1;i<numsSize;i++) { sum=(sum>0)?(sum+nums[i]):nums[i]; max=(max>sum)?max:sum; } return max;}
复制代码
运行效率如下所示：
第 9 题：有序数组中出现次数超过 25%的元素
试题要求如下：
回答（C 语言）：
int findSpecialInteger(int* arr, int arrSize){ int i = 1,cou = 0; int temp = arr[0]; while(i < arrSize){ if(temp == arr[i]){ cou++; if(cou*4 >= arrSize){ break; } } else{ cou = 0; } temp = arr[i]; i++; } return temp;}
复制代码
运行效率如下所示：
第 10 题：数组中字符串匹配
试题要求如下：
解答思路：
C 语言使用 strstr 库函数来进行子字符串匹配。strstr(str1,str2) 函数用于判断字符串 str2 是否是 str1 的子串。如果是，则该函数返回 str1 字符串从 str2 第一次出现的位置开始到 str1 结尾的字符串；否则，返回 NULL。
回答（C 语言）：
char ** stringMatching(char ** words, int wordsSize, int* returnSize){ if ((words == NULL) || (wordsSize <= 0)) { *returnSize = 0; return NULL; } char** res = (char**)malloc(sizeof(char*) * wordsSize); int index = 0; for (int i = 0; i < wordsSize; i++) { for (int j = 0; j < wordsSize; j++) { if (i != j) { if (strstr(words[j], words[i])) { res[index] = (char*)malloc(sizeof(char) * (strlen(words[i]) + 1)); memcpy(res[index], words[i], strlen(words[i]) + 1); index++; break; } } } } *returnSize = index; return res; }
复制代码
运行效率如下所示：
评论