当前位置:网站首页>Leetcode (issue 27)

Leetcode (issue 27)

2020-12-06 11:04:34 Procedural ape without hair loss

Catalog

The first 1 topic : Unique occurrences

The first 2 topic : Quick calculation robot

The first 3 topic : The perimeter of the island

The first 4 topic : Sort the array in ascending order by frequency

The first 5 topic : According to the digital binary system 1 The order of the number of

The first 6 topic : Can you join to form an array

The first 7 topic : Strong integer

The first 8 topic : Even numbers after query and

The first 9 topic : Get the maximum value in the generated array

The first 10 topic : The depth of the binary tree


Power button (LeetCode) Brush questions regularly , Each issue 10 Problem , Business heavy comrades can see the ideas I share , Not the most efficient solution , Just for mutual promotion .

The first 1 topic : Unique occurrences

The requirements of the test questions are as follows :

 

Their thinking :

Obviously using hashtable thinking , But when dealing with negative numbers, you need to pay attention to , So the index can't be from 0 Start .

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

The operating efficiency is as follows :


The first 2 topic : Quick calculation robot

The requirements of the test questions 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;
}

The operating efficiency is as follows :


The first 3 topic : The perimeter of the island

The requirements of the test questions are as follows :

Their thinking :

It's good to crack Dafa with violence , For each side of a land grid , It is calculated as the perimeter of the island if and only if this edge is the boundary of the grid or the adjacent grid is water . therefore , You can traverse every land grid , See if the four directions are boundaries or waters , 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;
}

The operating efficiency is as follows :


The first 4 topic : Sort the array in ascending order by frequency

The requirements of the test questions are as follows :

Their thinking :

1、 Application length is 201 Hash table for ;

2、 Traverse nums Array , take nums[ i ] The number of times an element value appears , Map to hash table ;

3、 Traverse nums Array , restructure nums Elements ,nums Element low 3 Bits store the value of the current element , The remaining elements store the number of elements that appear ;

4、 Using quicksort , Yes nums Array to sort ;

*    If the number of elements is not equal , The use of nums Compare the high positions of the elements , The less frequent elements are at the front , The elements with high frequency are at the back ;

*    If the number of elements is equal , According to the low position ( 0 - 3 ) Value , Judge , namely :return d % 1000 - c % 1000.

5、 Traverse nums Array , Restore the value of an element ;

6、 Release buffer , Returns an array of 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;
}

The operating efficiency is as follows :


The first 5 topic : According to the digital binary system 1 The order of the number of

The requirements of the test questions 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;
}

The operating efficiency is as follows :


The first 6 topic : Can you join to form an array

The requirements of the test questions are as follows :

Their thinking :

Proof array arr The value in , Array pieces There are , Can be connected to form an array .

1、 The range of numbers entered is [0,100], So you can create a map[101] Array of , And store it in arr The subscript +1;

2、 Traverse pieces The numbers in it , If in map There is no record of , return false, If pieces There is more than one number in the current row in , Then judge whether the two adjacent numbers are in arr From left to right , If not, return false
Exclude all false After the situation , Then return to 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;
}

The operating efficiency is as follows :


The first 7 topic : Strong integer

The requirements of the test questions 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;
    // Determine whether the number already exists in the answer array 
    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;// The processing base is 1 In special circumstances , The same below 
    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, To put it in the answer array 
            {
                if(*returnSize>=1)
                {
                    if(judge(re,(*returnSize),tmp)==1)// Check that the number has been put into the answer array 
                    {
                        re[*returnSize]=tmp;
                        (*returnSize)++;
                    }
                }
                else// The first number put into the answer array does not need to be checked for duplicate 
                {
                    re[*returnSize]=tmp;
                    (*returnSize)++;
                }
            }
        }
    }
    return re;
}

The operating efficiency is as follows :


The first 8 topic : Even numbers after query and

The requirements of the test questions 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++) // Find out first A Even numbers in and 
	{
		if (A[k] % 2 == 0) 
		{
			SumEven += A[k];
		}
	}
	for (int i=0; i<queriesSize; i++)
	{
		if (A[queries[i][1]] % 2 == 0) // According to the parity of the current traversal 
		{
			SumEven-= A[queries[i][1]];
		}
		A[queries[i][1]] += queries[i][0];
		if (A[queries[i][1]] % 2 == 0) // According to the parity of the current traversal 
		{
			SumEven+= A[queries[i][1]];
		}
		answer[i] = SumEven;
	}
	*returnSize = queriesSize;
	return answer;
}

The operating efficiency is as follows :


The first 9 topic : Get the maximum value in the generated array

The requirements of the test questions 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;
}

The operating efficiency is as follows :


The first 10 topic : The depth of the binary tree

The requirements of the test questions 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;
}

The operating efficiency is as follows :

版权声明
本文为[Procedural ape without hair loss]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/202012061104016180.html