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

目录

第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; icount)
            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; isums[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 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 = 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;
}

运行效率如下所示：