程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

力扣(LeetCode)刷题,简单+中等题(第32期)

发布于2021-03-07 22:30     阅读(900)     评论(0)     点赞(6)     收藏(5)


目录

第1题:数组的度

第2题:托普利茨矩阵

第3题:爱生气的书店老板

第4题:翻转图像

第5题:有效的数独

第6题:无重复字符的最长子串

第7题:区域和检索 - 数组不可变

第8题:二维区域和检索 - 矩阵不可变

第9题:比特位计数

第10题:最长回文子串


力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

第1题:数组的度

试题要求如下:

解题思路:

用一个哈希表去统计所有元素的出现次数,“度”就是整个哈希表取value的最大值,然后题目让你求达到这个值的最小连续子数组长度。做法是先遍历一遍数组找到“度”,然后不断滑窗找到最小。

回答(C语言):

  1. int findShortestSubArray(int* nums, int numsSize){
  2. int mark[50000]={0}, start[50000]={0}, end[500000]={0};
  3. int i;
  4. int count=0, min;
  5. for(i=0; i<numsSize; i++)
  6. {
  7. mark[nums[i]]++;//记录度
  8. if(mark[nums[i]]>count)
  9. count=mark[nums[i]];//记下最大的度
  10. if(mark[nums[i]]==1)//第一次出现,需要设置起点
  11. {
  12. start[nums[i]]=i;
  13. end[nums[i]]=i;
  14. }
  15. else if(mark[nums[i]]>1)//非第一次出现
  16. end[nums[i]]=i;
  17. }
  18. min=50000;//寻找最大
  19. for(i=0; i<50000; i++)
  20. {
  21. if(mark[i]==count)//判断符合要求的
  22. if(end[i]-start[i]<min)
  23. min=end[i]-start[i];
  24. }
  25. min++;
  26. return min;
  27. }

运行效率如下所示:


第2题:托普利茨矩阵

试题要求如下:

解题思路:

遍历该矩阵,将每一个元素和它左上角的元素相比对即可。

回答(C语言):

  1. bool isToeplitzMatrix(int** matrix, int matrixSize, int* matrixColSize) {
  2. int m = matrixSize, n = matrixColSize[0];
  3. for (int i = 1; i < m; i++) {
  4. for (int j = 1; j < n; j++) {
  5. if (matrix[i][j] != matrix[i - 1][j - 1]) {
  6. return false;
  7. }
  8. }
  9. }
  10. return true;
  11. }

运行效率如下所示:


第3题:爱生气的书店老板

试题要求如下:

解题思路:

回答(C语言):

  1. int maxSatisfied(int* customers, int customersSize, int* grumpy, int grumpySize, int X){
  2. int i;
  3. int sum = 0;
  4. int res = 0;
  5. /* 窗口[0,X-1]内顾客都满意 */
  6. for (i = 0; i < X; i++) {
  7. sum += customers[i];
  8. }
  9. /* 统计[0,X-1]窗口外的顾客满意人数 */
  10. for (; i < customersSize; i++) {
  11. sum += (grumpy[i] == 0) ? customers[i] : 0;
  12. }
  13. res = sum;
  14. /* 滑动窗口, 每次进一人出一人, 计算满意人数 */
  15. for (i = 1; i <= customersSize - X; i++) {
  16. sum -= customers[i - 1] * grumpy[i - 1]; /* 原窗口内生气的要减去 */
  17. sum += customers[i - 1 + X] * grumpy[i - 1 + X]; /* 新进窗口的, 生气的要加上 */
  18. res = fmax(res, sum);
  19. }
  20. return res;
  21. }

运行效率如下所示:


第4题:翻转图像

试题要求如下:

回答(C语言):

  1. /**
  2. * Return an array of arrays of size *returnSize.
  3. * The sizes of the arrays are returned as *returnColumnSizes array.
  4. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
  5. */
  6. int** flipAndInvertImage(int** A, int ASize, int* AColSize, int* returnSize, int** returnColumnSizes) {
  7. *returnSize = ASize;
  8. *returnColumnSizes = AColSize;
  9. int n = ASize;
  10. for (int i = 0; i < n; i++) {
  11. int left = 0, right = n - 1;
  12. while (left < right) {
  13. if (A[i][left] == A[i][right]) {
  14. A[i][left] ^= 1;
  15. A[i][right] ^= 1;
  16. }
  17. left++;
  18. right--;
  19. }
  20. if (left == right) {
  21. A[i][left] ^= 1;
  22. }
  23. }
  24. return A;
  25. }

运行效率如下所示:


第5题:有效的数独

试题要求如下:

回答(C语言):

  1. bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
  2. int i, j, r, c, row[9], col[9], martix[9];
  3. for (i = 0; i < boardSize; i++) {
  4. memset(row, 0, sizeof(row));
  5. memset(col, 0, sizeof(col));
  6. memset(martix, 0, sizeof(martix));
  7. for (j = 0; j < boardColSize[i]; j++) {
  8. // 行
  9. if (board[i][j] != '.') {
  10. if (row[board[i][j] - '1'] == 1) return false;
  11. row[board[i][j] - '1']++;
  12. }
  13. // 列
  14. if (board[j][i] != '.') {
  15. if (col[board[j][i] - '1'] == 1) return false;
  16. col[board[j][i] - '1']++;
  17. }
  18. // 九宫格
  19. r = 3 * (i / 3) + j / 3;
  20. c = (i % 3) * 3 + j % 3;
  21. if (board[r][c] != '.') {
  22. if (martix[board[r][c] - '1'] == 1) return false;
  23. martix[board[r][c] - '1']++;
  24. }
  25. }
  26. }
  27. return true;
  28. }

运行效率如下所示:


第6题:无重复字符的最长子串

试题要求如下:

回答(C语言):

  1. int lengthOfLongestSubstring(char * s){
  2. int res = 0;
  3. int len = strlen(s);
  4. /* 存储 ASCII 字符在子串中出现的次数 */
  5. int freq[256] = {0};
  6. /* 定义滑动窗口为 s[l...r] */
  7. int l = 0, r = -1;
  8. while (l < len) {
  9. /* freq 中不存在该字符,右边界右移,并将该字符出现的次数记录在 freq 中 */
  10. if (r < len - 1 && freq[s[r + 1]] == 0) {
  11. freq[s[++r]]++;
  12. /* 右边界无法拓展,左边界右移,刨除重复元素,并将此时左边界对应的字符出现的次数在 freq 的记录中减一 */
  13. } else {
  14. freq[s[l++]]--;
  15. }
  16. /* 当前子串的长度和已找到的最长子串的长度取最大值 */
  17. res = fmax(res, r - l + 1);
  18. }
  19. return res;
  20. }

运行效率如下所示:


第7题:区域和检索 - 数组不可变

试题要求如下:

回答(C语言):

  1. typedef struct {
  2. int* sums;
  3. } NumArray;
  4. NumArray* numArrayCreate(int* nums, int numsSize) {
  5. NumArray* ret = malloc(sizeof(NumArray));
  6. ret->sums = malloc(sizeof(int) * (numsSize + 1));
  7. ret->sums[0] = 0;
  8. for (int i = 0; i < numsSize; i++) {
  9. ret->sums[i + 1] = ret->sums[i] + nums[i];
  10. }
  11. return ret;
  12. }
  13. int numArraySumRange(NumArray* obj, int i, int j) {
  14. return obj->sums[j + 1] - obj->sums[i];
  15. }
  16. void numArrayFree(NumArray* obj) {
  17. free(obj->sums);
  18. }
  19. /**
  20. * Your NumArray struct will be instantiated and called as such:
  21. * NumArray* obj = numArrayCreate(nums, numsSize);
  22. * int param_1 = numArraySumRange(obj, i, j);
  23. * numArrayFree(obj);
  24. */

运行效率如下所示:


第8题:二维区域和检索 - 矩阵不可变

试题要求如下:

回答(C语言):

  1. typedef struct {
  2. int** sums;
  3. int sumsSize;
  4. } NumMatrix;
  5. NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
  6. NumMatrix* ret = malloc(sizeof(NumMatrix));
  7. ret->sums = malloc(sizeof(int*) * matrixSize);
  8. ret->sumsSize = matrixSize;
  9. for (int i = 0; i < matrixSize; i++) {
  10. ret->sums[i] = malloc(sizeof(int) * (matrixColSize[i] + 1));
  11. ret->sums[i][0] = 0;
  12. for (int j = 0; j < matrixColSize[i]; j++) {
  13. ret->sums[i][j + 1] = ret->sums[i][j] + matrix[i][j];
  14. }
  15. }
  16. return ret;
  17. }
  18. int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
  19. int sum = 0;
  20. for (int i = row1; i <= row2; i++) {
  21. sum += obj->sums[i][col2 + 1] - obj->sums[i][col1];
  22. }
  23. return sum;
  24. }
  25. void numMatrixFree(NumMatrix* obj) {
  26. for (int i = 0; i < obj->sumsSize; i++) {
  27. free(obj->sums[i]);
  28. }
  29. free(obj->sums);
  30. }
  31. /**
  32. * Your NumMatrix struct will be instantiated and called as such:
  33. * NumMatrix* obj = numMatrixCreate(matrix, matrixSize, matrixColSize);
  34. * int param_1 = numMatrixSumRegion(obj, row1, col1, row2, col2);
  35. * numMatrixFree(obj);
  36. */

运行效率如下所示:


第9题:比特位计数

试题要求如下:

回答(C语言):

  1. /**
  2. * Note: The returned array must be malloced, assume caller calls free().
  3. */
  4. int* countBits(int num, int* returnSize) {
  5. int* bits = malloc(sizeof(int) * (num + 1));
  6. *returnSize = num + 1;
  7. bits[0] = 0;
  8. int highBit = 0;
  9. for (int i = 1; i <= num; i++) {
  10. if ((i & (i - 1)) == 0) {
  11. highBit = i;
  12. }
  13. bits[i] = bits[i - highBit] + 1;
  14. }
  15. return bits;
  16. }

运行效率如下所示:


第10题:最长回文子串

试题要求如下:

回答(C语言):

  1. char * longestPalindrome(char * s){
  2. int right = 0, left = 0, count = 0;
  3. int startidx = 0;
  4. int max_len = 0;
  5. for (int i = 0; s[i] != '\0'; i += count) {
  6. count = 1;
  7. left = i - 1;
  8. right = i + 1;
  9. while ((s[right]!='\0') && (s[i] == s[right])) { // 选出重复字符
  10. right++;
  11. count++;
  12. }
  13. while ((left >= 0) && (s[right]!='\0') && (s[left] == s[right])) { // 由中心字符向左右扩展
  14. left--;
  15. right++;
  16. }
  17. if (max_len < (right - left - 1)) {
  18. max_len = right - left - 1; // 左右标记不在回文子串范围内,在外面两侧,需要减1
  19. startidx = left + 1;
  20. }
  21. }
  22. s[startidx + max_len] = '\0';
  23. return s + startidx;
  24. }

运行效率如下所示:




所属网站分类: 技术文章 > 博客

作者:代码搬运工

链接:http://www.qianduanheidong.com/blog/article/33517/c866e043712534da944c/

来源:前端黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

6 0
收藏该文
已收藏

评论内容:(最多支持255个字符)