目录
第1题：数组的度
第2题：托普利茨矩阵
第3题：爱生气的书店老板
第4题：翻转图像
第5题：有效的数独
第6题：无重复字符的最长子串
第7题：区域和检索 - 数组不可变
第8题：二维区域和检索 - 矩阵不可变
第9题：比特位计数
第10题：最长回文子串
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：数组的度
试题要求如下：
解题思路：
用一个哈希表去统计所有元素的出现次数，“度”就是整个哈希表取value的最大值，然后题目让你求达到这个值的最小连续子数组长度。做法是先遍历一遍数组找到“度”，然后不断滑窗找到最小。
回答（C语言）：
int findShortestSubArray(int* nums, int numsSize){ int mark[50000]={0}, start[50000]={0}, end[500000]={0}; int i; int count=0, min; for(i=0; i<numsSize; i++) { mark[nums[i]]++;//记录度 if(mark[nums[i]]>count) count=mark[nums[i]];//记下最大的度 if(mark[nums[i]]==1)//第一次出现，需要设置起点 { start[nums[i]]=i; end[nums[i]]=i; } else if(mark[nums[i]]>1)//非第一次出现 end[nums[i]]=i; } min=50000;//寻找最大 for(i=0; i<50000; i++) { if(mark[i]==count)//判断符合要求的 if(end[i]-start[i]<min) min=end[i]-start[i]; } min++; return min; }
运行效率如下所示：
第2题：托普利茨矩阵
试题要求如下：
解题思路：
遍历该矩阵，将每一个元素和它左上角的元素相比对即可。
回答（C语言）：
bool isToeplitzMatrix(int** matrix, int matrixSize, int* matrixColSize) { int m = matrixSize, n = matrixColSize[0]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] != matrix[i - 1][j - 1]) { return false; } } } return true; }
运行效率如下所示：
第3题：爱生气的书店老板
试题要求如下：
解题思路：
回答（C语言）：
int maxSatisfied(int* customers, int customersSize, int* grumpy, int grumpySize, int X){ int i; int sum = 0; int res = 0; /* 窗口[0,X-1]内顾客都满意 */ for (i = 0; i < X; i++) { sum += customers[i]; } /* 统计[0,X-1]窗口外的顾客满意人数 */ for (; i < customersSize; i++) { sum += (grumpy[i] == 0) ? customers[i] : 0; } res = sum; /* 滑动窗口, 每次进一人出一人, 计算满意人数 */ for (i = 1; i <= customersSize - X; i++) { sum -= customers[i - 1] * grumpy[i - 1]; /* 原窗口内生气的要减去 */ sum += customers[i - 1 + X] * grumpy[i - 1 + X]; /* 新进窗口的, 生气的要加上 */ res = fmax(res, sum); } return res; }
运行效率如下所示：
第4题：翻转图像
试题要求如下：
回答（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** flipAndInvertImage(int** A, int ASize, int* AColSize, int* returnSize, int** returnColumnSizes) { *returnSize = ASize; *returnColumnSizes = AColSize; int n = ASize; for (int i = 0; i < n; i++) { int left = 0, right = n - 1; while (left < right) { if (A[i][left] == A[i][right]) { A[i][left] ^= 1; A[i][right] ^= 1; } left++; right--; } if (left == right) { A[i][left] ^= 1; } } return A; }
运行效率如下所示：
第5题：有效的数独
试题要求如下：
回答（C语言）：
bool isValidSudoku(char** board, int boardSize, int* boardColSize) { int i, j, r, c, row[9], col[9], martix[9]; for (i = 0; i < boardSize; i++) { memset(row, 0, sizeof(row)); memset(col, 0, sizeof(col)); memset(martix, 0, sizeof(martix)); for (j = 0; j < boardColSize[i]; j++) { // 行 if (board[i][j] != '.') { if (row[board[i][j] - '1'] == 1) return false; row[board[i][j] - '1']++; } // 列 if (board[j][i] != '.') { if (col[board[j][i] - '1'] == 1) return false; col[board[j][i] - '1']++; } // 九宫格 r = 3 * (i / 3) + j / 3; c = (i % 3) * 3 + j % 3; if (board[r][c] != '.') { if (martix[board[r][c] - '1'] == 1) return false; martix[board[r][c] - '1']++; } } } return true; }
运行效率如下所示：
第6题：无重复字符的最长子串
试题要求如下：
回答（C语言）：
int lengthOfLongestSubstring(char * s){ int res = 0; int len = strlen(s); /* 存储 ASCII 字符在子串中出现的次数 */ int freq[256] = {0}; /* 定义滑动窗口为 s[l...r] */ int l = 0, r = -1; while (l < len) { /* freq 中不存在该字符，右边界右移，并将该字符出现的次数记录在 freq 中 */ if (r < len - 1 && freq[s[r + 1]] == 0) { freq[s[++r]]++; /* 右边界无法拓展，左边界右移，刨除重复元素，并将此时左边界对应的字符出现的次数在 freq 的记录中减一 */ } else { freq[s[l++]]--; } /* 当前子串的长度和已找到的最长子串的长度取最大值 */ res = fmax(res, r - l + 1); } return res; }
运行效率如下所示：
第7题：区域和检索 - 数组不可变
试题要求如下：
回答（C语言）：
typedef struct { int* sums; } NumArray; NumArray* numArrayCreate(int* nums, int numsSize) { NumArray* ret = malloc(sizeof(NumArray)); ret->sums = malloc(sizeof(int) * (numsSize + 1)); ret->sums[0] = 0; for (int i = 0; i < numsSize; i++) { ret->sums[i + 1] = ret->sums[i] + nums[i]; } return ret; } int numArraySumRange(NumArray* obj, int i, int j) { return obj->sums[j + 1] - obj->sums[i]; } void numArrayFree(NumArray* obj) { free(obj->sums); } /** * Your NumArray struct will be instantiated and called as such: * NumArray* obj = numArrayCreate(nums, numsSize); * int param_1 = numArraySumRange(obj, i, j); * numArrayFree(obj); */
运行效率如下所示：
第8题：二维区域和检索 - 矩阵不可变
试题要求如下：
回答（C语言）：
typedef struct { int** sums; int sumsSize; } NumMatrix; NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) { NumMatrix* ret = malloc(sizeof(NumMatrix)); ret->sums = malloc(sizeof(int*) * matrixSize); ret->sumsSize = matrixSize; for (int i = 0; i < matrixSize; i++) { ret->sums[i] = malloc(sizeof(int) * (matrixColSize[i] + 1)); ret->sums[i][0] = 0; for (int j = 0; j < matrixColSize[i]; j++) { ret->sums[i][j + 1] = ret->sums[i][j] + matrix[i][j]; } } return ret; } int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) { int sum = 0; for (int i = row1; i <= row2; i++) { sum += obj->sums[i][col2 + 1] - obj->sums[i][col1]; } return sum; } void numMatrixFree(NumMatrix* obj) { for (int i = 0; i < obj->sumsSize; i++) { free(obj->sums[i]); } free(obj->sums); } /** * Your NumMatrix struct will be instantiated and called as such: * NumMatrix* obj = numMatrixCreate(matrix, matrixSize, matrixColSize); * int param_1 = numMatrixSumRegion(obj, row1, col1, row2, col2); * numMatrixFree(obj); */
运行效率如下所示：
第9题：比特位计数
试题要求如下：
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* countBits(int num, int* returnSize) { int* bits = malloc(sizeof(int) * (num + 1)); *returnSize = num + 1; bits[0] = 0; int highBit = 0; for (int i = 1; i <= num; i++) { if ((i & (i - 1)) == 0) { highBit = i; } bits[i] = bits[i - highBit] + 1; } return bits; }
运行效率如下所示：
第10题：最长回文子串
试题要求如下：
回答（C语言）：
char * longestPalindrome(char * s){ int right = 0, left = 0, count = 0; int startidx = 0; int max_len = 0; for (int i = 0; s[i] != '\0'; i += count) { count = 1; left = i - 1; right = i + 1; while ((s[right]!='\0') && (s[i] == s[right])) { // 选出重复字符 right++; count++; } while ((left >= 0) && (s[right]!='\0') && (s[left] == s[right])) { // 由中心字符向左右扩展 left--; right++; } if (max_len < (right - left - 1)) { max_len = right - left - 1; // 左右标记不在回文子串范围内，在外面两侧，需要减1 startidx = left + 1; } } s[startidx + max_len] = '\0'; return s + startidx; }
运行效率如下所示：
