前言
思路及算法思維，指路 代碼隨想錄。
題目來自 LeetCode。
day26， 休息的周末~
day 27，周一，庫存沒了，哭死~
題目詳情
[39] 組合總和
題目描述
39 組合總和
解題思路
前提：組合的子集問題，統一元素可以重復選取
思路：回溯 + 剪枝。
重點：剪枝的前提是數組已排序。
代碼實現
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().*/void backtracing(int* candidates, int candidatesSize, int target, int index, int *nums, int numsSize, int ***ans, int* returnSize, int** returnColumnSizes)
{// 退出條件if (0 == target){*ans = (int **)realloc(*ans, sizeof(int *) * ((*returnSize) + 1));(*ans)[*returnSize] = (int *)malloc(sizeof(int) * (numsSize));for (int i = 0; i < numsSize; i++){(*ans)[*returnSize][i] = nums[i];}*returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * ((*returnSize) + 1));(*returnColumnSizes)[*returnSize] = numsSize;(*returnSize)++;return ;}for (int j = index; j < candidatesSize; j++){if (target < candidates[j]){continue ;}// 遞歸nums[numsSize] = candidates[j];numsSize++;backtracing(candidates, candidatesSize, target - candidates[j], j, nums, numsSize, ans, returnSize, returnColumnSizes);// 回溯numsSize--;nums[numsSize] = 0;}return ;
}int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {// 判空if (candidatesSize == 0){return NULL;}// 輸出int **ans = NULL;int nums[41];int index = 0;*returnSize = 0;printf("%d\n", target);backtracing(candidates, candidatesSize, target, 0, nums, 0, &ans, returnSize, returnColumnSizes);if (*returnSize == 0){return NULL;}return ans;
}
回溯 + 排序 + 剪枝
/*** 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 cmp(const void *p1, const void *p2)
{return *(int *)p1 > *(int *)p2;
}void backtracing(int* candidates, int candidatesSize, int target, int index, int *nums, int numsSize, int ***ans, int* returnSize, int** returnColumnSizes)
{// 退出條件if (0 == target){*ans = (int **)realloc(*ans, sizeof(int *) * ((*returnSize) + 1));(*ans)[*returnSize] = (int *)malloc(sizeof(int) * (numsSize));for (int i = 0; i < numsSize; i++){(*ans)[*returnSize][i] = nums[i];}*returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * ((*returnSize) + 1));(*returnColumnSizes)[*returnSize] = numsSize;(*returnSize)++;return ;}// 剪枝for (int j = index; (j < candidatesSize) && (target >= candidates[j]); j++){// 遞歸nums[numsSize] = candidates[j];numsSize++;backtracing(candidates, candidatesSize, target - candidates[j], j, nums, numsSize, ans, returnSize, returnColumnSizes);// 回溯numsSize--;nums[numsSize] = 0;}return ;
}int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {// 判空if (candidatesSize == 0){return NULL;}// 排序qsort(candidates, candidatesSize, sizeof(int), cmp);// 輸出int **ans = NULL;int nums[41];int index = 0;*returnSize = 0;backtracing(candidates, candidatesSize, target, 0, nums, 0, &ans, returnSize, returnColumnSizes);if (*returnSize == 0){return NULL;}return ans;
}
[40] 組合總和II
題目描述
40 組合總和II
解題思路
前提：組合的子集問題，同一元素只能使用一次，但是結果不包含重復組合
思路：回溯 + 剪枝
重點：結果子集中排除重復組合，需要樹形結構中，同一樹層的相同的元素值不可重復選取，使用used數組實現去重。
代碼實現
C語言
利用used數組 false，同一樹層 去重
/*** 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 cmp(const void *p1, const void *p2)
{return *(int *)p1 > *(int *)p2;
}void backtracing(int* candidates, int candidatesSize, int target, int index, int *nums, int numsSize, bool *used, int ***ans, int* returnSize, int** returnColumnSizes)
{// 退出條件if (0 == target){*ans = (int **)realloc(*ans, sizeof(int *) * ((*returnSize) + 1));(*ans)[*returnSize] = (int *)malloc(sizeof(int) * (numsSize));for (int i = 0; i < numsSize; i++){(*ans)[*returnSize][i] = nums[i];}*returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * ((*returnSize) + 1));(*returnColumnSizes)[*returnSize] = numsSize;(*returnSize)++;return ;}for (int j = index; (j < candidatesSize) && (target >= candidates[j]); j++){// 去重if ((j > 0) && (candidates[j] == candidates[j - 1]) && (used[j - 1] == false)){continue;}// 遞歸nums[numsSize] = candidates[j];used[j] = true;numsSize++;backtracing(candidates, candidatesSize, target - candidates[j], j + 1, nums, numsSize, used, ans, returnSize, returnColumnSizes);// 回溯numsSize--;used[j] = false;nums[numsSize] = 0;}return ;
}int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {// 判空if (candidatesSize == 0){return NULL;}// 排序qsort(candidates, candidatesSize, sizeof(int), cmp);// 輸出int **ans = NULL;int nums[100] = {0};bool used[100] = {false};int index = 0;*returnSize = 0;backtracing(candidates, candidatesSize, target, 0, nums, 0, used, &ans, returnSize, returnColumnSizes);if (*returnSize == 0){return NULL;}return ans;
}
[131] 分割回文串
題目描述
131 分割回文串
解題思路
前提：分割問題
思路：。
重點：。
代碼實現
C語言
// 待補充
今日收獲
- 組合子集問題：去重，同一樹層去重 vs 同一樹杈去重
- 切割問題。
