directory

Problem 1: Integer to Roman numerals

Problem 2: a combination of letters for telephone numbers

Problem 3: all paths to a binary tree

Problem 4: Brick walls

Problem 5: Next permutation

Problem 6: Parenthesis generation

Question 7: Delete and earn points

Problem 8: All permutations

Problem 9: Color classification

Problem 10: grouping of letter heterotopic words

---

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.

Question 1:Integer to Roman numerals

The requirements are as follows:

Answer:

1. Create two arrays, namely numeric values and Roman character arrays. The Roman number of these two arrays corresponds to the array value.

2, find the corresponding Roman character;

Copy the Roman character into the output string.

Answer (C language) :

#include<string.h>

char * intToRoman(int num){
    //step1: Define an array
    int s[13] = {1000.900.500.400.100.90.50.40.10.9.5.4.1};// Array of values
    char a[13] [3] = {"M"."CM"."D"."CD"."C"."XC"."L"."XL"."X"."IX"."V"."IV"."I"};// Roman character array
    char *res = (char *)calloc(16.sizeof(char));

    int count = 0;// The number of Roman characters copied

    //step2: find the corresponding Roman character
    for(int i = 0; i <13; i++){ count = num / s[i]; num %= s[i];//step3: copy Roman characters
        for(int j = 0; j < count; j++){strcat(res,a[i]);//"strcat": copies the string of a[I] to the end of res}}return res;
}
Copy the code

The operating efficiency is as follows:

---

Question 2:A combination of letters for a telephone number

The requirements are as follows:

Answer:

Use a Map table to store all possible letters for each number, and then go back and enumerate all the solutions.

Answer (C language) :

/** * Note: The returned array must be malloced, assume caller calls free(). */
char phoneMap[9] [5] = {""."abc"."def"."ghi"."jkl"."mno"."pqrs"."tuv"."wxyz"}; // 1 does not correspond to any letter
/* Note: The returned array must be malloced, assume caller calls free(). */
void backtrack(char* digits, int digits_size, int index, char* item, int item_size, char** ans, int* returnSize) {
    if (index == digits_size) {
        char* tmp = malloc((item_size + 1) * sizeof(char)); // Allocate space for each item
        strcpy(tmp, item); // Copy and save each item
        ans[(*returnSize)++] = tmp;
    } 
    else {
        char* letters = phoneMap[digits[index] - '1'];
        int size = strlen(letters);
        for (int i = 0; i < size; i++) {
            item[item_size++] = letters[i];
            item[item_size] = 0;
            backtrack(digits, digits_size, index + 1, item, item_size, ans, returnSize);
            item[--item_size] = 0; }}}char** letterCombinations(char* digits, int* returnSize) {
    int digits_size = strlen(digits);
    *returnSize = 0;

    if (digits_size == 0) {
        return NULL;
    }

    int num = pow(4, digits_size);
    char** ans = (char* *)malloc(num * sizeof(char*));
    char* item = malloc((digits_size + 1) * sizeof(char));

    backtrack(digits, digits_size, 0, item, 0, ans, returnSize);
    
    return ans;
}
Copy the code

The operating efficiency is as follows:

---

Question 3:All paths to a binary tree

The requirements are as follows:

Answer:

The most intuitive approach is to use depth-first search. When a depth-first search traverses a binary tree, the current node and its children need to be considered.

• If the current node is not a leaf node, the node is added at the end of the current path and each child node of the node continues to be recursively traversed.
• If the current node is a leaf node, add the node at the end of the current path to get a path from the root node to the leaf node. Add the path to the answer.

In this way, when traversing the entire binary tree, we get all the paths from the root node to the leaf node. Of course, depth-first search can also be implemented in a non-recursive way.

Answer (C language) :

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; *}; * /

/** * Note: The returned array must be malloced, assume caller calls free(). */
void construct_paths(struct TreeNode* root, char** paths, int* returnSize, int* sta, int top) {
    if(root ! =NULL) {
        if (root->left == NULL && root->right == NULL) {  // The current node is a leaf node
            char* tmp = (char*)malloc(1001);
            int len = 0;
            for (int i = 0; i < top; i++) {
                len += sprintf(tmp + len, "%d->", sta[i]);
            }
            sprintf(tmp + len, "%d", root->val);
            paths[(*returnSize)++] = tmp;  // Add the path to the answer
        } else {
            sta[top++] = root->val;  // The current node is not a leaf node, continue recursive traversal
            construct_paths(root->left, paths, returnSize, sta, top);
            construct_paths(root->right, paths, returnSize, sta, top); }}}char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    char** paths = (char* *)malloc(sizeof(char*) * 1001);
    *returnSize = 0;
    int sta[1001];

    construct_paths(root, paths, returnSize, sta, 0);
    
    return paths;
}
Copy the code

The operating efficiency is as follows:

---

Question 4:Brick wall

The requirements are as follows:

Answer:

For the current row, we scan each brick from left to right, use an accumulator to record the distance from the right edge of the current brick to the left edge of the brick, and add the distance from the right edge to the left edge of the brick except the right-most brick to the hash table. Finally, we iterate through the table to find the most common brick edge, which is the brick edge that the vertical line passes through, and the number of bricks that the vertical line passes through is the height of the brick wall minus the number of brick edges that the vertical line passes through.

Answer (C language) :

struct HashTable {
    int key, val;
    UT_hash_handle hh;
};

int leastBricks(int** wall, int wallSize, int* wallColSize) {
    struct HashTable* cnt = NULL;
    for (int i = 0; i < wallSize; i++) {
        int n = wallColSize[i];
        int sum = 0;
        for (int j = 0; j < n - 1; j++) {
            sum += wall[i][j];
            struct HashTable* tmp;
            HASH_FIND_INT(cnt, &sum, tmp);
            if (tmp == NULL) {
                tmp = malloc(sizeof(struct HashTable));
                tmp->key = sum, tmp->val = 1;
                HASH_ADD_INT(cnt, key, tmp);
            } else{ tmp->val++; }}}int maxCnt = 0;
    struct HashTable *iter, *tmp;
    HASH_ITER(hh, cnt, iter, tmp) {
        maxCnt = fmax(maxCnt, iter->val);
    }
    return wallSize - maxCnt;
}
Copy the code

The operating efficiency is as follows:

---

Question 5:Next permutation

The requirements are as follows:

Answer (C language) :

void swap(int *a, int *b) {
    int t = *a;
    *a = *b, *b = t;
}

void reverse(int *nums, int left, int right) {
    while (left < right) {
        swap(nums + left, nums + right); left++, right--; }}void nextPermutation(int *nums, int numsSize) {
    int i = numsSize - 2;

    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = numsSize - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        swap(nums + i, nums + j);
    }
    
    reverse(nums, i + 1, numsSize - 1);
}
Copy the code

The operating efficiency is as follows:

---

Question 6:Parentheses generates

The requirements are as follows:

Answer:

Backtracking algorithm recursive solution: if the number of open parentheses is not greater than n, we can put an open parenthesis. If the number of close parentheses is less than the number of open parentheses, we can put a close parentheses.

Answer (C language) :

// backtracking
#define MAX_SIZE 1430  // Catalan number: 1, 1, 2, 5, 14, 42, 132, 429, 1430

void generate(int left, int right, int n, char *str, int index, char **result, int *returnSize) {
    if (index == 2 * n) { // The current length is 2N
        result[(*returnSize)] =  (char*)calloc((2 * n + 1), sizeof(char));
        strcpy(result[(*returnSize)++], str);
        return;
    }
    // If the number of open parentheses is not greater than n, an open parenthesis can be placed
    if (left < n) {
        str[index] = '(';
        generate(left + 1, right, n, str, index + 1, result, returnSize);
    }
    // If the number of close parentheses is less than the number of open parentheses, you can put a close parentheses
    if (right < left) {
        str[index] = ') ';
        generate(left, right + 1, n, str, index + 1, result, returnSize); }}/** * Note: The returned array must be malloced, assume caller calls free(). */
char** generateParenthesis(int n, int *returnSize) {
    char *str = (char*)calloc((2 * n + 1), sizeof(char));
    char **result = (char* *)malloc(sizeof(char *) * MAX_SIZE);
    *returnSize = 0;
    generate(0.0, n, str, 0, result, returnSize);
    return result;
}
Copy the code

The operating efficiency is as follows:

---

Question 7:Delete and earn points

The requirements are as follows:

Answer (C language) :

int rob(int *nums, int numsSize) {
    int first = nums[0], second = fmax(nums[0], nums[1]);
    
    for (int i = 2; i < numsSize; i++) {
        int temp = second;
        second = fmax(first + nums[i], second);
        first = temp;
    }

    return second;
}

int deleteAndEarn(int *nums, int numsSize) {
    int maxVal = 0;

    for (int i = 0; i < numsSize; i++) {
        maxVal = fmax(maxVal, nums[i]);
    }

    int sum[maxVal + 1];
    memset(sum, 0.sizeof(sum));

    for (int i = 0; i < numsSize; i++) {
        sum[nums[i]] += nums[i];
    }

    return rob(sum, maxVal + 1);
}
Copy the code

The operating efficiency is as follows:

---

Question 8:The whole arrangement

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

void dfs(int* nums,int numsSize,int depth,int* cur,bool* used,int** res){
    if(depth==numsSize){
        res[count]=(int*)malloc(numsSize*sizeof(int));
        memcpy(res[count++],cur,numsSize*sizeof(int));
        return;
    }

    for(int i=0; i<numsSize; ++i){if(used[i]==true) continue;
        cur[depth]=nums[i];
        used[i]=true;
        //++depth;

        dfs(nums,numsSize,depth+1,cur,used,res);
        
        //--depth;
        used[i]=false; }}int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int s=1;
    for(int i=1; i<=numsSize; ++i) s*=i;int** res=(int* *)malloc(s*sizeof(int*));

    bool* used=(bool*)malloc(numsSize*sizeof(bool));
    memset(used,0,numsSize*sizeof(bool));

    int* cur=(int*)malloc(numsSize*sizeof(int));

    count=0;
    dfs(nums,numsSize,0,cur,used,res);
    
    *returnSize=s;
    *returnColumnSizes=(int*)malloc(s*sizeof(int));
    for(int i=0; i<s; ++i) (*returnColumnSizes)[i]=numsSize;return res;
}
Copy the code

The operating efficiency is as follows:

---

Question 9:Color classification

The requirements are as follows:

Answer (C language) :

void swap(int *a, int *b) {
    int t = *a;
    *a = *b, *b = t;
}

void sortColors(int *nums, int numsSize) {
    int ptr = 0;
    
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] == 0) {
            swap(&nums[i], &nums[ptr]); ++ptr; }}for (int i = ptr; i < numsSize; ++i) {
        if (nums[i] == 1) {
            swap(&nums[i], &nums[ptr]); ++ptr; }}}Copy the code

The operating efficiency is as follows:

---

Question 10:Grouping of letter ectopic words

The requirements are as follows:

Answer:

1. Sort the string first to see if it is an allotopic word.

2. Store a hashtable containing a string of heterotopic words from small to large;

3. Check ht to determine whether a new line of result needs to be created.

4. Insert string in ht by Str->id.

5. If there is no HT, create a new line in result.

Answer (C language) :

#define STR_MAX_LEN 10000

static int compare(const void* x, const void* y)
{
    return* (char*)x - *(char*)y;
}

struct Str {
    char key_str[STR_MAX_LEN];
    int id;
    UT_hash_handle hh;
};

char* * *groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes)
{
    if (strs == NULL || strsSize < 0) {
        return NULL;
    }
    struct Str *keyStrsHash = NULL, *str = NULL;
    char ***result = (char* * *)malloc(sizeof(char **) * strsSize);
    char **sortedStrs = (char* *)malloc(sizeof(char *) * strsSize);
    *returnSize = 0;
    *returnColumnSizes = (int *)malloc(sizeof(int) * strsSize);

    for (int i = 0; i < strsSize; i++) {
        int len = strlen(strs[i]);
        sortedStrs[i] = (char*)malloc(len + 1);
        (void)strcpy(sortedStrs[i], strs[i]);
        qsort(sortedStrs[i], len, sizeof(char), compare);
        
        HASH_FIND_STR(keyStrsHash, sortedStrs[i], str);
        if(! str) { str = (struct Str*)malloc(sizeof(struct Str));
            strcpy(str->key_str, sortedStrs[i]);
            str->id = *returnSize;
            HASH_ADD_STR(keyStrsHash, key_str, str);

            result[*returnSize] = (char* *)malloc(sizeof(char*) * strsSize);
            result[*returnSize][0] = (char*)malloc(len + 1);
            strcpy(result[*returnSize][0], strs[i]);

            (*returnColumnSizes)[*returnSize] = 1;
            (*returnSize)++;
        } else {
            int row = str->id;
            int col = (*returnColumnSizes)[row];
            result[row][col] = (char*)malloc(len + 1);
            strcpy(result[row][col], strs[i]); ((*returnColumnSizes)[row])++; }}HASH_CLEAR(hh, keyStrsHash);
    for (int i = 0; i < strsSize; i++) {
            free(sortedStrs[i]);
    }
    return result;
}
Copy the code

The operating efficiency is as follows: