代码随想录刷题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

相关文章

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

Python如何将大TXT文件分割成4KB小文件

《Python如何将大TXT文件分割成4KB小文件》处理大文本文件是程序员经常遇到的挑战,特别是当我们需要把一个几百MB甚至几个GB的TXT文件分割成小块时,下面我们来聊聊如何用Python自动完成这... 目录为什么需要分割TXT文件基础版:按行分割进阶版:精确控制文件大小完美解决方案:支持UTF-8编码

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面