directory

Question 1: The number of unique occurrences

Problem 2: Fast computing robots

Question 3: The circumference of the island

4. Sort the array by frequency ascending

Problem 5: Sort by the number of ones under the numeric binary

Question 6: can join to form an array

Problem 7: Strong integers

Question 8: The sum of even numbers after query

Problem 9: Get the maximum value in the generated array

Problem 10: the depth of binary trees

LeetCode brushes the questions regularly, with 10 questions in each period. Comrades with heavy business can look at the ideas I share, which are not the most efficient solutions, but for mutual improvement.

Question 1:Unique number of occurrences

The requirements are as follows:

Answer:

Obviously hash table thinking, but you need to be careful when dealing with negative numbers, so indexes don’t start at 0.

Answer (C language) :

#define N 2001
bool uniqueOccurrences(int* arr, int arrSize){
	char hash[N] = {0}, set[N] = {0};
 
	for (short i = 0; i < arrSize; i++) 
        hash[arr[i]+1000]++;
 
	for (short i = 0; i < N; i++) {
		if (hash[i] > 0 && set[hash[i]] > 0)
            return false;
        else 
            set[hash[i]] = 1;
	}
 
	return true;
}
Copy the code

The operating efficiency is as follows:

Question 2:Quick-calculation robot

The requirements are as follows:

Answer (C language) :

int calculate(char* s){ int x = 1, y = 0; for(int i = 0; i < strlen(s); i++){ if(s[i] == 'A'){ x = 2*x +y; } else if(s[i] == 'B'){ y = 2*y +x; } } return x+y; }Copy the code

The operating efficiency is as follows:

Question 3:The circumference of the island

The requirements are as follows:

Answer:

Well, for each side of a land grid, it counts as the perimeter of the island if and only if that side is the boundary of the grid or if the adjacent cell is water. Therefore, you can traverse each land grid to see if its four directions are boundaries or waters, and if so, add 1.

Answer (C language) :

const int dx[4] = {0, 1, 0, -1}; const int dy[4] = {1, 0, -1, 0}; int islandPerimeter(int** grid, int gridSize, int* gridColSize) { int n = gridSize, m = gridColSize[0]; int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j]) { int cnt = 0; for (int k = 0; k < 4; ++k) { int tx = i + dx[k]; int ty = j + dy[k]; if (tx < 0 || tx >= n || ty < 0 || ty >= m || ! grid[tx][ty]) { cnt += 1; } } ans += cnt; } } } return ans; }Copy the code

The operating efficiency is as follows:

Question 4:Sort the array by frequency

The requirements are as follows:

Answer:

1, apply for a hash table of length 201;

2. Traverse the NUMS array and map the number of occurrences of nums[I] elements to the hash table;

3. Traverse the NUMS array and reconstruct the NUMS elements. The lower three bits of the NUMS element store the value of the current element, and the remaining elements store the number of elements appearing;

4. Use quicksort to sort numS array;

* If the number of elements is not equal, the highest numS element is used for comparison, with the element with the lowest degree in front and the element with the highest degree in the back;

Return d % 1000-c % 1000; return d % 1000-c % 1000;

5. Iterate through the NUMS array and restore the value of the element;

6, release buffer, return array NUMs.

Answer (C language) :

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
#define Abs( a ) ( ( a > 0 ) * a + ( a <= 0 ) * a * -1 )
 
int cmp( const void * a , const void * b ) {
 
    int c = *( int * )a;
    int d = *( int * )b;
 
    int a_c = Abs( c ) / 1000 , b_c = Abs( d ) / 1000;
 
    if( a_c > b_c ) {
 
        return 1;
 
    } else if( a_c < b_c ) {
 
        return -1;
 
    }
 
    return d % 1000 - c % 1000;
 
}
 
int * frequencySort(int * nums , int numsSize , int * returnSize ){
 
    int * hash = ( int * )malloc( sizeof( int ) * 201 );
 
    //intializing hash table
    memset( hash , 0 , sizeof( int ) * 201 );
 
    //updating hash table
    for( int i = 0 ; i < numsSize ; i++ ) {
 
        hash[ nums[ i ] + 100 ] += 1;
 
    }
 
    //updating nums
    for( int i = 0 ; i < numsSize ; i++ ) {
 
        int flag = 1;
 
        ( nums[ i ] < 0 ) && ( flag = -1 );
        nums[ i ] = hash[ nums[ i ] + 100 ] * 1000 * flag + nums[ i ];
 
    }
 
    //qsort nums
    qsort( nums , numsSize , sizeof( int ) , cmp );
 
    //updating nums
    for( int i = 0 ; i < numsSize ; i++ ) {
 
        nums[ i ] %= 1000;
 
    }
 
    *returnSize = numsSize;
    free( hash );
    return nums;
}
Copy the code

The operating efficiency is as follows:

Question 5:Sort by the number of 1s in the numeric binary

The requirements are as follows:

Answer (C language) :

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
int* bit;
 
int get(int x) {
    int res = 0;
    while (x) {
        res += (x % 2);
        x /= 2;
    }
    return res;
}
 
int cmp(void* _x, void* _y) {
    int x = *(int*)_x, y = *(int*)_y;
    return bit[x] == bit[y] ? x - y : bit[x] - bit[y];
}
 
int* sortByBits(int* arr, int arrSize, int* returnSize) {
    bit = malloc(sizeof(int) * 10001);
    memset(bit, 0, sizeof(int) * 10001);
    for (int i = 0; i < arrSize; ++i) {
        bit[arr[i]] = get(arr[i]);
    }
    qsort(arr, arrSize, sizeof(int), cmp);
    free(bit);
    *returnSize = arrSize;
    return arr;
}
Copy the code

The operating efficiency is as follows:

Question 6:Can join to form an array

The requirements are as follows:

Answer:

Array pieces can be joined to form an array.

1, the input number range is [0,100], so we can create an array of maps [101] and store it in arr subscript + 1;

If there is not one row in pieces, return false if there is not more than one row in pieces, return false if there is not more than one row in pieces, return false if there is not more than one row in pieces. Returns true.

Answer (C language) :

bool canFormArray(int* arr, int arrSize, int** pieces, int piecesSize, int* piecesColSize){ int map[101] = {0}; for (int i = 0; i < arrSize; i++){ map[arr[i]] = i+1; } for (int i = 0; i < piecesSize; i++){ for (int j = 0; j < piecesColSize[i]; j++){ if (map[pieces[i][j]] == 0) return false; if (j > 0){ int x = map[pieces[i][j]] - map[pieces[i][j-1]]; if (x ! = 1) return false; } } } return true; }Copy the code

The operating efficiency is as follows:

Question 7:Strong integer

The requirements are as follows:

Answer (C language) :

/** * Note: The returned array must be malloced, assume caller calls free(). */ int judge(int *re,int size,int tmp){ int i=0; For (I =0; i<size; i++) { if(tmp==re[i]) { return 0; } } return 1; } int* powerfulIntegers(int x, int y, int bound, int* returnSize){ int i=0,j=0,tmp=0; int max_i = log(bound)/log(x); int max_j = log(bound)/log(y); if (x == 1) max_i = 0; If (y == 1) max_j = 0; if (y == 1) max_j = 0; int *re=(int *)malloc(sizeof(int)*(bound+1)); *returnSize=0; for(i=0; i<=max_i; i++) { for(j=0; j<=max_j; j++) { tmp=pow(x,i)+pow(y,j); If (TMP <=bound)// only this number is less than or equal to bound, {if(*returnSize>=1) {if(judge(re,(*returnSize), TMP)==1) {re[*returnSize]= TMP; (*returnSize)++; }} else {re[*returnSize]= TMP; (*returnSize)++; } } } } return re; }Copy the code

The operating efficiency is as follows:

Question 8:The even sum after the query

The requirements are as follows:

Answer (C language) :

int* sumEvenAfterQueries(int* A, int ASize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){ int* answer = (int*)calloc(queriesSize,sizeof(int)); int SumEven = 0; for (int k=0; k<ASize; K++) / / and the first in A even number and {the if (A [k] % 2 = = 0) {SumEven + = A, [k]. } } for (int i=0; i<queriesSize; I++) {if (A [queries [I] [1]] % 2 = = 0) / / with the current number of traverse the odd-even situation for processing {SumEven - = A [queries [I] [1]]. } A[queries[i][1]] += queries[i][0]; If (A[queries[I][1]] % 2 == 0) {SumEven+= A[queries[I][1]]; } answer[i] = SumEven; } *returnSize = queriesSize; return answer; }Copy the code

The operating efficiency is as follows:

Question 9:Gets the maximum value in the generated array

The requirements are as follows:

Answer (C language) :

int getMaximumGenerated(int n) {
    if (n == 0)
		return 0;
	if (n == 1)
		return 1;
 
	int* arr = (int*)malloc((n + 1) * sizeof(int));
	arr[0] = 0;
	arr[1] = 1;
	int max = 1;
 
	for (int i = 2; i < n + 1; i++)
	{
		if (i % 2 == 0)
			arr[i] = arr[i / 2];
		else
			arr[i] = arr[i / 2] + arr[i / 2 + 1];
		if (max < arr[i])
			max = arr[i];
	}
    
	return max;
}
Copy the code

The operating efficiency is as follows:

Question 10:The depth of a binary tree

The requirements are as follows:

Answer (C language) :

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 
int maxDepth(struct TreeNode* root){
    int height = 0;
    if(root != NULL)
    {
        int leftHeight = maxDepth(root->left);
        int rightHeight = maxDepth(root->right);
        height = leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
    return height;
}
Copy the code

The operating efficiency is as follows: