当前位置:网站首页>Leetcode, simple + medium (issue 28)

Leetcode, simple + medium (issue 28)

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

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 :

answer (C Language ):

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 :

answer (C Language ):

/**
 * 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 :

answer (C Language ):

int numPairsDivisibleBy60(int* time, int timeSize){
    int temp[61] = {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[0]*(temp[0] - 1)/2 + temp[30]*(temp[30] - 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 .

answer (C Language ):

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 :

answer (C Language ):

char* sortString(char* s) {
    int num[26];
    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.

answer (C Language ):

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 :

answer (C Language ):

/**
 * 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[26];

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 .

answer (C Language ):

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[26] = {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 :

answer (C Language ):

int cmp(const void* a , const void* b)
{
    int *aa = (int*)a;
    int *bb = (int*)b;
    /* sort from big to small */ 
    return bb[0] - aa[0];
}

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[26][2] = {0};
    for (int i = 0; i < len; i++) {
        a[S[i] - 'a'][0]++;
        a[S[i] - 'a'][1] = 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] > 0) {
                ret[rcnt++] = 'a' + a[i][1];
                tmp++;
                a[i][0]--;
            }
        }
    }

    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 .

answer (C Language ):

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 :

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