目錄

第1題：數(shù)組的度

第2題：托普利茨矩陣

第3題：愛生氣的書店老板

第4題：翻轉(zhuǎn)圖像

第5題：有效的數(shù)獨

第6題：無重復(fù)字符的最長子串

第7題：區(qū)域和檢索 - 數(shù)組不可變

第8題：二維區(qū)域和檢索 - 矩陣不可變

第9題：比特位計數(shù)

第10題：最長回文子串

---

力扣(LeetCode)定期刷題，每期10道題，業(yè)務(wù)繁重的同志可以看看我分享的思路，不是最高效解決方案，只求互相提升。

第1題：數(shù)組的度

試題要求如下：

解題思路：

用一個哈希表去統(tǒng)計所有元素的出現(xiàn)次數(shù)，“度”就是整個哈希表取value的最大值，然后題目讓你求達到這個值的最小連續(xù)子數(shù)組長度。做法是先遍歷一遍數(shù)組找到“度”，然后不斷滑窗找到最小。

回答（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)//第一次出現(xiàn)，需要設(shè)置起點{start[nums[i]]=i;end[nums[i]]=i;}else if(mark[nums[i]]>1)//非第一次出現(xiàn)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]內(nèi)顧客都滿意 */for (i = 0; i < X; i++) {sum += customers[i];}/* 統(tǒng)計[0,X-1]窗口外的顧客滿意人數(shù) */for (; i < customersSize; i++) {sum += (grumpy[i] == 0) ? customers[i] : 0;}res = sum;/* 滑動窗口, 每次進一人出一人, 計算滿意人數(shù) */for (i = 1; i <= customersSize - X; i++) {sum -= customers[i - 1]     * grumpy[i - 1];     /* 原窗口內(nèi)生氣的要減去     */sum += customers[i - 1 + X] * grumpy[i - 1 + X]; /* 新進窗口的, 生氣的要加上 */res  = fmax(res, sum);}return res;
}

運行效率如下所示：

---

第4題：翻轉(zhuǎn)圖像

試題要求如下：

回答（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題：有效的數(shù)獨

試題要求如下：

回答（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題：無重復(fù)字符的最長子串

試題要求如下：

回答（C語言）：

int lengthOfLongestSubstring(char * s){int res = 0;int len = strlen(s);/* 存儲 ASCII 字符在子串中出現(xiàn)的次數(shù) */int freq[256] = {0};  /* 定義滑動窗口為 s[l...r] */int l = 0, r = -1; while (l < len) {/* freq 中不存在該字符，右邊界右移，并將該字符出現(xiàn)的次數(shù)記錄在 freq 中 */if (r < len - 1 && freq[s[r + 1]] == 0) {freq[s[++r]]++;/* 右邊界無法拓展，左邊界右移，刨除重復(fù)元素，并將此時左邊界對應(yīng)的字符出現(xiàn)的次數(shù)在 freq 的記錄中減一 */} else {freq[s[l++]]--;}/* 當前子串的長度和已找到的最長子串的長度取最大值 */res = fmax(res, r - l + 1);}return res;
}

運行效率如下所示：

---

第7題：區(qū)域和檢索 - 數(shù)組不可變

試題要求如下：

回答（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題：二維區(qū)域和檢索 - 矩陣不可變

試題要求如下：

回答（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題：比特位計數(shù)

試題要求如下：

回答（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])) { // 選出重復(fù)字符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;  // 左右標記不在回文子串范圍內(nèi)，在外面兩側(cè)，需要減1startidx = left + 1;}}s[startidx + max_len] = '\0';return s + startidx;
}

運行效率如下所示：

總結(jié)

以上是生活随笔為你收集整理的力扣(LeetCode)刷题，简单+中等题(第32期)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。