代码随想录刷题day23丨39. 组合总和,40.组合总和II, 131.分割回文串

2024-09-05 19:28

本文主要是介绍代码随想录刷题day23丨39. 组合总和,40.组合总和II, 131.分割回文串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录刷题day23丨39. 组合总和,40.组合总和II, 131.分割回文串

1.题目

1.1组合总和

  • 题目链接:39. 组合总和 - 力扣(LeetCode)

    在这里插入图片描述

  • 视频讲解:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)| 回溯法精讲!_哔哩哔哩_bilibili

  • 文档讲解:https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html

  • 解题思路:回溯

    • 本题搜索的过程抽象成树形结构如下:

      在这里插入图片描述

    • 注意图中叶子节点的返回条件,因为本题没有组合数量要求,仅仅是总和的限制,所以递归没有层数的限制,只要选取的元素总和超过target,就返回!

    • 回溯三部曲

      • 递归函数参数

        List<Integer> path = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        void backtracking(int[] candidates,int target,int sum,int startIndex)
        
      • 递归终止条件

        if(sum > target){return;
        }
        if(sum == target){result.add(new ArrayList<>(path));return;
        }
        
      • 单层搜索的逻辑

        for(int i = startIndex;i < candidates.length;i++){path.add(candidates[i]);sum += candidates[i];backtracking(candidates,target,sum,i);sum -= candidates[i];path.remove(path.size() -1);
        }
        
  • 代码:

    class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates,target,0,0);return result;}void backtracking(int[] candidates,int target,int sum,int startIndex){if(sum > target){return;}if(sum == target){result.add(new ArrayList<>(path));return;}for(int i = startIndex;i < candidates.length;i++){path.add(candidates[i]);sum += candidates[i];backtracking(candidates,target,sum,i);sum -= candidates[i];path.remove(path.size() -1);}}
    }
    
    • 剪枝优化

      class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates); // 先进行排序backtracking(candidates,target,0,0);return result;}void backtracking(int[] candidates,int target,int sum,int startIndex){if(sum > target){return;}if(sum == target){result.add(new ArrayList<>(path));return;}for(int i = startIndex;i < candidates.length;i++){// 如果 sum + candidates[i] > target 就终止遍历if (sum + candidates[i] > target) break;path.add(candidates[i]);sum += candidates[i];backtracking(candidates,target,sum,i);sum -= candidates[i];path.remove(path.size() -1);}}
      }
      
  • 总结:

    • 在求和问题中,排序之后加剪枝是常见的套路!

1.2组合总和II

  • 题目链接:40. 组合总和 II - 力扣(LeetCode)

    在这里插入图片描述

  • 视频讲解:回溯算法中的去重,树层去重树枝去重,你弄清楚了没?| LeetCode:40.组合总和II_哔哩哔哩_bilibili

  • 文档讲解:https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html

  • 解题思路:回溯

    • 集合(数组candidates)有重复元素,但还不能有重复的组合

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

    • 强调一下,树层去重的话,需要对数组排序!

    • 选择过程树形结构如图所示:

      在这里插入图片描述

  • 代码:

    class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);  // 先排序backtracking(candidates, target, 0, 0);return result;}void backtracking(int[] candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {// 跳过相同的元素,避免产生重复组合if (i > startIndex && candidates[i] == candidates[i - 1]) {continue;}// 如果当前元素加上sum大于目标值,则不继续遍历if (sum + candidates[i] > target) {break;}path.add(candidates[i]);sum += candidates[i];backtracking(candidates, target, sum, i+1);sum -= candidates[i];path.remove(path.size() - 1);}}
    }
    
  • 总结:

    • 直接用startIndex来去重

1.3分割回文串

  • 题目链接:131. 分割回文串 - 力扣(LeetCode)

    在这里插入图片描述

  • 视频讲解:带你学透回溯算法-分割回文串(对应力扣题目:131.分割回文串)| 回溯法精讲!_哔哩哔哩_bilibili

  • 文档讲解:https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html

  • 解题思路:回溯

    • 本题涉及到两个关键问题:

      • 切割问题,有不同的切割方式
      • 判断回文
    • 回文串是向前和向后读都相同的字符串。

    • 我们来分析一下切割,其实切割问题类似组合问题

      • 例如对于字符串abcdef:
        • 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…。
        • 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…。
    • 所以切割问题,也可以抽象为一棵树形结构,如图:

      在这里插入图片描述

    • 递归用来纵向遍历,for循环用来横向遍历,切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。

    • 此时可以发现,切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

    • 回溯三部曲

      • 递归函数参数

        List<String> path = new ArrayList<>();
        List<List<String>> result = new ArrayList<>();
        void backtracking(String s,int startIndex)
        
      • 递归函数终止条件

        if(startIndex == s.length()){ // 递归终止条件:当索引遍历到字符串末尾时result.add(new ArrayList<>(path));// 将当前的分割路径 `path` 加入到 `result` 中return;
        }
        
      • 单层搜索的逻辑

        StringBuilder sb = new StringBuilder();
        for(int i = startIndex;i < s.length();i++){sb.append(s.charAt(i));// 将从 startIndex 开始的字符逐个加入 StringBuilderif(check(sb)){ // 如果当前的子串是回文串path.add(sb.toString());// 将该回文子串加入当前路径backtracking(s,i + 1);// 递归从下一个字符开始path.remove(path.size() -1);// 回溯,移除刚刚加入的回文子串}
        }
        
  • 代码:

    class Solution {List<String> path = new ArrayList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s,0);// 开始进行回溯,从索引0开始return result;// 返回最终的所有分割结果}void backtracking(String s,int startIndex){if(startIndex == s.length()){ // 递归终止条件:当索引遍历到字符串末尾时result.add(new ArrayList<>(path));// 将当前的分割路径 `path` 加入到 `result` 中return;}StringBuilder sb = new StringBuilder();for(int i = startIndex;i < s.length();i++){sb.append(s.charAt(i));// 将从 startIndex 开始的字符逐个加入 StringBuilderif(check(sb)){ // 如果当前的子串是回文串path.add(sb.toString());// 将该回文子串加入当前路径backtracking(s,i + 1);// 递归从下一个字符开始path.remove(path.size() -1);// 回溯,移除刚刚加入的回文子串}}}//检查是否是回文private 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;}
    }
    
  • 总结:

    • 切割线切到了字符串最后面,说明找到了一种切割方法,此时就是本层递归的终止条件。
    • 那么在代码里什么是切割线呢?
      • 在处理组合问题的时候,递归参数需要传入startIndex,表示下一轮递归遍历的起始位置,这个startIndex就是切割线。
    • 在递归循环中如何截取子串呢?
      • 在for循环中,我们 定义了起始位置startIndex,那么 [startIndex, i] 就是要截取的子串。
      • 首先判断这个子串是不是回文,如果是回文,就加入在path中,path用来记录切割过的回文子串。
      • 注意切割过的位置,不能重复切割,所以,backtracking(s, i + 1); 传入下一层的起始位置为i + 1
    • 如何判断一个字符串是否是回文?
      • 可以使用双指针法,一个指针从前向后,一个指针从后向前,如果前后指针所指向的元素是相等的,就是回文字符串了。
    • 本题有如下几个难点:
      • 切割问题可以抽象为组合问题
      • 如何模拟那些切割线
      • 切割问题中递归如何终止
      • 在递归循环中如何截取子串
      • 如何判断回文

这篇关于代码随想录刷题day23丨39. 组合总和,40.组合总和II, 131.分割回文串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139850

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

使用Dify访问mysql数据库详细代码示例

《使用Dify访问mysql数据库详细代码示例》:本文主要介绍使用Dify访问mysql数据库的相关资料,并详细讲解了如何在本地搭建数据库访问服务,使用ngrok暴露到公网,并创建知识库、数据库访... 1、在本地搭建数据库访问的服务,并使用ngrok暴露到公网。#sql_tools.pyfrom