写点什么

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

发布于: 2021 年 03 月 05 日
力扣(LeetCode)刷题,简单+中等题(第32期)

力扣(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;}
复制代码


运行效率如下所示:



发布于: 2021 年 03 月 05 日阅读数: 12
用户头像

【研究方向】物联网、嵌入式、AI、Python 2018.02.09 加入

【公众号】美男子玩编程

评论

发布
暂无评论
力扣(LeetCode)刷题,简单+中等题(第32期)