本文主要是介绍Day 27 39. 组合总和 40.组合总和II 131.分割回文串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
- 所有数字(包括 target)都是正整数。
- 解集不能包含重复的组合。
示例 1:
- 输入:candidates = [2,3,6,7], target = 7,
- 所求解集为: [ [7], [2,2,3] ]
示例 2:
- 输入:candidates = [2,3,5], target = 8,
- 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
首先考虑题目中提到的无限制重复选取,那么就一定要去除零的存在,否则将进入死循环;
题目给出1 <= candidates[i] <= 200,说明此处不用担心死循环的问题;
此处依然采取构建树形结构的回溯,可知此时树的深度是由target和sum的值来限定的:
和组合问题最大的区别是每一次取数都是从整个candidates数组取数,这样才保证了题目要求的无限制重复选取;
下面是回溯代码:
vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex){//sum记录路径总和以确定路径是否满足要求,startIndex防止结果出现重复的组合if(sum >= target){if(sum == target) res.push_back(path);return;}//终止条件不难理解,sum>=target即不再往下for(int i = startIndex; i < candidates.size(); i++){path.push_back(candidates[i]);sum += candidates[i];backtracking(candidates, target, sum, i);//注意这里不是i+1,因为要满足可取重复元素sum -= candidates[i];path.pop_back();}}
注意此处依然可以进行剪枝操作,如果得到的是一个排序数组,那只要for循环中的下一层的sum。即本层的sum + candidates[i]>target了,就可以直接退出for循环了;即
for(int i = startIndex; i < candidates.size() && sum + candiates[i] <= target; i++)
整体代码如下:
class Solution {
private:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex){//sum记录路径总和以确定路径是否满足要求,startIndex防止结果出现重复的组合if(sum >= target){if(sum == target) res.push_back(path);return;}//终止条件不难理解,sum>=target即不再往下for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++){path.push_back(candidates[i]);sum += candidates[i];backtracking(candidates, target, sum, i);sum -= candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {res.clear();path.clear();sort(candidates.begin(), candidates.end()); //剪枝操作要求有序数组backtracking(candidates, target, 0, 0);return res;}
};
组合总和Ⅱ
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明: 所有数字(包括目标数)都是正整数。解集不能包含重复的组合。
- 示例 1:
- 输入: candidates = [10,1,2,7,6,1,5], target = 8,
- 所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]
- 示例 2:
- 输入: candidates = [2,5,2,1,2], target = 5,
- 所求解集为:
[[1,2,2],[5]
]
和上道题的思路是极为类似的,这道题很明显是数组中可以含有数值相同的元素,但是组合中又不允许出现重复的组合,也就是剪枝需要剪掉所有可能出现重复元素的场景,因为此处去重操作是去除树层里的重复元素,而不是树枝里的重复元素,因为组合允许出现相同的数值;
显而易见,此时若想进行去重操作,原数组一定是一个排序好的数组;
此处举例说明为什么要进行数层剪枝:candidates = [1, 1, 2], target = 3;
所以我们可以使用一个和nums.size()等长的used数组来记录遍历情况,每次遍历之前先检索used数组即可知道此时是否应该进行剪枝操作;
vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, int targetSum, int sum, int startIndex, vector<bool> used){if(sum >= targetSum){//终止条件和上一样if(sum == targetSum) res.push_back(path);return;}for(int i = startIndex; i < nums.szie() && sum + nums[i] <= target; i++){//剪枝if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){//剪枝,如果是操作数层是继续下一层循环//此时used[i - 1] == true;则是操作树枝continue;}path.push_back(nums[i]);used[i] = true;sum += nums[i];backtracking(nums, targetSum, sum, i, used);sum -= nums[i];used[i] = false;path.pop_back();}}
不用used数组也可以实现,整体代码如下:
class Solution {
private:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, int targetSum, int sum, int startIndex/*, vector<bool>& used*/) {if (sum == targetSum) {res.push_back(path);return;}for (int i = startIndex; i < nums.size() && sum + nums[i] <= targetSum; i++) { // 剪枝// if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { // 剪枝,如果是操作数层是继续下一层循环// 把判空条件写在了执行语句后面,找了半个多小时才找到问题,警钟撅烂 // 此时used[i - 1] == true;则是操作树枝// continue;// }//可以不使用used数组的方式进行树层去重剪枝//此时要求i>startIndex说明至少已经操作过一个元素,不会漏掉组合的可能性,即保证了最左侧树枝可以取到,同时满足了i>0的判定数组下标非负判断if(i > startIndex && nums[i] == nums[i - 1]){continue;}path.push_back(nums[i]);// used[i] = true;sum += nums[i];backtracking(nums, targetSum, sum, i + 1/*, used*/);sum -= nums[i];// used[i] = false;path.pop_back();}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {res.clear();path.clear();//vector<bool> used(candidates.size(), false);sort(candidates.begin(), candidates.end()); // 排序backtracking(candidates, target, 0, 0);return res;}
};
分割回文串
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]
回文串是一个局部的字符串片段,它在正向和反向读来都保持一致;
组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个;
切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段;
所以切割问题可以抽象为和组合问题一样的解决方法;
for循环横向遍历,纵向递归当切割线到字符串最后一位的时候即得到一组切割方法;
vector<string> path;vector<vector<string>> res;//回溯函数的参数void backtracking(const string& s, int startIndex){if(startIndex == s.size()){//终止条件,判断回文是否放进单层递归逻辑里res.push_back(path);return;}for(int i = startIndex; i < s.size(); i++){if(isPalindrome2(s, startIndex, i)){//判断是否回文string temp = s.substr(startIndex, i - startIndex + 1);//左闭右闭path.push_back(temp);}//如果不是回文子串则放弃对此字串的搜索else continue;backtracking(s, i + 1);path.pop_back();}}bool isPalindrome1(const string& s, int begin, int end){//首尾遍历判断是否为回文串while(s[begin] == s[end] && begin <= end){begin++;end--;}if(begin >= end) return true;else return false;}bool isPalindrome2(const string& s, int begin, int end){for(int i = begin, j = end; i < j; i++, j--){if(s[i] != s[j]) return false;}return true;}
整体代码如下:
class Solution {
private:vector<string> path;vector<vector<string>> res;//回溯函数的参数void backtracking(const string& s, int startIndex){if(startIndex == s.size()){//终止条件,判断回文是否放进单层递归逻辑里res.push_back(path);return;}for(int i = startIndex; i < s.size(); i++){if(isPalindrome2(s, startIndex, i)){//判断是否回文string temp = s.substr(startIndex, i - startIndex + 1);//左闭右闭path.push_back(temp);}//如果不是回文子串则放弃对此字串的搜索else continue;backtracking(s, i + 1);path.pop_back();}}bool isPalindrome1(const string& s, int begin, int end){//首尾遍历判断是否为回文串while(s[begin] == s[end] && begin <= end){begin++;end--;}if(begin >= end) return true;else return false;}bool isPalindrome2(const string& s, int begin, int end){for(int i = begin, j = end; i < j; i++, j--){if(s[i] != s[j]) return false;}return true;}
public:vector<vector<string>> partition(string s) {path.clear();res.clear();backtracking(s,0);return res;}
};
这篇关于Day 27 39. 组合总和 40.组合总和II 131.分割回文串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!