leetcode_day26

本文最后更新于 2024年8月18日下午

今日任务：

39. 组合总和

题目：

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路：

递归挨个选取就行，选了一个之后递归下一个，起点不变，如果和到了target就加入答案，可以在下一步递归前判断当前值是否已经过大了，过大则跳过实现剪枝。比较简单

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    void backtrack(vector<int> &candidate, int target, int begin) {
        if(target == 0) {
            ans.push_back(temp);
            return;
        }
        for(int i = begin;i < candidate.size();i++) {
            if(candidate[i] > target) continue;
            temp.push_back(candidate[i]);
            backtrack(candidate, target - candidate[i], i);
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if(candidates.size() == 0) return {};
        backtrack(candidates, target, 0);

        return ans;
    }
};

40. 组合总和Ⅱ

题目：

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

提示:

1 <= candidates.length <= 100

1 <= candidates[i] <= 50

1 <= target <= 30

思路：

难点主要在于去重，下面举个例子来快速直观体会这道题要去什么重

对于示例：[10,1,1,7,6,1,5]、target = 8，正确结果应该是[[1,1,1,5],[1,1,6],[1,7]]。题目中candidate中的每个数字只能用一次是关键，勿错误理解为每种数字只能用一次，示例[10,1,1,7,6,1,5]中有3个1，当选中第一个1作为解成员之一递归下去的时候，由于之前无1，所以已有的解中肯定无1，后面的两个1仍然可用，由答案可见，选中第一个1递归下去已经可以得到全部解了。

那么选中第二个1作为解成员之一递归下去后，后面还有一个1，此时含有两个1的解已经出现过了，此时需要去重。

由上可看出不能简单使用used来阻止使用使用过的下标，因为第一个1把所有解得到后，回溯取消操作会开放used，后面的1又会变得可用，去重失败

carl哥的代码思路按我理解可以叙述为：重复元素只能由排前面的重复元素使用，对于上面的示例，就是含有多个1的解只能由第一个1的递归分支得到，后面的如果还是1就不能在解里出现1。

排前面的重复即对应carl哥说法的前一个树枝，即前一个重复元素的解空间树分支。

又瞟了题解才做出来，WA了4发😭😭😭

脑子抽了没看见1 <= candidates.length <= 100，还乐呵呵地用位运算当used[]用来记录哪些下标被用了，左移右移老半天跟二傻子似的，结果不仅位运算爆long long，而且用used记录本身就是脱裤子放屁，因为我回溯传了起点begin……

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    void backtrack(vector<int> &candidate, int target, int begin) {
        if(target == 0) {
            ans.push_back(temp);
            return;
        }
        for(int i = begin;i < candidate.size();i++) {
            if(candidate[i] > target) continue;
            if(i > begin && candidate[i] == candidate[i - 1]) continue;//去重关键
            temp.push_back(candidate[i]);
            backtrack(candidate, target - candidate[i], i + 1);
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if(candidates.size() == 0) return {};
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0);
        return ans;
    }
};

131. 分割回文串

题目：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

思路：

没做出来，贴出失败思路：

分割子串，想到之前做的有关题目了，至少分割操作还是比较熟悉，用迭代器构造新串就好，从首开始分割，分割长度逐渐递增，也就是回溯中的那个for循环，每个分割长度在分割前判断是否是回文串，如果是回文串就分割，不是就接着增大分割长度。

然后就卡了……没记住或者说想另辟蹊径结果弄巧成拙，没有像模板那样接着回溯下一种可能并取消当前轮次操作继续for循环。

接下来是正确思路：

仍然按照回溯模板，理清递归思路： 1. 递归参数与返回值：返回值void，参数应该是分割起点，确保能够递归下去接着分割之后的子串 2. 递归终止条件，如果真的分割到结尾，那么该条递归调用路线就是正确的，此时temp中即为一个答案，标准就是起点超过了终点，begin大于了string的长度 3. 递归操作：逐个尝试分割长度，合法就接着分割，不合法就跳过

carl哥这次画的解空间树很形象，如下图，失败思路想到了怎么分支，但是没想到怎么判断叶节点，具体的代码写法也写昏了头

代码

一般代码

之所以叫一般，是因为判断回文串的函数isValid每次调用都要俩指针相向而行，有很多重复操作，提高了时间复杂度

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> temp;
    bool isValid(string s, int begin, int end) {
        int left = begin, right = end;
        if(right > s.size()) return false;
        while(left <= right) {
            if(s[left++] != s[right--]) return false;
        }
        return true;
    }

    void backtrack(string &s, int begin) {
        if(begin >= s.size()) {
            ans.push_back(temp);
            return ;
        }
        for(int i = begin;i < s.size();i++) {
            if(isValid(s, begin, i)) {
                temp.push_back(string(s.begin() + begin, s.begin() + i + 1));
                backtrack(s, i + 1);
                temp.pop_back();
            }
            else continue;
            
        }
    }
    vector<vector<string>> partition(string s) {
        backtrack(s, 0);
        return ans;
    }
};

动态规划代码

使用动态规划（dynamic programming， DP）直接把所有子串是否是回文串都提前算好，这样后续判断时就只需要O(1)复杂度就可以了

动态规划状态转移方程为：

           ⌜1, i = j 

dp[i][j] = +s[i]==s[j], i = j - 1

           ㇗s[i]==s[j]ANDdp[i+1][j-1],else

~~不会打latex，好拉的公式，快去配置渲染器！！~~

(更新：现在会打公式了，留着当耻辱柱😁，提升观感，公式如下) \[ dp[i][j]\ = \begin{cases} 1,& \text{$i=j$} \\ s[i]==s[j],& \text{$i=j-1$} \\ s[i] == s[j]\ \and\ dp[i+1][j-1],& \text{$else$} \end{cases} \]

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> temp;
    vector<vector<bool>> dp;

    void backtrack(string &s, int begin) {
        if(begin >= s.size()) {
            ans.push_back(temp);
            return ;
        }
        for(int i = begin;i < s.size();i++) {
            if(dp[begin][i]) {
                temp.push_back(string(s.begin() + begin, s.begin() + i + 1));
                backtrack(s, i + 1);
                temp.pop_back();
            }
            else continue;
            
        }
    }
    void isValid(string &s) {
        dp.resize(s.size(), vector<bool>(s.size(), false));//vector还得resize了才能用
        for(int i = s.size() - 1;i >= 0;i--) {
            for(int j = i;j < s.size();j++) {
                if(i + 1 == j) dp[i][j] = s[i] == s[j];
                else if(i == j) dp[i][j] = true;
                else dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
            }
        }
    }
    vector<vector<string>> partition(string s) {
        isValid(s);
        backtrack(s, 0);
        return ans;
    }
};

#leetcode

leetcode_day26

https://novelyear.github.io/2024/06/17/leetcode-day26/

作者

Leoo Yann

更新于

2024年8月18日

许可协议

leetcode_day27 上一篇

leetcode_day24 下一篇