力扣(LeetCode)刷題，簡單+中等題(第32期)

目錄

第1題：數組的度

第2題：托普利茨矩陣

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

第4題：翻轉圖像

第5題：有效的數獨

第6題：無重複字元的最長子串

第7題：區域和檢索 - 數組不可變

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

第9題：比特位計數

第10題：最長回文子串

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

試題要求如下：

解題思路：

用一個哈希表去統計所有元素的出現次數，“度”就是整個哈希表取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;
}      

運作效率如下所示：

周遊該矩陣，将每一個元素和它左上角的元素相比對即可。

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;
}      

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;
}      

/**
 * 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;
}      

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;
}      

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;
}      

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);
*/      

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);
*/      

/**
 * 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;
}      

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;
}