首页 > 编程语言 >leetcode刷题day23|回溯算法Part02(39. 组合总和 、40.组合总和II、131.分割回文串)

leetcode刷题day23|回溯算法Part02(39. 组合总和 、40.组合总和II、131.分割回文串)

时间:2024-09-20 20:48:51浏览次数:12  
标签:39 target 组合 int startIndex candidates new path 总和

39. 组合总和

思路:这个题与77. 组合的差异在于元素可以无限制重复被选取,那么只需要更改startIndex即可,每一层递归都可以从头选用元素。

回溯三部曲与77. 组合基本一致。

代码如下:

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracking(candidates,target,0);
        return result;
    }
    public void backTracking(int[] candidates, int target, int startIndex){
        if(target==0){
            result.add(new ArrayList(path));
            return;
        }else if(target<0){
            return;
        }
        for(int i=startIndex;i<candidates.length;i++){
            path.add(candidates[i]);
            backTracking(candidates,target-candidates[i],i);
            path.removeLast();
        }
    }
}

注意:如果是一个集合来求组合的话,需要startIndex,例如:77.组合,216.组合总和III;如果是多个集合取组合,各个集合之间相互不影响,不用startIndex。我一开始没用startIndex,导致递归过程(同一树枝上)中重复扫描前面的元素,结果出现了重复的组合。

40.组合总和II

思路:这个题跟39. 组合总和的区别在于给定数组中有重复元素,但要求最终的结果集合里面不能有重复数组。把回溯理解为树的结构,元素在同一树枝上是可以重复的,但在同一层上不能重复。要实现同一层上不重复出现需要对数组排序,当当前元素与上一次遍历的元素相同时跳过。

题目要求candidates 中的每个数字在每个组合中只能使用 一次 ,所以也要使用startIndex进行约束,每次递归函数调用i要加1。

代码如下:

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates,target,0);
        return result;
    }
    public void backTracking(int[] candidates,int target,int startIndex){
        if(target==0){
            result.add(new ArrayList(path));
            return;
        }else if(target<0){
            return;
        }
        for(int i=startIndex;i<candidates.length;i++){
            if(i>startIndex && candidates[i]==candidates[i-1]) continue;
            path.add(candidates[i]);
            backTracking(candidates,target-candidates[i],i+1);
            path.removeLast();
        }
    }
}

131.分割回文串

切割问题类似组合问题,例如对于字符串abcdef:

组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…。
切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…。

回溯三部曲:
1、递归函数参数:全局变量:数组path存放切割后回文的子串,二维数组result存放结果集。 递归函数参数:原字符串;startIndex,因为切割过的地方不能重复切割,和组合问题是一样的;新的StringBuilder字符串,存放切割后的字符子串,如果字符串是回文子串,将其加入path,递归进行下一次切割。
2、终止条件:切割线切到了字符串最后面,说明找到了一种切割方法,此时就是本层递归的终止条件。切割线即startIndex的位置。
3、单层搜索的逻辑:在for (int i = startIndex; i < s.size(); i++)循环中,我们 定义了起始位置startIndex,那么 [startIndex, i] 就是要截取的子串。首先判断这个子串是不是回文,如果是回文,就加入path中,path用来记录切割过的回文子串。

还有一个问题是如何判断回文子串:可以使用双指针法,一个指针从前向后,一个指针从后向前,如果前后指针所指向的元素是相等的,就是回文字符串了。

代码如下:

class Solution {
    List<List<String>> result=new ArrayList<>();
    List<String> path=new LinkedList<>();
    public List<List<String>> partition(String s) {
        backTracking(s,0,new StringBuilder());
        return result;
    }
    public void backTracking(String s,int startIndex,StringBuilder sb){
        if(startIndex==s.length()){
            result.add(new ArrayList(path));
            return;
        }
        for(int i=startIndex;i<s.length();i++){
            sb.append(s.charAt(i));
            if(check(sb)){
                path.add(sb.toString());
                backTracking(s,i+1,new StringBuilder());
                path.removeLast();
            }
        }
        
    }
    public boolean check(StringBuilder sb){
        for(int i=0;i<sb.length()/2;i++){
            if(sb.charAt(i)!=sb.charAt(sb.length()-1-i)) return false;
        }
        return true;
    }
}

这个题相对困难,要理解清楚怎么切割,怎么回溯,怎么存放。

标签:39,target,组合,int,startIndex,candidates,new,path,总和
From: https://blog.csdn.net/m0_51007517/article/details/142356143

相关文章

  • 解决jupyter删除文件时出现:send2trash failed: [Errno 13] Permission denied: b'/dat
    参考资料:https://github.com/jupyter-server/jupyter_server/issues/1338今天在使用自己部署的jupyterlab删除文件的时候出现了一个奇怪的报错:send2trashfailed:[Errno13]Permissiondenied:b'/data/.Trash-1383490'好家伙,删东西都不让我删。虽然如此,问题......
  • js数组合并与对象合并的方法汇总
    ......
  • COSC2391 Further Programming
    COSC2391 FurtherProgramming/COSC1295AdvancedProgrammingAssignment2- Semester 2 20241.IntroductionThisassignmentisdesignedto:•   Evaluateyourabilitytodevelop GUI applications usingJavaFX.•   Evaluateyourskillsin stori......
  • 代码随想录算法训练营第十六天 | Javascript | 力扣Leetcode | 回溯 | 77. 组合、216.
    目录前言简介题目链接:77.组合题目链接:216.组合总和3题目链接:17.电话号码的字母组合前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,算法基础只有力扣几十道题,非常薄......
  • Liunx安装mysql8.0.39版本以及如何远程连接Navicat保姆级教学
    前言:对于MySQL数据库的安装,我们将要使用安装方式rpm进行安装通过百度网盘分享的文件:mysql-8.0.39-1.el7.x86_64.rpm-bundl...链接:https://pan.baidu.com/s/1uAOqAeH03eU7t8T1_ekXXA?pwd=obce 提取码:obce其他版本链接:MySQL::DownloadMySQLCommunityServer1:检测当前......
  • 如何解决"Warning: include(): Failed opening 'file_path' for inclusion"问题
    解决方法检查文件路径确认文件路径是否正确无误,包括路径中的每个目录和文件名。验证文件是否存在使用file_exists()函数检查文件是否真的存在于指定路径上。检查文件权限确认文件具有足够的权限供当前用户读取。可以使用chmod命令修改文件权限:bash chmod......
  • 如何解决"Unknown column 'column_name' in 'field list'"问题
    当遇到"Unknowncolumn'column_name'in'fieldlist'"这类错误时,通常表明SQL查询中引用了一个不存在的列。这类错误通常会给出具体的列名和出错的位置。下面是一些详细的解决步骤:解决方法:检查SQL查询:确认SQL查询中引用的列名是否正确。检查拼写错误或大小写问题。......
  • 如何解决"Can't connect to MySQL server on 'hostname' (10061)"问题
    当遇到"Can'tconnecttoMySQLserveron'hostname'(10061)"这类错误时,通常意味着应用程序无法连接到MySQL数据库服务器。错误代码10061通常表示连接拒绝,可能是因为服务器没有响应或者不允许来自该客户端的连接。以下是解决此类问题的一些步骤:解决方法:检查数据库服务......
  • 进入不了帝国cms后台,提示Cann't connect to DB!
    当您尝试登录帝国CMS后台时遇到“Cann'tconnecttoDB!”的提示,这通常表示帝国CMS无法连接到数据库。这个问题可能由多个原因造成,下面是一些排查和解决的步骤:排查步骤:检查数据库配置:确认数据库配置文件/e/class/config.php中的数据库连接信息是否正确。主要包括数据库服务......
  • 深入解析Vue 3组合函数:提高代码复用性和模块化的最佳实践
    随着Vue3的引入,组合式API(CompositionAPI)带来了更灵活的代码组织方式,组合函数作为其核心部分,能够显著提升代码的可维护性、复用性和模块化。在这篇文章中,我们将通过一个具体的表格管理和分页功能的示例,详细介绍如何使用组合函数来构建更加高效和清晰的Vue3应用。1.组合函数......