代码随想录【Day27】| 39. 组合总和、40. 组合总和 II、131. 分割回文串

news/2024/4/20 13:50:28/文章来源:https://blog.csdn.net/weixin_42764266/article/details/129235545

39. 组合总和

题目链接

题目描述:
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:

  • 输入:candidates = [2,3,6,7], target = 7,
  • 所求解集为: [ [7], [2,2,3] ]

示例 2:

  • 输入:candidates = [2,3,5], target = 8,
  • 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]

难点:
剪枝

思路:
回溯回溯~~

构造结果集,path集

回溯主体:
按部就班

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates, 0, target, 0);return result;}public void backtracking(int[] candidates, int curSum, int target, int startIdx) {if (curSum > target) return;if (curSum == target) {result.add(new ArrayList<>(path));return;}for (int i = startIdx; i < candidates.length; i++) {// if (curSum + candidates[i] > target) break; //自己写没想到这里的剪枝path.add(candidates[i]);curSum += candidates[i];backtracking(candidates, curSum, target, i);path.remove(path.size()-1);curSum -= candidates[i];}}
}

时长:
10min

收获:
不用IDEA也很顺手(*^_^*)
第二遍写一下就AC了,除了一个剪枝的地方没想到xixi


40. 组合总和 II

题目链接

题目描述:
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

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

说明: 所有数字(包括目标数)都是正整数。解集不能包含重复的组合。

示例 1:

  • 输入:
    candidates = [10,1,2,7,6,1,5], target = 8,
  • 所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]

示例 2:

  • 输入:
    candidates = [2,5,2,1,2], target = 5,
  • 所求解集为:
[[1,2,2],[5]
]

难点:
在这里插入图片描述

思路:
构造全局数组来标记元素是否被使用过,避免重复添加结果

  1. 构造candidates长度的布尔型全局数组used
  2. 在回溯的当前层遍历时进行判断
    3. 如果当前元素等于上一个元素(i>0)并且上一个元素未使用,continue
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean used[];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, 0);return result;}public void backtracking(int[] candidates, int target, int curSum, int startIdx) {if (curSum > target) return;if (curSum == target) {result.add(new ArrayList<>(path));return;}for (int i = startIdx; i < candidates.length; i++) {if (curSum + candidates[i] > target) return;//难点if (i > 0 && candidates[i-1] == candidates[i] && !used[i-1]) {continue;}used[i] = true;path.add(candidates[i]);curSum += candidates[i];backtracking(candidates, target, curSum, i+1);path.remove(path.size()-1);curSum -= candidates[i];used[i] = false;}}
}

时长:
15min

收获:
构造数组来标记元素是否被使用


131. 分割回文串

题目链接

题目描述:
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

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

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

难点:
如何定义切割?
什么时候收集结果?
在哪剪枝?

思路:
每次遍历到的元素,想象一个虚拟的分隔符在其后
用区间[startIdx, i]来取子串,并判断其是否是回文串

  1. 如果不是,continue(剪枝)
  2. 如果是,加入path
class Solution {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return result;}private void backTracking(String s, int startIdx) {//如果起始位置大于s的大小,说明找到了一组分割方案if (startIdx >= s.length()) {result.add(new ArrayList(path));return;}for (int i = startIdx; i < s.length(); i++) {//如果是回文子串,则记录if (isPalindrome(s, startIdx, i)) {String str = s.substring(startIdx, i + 1);path.add(str);} else {continue; //剪枝}//起始位置后移,保证不重复backTracking(s, i + 1);path.remove(path.size()-1);}}//判断是否是回文串private boolean isPalindrome(String s, int startIdx, int end) {for (int i = startIdx, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false;}}return true;}
}

时长:
20min

收获:
切个问题

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

taobao.top.secret.bill.detail( 服务商的商家解密账单详情查询 )

&#xffe5;免费必须用户授权 服务商的商家解密账单详情查询&#xff0c;仅对90天内的账单提供SLA保障。 公共参数 请求地址: HTTP地址 http://gw.api.taobao.com/router/rest 公共请求参数: 公共响应参数: 请求参数 响应参数 点击获取key和secret 请求示例 TaobaoClient…

js 拖动--动态改变div的宽高大小

index.html 如下&#xff1a;&#xff08;可以新建一个index.html文件直接复制&#xff0c;打开运行&#xff09; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta http-equiv"X-UA-Compatible&qu…

Mybatis源码学习笔记(五)之Mybatis框架缓存机制原理解析

1 Mybatis框架的缓存模块 MyBatis 内置了一个强大的事务性查询缓存机制&#xff0c;它可以非常方便地配置和定制。Mybatis框架中的缓存分为一级缓存和二级缓存&#xff0c;三级缓存基本都要借助自定义缓存或第三方服务来进行实现。但本质上是一样的&#xff0c;都是借助Cache接…

【Python学习笔记】第十九节 Python 面向对象(一)

在现实世界中&#xff0c;随处可见的一种事物就是对象&#xff0c;对象是事物存在的实体&#xff0c;如学生、汽车等。人类解决问题的方式总是将复杂的事物简单化&#xff0c;于是就会思考这些对象都是由哪些部分组成的。通常都会将对象划分为两个部分&#xff0c;即静态部分与…

SSL证书对虚拟主机的用处有哪些?

虚拟主机是指在同一台服务器上&#xff0c;通过不同的域名或IP地址为多个网站提供服务的一种网络主机。而SSL证书则是一种数字证书&#xff0c;它用于加密网站与用户之间的通信&#xff0c;确保数据传输的安全性和完整性。在虚拟主机上&#xff0c;SSL证书有以下几个用处&#…

HiveSql一天一个小技巧:如何巧用分布函数percent_rank()求去掉最大最小值的平均薪水问题

0 问题描述参考链接(3条消息) HiveSql面试题12--如何分析去掉最大最小值的平均薪水&#xff08;字节跳动&#xff09;_莫叫石榴姐的博客-CSDN博客文中已经给出了三种解法&#xff0c;这里我们借助于此题&#xff0c;来研究如何用percent_rank()函数求解&#xff0c;简化解题思路…

深入理解C#的协变和逆变及其限制原因

阅读本文需要的一些前置知识&#xff1a; C#基本语法、C#的泛型使用、C#的运行过程 由于协变和逆变存在一些细节&#xff0c;在阅读时请注意“接口”和“类型”的差异&#xff0c;此外&#xff0c;文中有可能在不同的语境中将“结构体”和“值类型”混用&#xff0c;但表达的同…

深入浅出1588v2(PTP)里的时间同步原理

1.时间同步1.1 单步同步(OneStep)单步同步最为简单&#xff0c;master向slave发送一个sync的同步包&#xff0c;同步包里带有这条信息发送时master的当前时间t1&#xff0c;假如这条信息从master传输到slave需要的传输时间是D&#xff0c;那么slave收到信息时&#xff0c;maste…

BIM小技巧丨关于如何在Revit明细表中显示门窗面积

在明细表中显示门窗面积(以门明细表为例)在新建一个门明细表后&#xff0c;可以发现在Revit中不能直接使用明细表统计门窗面积。 这时&#xff0c;可以通过使用添加“计算值”的方式来处理&#xff0c;得到如下图所示&#xff0c;两种不同的面积统计结果&#xff1a; 除此之外&…

前端基础之CSS扫盲

文章目录一. CSS基本规范1. 基本语法格式2. 在HTML引入CSS3. 选择器分类二. CSS常用属性1. 文本属性2. 文本格式3. 背景属性4. 圆角矩形和圆5. 元素的显示模式6. CSS盒子模型7. 弹性布局光使用HTML来写一个前端页面的话其实只是写了一个大体的框架, 整体的页面并不工整美观, 而…

ledcode【用队列实现栈】

目录 题目描述&#xff1a; 解析题目 代码解析 1.封装一个队列 1.2封装带两个队列的结构体 1.3封装指向队列的结构体 1.4入栈函数实现 1.5出栈函数实现 1.6取栈顶数据 1.7判空函数实现 题目描述&#xff1a; 解析题目 这个题我是用c语言写的&#xff0c;所以队列的pu…

JavaSE-3 Java运行原理

一、Java的运行过程 &#x1f34e;Java程序运行时,必须经过编译和运行两个步骤。 首先将后缀名为.java的源文件进行编译,最终生成后缀名为.class的字节码文件。然后Java虚拟机将字节码文件进行解释执行,并将结果显示出来。具体过程如下图所示。 &#x1f349;Java程序的运行过…

【Python数据挖掘入门】2.2文本分析-中文分词(jieba库cut方法/自定义词典load_userdict/语料库分词)

中文分词就是将一个汉字序列切分成一个一个单独的词。例如&#xff1a; 另外还有停用词的概念&#xff0c;停用词是指在数据处理时&#xff0c;需要过滤掉的某些字或词。 一、jieba库 安装过程见&#xff1a;https://blog.csdn.net/momomuabc/article/details/128198306 ji…

数字IC手撕代码--小米科技(除法器设计)

前言&#xff1a; 本专栏旨在记录高频笔面试手撕代码题&#xff0c;以备数字前端秋招&#xff0c;本专栏所有文章提供原理分析、代码及波形&#xff0c;所有代码均经过本人验证。目录如下&#xff1a;1.数字IC手撕代码-分频器&#xff08;任意偶数分频&#xff09;2.数字IC手撕…

原始GAN-pytorch-生成MNIST数据集(代码)

文章目录原始GAN生成MNIST数据集1. Data loading and preparing2. Dataset and Model parameter3. Result save path4. Model define6. Training7. predict原始GAN生成MNIST数据集 原理很简单&#xff0c;可以参考原理部分原始GAN-pytorch-生成MNIST数据集&#xff08;原理&am…

记一次线上es慢查询导致的服务不可用

现象 某日线上业务同学反馈订单列表查询页面一直loding&#xff0c;然后提示请求超时&#xff0c;几分钟之后恢复正常 接到报障之后&#xff0c;马上根据接口URL&#xff0c;定位到了请求链路&#xff0c;发现是es查询超时&#xff0c;这里我们的业务订单表数据是由几百万的&a…

如何基于MLServer构建Python机器学习服务

文章目录前言一、数据集二、训练 Scikit-learn 模型三、基于MLSever构建Scikit-learn服务四、测试模型五、训练 XGBoost 模型六、服务多个模型七、测试多个模型的准确性总结参考前言 在过去我们训练模型&#xff0c;往往通过编写flask代码或者容器化我们的模型并在docker中运行…

Python学习笔记202302

1、numpy.empty 作用&#xff1a;根据给定的维度和数值类型返回一个新的数组&#xff0c;其元素不进行初始化。 用法&#xff1a;numpy.empty(shape, dtypefloat, order‘C’) 2、logging.debug 作用&#xff1a;Python 的日志记录工具&#xff0c;这个模块为应用与库实现了灵…

C# Sqlite数据库加密

sqlite官方的数据库加密是收费的&#xff0c;而且比较贵。 幸亏微软提供了一种免费的方法。 1 sqlite加密demo 这里我做了一个小的demo演示如下&#xff1a; 在界面中拖入数据库名、密码、以及保存的路径 比如我选择保存路径桌面的sqlite目录&#xff0c;数据库名guigutool…

Verilog 学习第五节(串口接收部分)

小梅哥串口部分学习part2 串口通信接收原理串口通信接收程序设计与调试巧用位操作优化串口接收逻辑设计串口接收模块的项目应用案例串口通信接收原理 在采样的时候没有必要一直判断一个clk内全部都是高/低电平&#xff0c;如果采用直接对中间点进行判断的话&#xff0c;很有可能…