目录
第1题：Z 字形变换
第2题：删除字符串中的所有相邻重复项
第3题：基本计算器 II
第4题：螺旋矩阵
第5题：螺旋矩阵 II
第6题：盛最多水的容器
第7题：删除有序数组中的重复项 II
第8题：搜索旋转排序数组 II
第9题：平方数之和
第10题：最接近的三数之和
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：Z 字形变换
试题要求如下：
解题思路：
回答（C语言）：
char * convert(char * s, int numRows){ int n = strlen(s); if (numRows == 1) return s; char* res = (char*)malloc(sizeof(char) * (n + 1)); int k = 0; for (int i = 0; i < numRows; i++) { for (int j = 0; j < n; j++) { if (j % (2 * numRows - 2) == i || j % (2 * numRows - 2) == 2 * numRows - 2 - i) { res[k++] = s[j]; } } } res[k] = '\0'; return res; }
运行效率如下所示：
第2题：删除字符串中的所有相邻重复项
试题要求如下：
回答（C语言）：
char* removeDuplicates(char* S) { int n = strlen(S); char* stk = malloc(sizeof(char) * (n + 1)); int retSize = 0; for (int i = 0; i < n; i++) { if (retSize > 0 && stk[retSize - 1] == S[i]) { retSize--; } else { stk[retSize++] = S[i]; } } stk[retSize] = '\0'; return stk; }
运行效率如下所示：
第3题：基本计算器 II
试题要求如下：
回答（C语言）：
int calculate(char* s) { int n = strlen(s); int stk[n], top = 0; char preSign = '+'; int num = 0; for (int i = 0; i < n; ++i) { if (isdigit(s[i])) { num = num * 10 + (int)(s[i] - '0'); } if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) { switch (preSign) { case '+': stk[top++] = num; break; case '-': stk[top++] = -num; break; case '*': stk[top - 1] *= num; break; default: stk[top - 1] /= num; } preSign = s[i]; num = 0; } } int ret = 0; for (int i = 0; i < top; i++) { ret += stk[i]; } return ret; }
运行效率如下所示：
第4题：螺旋矩阵
试题要求如下：
解题思路：
可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) { if (matrixSize == 0 || matrixColSize[0] == 0) { *returnSize = 0; return NULL; } int rows = matrixSize, columns = matrixColSize[0]; int total = rows * columns; int* order = malloc(sizeof(int) * total); *returnSize = 0; int left = 0, right = columns - 1, top = 0, bottom = rows - 1; while (left <= right && top <= bottom) { for (int column = left; column <= right; column++) { order[(*returnSize)++] = matrix[top][column]; } for (int row = top + 1; row <= bottom; row++) { order[(*returnSize)++] = matrix[row][right]; } if (left < right && top < bottom) { for (int column = right - 1; column > left; column--) { order[(*returnSize)++] = matrix[bottom][column]; } for (int row = bottom; row > top; row--) { order[(*returnSize)++] = matrix[row][left]; } } left++; right--; top++; bottom--; } return order; }
运行效率如下所示：
第5题：螺旋矩阵 II
试题要求如下：
回答（C语言）：
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){ int i; int up = 0; int down = n - 1; int left = 0; int right = n - 1; int idx = 1; int **res = (int**)malloc(sizeof(int*) * n); *returnColumnSizes = (int*)malloc(sizeof(int) * n); *returnSize = n; /* 输出n*n矩阵 */ for (i = 0; i < n; i++) { res[i] = (int*)malloc(sizeof(int) * n); (*returnColumnSizes)[i] = n; } while (up <= down && left <= right) { for (i = left; i <= right; i++) { /* 上 */ res[up][i] = idx++; } up++; for (i = up; i <= down; i++) { /* 右 */ res[i][right] = idx++; } right--; for (i = right; i >= left && up <= down; i--) { /* 下 */ res[down][i] = idx++; } down--; for (i = down; i >= up && left <= down; i--) { /* 左 */ res[i][left] = idx++; } left++; } return res; }
运行效率如下所示：
第6题：盛最多水的容器
试题要求如下：
解题思路：
采用双指针思路：因为所求区间是类似于窗口的区间，在一直变化，只是取其中最大的一个；可以从两端往中间移动，一次移动中，最小的边与窗口区间组成的面积为本条边所组成的最大容积。
回答（C语言）：
#define MAXSIZE 30000 int stack[MAXSIZE] = {0}; int maxArea(int* height, int heightSize){ int ret = 0; int left = 0; int right = heightSize - 1; int temp = 0; while (left < right) { if (height[left] < height[right]) { temp = height[left] * (right - left); left++; } else { temp = height[right] * (right - left); right--; } ret = ret > temp ? ret : temp; } return ret; }
运行效率如下所示：
第7题：删除有序数组中的重复项 II
试题要求如下：
回答（C语言）：
int removeDuplicates(int* nums, int numsSize) { if (numsSize <= 2) { return numsSize; } int slow = 2, fast = 2; while (fast < numsSize) { if (nums[slow - 2] != nums[fast]) { nums[slow] = nums[fast]; ++slow; } ++fast; } return slow; }
运行效率如下所示：
第8题：搜索旋转排序数组 II
试题要求如下：
解题思路：
回答（C语言）：
bool search(int* nums, int numsSize, int target) { if (numsSize == 0) { return false; } if (numsSize == 1) { return nums[0] == target; } int l = 0, r = numsSize - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) { return true; } if (nums[l] == nums[mid] && nums[mid] == nums[r]) { ++l; --r; } else if (nums[l] <= nums[mid]) { if (nums[l] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { if (nums[mid] < target && target <= nums[numsSize - 1]) { l = mid + 1; } else { r = mid - 1; } } } return false; }
运行效率如下所示：
第9题：平方数之和
试题要求如下：
解题思路：
回答（C语言）：
bool judgeSquareSum(int c) { long left = 0; long right = (int)sqrt(c); while (left <= right) { long sum = left * left + right * right; if (sum == c) { return true; } else if (sum > c) { right--; } else { left++; } } return false; }
运行效率如下所示：
第10题：最接近的三数之和
试题要求如下：
解题思路：
1、先快速排序，再用双指针找三数之和
2、用一个变量gap记录 sum和target的距离（即差的绝对值）, ret记录此时的返回值
3、若有sum = target，直接返回sum。否则所有循环结束后返回ret
回答（C语言）：
int comp(const void* a, const void* b) { return *(int*)a - *(int*)b; } int threeSumClosest(int* nums, int numsSize, int target) { int ret, gap = 0x7fffffff; // gap 记录距离并初始化为最大值，ret 记录此时返回值 qsort(nums, numsSize, sizeof(int), comp); for (int i = 0; i < numsSize - 2; i++) { int left = i + 1; int right = numsSize - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (abs(sum - target) < gap) { //如果距离更短，则更新 gap 和 ret gap = abs(sum - target); ret = sum; } if (sum > target) right--; //移动左右指针 else if (sum < target) left++; else return sum; } } return ret; }
运行效率如下所示：
