day27 组合总和 组合总和Ⅱ 分割回文串

这篇具有很好参考价值的文章主要介绍了day27 组合总和 组合总和Ⅱ 分割回文串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目1:39 组合总和

题目链接:39 组合总和

题意

找出无重复元素的正整数数组candidates中元素和为目标数target的所有不同组合,同一个数字可重复选取

回溯

回溯三部曲:

1)参数和返回值

2)终止条件

3)单层搜索逻辑

day27 组合总和 组合总和Ⅱ 分割回文串,算法,leetcode,动态规划

代码文章来源地址https://www.toymoban.com/news/detail-818148.html

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates,int targetsum,int sum,int startIndex){
        if(sum>targetsum) return;
        //终止条件
        if(sum==targetsum){
            result.push_back(path);
            return;
        }
        //单层递归逻辑
        for(int i=startIndex;i<candidates.size();i++){
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,targetsum,sum,i);//递归
            sum -= candidates[i];//回溯
            path.pop_back();//回溯
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,target,0,0);
        return result;
    }
};
剪枝

给数组递增排序,排序后,如果组合中的一个分支使得和(sum+candidates[i])大于targetsum,那么该分支及其后面的分支没有必要存在了,因为和肯定都大于target了

day27 组合总和 组合总和Ⅱ 分割回文串,算法,leetcode,动态规划

代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates,int targetsum,int sum,int startIndex){
        //终止条件
        if(sum==targetsum){
            result.push_back(path);
            return;
        }
        //单层递归逻辑
        //注意限制条件是<= 一定要包含等于,因为还要将candidates[i]放入path数组中
        for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=targetsum;i++){
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,targetsum,sum,i);//递归
            sum -= candidates[i];//回溯
            path.pop_back();//回溯
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //排序
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,0);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n),复杂度的上界,剪枝使得真实的时间复杂度小于该值
  • 空间复杂度: O(target)

题目2:组合总和Ⅱ

题目链接:40 组合总和Ⅱ

题意

找出正整数数组candidates中使得元素和为target的组合,组合不能重复,数组中每个元素只能使用1次,但是candidates中可能存在重复的元素 例如 [2,2,2] target=4 只有1个组合满足[2 2]要求

回溯

回溯三部曲:

1)参数和返回值

2)终止条件

3)单层递归逻辑

本题主要是包含去重的操作  将数组按照增序排列,将相同的元素放在紧邻的位置

day27 组合总和 组合总和Ⅱ 分割回文串,算法,leetcode,动态规划

代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates,int targetsum,int sum,int startIndex,vector<bool>& used){
        //终止条件
        if(sum>targetsum) return;
        if(sum==targetsum){
            result.push_back(path);
            return;
        }
        //单层递归逻辑
        for(int i=startIndex;i<candidates.size();i++){
            //树层去重
            if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==0) continue;
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates,targetsum,sum,i+1,used);//递归
            sum -= candidates[i];//回溯
            path.pop_back();//回溯
            used[i] = false;//回溯
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        //对数组进行排序,使得数组中数值相等的元素可以相邻在一起,这样方便去重
        sort(candidates.begin(),candidates.end());
        vector<bool> used(candidates.size(),false); 
        backtracking(candidates,target,0,0,used);
        return result;
    }
};
剪枝
class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates,int targetsum,int sum,int startIndex,vector<bool>& used){
        //终止条件
        if(sum==targetsum){
            result.push_back(path);
            return;
        }
        //单层递归逻辑
        for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=targetsum;i++){
            //树层去重
            if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==0) continue;
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates,targetsum,sum,i+1,used);//递归
            sum -= candidates[i];//回溯
            path.pop_back();//回溯
            used[i] = false;//回溯
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        //对数组进行排序,使得数组中数值相等的元素可以相邻在一起,这样方便去重
        sort(candidates.begin(),candidates.end());
        vector<bool> used(candidates.size(),false); 
        backtracking(candidates,target,0,0,used);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

题目3:131 分割回文串

题目链接:131 分割回文串

题意

将字符串s(仅由小写字母组成)分割成若干回文子串  回文串是正读和反读相同的子串,返回分割方案

回溯

回溯三部曲:

1)参数和返回值

2)终止条件

3)单层搜索逻辑

day27 组合总和 组合总和Ⅱ 分割回文串,算法,leetcode,动态规划

代码

class Solution {
public:
    //判断字符串是否是回文串
    bool ispalidrom(const 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;
    }
    vector<string> path;//存放单个分割结果
    vector<vector<string>> result;//存放所有分割方案
    void backtracking(const string& s,int startIndex){
        //终止条件
        if(startIndex==s.size()){
            result.push_back(path);//path中只存放是回文串的子串
            return;
        }
        //单层搜索逻辑
        for(int i=startIndex;i<s.size();i++){
            if(ispalidrom(s,startIndex,i)){
                //截取[statrIndex,i]的子串
                string str  = s.substr(startIndex,i-startIndex+1);
                path.push_back(str);
            }
            else continue;
            backtracking(s,i+1);//递归
            path.pop_back();//回溯
        }
    }
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n^2)

到了这里,关于day27 组合总和 组合总和Ⅱ 分割回文串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法 DAY44 动态规划6 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。 动规五步曲来分

    2024年02月01日
    浏览(53)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

    2024年02月13日
    浏览(42)
  • leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    我的往期文章: leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501 leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001

    2024年02月05日
    浏览(56)
  • 【LeetCode题目详解】第九章 动态规划part06 完全背的讲解 518. 零钱兑换 II 377. 组合总和 Ⅳ (day44补)

    # 完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品都有无限个(也就是可以放入背包多次) ,求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。

    2024年02月09日
    浏览(38)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(50)
  • leetcode动态规划(零钱兑换II、组合总和 Ⅳ)

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面

    2024年02月01日
    浏览(43)
  • (C++/动态规划/深度讲解)LeetCode377. 组合总和 Ⅳ

    动态规划算法概述         动态规划算法是一个分治的方法,把重叠子问题从底层到顶层拆解后,基于已经求解的子问题来求解目标问题的算法,过程清晰明了,且具有记忆化功能,在某些问题中可以避免很多重复计算,效率高,故受到很多程序员的青睐。 为什么说动态

    2024年04月15日
    浏览(49)
  • Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ

    题目 文章讲解 视频讲解 完全背包和0-1背包的区别在于:物品是否可以重复使用 思路:对于完全背包问题,内层循环的遍历方式应该是从weight[i]开始一直遍历到V,而不是从V到weight[i]。这样可以确保每种物品可以被选择多次放入背包,从而求解完全背包问题。 对于完全背包问

    2024年02月20日
    浏览(44)
  • leetcode216. 组合总和 III(回溯算法-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/combination-sum-iii 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示例 1: 输

    2024年02月10日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包