当前位置: 首页 > news >正文

[Java·算法·中等]LeetCode39. 组合总和

每天一题,防止痴呆

  • 题目
  • 示例
  • 分析思路1
  • 题解1
  • 分析思路2
  • 题解2

👉️ 力扣原文

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
23 可以形成一组候选,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. 组合总和

每天一题&#xff0c;防止痴呆题目示例分析思路1题解1分析思路2题解2&#x1f449;️ 力扣原文 题目 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形…...

【Linux】vi和vim编辑器

目录主题主题 三种常见模式&#xff1a; 正常模式 以vim 打开一个档案就直接进入一般模式了(这是默认的模式)。在这个模式中&#xff0c;你可以使用[上下左右]按键来移动光标&#xff0c;你可以使用『删除字符』或『删除整行』来处理档案内容&#xff0c;也可以使用「复制、…...

BIO,NIO,AIO

IO模型 用什么样的通道进行数据传输和接收&#xff0c;java支持3种io网络编程模式 BIO NIO AIO BIO 同步阻塞 一个客户端连接对应一个处理线程 BIO示例代码&#xff08;客户端和服务端&#xff09; package com.tuling.bio;import java.io.IOException; import java.net.So…...

代码随想录刷题-数组-有序数组的平方

文章目录有序数组的平方习题暴力排序双指针有序数组的平方 本节对应代码随想录中&#xff1a;代码随想录&#xff0c;讲解视频&#xff1a;有序数组的平方_哔哩哔哩_bilibili 习题 题目链接&#xff1a;977. 有序数组的平方 - 力扣&#xff08;LeetCode&#xff09; 给你一…...

【玩转c++】stack和queue的介绍和模拟实现

本期主题&#xff1a;list的讲解和模拟实现博客主页&#xff1a; 小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限&#xff0c;出现错误希望大家不吝赐stack的介绍和使用1.1.stack的介绍1. stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上…...

Linux order(文件、磁盘、网络、系统管理、备份压缩)

1. Linux 文件命令 -rwxrwxrwx chmod&#xff1a;change mode&#xff0c;用于&#xff08;文件所有者或 root &#xff09;变更用户(u:owner g:group o:other a:all)的权限 chmod [OPTION]… MODE[,MODE]… FILE… OPTION -R&#xff1a;递归修改more option&#xff1a;chmod…...

最详细的CentOS7安装Mysql数据库服务

1.查看是否安装mysql: rpm -qa | grep mysql如果有查出来东西&#xff0c;使用命令删除&#xff1a; rpm -e xxx2.检查是否有mysql用户组和mysql用户,没有就添加有就忽略&#xff1a; groups mysql 添加用户组和用户 groupadd mysql && useradd -r -g mysql mysql&a…...

【IoT】项目管理:如何做好端到端的项目管理?

今天主要来谈谈项目管理这个话题。 首先来看一个我在网络上看到的一个关于项目管理的案例或者是段子。 将项目管理的作用及意义非常直观地展示了出来。 有一个植树搞绿化的企业&#xff0c;在公司内部设置有五个部门&#xff0c;分别是&#xff1a; 运输部门&#xff1b;挖坑部…...

渲染十万条数据就把你难住了?不存在的!

虚拟列表的使用场景如果我想要在网页中放大量的列表项&#xff0c;纯渲染的话&#xff0c;对于浏览器性能将会是个极大的挑战&#xff0c;会造成滚动卡顿&#xff0c;整体体验非常不好&#xff0c;主要有以下问题&#xff1a;页面等待时间极长&#xff0c;用户体验差CPU计算能力…...

编程学习的心路历程和困惑回顾

回首入行9年的经历&#xff0c;从大一开始学习C语言和数据结构&#xff0c;老师一直是在用IDE演示程序的编写和运行&#xff0c;我们也就一直在跟黑乎乎的命令行窗口打交道。 后来在一些课程的实验环节&#xff0c;接触到了一些别人编写好的工程代码&#xff0c;知道了Makefile…...

请介绍类加载过程,什么是双亲委派模型?

第23讲 | 请介绍类加载过程&#xff0c;什么是双亲委派模型&#xff1f; Java 通过引入字节码和 JVM 机制&#xff0c;提供了强大的跨平台能力&#xff0c;理解 Java 的类加载机制是深入 Java 开发的必要条件&#xff0c;也是个面试考察热点。 今天我要问你的问题是&#xff0…...

Navisworks编辑材质和Revit快速切换材质问题

一、如何在Navisworks2016中编辑材质 初次使用NW2016-2017时发现&#xff0c;原来用于创建编辑材质的小地球不见了&#xff0c;如图1所示&#xff0c;在各大技术群里求助没有回应&#xff0c;度娘搜索也总是摇头。 经过仔细排查可能出现的地方&#xff0c;终于找到了可以编辑材…...

Object对象键值的输出循序到底如何排列的?

1.日常摸鱼看八股 今天又是复习八股文的一天&#xff0c;发现还是彻底懂得原理才好和面试官吹牛批呀。 接着来看看我chat大宝贝的回答&#xff1a; 在现代浏览器中&#xff0c;Object 对象的键值输出循序是比较稳定的&#xff0c;通常是按照如下顺序输出&#xff1a; 所有的数…...

气泡式水位计的安装方法详解

气泡水位计的安装实际上就是气管的安装&#xff0c;气管的安装是否正确将直接影响到仪器测量数据的结果&#xff0c;气泡水位计它由活塞泵产生的压缩空气流经测量管和气泡室&#xff0c;进入被测的水体中&#xff0c;测量管中的静压力与气泡室上的水位高度成正比。那么接下来就…...

求“二维随机变量的期望E(X)与方差D(X)”例题(一)

离散型 设随机变量(X,Y)的联合分布律为 X\Y0100.10.210.30.4 (1)求E(X) 先求x的边缘分布律&#xff0c;表格里x0的概率为0.10.2&#xff0c;于是我们可得 X01P0.30.7直接求E(X)即可&#xff0c;得到结果 (2)求E(XY) 直接x与y相乘就行。 记得别乘多了&#xff0c;别的算了又…...

MySQL 搞定行转列,列转行

行转列方法总结1、使用case…when…then2、使用SUM(IF()) 生成列3、使用SUM(IF()) 生成列 WITH ROLLUP 生成汇总行4、使用SUM(IF()) 生成列 UNION 生成汇总行,并利用 IFNULL将汇总行标题显示为 Total5、使用SUM(IF()) 生成列&#xff0c;直接生成汇总结果&#xff0c;不再利用…...

正点原子裸机开发之C语言点灯程序

一. 简介 本文针对 IMX6ULL 的裸机开发的&#xff08;即不带Linux操作系统的开发&#xff09;。 主要分两部分的工作&#xff1a; 1. 配置 C语言运行环境 2. C 语言编写及运行 二. 配置C语言运行环境 配置 C 语言运行环境的工作分 三部分。如下&#xff1a; 1. 设置…...

cv::阈值分割OTUS原理+代码

opencv库的阈值分割分为全局分割和局部分割全局分割&#xff1a;普通分割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局部分割&#xff1a;…...

Postgresql-12.5 visual studio-2022 windows 添加pg工程并调试

pg内核学习&#xff0c;记录一下 文章目录安装包编译安装VS添加Postgresql工程调试源码安装包 &#xff08;1&#xff09;perl下载 https://www.perl.org/get.html &#xff08;2&#xff09;diff下载 http://gnuwin32.sourceforge.net/packages/diffutils.htm &#xff08;…...

长沙学院2023 第一次蓝桥训练题解

每道题都在洛谷上&#xff0c;每个题都有很详细的题解&#xff0c;可以先自行做&#xff0c;不会再看题解。 题目解析思路都写在代码中&#xff0c;中文题面就不单独解释题意了。 P2440 木材加工&#xff08;二分答案&#xff09; 链接&#xff1a;P2440 木材加工 解析 代码…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...