[Java·算法·中等]LeetCode39. 组合总和
每天一题,防止痴呆
- 题目
- 示例
- 分析思路1
- 题解1
- 分析思路2
- 题解2
👉️ 力扣原文
题目
给你一个 无重复元素 的整数数组 candidates
和一个目标整数 target
,找出 candidates
中可以使数字和为目标数 target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target
的不同组合数少于 150 个。
示例
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
输入: candidates = [2], target = 1
输出: []
分析思路1
使用回溯算法:
使用了一个 start 变量来避免重复搜索。每次迭代从 start 开始,而不是从0开始。这是因为我们不需要在同一层次上搜索相同的元素,这会导致重复组合的出现。
此外,我们还进行了剪枝操作,即当候选数大于目标数时,我们停止搜索。这可以大大减少搜索空间,提高代码效率。
最后,我们使用了一个 result 列表来存储所有找到的组合。每当找到一个组合时,我们将其添加到结果列表中。
题解1
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();List<Integer> temp = new ArrayList<>();Arrays.sort(candidates); // 排序,便于剪枝backtrack(candidates, target, 0, temp, result);return result;}private void backtrack(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> result) {if (target < 0) {return;}if (target == 0) {result.add(new ArrayList<>(temp));return;}for (int i = start; i < candidates.length; i++) {if (candidates[i] > target) { // 剪枝break;}temp.add(candidates[i]);backtrack(candidates, target - candidates[i], i, temp, result); // 注意这里传入的参数temp.remove(temp.size() - 1);}}
}
执行结果
分析思路2
动态规划:
使用了一个二维数组 dp 来存储中间结果,其中 dp[i] 表示数字和为 i 时的所有组合。初始时,dp[0] 存储一个空列表,表示数字和为 0 时只有一种组合,即不选任何数字。
接下来,对于每个数字 candidates[i],从 candidates[i] 开始枚举数字和 j,如果 dp[j - candidates[i]] 不为空,则将 dp[j - candidates[i]] 中的每个组合都加上 candidates[i],得到一个新的组合,将其加入到 dp[j] 中。这样,当枚举到 target 时,dp[target] 中存储的就是所有符合要求的组合。
最后,如果 dp[target] 为空,则返回一个空列表,否则返回 dp[target]。
题解2
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>>[] dp = new List[target + 1];dp[0] = new ArrayList<>();dp[0].add(new ArrayList<>());for (int i = 0; i < candidates.length; i++) {for (int j = candidates[i]; j <= target; j++) {if (dp[j - candidates[i]] != null) {if (dp[j] == null) {dp[j] = new ArrayList<>();}for (List<Integer> list : dp[j - candidates[i]]) {List<Integer> temp = new ArrayList<>(list);temp.add(candidates[i]);dp[j].add(temp);}}}}return dp[target] == null ? new ArrayList<>() : dp[target];}
}
执行结果
相关文章:
[Java·算法·中等]LeetCode39. 组合总和
每天一题,防止痴呆题目示例分析思路1题解1分析思路2题解2👉️ 力扣原文 题目 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形…...
【Linux】vi和vim编辑器
目录主题主题 三种常见模式: 正常模式 以vim 打开一个档案就直接进入一般模式了(这是默认的模式)。在这个模式中,你可以使用[上下左右]按键来移动光标,你可以使用『删除字符』或『删除整行』来处理档案内容,也可以使用「复制、…...
BIO,NIO,AIO
IO模型 用什么样的通道进行数据传输和接收,java支持3种io网络编程模式 BIO NIO AIO BIO 同步阻塞 一个客户端连接对应一个处理线程 BIO示例代码(客户端和服务端) package com.tuling.bio;import java.io.IOException; import java.net.So…...
代码随想录刷题-数组-有序数组的平方
文章目录有序数组的平方习题暴力排序双指针有序数组的平方 本节对应代码随想录中:代码随想录,讲解视频:有序数组的平方_哔哩哔哩_bilibili 习题 题目链接:977. 有序数组的平方 - 力扣(LeetCode) 给你一…...
【玩转c++】stack和queue的介绍和模拟实现
本期主题:list的讲解和模拟实现博客主页: 小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限,出现错误希望大家不吝赐stack的介绍和使用1.1.stack的介绍1. stack是一种容器适配器,专门用在具有后进先出操作的上…...
Linux order(文件、磁盘、网络、系统管理、备份压缩)
1. Linux 文件命令 -rwxrwxrwx chmod:change mode,用于(文件所有者或 root )变更用户(u:owner g:group o:other a:all)的权限 chmod [OPTION]… MODE[,MODE]… FILE… OPTION -R:递归修改more option:chmod…...
最详细的CentOS7安装Mysql数据库服务
1.查看是否安装mysql: rpm -qa | grep mysql如果有查出来东西,使用命令删除: rpm -e xxx2.检查是否有mysql用户组和mysql用户,没有就添加有就忽略: groups mysql 添加用户组和用户 groupadd mysql && useradd -r -g mysql mysql&a…...
【IoT】项目管理:如何做好端到端的项目管理?
今天主要来谈谈项目管理这个话题。 首先来看一个我在网络上看到的一个关于项目管理的案例或者是段子。 将项目管理的作用及意义非常直观地展示了出来。 有一个植树搞绿化的企业,在公司内部设置有五个部门,分别是: 运输部门;挖坑部…...
渲染十万条数据就把你难住了?不存在的!
虚拟列表的使用场景如果我想要在网页中放大量的列表项,纯渲染的话,对于浏览器性能将会是个极大的挑战,会造成滚动卡顿,整体体验非常不好,主要有以下问题:页面等待时间极长,用户体验差CPU计算能力…...
编程学习的心路历程和困惑回顾
回首入行9年的经历,从大一开始学习C语言和数据结构,老师一直是在用IDE演示程序的编写和运行,我们也就一直在跟黑乎乎的命令行窗口打交道。 后来在一些课程的实验环节,接触到了一些别人编写好的工程代码,知道了Makefile…...
请介绍类加载过程,什么是双亲委派模型?
第23讲 | 请介绍类加载过程,什么是双亲委派模型? Java 通过引入字节码和 JVM 机制,提供了强大的跨平台能力,理解 Java 的类加载机制是深入 Java 开发的必要条件,也是个面试考察热点。 今天我要问你的问题是࿰…...
Navisworks编辑材质和Revit快速切换材质问题
一、如何在Navisworks2016中编辑材质 初次使用NW2016-2017时发现,原来用于创建编辑材质的小地球不见了,如图1所示,在各大技术群里求助没有回应,度娘搜索也总是摇头。 经过仔细排查可能出现的地方,终于找到了可以编辑材…...
Object对象键值的输出循序到底如何排列的?
1.日常摸鱼看八股 今天又是复习八股文的一天,发现还是彻底懂得原理才好和面试官吹牛批呀。 接着来看看我chat大宝贝的回答: 在现代浏览器中,Object 对象的键值输出循序是比较稳定的,通常是按照如下顺序输出: 所有的数…...
气泡式水位计的安装方法详解
气泡水位计的安装实际上就是气管的安装,气管的安装是否正确将直接影响到仪器测量数据的结果,气泡水位计它由活塞泵产生的压缩空气流经测量管和气泡室,进入被测的水体中,测量管中的静压力与气泡室上的水位高度成正比。那么接下来就…...
求“二维随机变量的期望E(X)与方差D(X)”例题(一)
离散型 设随机变量(X,Y)的联合分布律为 X\Y0100.10.210.30.4 (1)求E(X) 先求x的边缘分布律,表格里x0的概率为0.10.2,于是我们可得 X01P0.30.7直接求E(X)即可,得到结果 (2)求E(XY) 直接x与y相乘就行。 记得别乘多了,别的算了又…...
MySQL 搞定行转列,列转行
行转列方法总结1、使用case…when…then2、使用SUM(IF()) 生成列3、使用SUM(IF()) 生成列 WITH ROLLUP 生成汇总行4、使用SUM(IF()) 生成列 UNION 生成汇总行,并利用 IFNULL将汇总行标题显示为 Total5、使用SUM(IF()) 生成列,直接生成汇总结果,不再利用…...
正点原子裸机开发之C语言点灯程序
一. 简介 本文针对 IMX6ULL 的裸机开发的(即不带Linux操作系统的开发)。 主要分两部分的工作: 1. 配置 C语言运行环境 2. C 语言编写及运行 二. 配置C语言运行环境 配置 C 语言运行环境的工作分 三部分。如下: 1. 设置…...
cv::阈值分割OTUS原理+代码
opencv库的阈值分割分为全局分割和局部分割全局分割:普通分割ret1,th1 cv2.threshold(img,127, 255, cv2.THRESH_BINARY) #127为阈值 #cv2.THRESH_BINARY |cv2.THRESH_BINARY_INV | cv2.THRESH_TRUNC|cv2.THRESH_TOZERO|cv2.THRESH_TOZERO_INV局部分割:…...
Postgresql-12.5 visual studio-2022 windows 添加pg工程并调试
pg内核学习,记录一下 文章目录安装包编译安装VS添加Postgresql工程调试源码安装包 (1)perl下载 https://www.perl.org/get.html (2)diff下载 http://gnuwin32.sourceforge.net/packages/diffutils.htm (…...
长沙学院2023 第一次蓝桥训练题解
每道题都在洛谷上,每个题都有很详细的题解,可以先自行做,不会再看题解。 题目解析思路都写在代码中,中文题面就不单独解释题意了。 P2440 木材加工(二分答案) 链接:P2440 木材加工 解析 代码…...
云端Docker搭建ABY库以及本地CLion使用
文章目录ABY的搭建以及使用前言ABY库的下载、安装及测试CLion配置后续杂项项目改名使用其他的库最后ABY的搭建以及使用 前言 仅做记录,仅供参考,不同人有不同的使用方式命令手敲,可能有错,自己辨识勿问,我懂的也不多…...
ES6-箭头函数、解构赋值、对象简写
箭头函数特点 1、 (只有1个形参) 可以省略() 2、 {} 可以省略 只有一句代码 或 只有返回值的时候,省略return 3、arguments 不可用,arguments在没有形参的时候可以拿到调用函数拿在的实参 获取伪数组通过Array.from转为真数组。 4、 箭头函数没有this, …...
【CSS】CSS 背景设置 ② ( 背景位置 | 背景位置-方位值设置 )
文章目录一、背景位置1、语法说明2、注意事项二、背景位置-方位值设置1、效果展示2、完整代码示例一、背景位置 1、语法说明 如果 盒子的大小 大于 背景图片的大小 , 默认的 图片 位置是 左上角 ; 设置背景位置的 CSS 语法如下 : background-position : length length backgro…...
HTML 扫盲
✏️作者:银河罐头 📋系列专栏:JavaEE 🌲“种一棵树最好的时间是十年前,其次是现在” 目录前言HTML 结构快速生成代码框架HTML 常见标签注释标签标题标签: h1-h6段落标签:p换行标签:br格式化标签…...
项目中用到的责任链模式
目录 1.什么是责任链?它的原理是什么? 2.应用场景 3.项目中的应用 传送门:策略模式,工作中你用上了吗? 1.什么是责任链?它的原理是什么? 将请求的发送和接收解耦,让多个接收对象…...
C++复习笔记--STL的string容器和vector容器
1--string容器string 本质上是一个类,其不同于指针 char*,string 类的内部封装了 char*,用于管理字符串,是一个 char* 型的容器;1-1--string构造函数string 的构造函数原型:string(); // 创建一个空的字符串…...
第一章 软件项目管理概述
项目(Project)是为了创造一个唯一的产品或提供一个唯一的服务而进行的临时性的努力。项目的特征PMBOK(A guide to the Project management Body Of Knowledge:项目管理知识体系指南)五大过程组和十大知识领域从时间角度出发,项目管理分为五大过程组:启动…...
【Linux系统编程】06:共享内存
共享内存 OVERVIEW共享内存一、文件上锁flock二、共享内存1.关联共享内存ftok2.获取共享内存shmget3.绑定共享内存shmat4.绑定分离shmdt5.控制共享内存shmctl三、亲缘进程间通信1.共享内存写入与读取2.共享内存解绑与删除3.共享内存综合四、非亲缘进程间通信1.通过sleep同步2.通…...
【专项】112. 路径总和
112. 路径总和 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。 叶子节点 …...
【数据结构】堆排序
堆是一种叫做完全二叉树的数据结构,可以分为大根堆,小根堆,而堆排序就是基于这种结构而产生的一种程序算法。大堆:每个节点的值都大于或者等于他的左右孩子节点的值小堆:每个结点的值都小于或等于其左孩子和右孩子结点…...
论文阅读笔记《GAMnet: Robust Feature Matching via Graph Adversarial-Matching Network》
核心思想 本文提出一种基于图对抗神经网络的图匹配算法(GAMnet),使用图神经网络作为生成器分别生成源图和目标图的节点的特征,并用一个多层感知机作为辨别器来区分两个特征是否来自同一个图,通过对抗训练的办法提高生成器特征提取…...
数据安全—数据完整性校验
1、数据安全保障三要素即 保密性 完整性、可用性机密性:要求数据不被他人轻易获取,需要进行数据加密。完整性:要求数据不被他人随意修改,需要进行签名技术可用性:要求服务不被他人恶意攻击,需要进行数据校验…...
Java 最小路径和
最小路径和中等给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明:每次只能向下或者向右移动一步。示例 1:输入:grid [[1,3,1],[1,5,1],[4,2,1]]输出&…...
Flask+VUE前后端分离的登入注册系统实现
首先Pycharm创建一个Flask项目: Flask连接数据库需要下载的包: pip install -U flask-cors pip install flask-sqlalchemy Flask 连接和操作Mysql数据库 - 王滚滚啊 - 博客园 (cnblogs.com) sqlAlchemy基本使用 - 简书 (jianshu.com) FlaskVue前后端分…...
【Go】用Go在命令行输出好看的表格
用Go在命令行输出好看的表格前言正文生成Table表头设置插入行表格标题自动标号单元格合并列合并行合并样式设置居中设置数字自动高亮标红完整Demo代码结语前言 最近在写一些运维小工具,比如批量进行ping包的工具,实现不困难,反正就是ping&am…...
怎么处理消息重发的问题?
消息队列在消息传递的过程中,如果出现传递失败的情况,发送方会重试,在重试的过程中,可能会产生重复的消息。 消息重复的情况必然存在 关于传递消息时能够提供的服务质量标准,MQTT协议给出了三种不同的标准࿱…...
JVM 运行时数据区(数据区组成表述,程序计数器,java虚拟机栈,本地方法栈)
JVM 运行时数据区JVM 运行时数据区3.1运行时的数据区组成概述3.1.1程度计数器3.1.2java虚拟机栈3.1.3本地方法栈3.1.4java堆3.1.5方法区3.2程序计数器3.3java虚拟机栈3.4本地方法栈JVM 运行时数据区 堆,方法区(元空间) 主要用来存放数据 是线程共享的. 程序计数器,本地方法栈…...
Oracle ASM磁盘组配置、日常运维、故障处理等操作资料汇总
ASM(自动存储管理)在数据库中是非常重要的组成部分,它可以为磁盘提供统一的存储管理、提高磁盘访问的性能和可用性、简化管理复杂度,从而为数据库的运行提供更好的支持。这里就为大家整理了墨天轮数据社区上一些ASM相关基础知识、…...
java对象的创建与内存分配机制
文章目录对象的创建与内存分配机制对象的创建类加载检查分配内存初始化零值设置对象头指向init方法其他:指针压缩对象内存分配对象在栈上分配对象在Eden区中分配大对象直接分配到老年代长期存活的对象进入老年代对象动态年龄判断老年代空间分配担保机制对象的内存回…...
本地存储localStorage、sessionStorage
目录 一、localStorage 二、sessionStorage 三、本地存储处理复杂数据 一、localStorage 介绍 (1)数据存储在用户浏览器中 (2)设置、读取方便、甚至页面刷新不会丢失数据 (3)容量较大,se…...
JavaSE: 网络编程
1.1 概述java程序员面对统一的网络编程环境B/S 架构 和 C/S架构1.2 网络通信的两个要素通信双方的地址:ip 端口号网络通信协议:TCP/IP协议(事实上的国际规则)、OSI模型(理想化)1.3 Inet Address本地回环地…...
计算机图形学09:二维观察之点的裁剪
作者:非妃是公主 专栏:《计算机图形学》 博客地址:https://blog.csdn.net/myf_666 个性签:顺境不惰,逆境不馁,以心制境,万事可成。——曾国藩 文章目录专栏推荐专栏系列文章序一、二维观察基本…...
2023Java 并发编程面试题
Java 并发编程 1、在 java 中守护线程和本地线程区别? java 中的线程分为两种:守护线程(Daemon)和用户线程(User)。任何线程都可以设置为守护线程和用户线程,通过方法Thread.setDaemon(boolon…...
CAD如何绘制A0/A1/A2/A3/A4图框?
在CAD制图时,设计师一般会使用企业的定制图框模板或者个人的特色图框模板,让设计方案更加标准化、规范化。对于新人设计师而言,完成CAD制图已经非常头疼了,图框的绘制更是手忙脚乱。那么是否有更加高效的方式来完成A0、A1、A2、A3…...
R 安装 “umap-learn“ python 包
首先需要在R中下载并读取reticulate包,该包提供了一系列R-Python的交互式命令由于之前在电脑中通过三个方式安装了Python:直接安装 Python 3.10安装Anaconda,携带3.9安装 Miniconda,又是另外一个版本的Python版本各不相同…...
测试同学如何快速开发测试平台?
转眼已经好几个月没有发表什么文章了,因为疫情原因,大家工作都不怎么顺利,没有什么心情。再者,最近一直在搞移动端精准测试的项目,有太多技术难点需要攻克。从各个网站上都找不到解决方案,只能不断地尝试&a…...
【程序员接口百宝箱】免费常用API接口
一、短信发送 短信的应用可以说是非常的广泛了,短信API也是当下非常热门的API~ 短信验证码:可用于登录、注册、找回密码、支付认证等等应用场景。支持三大运营商,3秒可达,99.99%到达率,支持大容量高并发。…...
使数组和能被P整除[同余定理+同余定理变形]
同余定理同余定理变形前言一、使数组和能被P整除二、同余定理变形总结参考资料前言 同余定理非常经典,采用前缀和 map,当两个余数前缀和为一个值时,则中间一段子数组刚好对P整除。但是能否找到前面是否有一段子数组和可以对P整除呐…...
25k的Java开发常问的Synchronized问题有哪些?
前言:面试高频的Synchronized问题大多集中在应用场景、底层实现原理、锁的升级过程。 文章目录 Synchronized定义应用场景对象加锁实现原理JDK6以前JDK6版本及以后对象从无锁到偏向锁转化的过程(大概讲五分钟)轻量级锁升级的过程(大概讲五分钟)自旋锁策略(大概讲五分钟)…...
ES增量同步方案
1 基于业务代码嵌入式的增量同步方式在Java业务代码要修改业务数据的地方,增加调用写入ES数据的方法优点:1、实现方式简单,可控粒度高;2、不依赖第三方数据同步框架;3、数据库不用做特殊配置和部署;缺点&am…...