当前位置: 首页 > 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 木材加工 解析 代码…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

微信小程序之bind和catch

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

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...