最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

信息：【算法训练营day27】LeetCode39. 组合总和 LeetCode40. 组合总和II LeetCode131. 分割回文串

来源：博客园

LeetCode39. 组合总和

题目链接：39. 组合总和

独上高楼，望尽天涯

题目不难，注意start_index参数的使用。

class Solution {private:    vector> result;    vector path;    void backtracking(vector& candidates, int target, int start_index) {        if (target == 0) {            result.push_back(path);            return;        }        else if (target < 0) {            return;        }        for (int i = start_index; i < candidates.size(); i++) {            target -= candidates[i];            path.push_back(candidates[i]);            backtracking(candidates, target, i); //不用i+1，因为可以无限重复选取            target += candidates[i];            path.pop_back();        }    }public:    vector> combinationSum(vector& candidates, int target) {        backtracking(candidates, target, 0);        return result;    }};

慕然回首，灯火阑珊

和题解想的一样。


(相关资料图)

剪枝操作

在求和问题中，排序之后加剪枝是常见的套路。

class Solution {private:    vector> result;    vector path;    void backtracking(vector& candidates, int target, int start_index) {        if (target == 0) {            result.push_back(path);            return;        }        for (int i = start_index; i < candidates.size() && target - candidates[i] >= 0; i++) { // 剪枝操作            target -= candidates[i];            path.push_back(candidates[i]);            backtracking(candidates, target, i);            target += candidates[i];            path.pop_back();        }    }public:    vector> combinationSum(vector& candidates, int target) {        sort(candidates.begin(), candidates.end()); // 需要排序        backtracking(candidates, target, 0);        return result;    }};

LeetCode40. 组合总和II

题目链接：40. 组合总和II

独上高楼，望尽天涯

本题的难点在于去重，建议回溯问题以后都要在纸上画出清晰的递归树形结构，会对解题有很大帮助！

慕然回首，灯火阑珊

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

强调一下，树层去重的话，需要对数组排序！

class Solution {private:    vector> result;    vector path;    void backtracking(vector& candidates, int target, int start_index) {        if (target == 0) {            result.push_back(path);            return;        }        for (int i = start_index; i < candidates.size() && target - candidates[i] >= 0; i++) {            if (i > start_index && candidates[i] == candidates[i-1]) { //去重操作                continue;            }            target -= candidates[i];            path.push_back(candidates[i]);            backtracking(candidates, target, i+1);            target += candidates[i];            path.pop_back();        }    }public:    vector> combinationSum2(vector& candidates, int target) {        sort(candidates.begin(), candidates.end()); //去重需要排序        backtracking(candidates, target, 0);        return result;    }};

LeetCode131. 分割回文串

题目链接：131. 分割回文串

独上高楼，望尽天涯

很有难度的一道题，需要分别处理切割和判断是否是回文串两个问题。

慕然回首，灯火阑珊

切割问题类似组合问题。

class Solution {private:    vector> result;    vector path;    bool isPalindrome(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;    }    void backtracking(string s, int start_index) {        // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了        if (start_index >= s.size()) {            result.push_back(path);            return;        }        // for循环横向遍历，寻找所有以start_index为首的回文子串        for (int i = start_index; i < s.size(); i++) {            if (isPalindrome(s, start_index, i)) {                string str = s.substr(start_index, i - start_index + 1);                path.push_back(str);                backtracking(s, i + 1);                path.pop_back();            }        }    }public:    vector> partition(string s) {        backtracking(s, 0);        return result;    }};

关键词： 灯火阑珊 独上高楼 树形结构