代码随想录算法训练营第二十六天|39. 组合总和、 40.组合总和II、 131.分割回文串

39. 组合总和

在这里插入图片描述

题目链接:39. 组合总和
文档讲解:代码随想录
状态:卡了一会儿

思路:先排序,方便剪枝。允许数字重复使用,因此递归调用时传入当前索引i。

题解:

public class Solution {// 用于存储所有可能的组合private List<List<Integer>> res = new ArrayList<>();// 当前正在构建的组合private LinkedList<Integer> list = new LinkedList<>();// 用于存储当前组合的和private int sum = 0;/*** 组合求和函数* @param candidates 候选数字数组* @param target 目标数字* @return 所有可能的组合列表*/public List<List<Integer>> combinationSum(int[] candidates, int target) {// 首先对候选数字进行排序Arrays.sort(candidates);// 调用回溯函数backtracking(candidates, target, 0);// 返回所有可能的组合return res;}/*** 回溯函数,用于递归地搜索所有可能的组合* @param candidates 候选数字数组* @param target 目标数字* @param startIndex 当前搜索的起始索引*/public void backtracking(int[] candidates, int target, int startIndex) {// 如果当前和大于目标,则回溯if (sum > target) {return;}// 如果当前和等于目标,将当前组合添加到结果列表中if (sum == target) {res.add(new ArrayList<>(list));return;}// 遍历候选数字,从startIndex开始,直到sum+当前数字大于目标或遍历完所有数字for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {// 将当前数字添加到当前组合中,并更新当前和sum += candidates[i];list.add(candidates[i]);// 递归调用回溯函数,搜索当前数字之后的组合backtracking(candidates, target, i); // 注意这里传入i,允许重复使用同一个数字// 回溯,移除当前数字,恢复当前和sum -= candidates[i];list.removeLast();}}
}

40.组合总和II

在这里插入图片描述

题目链接:40.组合总和II
文档讲解:代码随想录
状态:自己在去重的时候,将集合中的重复元素也去掉了,导致结果缺少。集合(数组candidates)有重复元素,但还不能有重复的组合,这个不会处理。

思路:使用used数组标记树层或树枝中的元素是否使用,从而将集合有重复元素和结果又重复组合区分开。
默认used数组都为false,树层有重复元素和树枝有重复元素的关键区别在于used[i-1]是否为true,树层中元素因为回溯会使used[i-1]恢复成false,树枝中有重复元素则used[i-1]使用过,因此为true。在这里插入图片描述

题解:

    List<List<Integer>> res = new ArrayList<>();  // 结果集LinkedList<Integer> list = new LinkedList<>();  // 当前组合int sum = 0;  // 当前组合的和public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);  // 排序,方便后续处理boolean[] used = new boolean[candidates.length];  // 记录每个元素是否被使用过Arrays.fill(used, false);  // 初始化为未使用backtracking(candidates, used, target, 0);  // 开始回溯return res;  // 返回结果集}public void backtracking(int[] candidates, boolean[] used, int target, int startIndex) {if (sum == target) {  // 当前组合的和等于目标值res.add(new ArrayList<>(list));  // 将当前组合加入结果集return;}for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {  // 去重continue;}sum += candidates[i];  // 做出选择,更新当前组合的和list.add(candidates[i]);  // 将当前元素加入当前组合used[i] = true;  // 标记当前元素已被使用backtracking(candidates, used, target, i + 1);  // 递归,处理下一个元素list.removeLast();  // 撤销选择,回溯到上一个状态used[i] = false;  // 标记当前元素未被使用sum -= candidates[i];  // 更新当前组合的和}}

131.分割回文串

在这里插入图片描述

题目链接:131.分割回文串
文档讲解:代码随想录
状态:不会,想到分割方法,代码没写出来!

代码没写出来的原因:

  1. 写成了 if (startIndex == chars.length) { res.add(new ArrayList<>(list)); return; }认为 startIndex == chars.length - 1 时将list添加到res中。实际上因为backtracking(chars, i + 1);的存在,res中添加list的操作都是在下次递归中完成的,而这时i+1就导致startIndex每次都比原来的大了1。
  2. 写成了new String(chars, startIndex, i),而实际上第三个参数是长度
    // 存储所有分割方案的列表List<List<String>> res = new ArrayList<>();// 当前正在构建的分割方案LinkedList<String> list = new LinkedList<>();/*** 将字符串分割成回文子串的方案* @param s 输入的字符串* @return 分割方案的列表*/public List<List<String>> partition(String s) {// 将字符串转换为字符数组char[] chars = s.toCharArray();// 从索引0开始回溯backtracking(chars, 0);// 返回所有分割方案return res;}/*** 回溯函数,用于递归地搜索所有可能的回文子串分割方案* @param chars 字符串转换后的字符数组* @param startIndex 当前搜索的起始索引*/public void backtracking(char[] chars, int startIndex) {// 如果当前索引等于字符数组的长度,说明已经处理完所有字符,将当前方案添加到结果中if (startIndex == chars.length) {res.add(new ArrayList<>(list));return;}// 从当前索引开始,尝试所有可能的分割点for (int i = startIndex; i < chars.length; i++) {// 如果从startIndex到i的子串是回文串,则将其添加到当前方案中if (isPalindrome(chars, startIndex, i)) {// 添加子串到当前方案list.add(new String(chars, startIndex, i - startIndex + 1));// 递归调用回溯函数,继续搜索i之后的分割方案backtracking(chars, i + 1);// 回溯,移除最后一个添加的子串,以便尝试其他分割方案list.removeLast();}}}/*** 判断子串是否为回文串* @param chars 字符数组* @param start 子串的起始索引* @param end 子串的结束索引* @return 如果子串是回文串返回true,否则返回false*/public boolean isPalindrome(char[] chars, int start, int end) {// 从子串的两端向中间遍历,如果字符不相等则不是回文串while (start <= end) {if (chars[start] != chars[end]) {return false;}start++;end--;}// 如果遍历完所有字符都相等,则子串是回文串return true;}

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

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

相关文章

深度学习训练——batch_size参数设置过大反而训练更耗时的原因分析

&#x1f4aa; 专业从事且热爱图像处理&#xff0c;图像处理专栏更新如下&#x1f447;&#xff1a; &#x1f4dd;《图像去噪》 &#x1f4dd;《超分辨率重建》 &#x1f4dd;《语义分割》 &#x1f4dd;《风格迁移》 &#x1f4dd;《目标检测》 &#x1f4dd;《暗光增强》 &a…

长短期记忆神经网络(LSTM)的回归预测(免费完整源代码)【MATLAB】

LSTM&#xff08;Long Short-Term Memory&#xff0c;长短期记忆网络&#xff09;是一种特殊类型的递归神经网络&#xff08;RNN&#xff09;&#xff0c;专门用于处理和预测基于时间序列的数据。与传统RNN相比&#xff0c;LSTM在处理长期依赖问题时具有显著优势。 LSTM的基本…

FFmpeg中内存分配和释放相关的源码:av_malloc函数、av_mallocz函数、av_free函数和av_freep函数分析

一、av_malloc函数分析 &#xff08;一&#xff09;av_malloc函数的声明 av_malloc函数的声明放在在FFmpeg源码&#xff08;本文演示用的FFmpeg源码版本为5.0.3&#xff0c;该ffmpeg在CentOS 7.5上通过10.2.1版本的gcc编译&#xff09;的头文件libavutil/mem.h中&#xff1a;…

Ubuntu网络管理命令:ifconfig

安装Ubuntu桌面系统&#xff08;虚拟机&#xff09;_虚拟机安装ubuntu桌面版-CSDN博客 关于ifconfig命令&#xff0c;在11.1节已经介绍过了。通过该命令可以查看和配置网络接口。ifconfig是一个比较古老的命令&#xff0c;在Ubuntu 22以及其他的许多发行版中&#xff0c;已经不…

【前端项目笔记】2 主页布局

主页布局 element-ui提供的组件名称就是它的类名 ☆☆ CSS选择器&#xff1a; &#xff08;1&#xff09;基本选择器 类型选择器 p/span/div…… 类选择器 (.classname) ID选择器 (#idname) 通配选择器 ( * ) &#xff08;2&#xff09;属性选择器 选择具有特定属性或属性值的…

最新下载:CrossOver 2024【软件附加安装教程】

CrossOver不像Parallels或VMware的模拟器&#xff0c;而是实实在在Mac OS X系统上运行的一个软件。CrossOvers能够直接在Mac上运行Windows软件与游戏&#xff0c;而不需虚拟机。它为Windows软件提供所需的资源&#xff0c;以达到在Mac OS X系统上运行Windows程序的目的。 安 装…

【网络安全学习】使用Kali做渗透情报收集-01-<域名信息主机信息>

1.收集开源情报 开源情报(Open Source Intelligence&#xff0c;OSINT)是指从各种公开的渠道中寻找和获取有价值的信息 如&#xff1a;互联网、媒体、社交网络、公共数据库等开源情报具有以下特点&#xff1a; - 丰富性&#xff1a;开源情报涵盖了各种类型和领域的信息 - 可…

linux centos consul1.15.2一键安装部署

consul原理、作用、安装相关内容 一、理论部分二、安装下载版本地址三、安装consul服务 一、理论部分 1、consul的原理 Consul的原理及作用可以归纳为以下几点&#xff1a; ①、基于Gossip协议的通信&#xff1a;Consul使用了基于Gossip协议的Serf实现来进行通信。 Gossip协议…

矩阵乘法的直觉

矩阵乘法是什么意思&#xff1f; 一种常见的观点是矩阵乘法缩放/旋转/倾斜几何平面&#xff1a; NSDT工具推荐&#xff1a; Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 可编程3D场景编辑器 - REVIT导出3D模型插件 - 3D模型语义搜…

分数限制下,选好专业还是选好学校?

目录 分数限制下&#xff0c;选好专业还是选好学校&#xff1f; 方向一&#xff1a;专业解析 1. 专业选择的重要性 2. 不同专业的优势与挑战 3. 个人专业选择经验分享 4. 实际场景下的“专业VS学校”选择方案 方向二&#xff1a;名校效应分析 1. 名校声誉与品牌效应 2…

Unity 使用TextMeshPro实现图文混排

最后实现出的效果是这样的 开始实现 准备两张图 选中图片右键->Create->TextMeshPro->Sprite Asset 然后文件夹内就会出现一个同名的这个文件 新建一个Text Inspector面板 点击最底下的Extra Settings 然后把刚刚创建的SpriteAsset拖过来 放到对应的地方 然后…

李沐:用随机梯度下降来优化人生!

大侠幸会&#xff0c;在下全网同名「算法金」 0 基础转 AI 上岸&#xff0c;多个算法赛 Top 「日更万日&#xff0c;让更多人享受智能乐趣」 今天我们来聊聊达叔 6 大核心算法之 —— 优化 算法。吴恩达&#xff1a;机器学习的六个核心算法&#xff01; 梯度下降优化算法是机器…

HarmoneyOS星河版 安装和启动

一、下载和安装DevEco Studio 官网链接&#xff1a;OpenAtom OpenHarmony 1.1 找到对应的操作系统进行下载 创建安装Harmony的文件夹&#xff1a; 1.2 下载后进行安装 1.3 分别安装Node、Ohpm、SDK 分别安装Node、Ohpm和SDK 二、.创建一个新项目并运行 2.1 选择[OpenHarmon…

当OpenHarmony遇上OpenEuler

1、 安装openEuler 虚拟机、物理机器当然都可以安装。虚拟机又可以使用WSL、或者VMWare、VirtualBox虚拟机软件&#xff0c;如果需要安装最新版本&#xff0c;建议使用后者。当前WSL只支持OpenEuler 20.03。 1.1 WSL openEuler WSL的安装都是程序员的必备技能了&#xff0c;…

大学课设项目,Windows端基于UDP的网络聊天程序的服务端和客户端

文章目录 前言项目需求介绍一、服务端1.对Udp套接字进行一个封装2. UdpServer的编写3. Task.h4.protocol.h的编写5.线程池的编写6.main.cc 二、客户端1. Socket.h2.protocol.h3.UdpClient4.menu.h5.main.cpp 三、运行图 前言 本次项目可以作为之前内容的一个扩展&#xff0c;学…

《数据安全产品及服务购买决策参考》

“新全球化”下的数据安全威胁态势与挑战 随着中国企业数字化转型和数字经济的高速发展&#xff0c;数据要素和数据安全的战略价值正不断提升。 同时&#xff0c;在“脱钩”与“新全球化”的全球政治经济博弈中&#xff0c;中国作为全球重要的数据安全市场之一&#xff0c;其…

LeetCode esay mid 记录

1486. 数组异或操作 感觉一般也用不到 emmm 灵茶山艾府传送门 推导过程可以结合官网部分观看 重点由两部分的结合 将特定部分转换为常见部分 0到n的异或和表示 2595. 奇偶位数 0x555是十六进制数&#xff0c;转换为二进制为 0101 0101 0101 class Solution {public int[…

90. 子集 II

90. 子集 II 原题链接&#xff1a;完成情况&#xff1a;解题思路&#xff1a;参考代码&#xff1a;_90子集II_递归法求子集_90子集II_迭代法求子集 错误经验吸取 原题链接&#xff1a; 90. 子集 II https://leetcode.cn/problems/subsets-ii/ 完成情况&#xff1a; 解题思路…

代码解读 | Hybrid Transformers for Music Source Separation[07]

一、背景 0、Hybrid Transformer 论文解读 1、代码复现|Demucs Music Source Separation_demucs架构原理-CSDN博客 2、Hybrid Transformer 各个模块对应的代码具体在工程的哪个地方 3、Hybrid Transformer 各个模块的底层到底是个啥&#xff08;初步感受&#xff09;&#xff1…

Vue48-ref属性

一、需求&#xff1a;操作DOM元素 1-1、使用原生的id属性 不太好&#xff01; 1-2、使用 ref属性 原生HTML中&#xff0c;用id属性给元素打标识&#xff0c;vue里面用ref属性。 给哪个元素加了ref属性&#xff0c;vc实例对象就收集哪个元素&#xff01;&#xff01;&#xff0…