代码随想录Day27
39. 组合总和
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
// 终止条件
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
// 回溯函数
for (int i = startIndex; i < candidates.size(); i) {
sum = candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i);
// 回溯
sum -= candidates[i];
path.pop_back();
}
}
// 剪枝版本
void backtracking1(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum candidates[i] <= target; i) {
sum = candidates[i];
path.push_back(candidates[i]);
backtracking1(candidates, target, sum, i);
// 回溯
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
sort(candidates.begin(), candidates.end()); // 需要排序
backtracking1(candidates, target, 0, 0);
return result;
}
};
40.组合总和II
class Solution {
public:
// 时间复杂度: O(n * 2^n)
// 空间复杂度: O(n)
// 用used数组版本
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum candidates[i] <= target; i) {
// used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false,说明同一树层candidates[i - 1]使用过
// 要对同一树层使用过的元素进行跳过
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
continue;
}
sum = candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i 1, used);
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
result.clear();
path.clear();
vector<bool> used(candidates.size(), false);
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
};
// 不用used的版本,不太好理解
class Solution1 {
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum candidates[i] <= target; i ) {
// 要对同一树层使用过的元素进行跳过
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
sum = candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i 1); // 和39.组合总和的区别1,这里是i 1,每个数字在每个组合中只能使用一次
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
path.clear();
result.clear();
// 首先把给candidates排序,让其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0);
return result;
}
};
131.分割回文串
力扣题目链接 其实切割问题类似组合问题。
例如对于字符串abcdef:
- 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个.....。
- 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段.....。
class Solution {
public:
// 时间复杂度: O(n * 2^n)
// 空间复杂度: O(n^2)
vector<vector<string>> result;
vector<string> path;
bool isPalindrome1(const string& s, int start, int end) {
for (int i = start, j = end; j > i; i, --j) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
// 动态规划思想优化
vector<vector<bool>> isPalindrome;
void computePalindrome(const string& s) {
// isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串
isPalindrome.resize(s.size(), vector<bool>(s.size(), false));
for (int i = s.size() - 1; i >= 0; i--) {
// 需要倒序计算, 保证在i行时, i 1行已经计算好了
for (int j = i; j < s.size(); j ) {
if (j == i) {isPalindrome[i][j] = true;}
else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);}
else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i 1][j-1]);}
}
}
}
void backtracking(const string& s, int startIndex) {
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i ) {
// if (isPalindrome(s, startIndex, i))
if (isPalindrome[startIndex][i])
{
string tmp = s.substr(startIndex, i - startIndex 1);
path.push_back(tmp);
} else {
continue;
}
backtracking(s, i 1);
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgajehb
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22