目錄

第1題：整數(shù)轉羅馬數(shù)字

第2題：電話號碼的字母組合

第3題：二叉樹的所有路徑

第4題：磚墻

第5題：下一個排列

第6題：括號生成

第7題：刪除并獲得點數(shù)

第8題：全排列

第9題：顏色分類

第10題：字母異位詞分組

---

力扣(LeetCode)定期刷題，每期10道題，業(yè)務繁重的同志可以看看我分享的思路，不是最高效解決方案，只求互相提升。

第1題：整數(shù)轉羅馬數(shù)字

試題要求如下：

解題思路：

1、建立兩個數(shù)組，分別是數(shù)值數(shù)值以及羅馬字符數(shù)組，這兩個數(shù)組的羅馬數(shù)與數(shù)組值對應；

2、找對應的羅馬字符；

3、將羅馬字符拷貝進輸出字符串中。

回答（C語言）：

#include<string.h>char * intToRoman(int num){//step1：定義數(shù)組int s[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};//數(shù)值數(shù)組char a[13][3] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};//羅馬字符數(shù)組char *res = (char *)calloc(16,sizeof(char));int count = 0;//羅馬字符拷貝次數(shù)//step2：找對應的羅馬字符for(int i = 0;i < 13;i++){count = num / s[i];num %= s[i];//step3：拷貝羅馬字符for(int j = 0;j < count;j++){strcat(res,a[i]);//"strcat":該函數(shù)是將a[i]的字符串拷貝到res后面}}return res;
}

運行效率如下所示：

---

第2題：電話號碼的字母組合

試題要求如下：

解題思路：

使用Map表存儲每個數(shù)字對應的所有可能的字母，然后進行回溯操作，窮舉出所有的解。

回答（C語言）：

/*** Note: The returned array must be malloced, assume caller calls free().*/
char phoneMap[9][5] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 1 不對應任何字母
/* 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)); // 為每一個 item 分配獨立空間strcpy(tmp, item); // 把每一個 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;
}

運行效率如下所示：

---

第3題：二叉樹的所有路徑

試題要求如下：

解題思路：

最直觀的方法是使用深度優(yōu)先搜索。在深度優(yōu)先搜索遍歷二叉樹時，需要考慮當前的節(jié)點以及它的孩子節(jié)點。

• 如果當前節(jié)點不是葉子節(jié)點，則在當前的路徑末尾添加該節(jié)點，并繼續(xù)遞歸遍歷該節(jié)點的每一個孩子節(jié)點。
• 如果當前節(jié)點是葉子節(jié)點，則在當前路徑末尾添加該節(jié)點后我們就得到了一條從根節(jié)點到葉子節(jié)點的路徑，將該路徑加入到答案即可。

如此，當遍歷完整棵二叉樹以后就得到了所有從根節(jié)點到葉子節(jié)點的路徑。當然，深度優(yōu)先搜索也可以使用非遞歸的方式實現(xiàn)。

回答（C語言）：

/*** 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) {  // 當前節(jié)點是葉子節(jié)點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;  // 把路徑加入到答案中} else {sta[top++] = root->val;  // 當前節(jié)點不是葉子節(jié)點，繼續(xù)遞歸遍歷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;
}

運行效率如下所示：

---

第4題：磚墻

試題要求如下：

解題思路：

遍歷磚墻的每一行，對于當前行，我們從左到右地掃描每一塊磚，使用一個累加器記錄當前磚的右側邊緣到磚墻的左邊緣的距離，將除了最右側的磚塊以外的其他磚塊的右邊緣到磚墻的左邊緣的距離加入到哈希表中。最后我們遍歷該哈希表，找到出現(xiàn)次數(shù)最多的磚塊邊緣，這就是垂線經過的磚塊邊緣，而該垂線經過的磚塊數(shù)量即為磚墻的高度減去該垂線經過的磚塊邊緣的數(shù)量。

回答（C語言）：

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

運行效率如下所示：

---

第5題：下一個排列

試題要求如下：

回答（C語言）：

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);
}

運行效率如下所示：

---

第6題：括號生成

試題要求如下：

解題思路：

回溯算法遞歸求解：如果左括號數(shù)量不大于 n，我們可以放一個左括號。如果右括號數(shù)量小于左括號的數(shù)量，我們可以放一個右括號。

回答（C語言）：

// 回溯法求解
#define MAX_SIZE 1430  // 卡特蘭數(shù): 1, 1, 2, 5, 14, 42, 132, 429, 1430void generate(int left, int right, int n, char *str, int index, char **result, int *returnSize) {if (index == 2 * n) { // 當前長度已達2nresult[(*returnSize)] =  (char*)calloc((2 * n + 1), sizeof(char));strcpy(result[(*returnSize)++], str);return;}// 如果左括號數(shù)量不大于 n，可以放一個左括號if (left < n) {str[index] = '(';generate(left + 1, right, n, str, index + 1, result, returnSize);}// 如果右括號數(shù)量小于左括號的數(shù)量，可以放一個右括號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;
}

運行效率如下所示：

---

第7題：刪除并獲得點數(shù)

試題要求如下：

回答（C語言）：

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);
}

運行效率如下所示：

---

第8題：全排列

試題要求如下：

回答（C語言）：

/*** 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;
}

運行效率如下所示：

---

第9題：顏色分類

試題要求如下：

回答（C語言）：

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

運行效率如下所示：

---

第10題：字母異位詞分組

試題要求如下：

解題思路：

1、先排序字符串，以判斷是否是異位詞；

2、在hashtable中存放異位詞的從小到大的字符串;

3、在ht中查找，以此判斷是否需要創(chuàng)建result的新行；

4、存在ht中，則通過Str->id插入字符串即可；

5、不存在ht中，則在result中創(chuàng)建新行。

回答（C語言）：

#define STR_MAX_LEN 10000static 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;
}

運行效率如下所示：

總結

以上是生活随笔為你收集整理的力扣(LeetCode)刷题，简单+中等题(第34期)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。