矩阵
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; }
5. 按公因数计算最大组件大小
代码实现：
思路：森林与并查集
