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: