代码随想录刷题day27|组合总和II组合总和II分割回文串

2024-03-19 01:12

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

文章目录

  • day27学习内容
  • 一、组合总和-所选数字可重复
    • 1.1、代码-正确写法
    • 1.1.1、为什么递归取的是i而不是i+1呢?
  • 二、组合总和II-所选数字不可重复
    • 2.1、和39题有什么不同
    • 2.2、思路
      • 2.2.1、初始化
      • 2.2.2、主要步骤
      • 2.2.3、回溯函数 `backTracking`
    • 2.3、正确写法1
      • 2.3.1、为什么要先排序
      • 2.3.2、去重为什么是!used[i - 1]而不是used[i - 1]
  • 三、分割回文串
    • 3.1、科普-什么是回文串?
    • 3.2、思路
    • 3.3、代码-正确写法
    • 3.3.1、为什么看到deque结果就往最终的result里面add?
    • 3.3.2、为什么判断回文串是从i开始,截取却从i+1开始呢?
  • 总结
    • 1.感想
    • 2.思维导图


day27学习内容

day27主要内容

  • 组合总和
  • 组合总和II
  • 分割回文串

声明
本文思路和文字,引用自《代码随想录》

一、组合总和-所选数字可重复

39.原题链接

1.1、代码-正确写法

class Solution {List<List<Integer>> result = new ArrayList();List<Integer> path = new ArrayList();public List<List<Integer>> combinationSum(int[] candidates, int target) {backTracking(candidates, target, 0, 0);return result;}private void backTracking(int[] candidates, int target, int sum, int startIndex) {// 累加和大于target,直接returnif (sum > target) {return;}if (sum == target) {result.add(new ArrayList(path));return;}for (int i = startIndex; i < candidates.length; i++) {path.add(candidates[i]);// 递归backTracking(candidates, target, sum + candidates[i], i);// 回溯path.removeLast();}}
}

1.1.1、为什么递归取的是i而不是i+1呢?

看题意,在这里插入图片描述
题目中说的很清楚了,可以无限制重复选取,所以不是从n+1开始迭代的。

二、组合总和II-所选数字不可重复

40.原题链接

2.1、和39题有什么不同

不同点1:看题目,原始数组中有重复的元素。
在这里插入图片描述
不同点2:累加求和的时候,可以用同样的元素。但是很重要的一点是每个数字在每个组合中只能使用一次。

2.2、思路

  • 对树层进行去重,对树枝不去重

2.2.1、初始化

  • LinkedList<Integer> path:用于临时存储当前探索路径中的数字序列。
  • List<List<Integer>> ans:用来存储所有符合条件的组合。
  • boolean[] used:标记数组中的元素是否被使用过,以避免在同一层中重复使用相同的元素。
  • int sum:记录当前路径上所有元素的总和。

2.2.2、主要步骤

  1. 排序:首先对数组 candidates 进行排序,这是为了实现有效去重和提前终止搜索。
  2. 调用回溯函数:通过 backTracking 函数开始回溯搜索。

2.2.3、回溯函数 backTracking

  • 结束条件:当 sum(当前路径元素的总和)等于 target 时,将当前路径复制一份并添加到结果集 ans 中,然后返回上一层继续探索。
  • 遍历候选数组:从 startIndex 开始遍历 candidates 数组,以避免重复使用元素。
  • 剪枝条件
    • 如果当前元素加上 sum 超过了 target,则由于数组已经排序,后面的元素只会更大,所以直接中断当前循环。
    • 如果当前元素与前一个元素相同,且前一个元素未被使用过,则跳过当前元素。这一步是去重的关键。
  • 递归与回溯
    • 首先标记当前元素为已使用,将其加入 path,并更新 sum
    • 然后递归调用 backTracking,注意 startIndex 更新为 i + 1,因为每个元素只能使用一次。
    • 递归返回后,撤销当前元素的选择:将其标记为未使用,从 path 中移除,并更新 sum

通过这样的递归+回溯的方式,加上有效的剪枝条件,代码能够高效地搜索整个解空间,找出所有满足条件的组合。排序是去重和剪枝的基础,确保了算法的高效和正确性。

2.3、正确写法1

class Solution {LinkedList<Integer> path = new LinkedList<>();List<List<Integer>> ans = new ArrayList<>();boolean[] used;int sum = 0;public List<List<Integer>> combinationSum2(int[] candidates, int target) {used = new boolean[candidates.length];// 加标志,用来判断同层节点是否已经遍历Arrays.fill(used, false);// 去重必须先排序Arrays.sort(candidates);backTracking(candidates, target, 0);return ans;}private void backTracking(int[] candidates, int target, int startIndex) {if (sum == target) {ans.add(new ArrayList(path));}for (int i = startIndex; i < candidates.length; i++) {if (sum + candidates[i] > target) {break;}// 去重逻辑if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {continue;}used[i] = true;sum += candidates[i];path.add(candidates[i]);// 每个节点仅能选择一次,所以从下一位开始backTracking(candidates, target, i + 1);used[i] = false;sum -= candidates[i];path.removeLast();}}
}

2.3.1、为什么要先排序

  • 去重逻辑的实现
    • 排序是实现去重逻辑的前提。当数组被排序后,重复的数字会被排列在一起。
    • 在回溯过程中,为了避免选择相同的数字造成的重复组合,需要检查当前数字是否与前一个数字相同,如果相同且前一个数字没有被使用(即在这一层中还未使用过),则跳过当前数字
    • 如果数组未排序,重复的数字可能散布在数组中的不同位置,我们就不能通过比较当前数字和前一个数字是否相同来有效地去重。
  • 提前终止搜索
    • 排序还允许我们在确定总和已经超过目标值时提前终止搜索。因为数组是有序的,
    • 如果在某一点上,当前路径上的数字总和加上当前考虑的数字已经超过了目标值,那么对于当前数字之后的所有数字,它们加入路径的结果也都会超过目标值(因为它们都是非负的,并且等于或大于当前数字)。
    • 这样可以避免无谓的搜索,从而提高算法的效率。

2.3.2、去重为什么是!used[i - 1]而不是used[i - 1]

看卡尔大佬的图,或者自己画个图,就很好理解了。简单来说,就是当你递归到最后一层往回回溯时,之前的节点,used的状态会重新变回[0]

三、分割回文串

131.原题链接

3.1、科普-什么是回文串?

来自gpt的解释:回文是一种特殊的字符串,它从前往后读和从后往前读是完全相同的。回文不仅限于单词和短语,也可以是一系列数字、字符或者其他序列,它们的特点是对称性。这种对称可以是字符级的,也就是说,忽略空格、标点符号和大小写后,字符串的前半部分和后半部分是镜像对称的。

3.2、思路

  • 什么时候分割结束
    • 看卡尔画出来的树图或者自己画一个,很明显到了字符串的末尾(可以理解为是叶子结点),就说明分割结束了。
  • 那么什么时候可以返回结果
    • 很明显,是回文字符串的时候,才能放入结果集。
  • 综上所述,这道问题就变成了判断每一个叶子结点是不是回文子串。如果叶子结点是回文字符串,就直接返回即可。
  • 怎么切割字符串
    • S0tring.subString()这方法应该知道吧。问题在于从哪里切割到哪里,
    • 答案是从startIndex切割到i。而且是左闭右闭。为什么呢?看3.3.2。

3.3、代码-正确写法

class Solution {List<List<String>> result= new ArrayList<>();Deque<String> deque = new LinkedList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return result;}private void backTracking(String s, int startIndex) {// 如果起始位置大于s的大小,说明找到了一组分割方案if (startIndex >= s.length()) {//为什么看到结果就add了呢?请看3.3.1result.add(new ArrayList(deque));return;}for (int i = startIndex; i < s.length(); i++) {// 判断是不是回文串,如果是就加入到deque里面if (isPalindrome(s, startIndex, i)) {String str = s.substring(startIndex, i + 1);deque.addLast(str);} else {continue;}// 起始位置+1,不能取已经取过的字符串。backTracking(s, i + 1);deque.removeLast();}}// 判断是否是回文串// 用双指针法private boolean isPalindrome(String s, int startIndex, int end) {for (int i = startIndex, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false;}}return true;}
}

3.3.1、为什么看到deque结果就往最终的result里面add?

因为判断回文子串,是在单层逻辑里面判断的,在deque里面的字符串,一定是回文子串,不是回文子串不会往里面add的。所以可以无脑add。

3.3.2、为什么判断回文串是从i开始,截取却从i+1开始呢?

  • 在这段代码中,判断回文串是从startIndexi(包括i),这是因为需要检查从startIndexi的子字符串是否构成回文串。
  • 一旦确认这个子字符串是回文串,就加入deque中。
  • 截取从i+1开始是因为在回溯过程中,当我们确定了一个回文子字符串后,下一步应该从这个子字符串的下一个字符开始继续寻找新的回文子字符串。这样,我们可以确保不会重复使用已经被包含在找到的回文子字符串中的字符。
  • 例如,对于字符串"aab",当startIndex为0,且我们发现"aa"是回文时,下一次递归调用backTracking时的startIndex应该是2,即"aa"之后的字符,这就是为什么截取开始的索引是i+1。这样做可以避免重复处理相同的字符,确保每次递归都是针对剩余未处理的字符串部分。

总结

1.感想

  • 分割回文串这题好难,不咋会写,另外吐槽一下,卡尔老师的视频反光好严重。

2.思维导图

本文思路引用自代码随想录,感谢代码随想录作者。

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



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

相关文章

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1