力扣(LeetCode)定期刷题，每期 10 道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第 1 题：判断能否形成等差数列
试题要求如下：
回答（C 语言）：
int cmp(const void *a, const void *b){ return *((int*)a) - *((int*)b);} bool canMakeArithmeticProgression(int* arr, int arrSize){ qsort(arr, arrSize, sizeof(int), cmp); int minus = arr[1] - arr[0]; for (int i = 0; i < arrSize; i++) { if (arr[i] != (arr[0] + i * minus)) { return false; } } return true;}
复制代码
运行效率如下所示：
第 2 题：整数拆分
试题要求如下：
解答思路：
1、当 n <= 3 的时候，由提议 n >=2 ,因此当 n = 2 的时候，只有 1 + 1，因此返回 1，当 n = 3 的时候，2 + 1 ，则返回 2,所以 n <= 3 的时候直接返回 n - 1；
2、当 n > 3 的时候，我们用动态规划，dp[n] = Max(dp[n - 1] * 1, dp[n - 2] * 2，dp[n - 3] * 3 ....,dp[1] * (n - 1))这里面对 dp 中 1,2,3 的初始化很重要，比如 dp[4] = Max(dp[3] * 1, dp[2] * 2, dp[1] * 3),显然这里面的 dp[1],dp[2],dp[3]分别对应的是值 1,2,3,所以初始值就是这样子；
再后面的比如 dp[5] = Max(dp[4] * 1, dp[3] * 2, dp[2] * 3, dp[1] * 4),4 以及之后的由于都是根据前面正确计算得到的，因此不用再初始化，直接在公式里面循环即可。
回答（C 语言）：
int integerBreak(int n){ if (n <= 3) return n - 1; int* dp = (int*) malloc(sizeof(int) * (n + 1)); memset(dp, 0, sizeof(int) * (n + 1)); dp[1] = 1; dp[2] = 2; dp[3] = 3; for (int i = 2; i <= n; i++) { for (int j = 1; j < i ; j++) { dp[i] = fmax(dp[i], dp[i - j] * j); } } return dp[n];}
复制代码
运行效率如下所示：
第 3 题：魔术索引
试题要求如下：
回答（C 语言）：
int findMagicIndex(int* nums, int numsSize){ for(int i = 0; i < numsSize; i++){ if(nums[i] == i){ return i; } } return -1;}
复制代码
运行效率如下所示：
第 4 题：连续数列
试题要求如下：
回答（C 语言）：
int maxSubArray(int* nums, int numsSize){ int sum = 0; int max = nums[0]; if (numsSize < 1) return 0; for (int i = 0; i < numsSize; i++) { sum += nums[i]; if (max < sum) max = sum; if (sum < 0) sum = 0; //为负数时忽略其的奉献为0 } return max;}
复制代码
运行效率如下所示：
第 5 题：字符串相加
试题要求如下：
解答思路：
回答（C 语言）：
char* addStrings(char* num1, char* num2) { int i = strlen(num1) - 1, j = strlen(num2) - 1, add = 0; char* ans = (char*)malloc(sizeof(char) * (fmax(i, j) + 3)); int len = 0; while (i >= 0 || j >= 0 || add != 0) { int x = i >= 0 ? num1[i] - '0' : 0; int y = j >= 0 ? num2[j] - '0' : 0; int result = x + y + add; ans[len++] = '0' + result % 10; add = result / 10; i--, j--; } // 计算完以后的答案需要翻转过来 for (int i = 0; 2 * i < len; i++) { int t = ans[i]; ans[i] = ans[len - i - 1], ans[len - i - 1] = t; } ans[len++] = 0; return ans;}
复制代码
运行效率如下所示：
第 6 题：数组拆分 1
试题要求如下：
回答（C 语言）：
int cmp(int *a, int *b) { return *(int *)a > *(int *)b;} int arrayPairSum(int* nums, int numsSize){ int i, j; int sum = 0; if (numsSize < 2) { return 0; } qsort(nums, numsSize, sizeof(int), cmp); for (sum = nums[0], i = 2; i < numsSize; i = i + 2) { sum += nums[i]; } return sum;}
复制代码
运行效率如下所示：
第 7 题：找出数组中的幸运数
试题要求如下：
回答（C 语言）：
int findLucky(int* arr, int arrSize){ int ret = -1; int temp[501] = {0}; int i = 0; for(; i < arrSize; i++) { temp[arr[i]]++; } i = 500; for(; i > 0; i--) { if(temp[i] == i) return i; } return ret;}
复制代码
运行效率如下所示：
第 8 题：期望个数统计
试题要求如下：
解答思路：
1、如果数组的长度 scoresSize <= 0，返回 0；
2、利用快速排序对 scores 进行排序；
3、遍历数组 scores，统计不相同的元素的个数 count；
4、返回 count。
回答（C 语言）：
int cmp( const void * a , const void * b ){ return *( int * )a - *( int * )b; } int expectNumber( int * scores , int scoresSize ){ if( scoresSize <= 0 ){ return 0; } qsort( scores , scoresSize , sizeof( int ) , cmp ); int count = 1; for( int i = 1 ; i < scoresSize ; i++ ){ if( *( scores + i ) != *( scores + i - 1 ) ){ count++; } } return count;}
复制代码
运行效率如下所示：
第 9 题：检查单词是否为句中其他单词的前缀
试题要求如下：
回答（C 语言）：
int isPrefixOfWord(char *sentence, char *searchWord){ int cnt = 1; char *token = NULL; const char space[2] = " "; /* 获取第一个子字符串，使用空格分隔 */ token = strtok(sentence, space); /* 继续获取其他的子字符串 */ while (token != NULL ) { if (strstr(token, searchWord) == token) { return cnt; } cnt++; token = strtok(NULL, space); } return -1;}
复制代码
运行效率如下所示：
第 10 题："气球”的最大数量
试题要求如下：
回答（C 语言）：
#define MIN(a, b) (((a) < (b)) ? (a) : (b)) int maxNumberOfBalloons(char * text){ int charCount[26] = {0}; int i, len, ret; len = strlen(text); for (i = 0; i < len; i++) { charCount[text[i] - 'a']++; } charCount['l' - 'a'] /= 2; charCount['o' - 'a'] /= 2; ret = INT_MAX; ret = MIN(ret, charCount['b' - 'a']); ret = MIN(ret, charCount['a' - 'a']); ret = MIN(ret, charCount['l' - 'a']); ret = MIN(ret, charCount['o' - 'a']); ret = MIN(ret, charCount['n' - 'a']); return ret;}
复制代码
运行效率如下所示：
评论