目錄
第1題：Z 字形變換
第2題：删除字元串中的所有相鄰重複項
第3題：基本電腦 II
第4題：螺旋矩陣
第5題：螺旋矩陣 II
第6題：盛最多水的容器
第7題：删除有序數組中的重複項 II
第8題：搜尋旋轉排序數組 II
第9題：平方數之和
第10題：最接近的三數之和
力扣(LeetCode)定期刷題，每期10道題，業務繁重的同志可以看看我分享的思路，不是最高效解決方案，隻求互相提升。
試題要求如下：
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;
} 運作效率如下所示：
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;
} 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;
} 可以将矩陣看成若幹層，首先輸出最外層的元素，其次輸出次外層的元素，直到輸出最内層的元素。
/**
* 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;
} /**
* 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;
} 采用雙指針思路：因為所求區間是類似于視窗的區間，在一直變化，隻是取其中最大的一個；可以從兩端往中間移動，一次移動中，最小的邊與視窗區間組成的面積為本條邊所組成的最大容積。
#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;
} 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;
} 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;
} 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;
} 1、先快速排序，再用雙指針找三數之和
2、用一個變量gap記錄 sum和target的距離（即差的絕對值）, ret記錄此時的傳回值
3、若有sum = target，直接傳回sum。否則所有循環結束後傳回ret
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;
}