directory

Problem 1: Square an ordered array

Problem 2: add or subtract string matching

Problem 3: The complement of numbers

Problem 4: Nim games

Problem 5: Delete all adjacent duplicates in a string

Problem 6: Divisor games

Problem 7: Convert to lowercase letters

Problem 8: Generate a string with an odd number of each character

Sort an array by parity

Problem 10: transpose matrix


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.

Problem 1: Square an ordered array

The requirements are as follows:

Answer (C language) :

/** * Note: The returned array must be malloced, assume caller calls free(). */
int cmp (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int* sortedSquares(int* A, int ASize, int* returnSize){
    *returnSize=ASize;

    for(int i=0; i<ASize; i++){ A[i]=A[i]*A[i]; }qsort(A, ASize, sizeof(int), cmp);

    return A;
}
Copy the code

The operating efficiency is as follows:


Problem 2: add or subtract string matching

The requirements are as follows:

Answer (C language) :

/** * Note: The returned array must be malloced, assume caller calls free(). */
int* diStringMatch(char * S, int* returnSize)
{
    int N = strlen(S);
    int a=N;
    int b=0;
    int *ret = (int *)malloc(sizeof(int)*(N+1));
    *returnSize = N + 1;

    for (int i=0; i<N; i++){if (S[i] == 'I'){
            ret[i] = b;
            b++;
        }
        else{
            ret[i] = a;
            a--;
        }
    }

    ret[N] = b;
    
    return ret;
}
Copy the code

The operating efficiency is as follows:


Problem 3: The complement of numbers

The requirements are as follows:

Answer (C language) :

int findComplement(int num){
    long temp = 1;
    
    while (num >= temp){
        temp <<= 1;
    }
    return (temp - 1 - num);
}
Copy the code

The operating efficiency is as follows:


Problem 4: Nim games

The requirements are as follows:

Answer (C language) :

bool canWinNim(int n){
   return (n % 4! =0); 
}
Copy the code

The operating efficiency is as follows:


Problem 5: Delete all adjacent duplicates in a string

The requirements are as follows:

Answer (C language) :

char * removeDuplicates(char * S){
    int i, cnt, len = strlen(S);

    for(i = 1, cnt = 0; i <= len; ++i) {if(cnt == - 1|| S[i] ! = S[cnt]) S[++cnt] = S[i];else 
            --cnt;
    }
    return S;
}
Copy the code

The operating efficiency is as follows:


Problem 6: Divisor games

The requirements are as follows:

Answer (C language) :

bool divisorGame(int N){
    // If Alice gets an odd number, she must lose.
    // Since the factors of an odd number must be odd, n-x must be even,
    // After Bob gets the even number, he just needs to return -1 to Alice, and Alice gets the odd number again.
    // Bob always gets an even number until he gets a 2 to win the game

    // Conversely, if Alice gets an even number, she only needs to give Bob -1, and Bob must lose.
    return N%2= =0;
}
Copy the code

The operating efficiency is as follows:


Problem 7: Convert to lowercase letters

The requirements are as follows:

Answer (C language) :

char * toLowerCase(char * str){

    for(int i=0; i<strlen(str); i++){if(str[i]>='A'&&str[i]<='Z')
            str[i]=str[i]+32;
    }

    return str;
}
Copy the code

The operating efficiency is as follows:


Problem 8: Generate a string with an odd number of each character

The requirements are as follows:

Answer (C language) :

char * generateTheString(int n)
{
    char *ret=(char *)malloc(sizeof(char)*(n+1));
    ret[n]='\ 0';
    memset(ret,'a',n);

    ret[n- 1] ='a'+(n%2= =0);
    
    return ret;
}
Copy the code

The operating efficiency is as follows:


Sort an array by parity

The requirements are as follows:

Answer (C language) :

/** * Note: The returned array must be malloced, assume caller calls free(). */
int* sortArrayByParity(int* A, int ASize, int* returnSize){
    int i=0,j=ASize- 1;
    int temp=0;

    while(i<j){
        if(A[i]%2! =0 && A[j]%2= =0){
            temp=A[j];
            A[j]=A[i];
            A[i]=temp;
        }

        if(A[i]%2= =0)
            i++;

        if(A[j]%2! =0)
            j--;
    }

    *returnSize=ASize;

    return A;
}
Copy the code

The operating efficiency is as follows:


Problem 10: transpose matrix

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** transpose(int** A, int ASize, int* AColSize, int* returnSize, int** returnColumnSizes){
    int** num=(int* *)malloc(sizeof(int*)*(*AColSize));
    *returnColumnSizes=(int*)malloc(sizeof(int)*(*AColSize));
    *returnSize=*AColSize;

    // Allocate memory
    for(int i=0; i<*AColSize; i++){ num[i]=(int*)malloc(sizeof(int)*ASize);
        returnColumnSizes[0][i] = ASize;
    }

    // Matrix transpose
    for(int i=0; i<ASize; i++){for(int j=0; j<*AColSize; j++){ num[j][i]=A[i][j]; }}return num;
}
Copy the code

The operating efficiency is as follows: