算法训练(leetcode)二刷第十九天 | *39. 组合总和、*40. 组合总和 II、*131. 分割回文串

刷题记录

  • *39. 组合总和
  • *40. 组合总和 II
  • *131. 分割回文串

*39. 组合总和

leetcode题目地址

元素可以重复,但结果不可以重复,此题与216. 组合总和 III的思路相似,只是,216. 组合总和 III不可重复使用数字。

不可重复使用,则在回溯算法下一次递归时就从下一个位置开始计算。
可以重复使用,则在回溯算法下一次递归时仍然从当前位置开始计算。

时间复杂度: O ( n ∗ 2 n ) O(n*2^n) O(n2n)
空间复杂度: O ( n ) O(n) O(n)

// java
class Solution {private int sum = 0;private List<Integer> path = new LinkedList<>();private List<List<Integer>> result = new ArrayList<>();public void backtracing(int[] candidates, int target, int startIdx){if(startIdx >= candidates.length) return;if(sum > target) return;if(sum == target){result.add(new ArrayList<>(path));return;}for(int i=startIdx; i<candidates.length; i++){// 剪枝if(sum>=target) return;path.add(candidates[i]);sum += candidates[i];backtracing(candidates, target, i);sum -= candidates[i];path.removeLast();}}public List<List<Integer>> combinationSum(int[] candidates, int target) {// 排序Arrays.sort(candidates);backtracing(candidates, target, 0);return result;}
}

*40. 组合总和 II

leetcode题目地址

本题难点在于去重。数组中有重复数字,但不可以有重复组合。

因此需要先对数组排序,排序后在同一层递归中相同的数字只进行一次。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)

// java
class Solution {private int sum = 0;private List<Integer> path = new LinkedList<>();private List<List<Integer>> result = new ArrayList<>();public void backtracking(int[] candidates, int target, int startIdx){if(sum > target) return;if(sum == target){result.add(new ArrayList<>(path));return;}for(int i=startIdx; i<candidates.length; i++){// 去重 本层循环已使用相同元素if(i>startIdx && candidates[i] == candidates[i-1]) continue;if(sum >= target) return;sum += candidates[i];path.add(candidates[i]);backtracking(candidates, target, i+1);sum -= candidates[i];path.removeLast();}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates, target, 0);return result;}
}

*131. 分割回文串

leetcode题目地址

这里需要注意记录字符串每次递归都需要新创建一个空串,而不是接着上一层接着拼接。

时间复杂度: O ( n ∗ 2 n ) O(n*2^n) O(n2n)
空间复杂度: O ( n 2 ) O(n^2) O(n2)

// java
class Solution {private List<String> path = new LinkedList<>();private List<List<String>> result = new ArrayList<>();public boolean isPalindrome(StringBuilder s){for(int i=0; i<=s.length()/2; i++){if(s.charAt(i) != s.charAt(s.length()-1-i)){return false;}}return true;}public void backtracing(String s, int startIdx, StringBuilder sb){if(startIdx >= s.length()) {result.add(new ArrayList<>(path));return;}for(int i=startIdx; i<s.length(); i++){sb.append(s.charAt(i));    if(isPalindrome(sb)){path.add(sb.toString());backtracing(s, i+1, sb);path.removeLast();}}}public List<List<String>> partition(String s) {backtracing(s, 0, new StringBuilder());return result;}
}

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

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

相关文章

右旋圆极化散射后的stocks矢量 与T3矩阵的关系

T3矩阵如下 斯托克斯与T3的关系如下。 斯托克斯与T3均没有平均处理&#xff0c;即斯托克斯是完全极化波的&#xff08;一种琼斯矢量得到&#xff09;&#xff0c;T3是由一个散射矩阵得到&#xff0c;只有一个特征值。

电子电气架构 -- 智能汽车电子电气架构开发关键技术

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所有人的看法和评价都是暂时的,只有自己的经历是伴随一生的,几乎所有的担忧和畏惧,都是来源于自己的想象,只有你真的去做了,才会发现有多快乐。…

Windows下mysql数据库备份策略

Windows下mysql的增量备份和全量备份&#xff0c;并利用schtasks设置定时任务执行bat脚本。 一、备份要求 序号 备份类型 备份频次 备份时间 1 增量备份 每周一-每周六各一次 18:00:00 2 全量备份 每周日一次 18:00:00 二、备份方法 2.1增量备份 2.1.1准备工作…

使用CentOS宝塔面板docker搭建EasyTier内网穿透服务

0. 前言 EasyTier是一个简单、安全、去中心化的内网穿透 VPN 组网方案&#xff0c;部署方便&#xff0c;支持 MacOS/Linux/Windows/FreeBSD/Android平台&#xff0c;而且作者搭建了一个公共服务器&#xff0c;不想折腾自建服务&#xff0c;可以使用默认的公共服务器地址 tcp:/…

Moment.js、Day.js、Miment,日期时间库怎么选?

一直以来&#xff0c;处理时间和日期的JavaScript库&#xff0c;选用的都是Momment.js。它的API清晰简单&#xff0c;使用方便灵巧&#xff0c;功能还特别齐全。 大师兄是Moment.js的重度使用者。凡是遇到时间和日期的操作&#xff0c;就把Moment.js引用上。 直到有天我发现加…

AOSP去特征|AOSP导入android-studio|AOSP导入clion

什么是AOSP 开源性&#xff1a;AOSP的源代码公开&#xff0c;任何人都可以获取和修改&#xff0c;适合想要开发或自定义安卓系统的开发者。 灵活性&#xff1a;AOSP提供了基本的安卓功能&#xff0c;制造商可以基于AOSP开发出自己的定制系统&#xff08;如三星的One UI、小米的…

JavaScript 网页设计详解教程

JavaScript 网页设计详解教程 引言 JavaScript 是一种广泛使用的编程语言&#xff0c;主要用于网页开发。它使得网页具有动态交互性&#xff0c;能够响应用户的操作。随着前端开发的不断发展&#xff0c;JavaScript 已成为现代网页设计中不可或缺的一部分。本文将详细介绍 Ja…

Android关机流程知多少?

在 Android 中&#xff0c;关机流程涉及系统各个组件的协同工作&#xff0c;确保设备在断电之前能够安全地关闭所有活动并保存数据。以下是 Android 系统中关机流程的详细介绍&#xff1a; 1. 用户触发关机请求 关机流程由用户的操作触发&#xff0c;通常有以下几种方式&#…

【Mac】PD报错:无法为“Windows” 完成操作,虚拟机ID无效的解决办法

Parallels Desktop是Mac上一款非常常用的虚拟机软件&#xff0c;但是在使用过程中&#xff0c;可能会遇到一些问题不知道如何处理。比如有时会遇到PD报错&#xff1a;无法为“Windows 11”完成操作&#xff0c;虚拟机ID无效。 错误原因 电脑上安装过虚拟机&#xff0c;虚拟机被…

51c大模型~合集17

我自己的原文哦~ https://blog.51cto.com/whaosoft/11599989 #关于大模型「越狱」的多种方式 此项目是由伊利诺伊大学香槟分校&#xff08;UIUC&#xff09;的汪浩瀚教授主导&#xff0c;汇集了多名intern的共同努力而成。长久以来&#xff0c;这个跨学科的团队一直在前沿科…

一:时序数据库-Influx应用

目录 0、版本号 1、登录页面 2、账号基本信息 3、数据库案例 4、可视化 5、java案例 0、版本号 InfluxDB v2.4.0 1、登录页面 http://127.0.0.1:8086/signin 账号&#xff1a;自己账号 密码&#xff1a;自己密码 2、账号基本信息 查看用户id和组织id&#xff01;&…

Uefi Application小游戏开发之贪吃蛇

这段代码是一个 UEFI 应用程序&#xff0c;它实现了一个简单的贪吃蛇游戏。 #include <Uefi.h> #include <Library/UefiLib.h> #include <Library/ShellCEntryLib.h> #include <Library/UefiBootServicesTableLib.h> #include <Library/UefiRuntim…

C++设计模式结构型模式———组合模式

文章目录 一、引言二、组合模式三、总结 一、引言 组合模式是一种结构型设计模式&#xff0c; 可以使用它将对象组合成树状结构&#xff0c; 并且能像使用独立对象一样使用它们。代码实现中涉及了递归调用。组合模式与传统上的“类与类之间的组合关系”没有关联&#xff0c;不…

『大模型笔记』IBM技术团队:什么是智能体型RAG!

『大模型笔记』IBM技术团队:什么是智能体型RAG! 文章目录 一. 『大模型笔记』IBM技术团队:什么是智能体型RAG!二. 参考文献一. 『大模型笔记』IBM技术团队:什么是智能体型RAG! ✅检索增强生成(RAG)是一种结合检索和生成能力的技术,通过从向量数据库检索相关信息作为上…

快速傅里叶变换(FFT)基础(附python实现)

对于非专业人士&#xff0c;傅里叶变换一直是一个神秘的武器&#xff0c;它可以分析出不同频域的信息&#xff0c;从时域转换到频域&#xff0c;揭示了信号的频率成分&#xff0c;对于数字信号处理&#xff08;DSP&#xff09;、图像、语音等数据来说&#xff0c;傅里叶变换是最…

丹摩征文活动|新手入门指南

在AI大模型发展的今天&#xff0c;高性能计算平台已经成为研究和应用领域中不可或缺的工具。丹摩智算平台专注于为用户提供强大的算力支持和便捷的操作流程&#xff0c;帮助研究者和开发者更高效地训练和优化AI模型。本教程将深入介绍丹摩智算平台的核心功能及具体操作步骤&…

Java项目实战II基于Spring Boot的便利店信息管理系统(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在快节奏的…

【VScode】VScode内的ChatGPT插件——CodeMoss全解析与实用教程

在当今快速发展的编程世界中&#xff0c;开发者们面临着越来越多的挑战。如何提高编程效率&#xff0c;如何快速获取解决方案&#xff0c;成为了每位开发者心中的疑问。今天&#xff0c;我们将深入探讨一款颠覆传统编程体验的插件——CodeMoss&#xff0c;它将ChatGPT的强大功能…

数据冒险-dadd,sub和and

从图中的流水线执行情况来看&#xff0c;我们可以分析指令之间的依赖关系。图中每条指令对应的执行阶段标注为 IF (取指令)&#xff0c;ID (指令译码)&#xff0c;EX (执行)&#xff0c;Mem (访存)&#xff0c;和 WB (写回)。以下是对每条指令依赖情况的分析&#xff1a; 第一条…

如何修改WordPress经典编辑器的默认高度?

boke112百科有一个使用WordPress搭建的小网站&#xff0c;文章内容就是几个字不到一行&#xff0c;但是每次使用经典编辑器编辑文章时&#xff0c;都觉得编辑器默认高度太高了&#xff0c;影响了我添加文章摘要和其他属性&#xff0c;有没有办法修改WordPress经典编辑器的默认高…