Leetcode, simple + medium (issue 28)

2020-12-06 11:04:26

Catalog

The first 1 topic ： Flip word order

The first 2 topic ： Print matrix clockwise

The first 3 topic ： The total duration can be 60 The song of division

The first 4 topic ： The greatest common factor of a string

The first 5 topic ： Up down string

The first 6 topic ： Divide the array into three parts equal to and

The first 7 topic ： Can be 5 Binary prefixes for division

The first 8 topic ： Remove duplicate letters

The first 9 topic ： Refactoring strings

The first 10 topic ： The maximum circumference of a triangle

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 ： Flip word order

The requirements of the test questions are as follows ： char* reverseWords(char* s){
//  Remove trailing spaces . In the end, leave at least one space , Unless its length is 0
int n = strlen(s);
while(n > 0 && s[n-1] == ' ')
n--;

//  Remove the space in the head
int front = 0;
if(n > 0){
while(s[front] == ' ')
front++;
}

//  If it is empty , return
if( n - front == 0)
return "";

//  Create a character pointer , The length is greater than or equal to the actual length
char *p = (char *)calloc(n + 1 - front, sizeof(char));

int index = 0; //  This is the subscript of the new string

for( int i = n-1 , j = n-1; i >= front ; i--){
//  It's time to write words
if(i == front || (s[i] == ' ' && i != j) ){
int k = i + 1;
//  If it comes to an end , That end should also write
if(i == front)
k--;
for(; k <= j ; k++,index++){
p[index] = s[k];
}
//  Be careful ！ Put a space after the word
if(i != front)
p[index] = s[i];
j = i - 1;
index = index + 1;
}
//  When there are many spaces in the middle, you should skip
else if(s[i] == ' '){
j--;
}
}
return p;
}

The operating efficiency is as follows ： The first 2 topic ： Print matrix clockwise

The requirements of the test questions are as follows ： Their thinking ： /**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
if(!matrixSize){
*returnSize=0;
return NULL;
}

int ColSize=*matrixColSize;
*returnSize=matrixSize*ColSize;
int num=*returnSize;
int* val=(int*)malloc(sizeof(int)*num);
int x=0,y=0;
int count=0;
int no;

while(count<num){
no=0;
// Left to right
while(no++<ColSize&&count<num){
val[count++]=matrix[y][x++];
}
y++,x--,matrixSize--,no=0;
// Up and down
while(no++<matrixSize&&count<num){
val[count++]=matrix[y++][x];
}
y--,x--,ColSize--,no=0;
// Right to left
while(no++<ColSize&&count<num){
val[count++]=matrix[y][x--];
}
x++,y--,matrixSize--,no=0;
// Down to up
while(no++<matrixSize&&count<num){
val[count++]=matrix[y--][x];
}
ColSize--,y++,x++;
}

return val;
}

The operating efficiency is as follows ： The first 3 topic ： The total duration can be 60 The song of division

The requirements of the test questions are as follows ： int numPairsDivisibleBy60(int* time, int timeSize){
int temp = {0};
int cnt = 0;

// Count the number of times the remainder appears , Remainder as subscript
for(int i = 0;i < timeSize;i++)
{
temp[time[i]%60]++;
}

// Remainder is 0 and 30 The situation of , Logarithms are combinations Cn2 = n*（n-1）/2
cnt = temp*(temp - 1)/2 + temp*(temp - 1)/2;
// The remainder is in other cases , Every remainder i Can be associated with the remainder 60-i pairing , So the logarithm is temp[i]*temp[60-i]
for(int i = 0;i < 30;i++)
{
cnt = cnt +temp[i]*temp[60-i];
}

return cnt;
}

The operating efficiency is as follows ： The first 4 topic ： The greatest common factor of a string

The requirements of the test questions are as follows ： Their thinking ：

Recursive method .

1、 Guarantee the present str1 The length is greater than or equal to str2( Through judgment exchange );

2、 If at present str1 Longer than str2, And str1 The front part of the str2 atypism , Then there is no common cause string between them ;

3、 If at present str1 Longer than str2, And str1 The front part of the str2 Agreement , Otherwise intercept str1 The latter part is reconstituted with str2 Compare ;

4、 If at present str1 And str2 Agreement , Then the greatest common factor is itself .

char * gcdOfStrings(char * str1, char * str2){
int len1 = strlen(str1);
int len2 = strlen(str2);

if (len2 > len1) {
char *tmp = str1;
str1 = str2;
str2 = tmp;
len2 = len1;
}

if (memcmp(str1, str2, len2)) {
return "";
}
else if (str1[len2] == '\0' && str2[len2] == '\0') {
return str1;
}

return gcdOfStrings(str1 + len2, str2);
}

The operating efficiency is as follows ： The first 5 topic ： Up down string

The requirements of the test questions are as follows ： char* sortString(char* s) {
int num;
memset(num, 0, sizeof(num));
int n = strlen(s);
for (int i = 0; i < n; i++) {
num[s[i] - 'a']++;
}

char* ret = malloc(sizeof(char) * (n + 1));
int retSize = 0;
while (retSize < n) {
for (int i = 0; i < 26; i++) {
if (num[i]) {
ret[retSize++] = i + 'a';
num[i]--;
}
}
for (int i = 25; i >= 0; i--) {
if (num[i]) {
ret[retSize++] = i + 'a';
num[i]--;
}
}
}
ret[retSize] = 0;
return ret;
}

The operating efficiency is as follows ： The first 6 topic ： Divide the array into three parts equal to and

The requirements of the test questions are as follows ： Their thinking ：

1、 Sum up , If and not 3 Multiple , direct false;

2、 One third of the sum , Go through the accumulation from the beginning , Meet equal to and one third of , Out of the loop , And point to the next element ;

3、 Continue to traverse and sum , If it's two-thirds of the sum , Out of the loop ;

4、 Determine the position at this time , If it's the last one , It doesn't meet the conditions ,false, otherwise true.

bool canThreePartsEqualSum(int* A, int ASize){
int sum = 0,i,j,temp,sum1 = 0;

// Sum up , If and not 3 Multiple , direct false
for(int i = 0;i < ASize;i++)
{
sum = sum + A[i];
}
if(sum%3 != 0) return false;

// One third of the sum
temp = sum/3;
// Ergodic accumulation , Meet equal to and one third of , Out of the loop , And point to the next element
for(i = 0;i < ASize;i++)
{
sum1 = sum1 + A[i];
if(sum1 == temp) break;
}
// Continue to traverse and sum , If it's two-thirds of the sum , Out of the loop
for(j = i + 1;j < ASize;j++)
{
sum1 = sum1 + A[j];
if(sum1 == temp*2) break;
}
// Determine the position at this time , If it's the last one , It doesn't meet the conditions ,false, otherwise true
if(j > ASize - 2)
return false;
else
return true;
}

The operating efficiency is as follows ： The first 7 topic ： Can be 5 Binary prefixes for division

The requirements of the test questions are as follows ： /**
* Note: The returned array must be malloced, assume caller calls free().
*/
bool* prefixesDivBy5(int* A, int ASize, int* returnSize)
{
int temp = 0;
*returnSize = ASize;

bool* ret = (bool*)malloc(ASize * sizeof(bool));

for (int i = 0; i < ASize; i++) {
temp = (temp << 1) + A[i];
temp = temp % 5;
if (temp == 0) {
ret[i] = true;
} else {
ret[i] = false;
}
}

return ret;
}

The operating efficiency is as follows ： The first 8 topic ： Remove duplicate letters

The requirements of the test questions are as follows ： Their thinking ：

1、 Initializing an array recode;

2、 Traverse s Record the number of times each letter appears ;

3、 Create a new stack , Traverse s Go to the stack ;

4、 Traversal stack , If s[i] In the stack , be recode[s[i]-’a‘]--, And continue the next traversal ;

5、 Otherwise compare the top of the stack letters with s[i] Size , If stack[top]>s[i] also recode[stack[top]-'a']>1( explain stack[top] There will be ) Out of the stack , also recode[s[i]-’a‘]--;

6、 Push ;

7、 Last stack[++top]=’\0‘ Convert to string .

char * removeDuplicateLetters(char * s){
if (s == NULL || strlen(s) == 0) {
return "";
}
if (strlen(s) == 1) {
return s;
}
int len = (int)strlen(s);
// Be careful , This needs to be initialized to 0
char recode = {0};

for (int i=0; i<len; i++) {
recode[s[i] - 'a']++;
}

char * stack = (char *)malloc(sizeof(char) * (len+1));
int top = -1;

int isExist;
for (int i=0; i<len; i++) {
isExist = 0;
for (int j=0; j<=top; j++) {
if (s[i] == stack[j]) {
isExist = 1;
break;
}
}

if (isExist) {
recode[s[i] - 'a']--;
}else{
while(top>-1 && stack[top] > s[i] && recode[stack[top] - 'a'] > 1) {
// If the character at the top of the stack is larger than the current one , And there will be
recode[stack[top] - 'a']--;
// Out of the stack
top--;
}
// Push
stack[++top] = s[i];
}
}
stack[++top] = '\0';
return stack;
}

The operating efficiency is as follows ： The first 9 topic ： Refactoring strings

The requirements of the test questions are as follows ： int cmp(const void* a , const void* b)
{
int *aa = (int*)a;
int *bb = (int*)b;
/* sort from big to small */
return bb - aa;
}

char * reorganizeString(char * S){

int rcnt = 0;
int len = strlen(S);
char * ret = (char *)malloc(sizeof(char)*len+1);
memset(ret, 0, sizeof(char)*len+1);
int a = {0};
for (int i = 0; i < len; i++) {
a[S[i] - 'a']++;
a[S[i] - 'a'] = S[i] - 'a';
}
int tmp = 0;
while (rcnt < len) {
tmp = 0;
qsort(a, 26, sizeof(int)*2, cmp);
for (int i = 0; i < 26 && tmp < 2; i++) {
if (a[i] > 0) {
ret[rcnt++] = 'a' + a[i];
tmp++;
a[i]--;
}
}
}

for (int i = 1; i < rcnt; i++) {
if (ret[i] == ret[i-1]) {
return "";
}
}
return ret;
}

The operating efficiency is as follows ： The first 10 topic ： The maximum circumference of a triangle

The requirements of the test questions are as follows ： Their thinking ：

The sum of the two sides of a triangle , It must be bigger than the third side .

int cmp(void *_a, void *_b) {
int a = *(int *)_a, b = *(int *)_b;
return a - b;
}

int largestPerimeter(int *A, int ASize) {
qsort(A, ASize, sizeof(int), cmp);
for (int i = ASize - 1; i >= 2; --i) {
if (A[i - 2] + A[i - 1] > A[i]) {
return A[i - 2] + A[i - 1] + A[i];
}
}
return 0;
}

The operating efficiency is as follows ： https://chowdera.com/2020/12/20201206110401609y.html