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 codeThe 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 codeThe 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 codeThe 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 codeThe 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 codeThe 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 codeThe 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 codeThe 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 codeThe 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 codeThe 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 codeThe operating efficiency is as follows:
