力扣—2024 春招冲刺百题计划

本文主要是介绍力扣—2024 春招冲刺百题计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

矩阵

1. 螺旋矩阵

代码实现：

/** @param matrix int整型二维数组 * @param matrixRowLen int matrix数组行数* @param matrixColLen int* matrix数组列数* @return int整型一维数组* @return int* returnSize 返回数组行数
*/
int* spiralOrder(int **matrix, int matrixRowLen, int *matrixColLen, int *returnSize) {int s = 0, x = matrixRowLen - 1, z = 0, y = *matrixColLen - 1; // s = 上, x = 下, z = 左, y = 右int len = matrixRowLen * *matrixColLen;int *arr = (int*)malloc(sizeof(int) * len);int count = 0;while (1) {for (int i = z; i <= y; i++) { // 从左到右arr[count++] = matrix[s][i];}if (count >= len) {break; }for (int i = s + 1; i < x; i++) { // 从上到下arr[count++] = matrix[i][y];}if (count >= len) {break;}for (int i = y; i >= z; i--) { // 从右到左arr[count++] = matrix[x][i];}if (count >= len) { break;}for (int i = x - 1; i > s; i--) { // 从下到上arr[count++] = matrix[i][z];}if (count >= len) {break;}s++;x--;z++;y--;}*returnSize = len;return arr;
}

2. 生命游戏

代码实现：

int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
};
int getLifeCellNum(int **board, int boardSize, int *boardColSize, int m, int n) {int i, j;int x, y;int result = 0;for (i = 0; i < 8; i++) {x = m + dir[i][0];y = n + dir[i][1];if ((x >= 0) && (x < boardSize) && (y >= 0) && (y < boardColSize[x])) {if (board[x][y] == 1) {result++;}}}return result;
}void gameOfLife(int **board, int boardSize, int *boardColSize) {int i, j;if ((board == NULL) || (boardSize == 0) || (boardColSize == NULL)) {return;}int **tmp = (int**)malloc(sizeof(int *) * boardSize);for (i = 0; i < boardSize; i++) {tmp[i] = (int*)malloc(sizeof(int) * boardColSize[i]);}for (i = 0; i < boardSize; i++) {for (j = 0; j < boardColSize[i]; j++) {tmp[i][j] = getLifeCellNum(board, boardSize, boardColSize, i, j);}}for (i = 0; i < boardSize; i++) {for (j = 0; j < boardColSize[i]; j++) {if (board[i][j]) {if ((tmp[i][j] != 2) && (tmp[i][j] != 3)) {board[i][j] = 0;}} else {if (tmp[i][j] == 3) {board[i][j] = 1;}}}}for (i = 0; i < boardSize; i++) {free(tmp[i]);}free(tmp);return;
}

3. 旋转图像

代码实现：

方法一：使用辅助数组

void rotate(int **matrix, int matrixSize, int *matrixColSize) {int a[matrixSize][matrixSize];for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < matrixSize; j++) {a[i][j] = matrix[i][j];}}for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < matrixSize; j++) {matrix[j][matrixSize - i - 1] = a[i][j];}}
}

方法二：先将矩阵(x, y)转置，在左右对称即可实现90度顺时针旋转

void rotate(int **matrix, int matrixSize, int *matrixColSize){// 先进行矩阵的转置for (int i = 0; i < matrixSize; i++){for (int j = i; j < *matrixColSize; j++){int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}// 在将矩阵左右对称转换int left = 0, right = (*matrixColSize) - 1;while (left < right) {for (int i = 0; i < matrixSize; i++) {int temp = matrix[i][left];matrix[i][left] = matrix[i][right];matrix[i][right] = temp;}left++;right--;}
}

4. 矩阵置零

代码实现：

void setZeroes(int **matrix, int matrixSize, int *matrixColSize) {int m = matrixSize;int n = matrixColSize[0];int row[m], col[n];memset(row, 0, sizeof(row));memset(col, 0, sizeof(col));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!matrix[i][j]) {row[i] = col[j] = 1;}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (row[i] || col[j]) {matrix[i][j] = 0;}}}
}

栈

1. 有效的括号

代码实现：

bool isValid(char *s) {char stack[10000];int top = -1;while (*s) {if (*s == '(' || *s == '{' || *s == '[') {stack[++top] = *s;} else {if (top == -1) { // 栈空return false;}char top_val = stack[top]; // 获取栈顶元素if (top_val == '(' && *s != ')' || top_val == '[' && *s != ']' || top_val == '{' && *s != '}') {return false;} else {top--;}}s++;}if (top != -1) {return false;}return true;
}

2. 二叉树的中序遍历

代码实现：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/#define MAX_NODE 100// 递归
// void mid_order1(struct TreeNode *root, int *res, int *returnSize) {
//     if (root == NULL) { // 终止条件
//         return;
//     }
//     mid_order1(root->left, res, returnSize);
//     res[(*returnSize)++] = root->val;
//     mid_order1(root->right, res, returnSize);
// }// 迭代（非递归） 深度优先搜索---借用栈
void mid_order2(struct TreeNode *root, int *res, int *returnSize) {if (root == NULL) {return ;}struct TreeNode *stack[MAX_NODE]; // 定义一个栈int top = -1; // 栈顶struct TreeNode *p = root;struct TreeNode *q = NULL;while (p || top != -1) {if (p) {stack[++top] = p;p = p->left;} else {q = stack[top];res[(*returnSize)++] = q->val;top--;p = q->right;}}
}int* inorderTraversal(struct TreeNode *root, int *returnSize) {int *res = malloc(sizeof(int) * MAX_NODE);*returnSize = 0;// mid_order1(root, res, returnSize);mid_order2(root, res, returnSize);return res;
}

3. 移掉K位数字

代码实现：

思路：贪心 + 单调栈

char* removeKdigits(char *num, int k) {int n = strlen(num), top = -1;char *stack = malloc(sizeof(char) * n);for (int i = 0; i < n; i++) {while (top > -1 && stack[top] > num[i] && k) {top--;k--;}stack[++top] = num[i];}top -= k;char *ans = malloc(sizeof(char) * (n + 1));int ansSize = 0;bool flag = true;for (int i = 0; i <= top; i++) {if (flag && stack[i] == '0') {continue;}flag = false;ans[ansSize++] = stack[i];}if (ansSize == 0) {ans[0] = '0';ans[1] = 0;} else {ans[ansSize] = 0;}return ans;
}

4. 去除重复字母

代码实现：

char* removeDuplicateLetters(char *s) {int hash[26] = {0};int vis[26] = {0};int n = strlen(s);for (int i = 0; i < n; i++) {hash[s[i] - 'a']++;}char *stack = malloc(sizeof(char) * (n + 1));int top = -1;for (int i = 0; i < n; i++) {if (!vis[s[i] - 'a']) {while (top > -1 && stack[top] > s[i]) {if (hash[stack[top] - 'a'] > 0) {vis[stack[top--] - 'a'] = 0;} else {break;}}vis[s[i] - 'a'] = 1;stack[++top] = s[i];}hash[s[i] - 'a'] -= 1;}stack[++top] = '\0';return stack;
}

😭5. 拼接最大数

代码实现：

数论

1. 计数质数

代码实现：

方法一：暴力—超时

bool isPrime(int x) {for (int i = 2; i * i <= x; i++) {if (x % i == 0) {return false;}}return true;
}int countPrimes(int n) {int ans = 0;for (int i = 2; i < n; ++i) {ans += isPrime(i);}return ans;
}

方法二：埃氏筛
如果 x 是质数，那么 x 的倍数：2x, 3x,…一定不是质数

int countPrimes(int n) {if (n < 2) {return 0;}int isPrime[n];memset(isPrime, 1, sizeof(isPrime));int ans = 0;for (int i = 2; i < n; i++) {if (isPrime[i]) {ans += 1;for (int j = i + i; j < n; j += i) {isPrime[j] = 0;}}}return ans;
}

2. n的第K个因子

代码实现：

int kthFactor(int n, int k){int i, j = 0;int count = 0;for(i = 1; i <= n; i++){if (n % i == 0){count++;if (count == k) {return i;}}}return -1;
}

3. 找出数组的做大公约数

代码实现：

int findGCD(int *nums, int numsSize) {int i;int min = INT_MAX, max = INT_MIN;// 找到最大值和最小值for (i = 0; i < numsSize; i++) {if (nums[i] > max) {max = nums[i];}if (nums[i] < min) {min = nums[i];}}for (i = min; i > 0; i--) {if (max % i == 0 && min % i == 0) { return i;}}return 1;
}

4. 生成乘积数组的方案数

代码实现：

方法一：回溯—超时

/*** Note: The returned array must be malloced, assume caller calls free().*/int path[10000];
int pathSize;void dfs(int k, int num, int sum, int *count) {if (sum > num) {return;}if (pathSize == k) {if (sum == num) {(*count)++;*count %= 1000000007;}return;}for (int i = 1; i <= num; i++) {path[pathSize++] = i;dfs(k, num, sum * i, count);pathSize--;}
}int* waysToFillArray(int **queries, int queriesSize, int *queriesColSize, int *returnSize){int *res = malloc(sizeof(int) * queriesSize);for (int i = 0; i < queriesSize; i++) {pathSize = 0;int count = 0;dfs(queries[i][0], queries[i][1], 1, &count);res[i] = count;}*returnSize = queriesSize;return res;
}