39.组合总和
给你一个 无重复元素 的整数数组 candidates
和一个目标整数 target
,找出 candidates
中可以使数字和为目标数 target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target
的不同组合数少于 150
个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。
示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2], target = 1
输出: []
提示:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates
的所有元素 互不相同1 <= target <= 40
思路:
这道题跟昨天的思路很像,但是要注意的是我们要添加合适的退出条件,比如当总和大于目标值时,我们要直接返回,结束递归,同时我们要加上相应的start来寻找元素的正确位置,以免找到重复元素,以及从题目所给数组取元素的所对元素要把它按所取元素的最大元素个数来创造,以免超出数组的界限。
解答:
/*** 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 travelback(int* candidates,int candidatesSize,int target,int* returnSize,int** returnColumnSizes,int*** result,int sum,int combinesize,int* num,int start)
{if(sum == target){(*returnSize)++;(*result) = realloc(*result,sizeof(int*)*(*returnSize));(*result)[(*returnSize)-1] = malloc(sizeof(int)*combinesize);for(int i = 0;i < combinesize;i++){(*result)[(*returnSize)-1][i] = num[i];}*returnColumnSizes = realloc(*returnColumnSizes,sizeof(int*)*(*returnSize));(*returnColumnSizes)[(*returnSize)-1] = combinesize;return;}if(sum > target){return;}for(int i = start;i < candidatesSize;i++){sum += candidates[i];num[combinesize] = candidates[i];travelback(candidates,candidatesSize,target,returnSize,returnColumnSizes,result,sum,combinesize+1,num,i);sum -= candidates[i];}
}
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int sum = 0;int** result = NULL;int combinesize = 0;*returnColumnSizes = NULL;int* num = malloc(sizeof(int)*target);travelback(candidates,candidatesSize,target,returnSize,returnColumnSizes,&result,sum,combinesize,num,0);return result;
}
40.组合总和||
给定一个候选人编号的集合 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
思路:
这道题的思路跟前面都差不多,但是这里最重要的是去重,所以在这里我用了一个qsort函数,把整个数组进行了重新排序,当后一个数组元素和前一个数组元素一样时,我们跳过后一个数组元素,后面就是之前的回溯方法。
解答:
/*** 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 compare(const void* a,const void* b)
{return (*(int*)a - *(int*)b);
}
void travelback(int* candidates,int candidatesSize,int target,int* returnSize,int** returnColumnSizes,int*** result,int combinsize,int* num,int start,int sum)
{if(sum == target){(*returnSize)++;*result = realloc(*result,(*returnSize)*sizeof(int*));(*result)[(*returnSize)-1] = malloc(sizeof(int)*combinsize);for(int i = 0;i < combinsize;i++){(*result)[(*returnSize)-1][i] = num[i];}*returnColumnSizes = realloc(*returnColumnSizes,(*returnSize)*sizeof(int));(*returnColumnSizes)[(*returnSize)-1] = combinsize;return;}if(sum > target){return;}for(int i = start;i < candidatesSize;i++){if(i > start && candidates[i] == candidates[i-1]){continue;}sum += candidates[i];num[combinsize] = candidates[i];travelback(candidates,candidatesSize,target,returnSize,returnColumnSizes,result,combinsize+1,num,i+1,sum);sum -= candidates[i];}
}
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int sum = 0;int start = 0;int combinsize = 0;*returnColumnSizes = NULL;int** result = NULL;int* num = malloc(sizeof(int)*target);qsort(candidates,candidatesSize,sizeof(int),compare);travelback(candidates,candidatesSize,target,returnSize,returnColumnSizes,&result,combinsize,num,start,sum);return result;
}
131.分割回文串
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是回文串。返回 s
所有可能的分割方案。
示例 1:
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a"
输出:[["a"]]
提示:
1 <= s.length <= 16
s
仅由小写英文字母组成
思路:
跟之前的题目一样,只不过我们在判断条件中需要加上一条判断这个字符串数组是否为回文串,如果是,我们就把字符串加进去,如果不是我们继续向下寻找。但是第一次使用跟之前相似的方法时,最终判了超出内存限制。第二种方法则是运用动态规划和创建一个大数组来减少对realloc的使用,同时清理相应的数组来减少内存的使用,最终内存不在超出限制,但是太复杂了,我也不知道怎么做的了。
解答:
第一种方法(超出内存限制)
/*** 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().*/
bool isnot(char* s,int start,int end)
{for(int i = start,j = end;i < j;i++,j--){if(s[i] != s[j]){return false;}}return true;
}
void travelback(char* s,int* returnSize,int** returnColumnSizes,char**** result,int start,char** num,int combinesize)
{if(start == strlen(s)){(*returnSize)++;*result = realloc(*result,sizeof(char**)*(*returnSize));(*result)[(*returnSize)-1] = malloc(sizeof(char*)*(combinesize));for(int i = 0;i < combinesize;i++){(*result)[(*returnSize)-1][i] = strdup(num[i]);}*returnColumnSizes = realloc(*returnColumnSizes,sizeof(int)*(*returnSize));(*returnColumnSizes)[(*returnSize)-1] = combinesize;return;}for(int i = start;i < strlen(s);i++){if(isnot(s,start,i)){num[combinesize] = strndup(s+start,i-start+1);travelback(s,returnSize,returnColumnSizes,result,i+1,num,combinesize+1);}}
}
char*** partition(char* s, int* returnSize, int** returnColumnSizes) {*returnSize = 0;*returnColumnSizes = NULL;char*** result = NULL;int start = 0;char** num = malloc(sizeof(char*)*strlen(s));int combinesize = 0;travelback(s,returnSize,returnColumnSizes,&result,start,num,combinesize);return result;
}
第二种方法(gpt)
/*** 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 backtrack(char* s, int len, int start, int* returnSize, int** returnColumnSizes, char**** result, char** path, int pathSize, bool** isPalindrome, int* resultCapacity) {if (start == len) {if (*returnSize >= *resultCapacity) {*resultCapacity *= 2;*result = realloc(*result, sizeof(char**) * (*resultCapacity));*returnColumnSizes = realloc(*returnColumnSizes, sizeof(int) * (*resultCapacity));}(*result)[*returnSize] = malloc(sizeof(char*) * pathSize);for (int i = 0; i < pathSize; i++) {(*result)[*returnSize][i] = strdup(path[i]);}(*returnColumnSizes)[*returnSize] = pathSize;(*returnSize)++;return;}for (int end = start; end < len; end++) {if (isPalindrome[start][end]) {path[pathSize] = strndup(s + start, end - start + 1);backtrack(s, len, end + 1, returnSize, returnColumnSizes, result, path, pathSize + 1, isPalindrome, resultCapacity);free(path[pathSize]);}}
}
char*** partition(char* s, int* returnSize, int** returnColumnSizes) {*returnSize = 0;*returnColumnSizes = NULL;int len = strlen(s);int resultCapacity = 128;char*** result = malloc(sizeof(char**) * resultCapacity);*returnColumnSizes = malloc(sizeof(int) * resultCapacity);bool** isPalindrome = malloc(len * sizeof(bool*));for (int i = 0; i < len; i++) {isPalindrome[i] = malloc(len * sizeof(bool));memset(isPalindrome[i], false, len * sizeof(bool));}for (int end = 0; end < len; end++) {for (int start = 0; start <= end; start++) {if (s[start] == s[end] && (end - start <= 2 || isPalindrome[start + 1][end - 1])) {isPalindrome[start][end] = true;}}}char** path = malloc(len * sizeof(char*));backtrack(s, len, 0, returnSize, returnColumnSizes, &result, path, 0, isPalindrome, &resultCapacity);for (int i = 0; i < len; i++) {free(isPalindrome[i]);}free(isPalindrome);free(path);return result;
}
反思
这个跟昨天的题相差不大,但是分割回文串最开始的思路还好,但是容易超出内存限制,下次做的时候就不用C语言了,用C++。