力扣(LeetCode)定期刷题，每期 10 道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第 1 题：两数之和 2-输入有序数组
试题要求如下：
回答（C 语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) { int* ret = (int*)malloc(sizeof(int) * 2); *returnSize = 2; for (int i = 0; i < numbersSize; ++i) { int low = i + 1, high = numbersSize - 1; while (low <= high) { int mid = (high - low) / 2 + low; if (numbers[mid] == target - numbers[i]) { ret[0] = i + 1, ret[1] = mid + 1; return ret; } else if (numbers[mid] > target - numbers[i]) { high = mid - 1; } else { low = mid + 1; } } } ret[0] = -1, ret[1] = -1; return ret;}
复制代码
运行效率如下所示：
第 2 题：换酒问题
试题要求如下：
回答（C 语言）：
int numWaterBottles(int numBottles, int numExchange){ int temp_numBottles = numBottles; int temp_num = 0; int temp_data = numBottles; while(temp_numBottles >= numExchange){ temp_num = temp_numBottles/numExchange; temp_data += temp_num; temp_numBottles %= numExchange; temp_numBottles += temp_num; } return temp_data;}
复制代码
运行效率如下所示：
第 3 题：山脉数组的峰顶索引
试题要求如下：
回答（C 语言）：
int peakIndexInMountainArray(int* A, int ASize){ int i=0; while(A[i]<A[i+1]) i++; return i;}
复制代码
运行效率如下所示：
第 4 题：矩阵中的幸运数
试题要求如下：
解答思路：
注意：题目有说数字都不同，那返回数组的 size 用行数或者列数都行。
第 1 次遍历：存下每行的最小值到数组；
第 2 次遍历：存下每列的最大值到数组；
第 3 次遍历：满足条件的加入要返回的结果数组。
回答（C 语言）：
int* luckyNumbers (int** matrix, int matrixSize, int* matrixColSize, int* returnSize){ int i, j; int *ret = (int*)malloc(sizeof(int) * matrixSize); int minRow[matrixSize], maxCol[*matrixColSize]; for (i = 0; i < matrixSize; i++) { minRow[i] = INT_MAX; for (j = 0; j < *matrixColSize; j++) { if (matrix[i][j] <= minRow[i]) { minRow[i] = matrix[i][j]; } } } for (i = 0; i < *matrixColSize; i++) { maxCol[i] = INT_MIN; for (j = 0; j < matrixSize; j++) { if (matrix[j][i] >= maxCol[i]) { maxCol[i] = matrix[j][i]; } } } *returnSize = 0; for (i = 0; i < matrixSize; i++) { for (j = 0; j < *matrixColSize; j++) { if (matrix[i][j] == minRow[i] && matrix[i][j] == maxCol[j]) { ret[*returnSize] = matrix[i][j]; (*returnSize)++; } } } return ret;}
复制代码
运行效率如下所示：
第 5 题：去掉最低工资和最高工资后的工资平均值
试题要求如下：
解答思路：
一次遍历找出最大 max、最小 min 和总和 sum，平均值 average = (sum - max - min) / (salarySize - 2)，没有难度，只需要注意数据类型即可。
回答（C 语言）：
double average(int* salary, int salarySize){ int max = salary[0]; int min = salary[0]; int sum = 0; double average = 0; if(salarySize <= 2) return 0; for(int i = 0; i < salarySize; i++){ if(max < salary[i]) max = salary[i]; else if(min > salary[i]) min = salary[i]; sum += salary[i]; } average = (double)(sum - max - min) / (double)(salarySize - 2); return average;}
复制代码
运行效率如下所示：
第 6 题：非递增顺序的最小子序列
试题要求如下：
回答（C 语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */int cmp(int *a,int *b){ return *b - *a;} int* minSubsequence(int* nums, int numsSize, int* returnSize){ qsort(nums,numsSize,sizeof(int),cmp); int left = 0,right = numsSize-1,leftsum = nums[left],rightsum = nums[right]; while(left < right) { if(leftsum > rightsum) { right--; rightsum += nums[right]; } else { left++; leftsum +=nums[left]; } } *returnSize = left+1; return nums;}
复制代码
运行效率如下所示：
第 7 题：独一无二的出现次数
试题要求如下：
回答（C 语言）：
bool uniqueOccurrences(int* arr, int arrSize){ int result[2001]; int result_nums[2001]; memset(result, 0, 2001 * sizeof(int)); memset(result_nums, 0, 2001 * sizeof(int)); for(int i=0; i < arrSize;++i){ if(arr[i] < 0){ result[arr[i]*(-1)+1000] += 1; } else{ result[arr[i]] += 1; } } for(int j=0;j < 2001 ;++j){ if(result[j]>0){ result_nums[result[j]] += 1; } if(result_nums[result[j]]>1){ return false; } } return true;}
复制代码
运行效率如下所示：
第 8 题：反转字符串中的单词 3
试题要求如下：
解答思路：
1、用 i 和 j 锁定单词的首尾；
2、用 revers 对 s[i]到 s[j]进行翻转；
3、反复执行 1、2 直到遍历完字符串结束。
回答（C 语言）：
void revers(char *s,int i,int j){ char temp; while(i<j){ temp=s[i]; s[i]=s[j]; s[j]=temp; i++;j--; }} char * reverseWords(char * s){ int i=0,j=0;int slen=strlen(s); for(int n=0;n<slen;n++){ if(s[n]!=' '){ i=n;n++; while(s[n]!='\0'&&s[n]!=' '){ n++; } j=n-1; revers(s,i,j); } } return s;}
复制代码
运行效率如下所示：
第 9 题：玩筹码
试题要求如下：
解答思路：
1、首先分析发现：偶数位置转移到任意偶数位置代价为 0，同理奇数位置转移到任意奇数位置代价也为 0；
2、其次，我们简化筹码位置，将所有偶数集中到 2X 位置，所有奇数集中到 2X+1（或 2X-1）位置；
3、要想代价最小，就是移动数量最小的集合。
4、综合分析，发现实际上就是统计奇数和偶数的个数，取小者。
回答（C 语言）：
int minCostToMoveChips(int* chips, int chipsSize){ int odd =0, even = 0; for(int i = 0; i < chipsSize; i++){ if(chips[i]%2) odd++; else even++; } return (odd <= even)? odd: even;}
复制代码
运行效率如下所示：
第 10 题：字母大小写全排列
试题要求如下：
回答（C 语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */char ** letterCasePermutation(char * S, int* returnSize){ int len = strlen(S), size = 1; char **res = (char**)malloc(sizeof(char*)*pow(2, len)); *res = (char*)calloc(len + 1, sizeof(char)); strcpy(*res, S); for (int i = 0; i < len; i++){ if (S[i]>'9'){ int k = size; for (int j = 0; j < k; j++){ res[k + j] = (char*)calloc(len + 1, sizeof(char)); strcpy(res[k + j], res[j]); res[k + j][i] = S[i] < 'a' ? S[i] + 32 : S[i] - 32; size++; } } } *returnSize = size; return res;}
复制代码
运行效率如下所示：
评论