做视频网站用什么格式,网页考试题及答案,做网站论坛赚钱,做电视的视频网站前言
思路及算法思维#xff0c;指路 代码随想录。 题目来自 LeetCode。
day26#xff0c; 休息的周末~ day 27#xff0c;周一#xff0c;库存没了#xff0c;哭死~
题目详情
[39] 组合总和
题目描述
39 组合总和
解题思路
前提#xff1a;组合的子集问题…前言
思路及算法思维指路 代码随想录。 题目来自 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 同一树杈去重切割问题。
