Day 26| 39. 组合总和 、 40.组合总和II 、 131.分割回文串

news/2024/7/20 13:49:38
  1. 组合总和

本题是 集合里元素可以用无数次,那么和组合问题的差别 其实仅在于 startIndex上的控制

题目链接/文章讲解:https://programmercarl.com/0039.组合总和.html
视频讲解:https://www.bilibili.com/video/BV1KT4y1M7HJ
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

思考

这道题的特点是可以重复选取。
因此for循环内遍历的时候,start_index = i

class Solution:def __init__(self):self.path = []self.res_list_all = []self.sum = 0def backtracking(self,candidates,target,start_index):if self.sum == target:self.res_list_all.append(self.path[:])return elif self.sum > target:return else:for i in range(start_index,len(candidates)):self.path.append(candidates[i])self.sum+=candidates[i]self.backtracking(candidates,target,i)self.path.pop()self.sum-=candidates[i]def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.backtracking(candidates,target,0)return self.res_list_all

排序后,回溯的过程可以剪枝,同一层,前面的数和已经超了的话,后面的就不用再试了,因为后面的数更大。

class Solution:def __init__(self):self.path = []self.res_list_all = []self.sum = 0def backtracking(self,candidates,target,start_index):if self.sum == target:self.res_list_all.append(self.path[:])return elif self.sum > target:return else:for i in range(start_index,len(candidates)):if self.sum+candidates[i] > target:breakself.path.append(candidates[i])self.sum+=candidates[i]self.backtracking(candidates,target,i)self.path.pop()self.sum-=candidates[i]def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.backtracking(candidates,target,0)return self.res_list_all

40.组合总和II

本题开始涉及到一个问题了:去重。

注意题目中给我们 集合是有重复元素的,那么求出来的 组合有可能重复,但题目要求不能有重复组合。

题目链接/文章讲解:https://programmercarl.com/0040.组合总和II.html
视频讲解:https://www.bilibili.com/video/BV12V4y1V73A

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意:解集不能包含重复的组合。

思考

这道题的难点是要在回溯中去重,即去除重复的组合。
两种方法:

  1. 需要定义一个used数组。
    used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
    used[i - 1] == false,说明同一树层candidates[i - 1]使用过

    2. 判断条件增加i>start_index
    两种方案都需要先排序才能去重。

方案二的方法

class Solution:def __init__(self):self.res = []self.res_all = []self.sum = 0def backtracking(self,candidates,target,start_index):if self.sum > target:returnif self.sum == target:self.res_all.append(self.res[:])returnfor i in range(start_index,len(candidates)):if i > start_index and (candidates[i-1] == candidates[i]):continueself.sum+=candidates[i]self.res.append(candidates[i])self.backtracking(candidates,target,i+1)self.res.pop()self.sum-=candidates[i]def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.backtracking(candidates,target,0)return self.res_all

131.分割回文串

本题较难,大家先看视频来理解 分割问题,明天还会有一道分割问题,先打打基础。

https://programmercarl.com/0131.分割回文串.html
视频讲解:https://www.bilibili.com/video/BV1c54y1e7k6
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

思考

分割问题本质上也是求组合问题。start_index表示分割线。

def is_huiwen(s):i = 0j = len(s)-1while i<j:if s[i]==s[j]:i+=1j-=1else:return Falsereturn True
class Solution:def partition(self, s: str) -> List[List[str]]:def backtracking(s,star_index):if star_index == len(s):res.append(path[:])returnfor i in range(star_index,len(s)):if is_huiwen(s[star_index:i+1]):path.append(s[star_index:i+1])backtracking(s,i+1)path.pop()path = []res = []backtracking(s,0)return res   

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ryyt.cn/news/45265.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

2024嵌入式大作业

2024年上海交通大学嵌入式课程大作业 本学年是嵌入式第一次上升到4学分,即在原本的2学分的理论课程之上增设了2学分的实验课,因而成为了一门大课。 不同老师之间大作业的要求不同,所以我把我们班的实验要求罗列出来,并谈一谈我的实现方案,希望能够作为前人的智慧,起到抛砖…

【Playwright+Python】系列教程(一)环境搭建及脚本录制

一、前言 看到这个文章,有的同学会说: 六哥,你为啥不早早就写完python系列的文章。 因为有徒弟需要吧,如果你也想学自学,那这篇文章,可以说是我们结缘一起学习的开始吧! 如果对你有用,建议收藏和转发! 二、Playwright是什么? 微软开源自动化测试工具Playwright,支持…

苹果CMS 阿里云OSS插件

直接下载插件上传到CMS的addons目录解压点击启用插件点击配置插件配置完毕后进入系统菜单>附件参数配置保存方式改为阿里云OSS即可需要插件直接联系我 :vx:qianjingchuangqi本文来自博客园,作者:ikay,转载请注明原文链接:https://www.cnblogs.com/ikay/p/18255405

PPT使用技巧

PPT使用说明: 查看版本:账户 撤回次数: 自动保存: 图片压缩:(ppt图片默认是压缩的),只针对单个ppt文件 字体嵌入:解决不同电脑导致字体显示的不一样。 ppt多格式导出:如视频、图片、图片型的ppt 参考线: 默认字体: 默认样式:设置所有图形的样式清除占位符:…

点云分割网络PointConv

PDF:《PointConv: Deep Convolutional Networks on 3D Point Clouds》 CODE: https://github.com/DylanWusee/pointconv 一、大体内容 PointConv是一种在非均匀采样下对3D点云进行卷积的运算,可以用来构建深度卷积网络,其将卷积核视为由权重函数和密度函数组成的三维点的局部…

算法金 | 一个强大的算法模型:t-SNE !!

大侠幸会,在下全网同名「算法金」0 基础转 AI 上岸,多个算法赛 Top「日更万日,让更多人享受智能乐趣」t-SNE(t-Distributed Stochastic Neighbor Embedding)是一种用于降维和数据可视化的非线性算法。它被广泛应用于图像处理、文本挖掘和生物信息学等领域,特别擅长处理高…

软件测试理论基础Part2

测试用例设计 等价类划分法有效等价类满足需求的无效等价类不满足需求的等价类划分方法操作步骤明确需求 确定有效和无效等价类 编写测试用例边界值划分法 边界范围上点处在边界上的点(正好等于)离点离上点最近的点内点范围内的点开区间,闭区间[开始值,结束值] - 闭区间,包含开…