忆唐网不做网站做品牌,邯郸快讯网络科技有限公司,施工企业准入,电商网站架构代码随想录算法训练营第二十七天#xff08;二十六填休息#xff09; | 39. 组合总和、40、组合总和 II、131. 分割回文串 39. 组合总和题目解法 40、组合总和 II题目解法 131. 分割回文串题目解法substr()用法 感悟 39. 组合总和
题目 解法
初始解法#xff1a;出现重复组… 代码随想录算法训练营第二十七天二十六填休息 | 39. 组合总和、40、组合总和 II、131. 分割回文串 39. 组合总和题目解法 40、组合总和 II题目解法 131. 分割回文串题目解法substr()用法 感悟 39. 组合总和
题目 解法
初始解法出现重复组合每一次递归从头开始了
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum) {if(sum target) {result.push_back(path);return ;}if (sum target) return;for (int i 0; i candidates.size(); i) {sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum);path.pop_back();sum - candidates[i];}return ;}vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();int sum 0;backtracking(candidates, target, sum);return result;}
};2.看完题解之后加上startIdx之后,使用重复元素只使用一次
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIdx) {if(sum target) {result.push_back(path);return ;}if (sum target) return;// sum candidates[i] target 会终止遍历 所以candidates 需要排序 for (int i startIdx; i candidates.size() sum candidates[i] target; i) { // 剪枝优化sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i);path.pop_back();sum - candidates[i];}return ;}vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0);return result;}
};40、组合总和 II
题目 解法
初始想法题解 对于重复元素自取一次的逻辑只取同一树枝上的
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIdx) {if(sum target) {result.push_back(path);return ;}if (sum target) return;// sum candidates[i] target 会终止遍历 所以candidates 需要排序 for (int i startIdx; i candidates.size() sum candidates[i] target; i) { // 剪枝优化if(i startIdx candidates[i] candidates[i-1]) continue ; // 去重 同一树层去重sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i 1);path.pop_back();sum - candidates[i];}return ;}vectorvectorint combinationSum2(vectorint candidates, int target) {result.clear();path.clear();sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0);return result;}
};2.使用数组储存是否已经使用过同一树层的元素
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIdx, vectorbool used) {if(sum target) {result.push_back(path);return ;}if (sum target) return;// sum candidates[i] target 会终止遍历 所以candidates 需要排序 for (int i startIdx; 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;path.pop_back();sum - candidates[i];}return ;}vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);result.clear();path.clear();sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};131. 分割回文串
题目 解法
看完题解之后
class Solution {
private:vectorvectorstring result;vectorstring path;void backtracking(string s, int startIdx) {if (startIdx s.size()) {result.push_back(path);return ;}for (int i startIdx; i s.size(); i) {if(isHuiWen(s, startIdx, i)) {string str s.substr(startIdx, i - startIdx 1);path.push_back(str);}else {continue;}backtracking(s, i 1);path.pop_back();}return ;}bool isHuiWen(string s, int start, int end) {for(int i start, j end; i j; i, j--) {if(s[i] ! s[j]) return false;}return true;}
public:vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};substr()用法
在C中substr() 是一个常用于 std::string 类的成员函数用于获取字符串的子串。这个函数的基本语法如下
std::string substr(size_t pos 0, size_t count npos) const;pos这是子串开始的位置基于0的索引。如果 pos 大于字符串的长度则 substr() 函数会抛出一个 std::out_of_range 异常。
count这是要提取的字符数。如果 count 是 std::string::npos 或大于从 pos 到字符串末尾的字符数则子串将包括从 pos 开始到字符串末尾的所有字符。以下是一些使用 substr() 函数的示例
#include iostream
#include string int main() { std::string str Hello, World!; // 从位置0开始提取5个字符 std::string substr1 str.substr(0, 5); // Hello std::cout substr1 std::endl; // 从位置7开始提取到字符串结束 std::string substr2 str.substr(7); // World! std::cout substr2 std::endl; // 从位置7开始提取4个字符 std::string substr3 str.substr(7, 4); // Worl std::cout substr3 std::endl; return 0;
}注意如果提供的 pos 超出了字符串的范围substr() 函数会抛出一个 std::out_of_range 异常。因此在使用 substr() 函数时最好确保 pos 的值在有效范围内。此外还要注意的是substr() 函数返回的是一个新的字符串它包含原字符串中指定位置的子串。原字符串本身不会被修改。感悟
关键细节要理解清楚比如startIdx的使用
