The requirements are as follows:

Answer:

You take a hash table and count the number of occurrences of all the elements, and the degree is the maximum value of the hash table, and then they ask you to find the minimum length of the contiguous subarray that reaches that value. You do this by walking through the array to find the “degree” and then sliding down to the smallest.

Answer (C language) :

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]]++;/ / record
        if(mark[nums[i]]>count)
            count=mark[nums[i]];// Write down the maximum degree

        if(mark[nums[i]]==1)// For the first time, you need to set the starting point
        {
            start[nums[i]]=i;
            end[nums[i]]=i;
        }
        else if(mark[nums[i]]>1)// Not the first time
            end[nums[i]]=i;
    }

    min=50000;// Find the largest

    for(i=0; i<50000; i++)
    {
        if(mark[i]==count)// Check whether it meets the requirements
            if(end[i]-start[i]<min)
                min=end[i]-start[i];
    } 

    min++;
    return min;
}
Copy the code

The operating efficiency is as follows:

Question 2:Toplitz matrix

The requirements are as follows:

Answer:

Walk through the matrix, comparing each element to its upper-left element.

Answer (C language) :

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;
}
Copy the code

The operating efficiency is as follows:

Question 3:An angry bookstore owner

The requirements are as follows:

Answer:

Answer (C language) :

int maxSatisfied(int* customers, int customersSize, int* grumpy, int grumpySize, int X){
    int i;
    int sum = 0;
    int res = 0;

    /* Window [0, x-1] all customers are satisfied */
    for (i = 0; i < X; i++) {
        sum += customers[i];
    }

    /* Count the number of satisfied customers outside the window [0, x-1] */
    for (; i < customersSize; i++) {
        sum += (grumpy[i] == 0)? customers[i] :0;
    }

    res = sum;

    /* Slide the window, each time one person in one out, calculate the number of satisfied */
    for (i = 1; i <= customersSize - X; i++) {
        sum -= customers[i - 1]     * grumpy[i - 1];     /* Subtract */ from the original window
        sum += customers[i - 1 + X] * grumpy[i - 1 + X]; /* add */ to a new window
        res  = fmax(res, sum);
    }
    
    return res;
}
Copy the code

The operating efficiency is as follows:

Question 4:Flip the image

The requirements are as follows:

Answer (C language) :

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

The operating efficiency is as follows:

Question 5:Valid sudoku

The requirements are as follows:

Answer (C language) :

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++) {
      / / line
      if(board[i][j] ! ='. ') {
        if (row[board[i][j] - '1'] = =1) return false;
        row[board[i][j] - '1'] + +; }/ / column
      if(board[j][i] ! ='. ') {
        if (col[board[j][i] - '1'] = =1) return false;
        col[board[j][i] - '1'] + +; }/ / scratchable latex
      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;
}
Copy the code

The operating efficiency is as follows:

Question 6:The oldest string without repeating characters

The requirements are as follows:

Answer (C language) :

int lengthOfLongestSubstring(char * s){
    int res = 0;
    int len = strlen(s);
    /* Stores the number of occurrences of ASCII characters in a substring */
    int freq[256] = {0};  
    /* Define the sliding window as s[l...r] */
    int l = 0, r = - 1; 
    
    while (l < len) {
        /* The character does not exist in freq, the right boundary moves right, and the number of occurrences of the character is recorded in freq */
        if (r < len - 1 && freq[s[r + 1= =]]0) {
            freq[s[++r]]++;
        /* The right boundary cannot be expanded, and the left boundary moves to the right, removing the repeated elements and subtracting the number of occurrences of characters corresponding to the left boundary in freq by one */
        } else {
            freq[s[l++]]--;
        }
        /* Maximizes the length of the current substring and the length of the oldest string found */
        res = fmax(res, r - l + 1);
    }

    return res;
}
Copy the code

The operating efficiency is as follows:

Question 7:Region and retrieval – Arrays are immutable

The requirements are as follows:

Answer (C language) :

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

The operating efficiency is as follows:

Question 8:Two dimensional region and retrieval – matrix immutable

The requirements are as follows:

Answer (C language) :

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

The operating efficiency is as follows:

Question 9:Bit count

The requirements are as follows:

Answer (C language) :

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

The operating efficiency is as follows:

Question 10:Longest string of subroutines

The requirements are as follows:

Answer (C language) :

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])) { // Select repeated characters
            right++;
            count++;
        }

        while ((left >= 0) && (s[right]! ='\ 0') && (s[left] == s[right])) { // Expand from the center character to the left and right
            left--;
            right++;
        }

        if (max_len < (right - left - 1)) {
            max_len = right - left - 1;  // The left and right tokens are outside the range of the substring
            startidx = left + 1;
        }
    }

    s[startidx + max_len] = '\ 0';
    return s + startidx;
}
Copy the code

The operating efficiency is as follows: