权威的手机网站制作/自己做网站的流程
文章目录
- 39. 组合总和:
- 样例 1:
- 样例 2:
- 样例 3:
- 提示:
- 分析:
- 题解:
- rust
- go
- c++
- c
- python
- java
39. 组合总和:
给你一个 无重复元素 的整数数组 candidates
和一个目标整数 target
,找出 candidates
中可以使数字和为目标数 target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target
的不同组合数少于 150
个。
样例 1:
输入:candidates = [2,3,6,7], target = 7输出:[[2,2,3],[7]]解释:2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选, 7 = 7 。仅有这两种组合。
样例 2:
输入: candidates = [2,3,5], target = 8输出: [[2,2,2,2],[2,3,3],[3,5]]
样例 3:
输入: candidates = [2], target = 1输出: []
提示:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates
的所有元素 互不相同1 <= target <= 40
分析:
- 面对这道算法题目,二当家的陷入了沉思。
- 遍历或者递归,递归比较直观,深度优先,回溯。
- 题目要求所有可能的组合,不能重复,本来是需要想办法去重的,但是题目规定参数中所有元素互不相同,那我们只要选择不同下标的组合就相当于选择了不同元素的组合。
题解:
rust
impl Solution {pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {fn dfs(candidates: &Vec<i32>, target: i32, idx: usize, row: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {if idx == candidates.len() {// 尝试到底,开始回溯return;}if target == 0 {// 符合条件的一个组合ans.push(row.clone());return;}if target >= candidates[idx] {// 选择当前下标数字row.push(candidates[idx]);dfs(candidates, target - candidates[idx], idx, row, ans);row.pop();}// 跳过当前下标数字dfs(candidates, target, idx + 1, row, ans);}let mut ans = Vec::new();dfs(&candidates, target, 0, &mut Vec::new(), &mut ans);return ans;}
}
go
func combinationSum(candidates []int, target int) [][]int {var ans [][]intvar dfs func(int, int, []int)dfs = func(target int, idx int, row []int) {if idx == len(candidates) {// 尝试到底,开始回溯return}if target == 0 {// 符合条件的一个组合ans = append(ans, append([]int{}, row...))return}// 选择当前下标数字if target >= candidates[idx] {row = append(row, candidates[idx])dfs(target-candidates[idx], idx, row)row = row[:len(row)-1]}// 跳过当前下标数字dfs(target, idx+1, row)}dfs(target, 0, []int{})return ans
}
c++
class Solution {
private:void dfs(vector<int>& candidates, int target, int idx, vector<int>& row, vector<vector<int>>& ans) {if (idx == candidates.size()) {// 尝试到底,开始回溯return;}if (target == 0) {// 符合条件的一个组合ans.emplace_back(row);return;}// 选择当前下标数字if (target >= candidates[idx]) {row.emplace_back(candidates[idx]);dfs(candidates, target - candidates[idx], idx, row, ans);row.pop_back();}// 跳过当前下标数字dfs(candidates, target, idx + 1, row, ans);}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> ans;vector<int> row;dfs(candidates, target, 0, row, ans);return ans;}
};
c
void dfs(int *candidates, int candidatesSize, int target, int idx, int *row, int rowSize, int **ans, int *returnSize,int **returnColumnSizes) {if (idx == candidatesSize) {// 尝试到底,开始回溯return;}if (target == 0) {// 符合条件的一个组合ans[*returnSize] = (int *) malloc(sizeof(int) * rowSize);memcpy(ans[*returnSize], row, sizeof(int) * rowSize);(*returnColumnSizes)[*returnSize] = rowSize;++(*returnSize);return;}// 选择当前下标数字if (target >= candidates[idx]) {row[rowSize] = candidates[idx];dfs(candidates, candidatesSize, target - candidates[idx], idx, row, rowSize + 1, ans, returnSize,returnColumnSizes);}// 跳过当前下标数字dfs(candidates, candidatesSize, target, idx + 1, row, rowSize, ans, returnSize, returnColumnSizes);
}/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int **combinationSum(int *candidates, int candidatesSize, int target, int *returnSize, int **returnColumnSizes) {*returnSize = 0;*returnColumnSizes = (int *) malloc(sizeof(int) * 150);int **ans = (int **) malloc(sizeof(int *) * 150);int row[target];dfs(candidates, candidatesSize, target, 0, row, 0, ans, returnSize, returnColumnSizes);return ans;
}
python
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:ans = []def dfs(target: int, idx: int, row: List[int]):if idx == len(candidates):# 尝试到底,开始回溯returnif target == 0:# 符合条件的一个组合ans.append(row.copy())return# 选择当前下标数字if target >= candidates[idx]:row.append(candidates[idx])dfs(target - candidates[idx], idx, row)row.pop()# 跳过当前下标数字dfs(target, idx + 1, row)dfs(target, 0, [])return ans
java
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>();this.dfs(candidates, target, 0, new LinkedList<>(), ans);return ans;}private void dfs(int[] candidates, int target, int idx, Deque<Integer> row, List<List<Integer>> ans) {if (idx == candidates.length) {// 尝试到底,开始回溯return;}if (target == 0) {// 符合条件的一个组合ans.add(new ArrayList<>(row));return;}if (target >= candidates[idx]) {// 选择当前下标数字row.addLast(candidates[idx]);this.dfs(candidates, target - candidates[idx], idx, row, ans);row.pollLast();}// 跳过当前下标数字this.dfs(candidates, target, idx + 1, row, ans);}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~
相关文章:

算法leetcode|39. 组合总和(rust重拳出击)
文章目录39. 组合总和:样例 1:样例 2:样例 3:提示:分析:题解:rustgoccpythonjava39. 组合总和: 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找…...

JavaSE学习笔记总结day18
今日内容 零、 复习昨日 一、作业 二、进程与线程 三、创建线程 四、线程的API 五、线程状态 六、线程同步 零、 复习昨日 晨考 一、作业 见答案 二、进程与线程[了解] 一个进程就是一个应用程序,进程包含线程 一个进程至少包含一个线程,大部分都是有多条线程在执行任务(多线…...

HybridFusion: LiDAR和视觉交叉源点云融合
一、基本信息 研究方向: 大场景点云配准 HybridFusion: 它可以在户外大型场景中从不同视角记录交叉源密集点云。 团队链接:http://www.adv-ci.com 视频链接: https://www.bilibili.com/video/BV1vM41147yD/?spm_id_from333.337.sear…...

走进JVM
JVM的位置 在操作系统之上,可以想象成一个软件,Java程序都运行在上面 JVM结构图 JVM调优的位置 99%的调优在堆中,极少数在方法区中 很多第三方插件都是在执行引擎那块地方做出修改而来,比如Lombook在程序运行时动态生成get/s…...

C语言-基础了解-15-C函数指针与回调函数
C函数指针与回调函数 一、函数指针 函数指针是指向函数的指针变量。 通常我们说的指针变量是指向一个整型、字符型或数组等变量,而函数指针是指向函数。 函数指针可以像一般函数一样,用于调用函数、传递参数。 函数指针变量的声明: type…...

react和vue在响应式上的不同理解
vue和react的区别总是被提及,关于这个问题最近也有了自己的想法。我认为它们之间最大的区别是对于响应数据变化的实现方式不同。 vue实现响应的方法是,首先收集依赖这个数据的副作用(视图更新、计算属性等),当数据修改…...

多线程二 多线程了解与使用
文章目录synchronized 锁有两种synchronized异常捕获主线程和子线程volatile的作用notify是随机启动等待线程中的一个synchronized 锁有两种 类对象类的实例 第一种:锁类对象,有两种方式,如下: // 方法一:synchroni…...

嵌入式 Linux 的僵尸进程是什么?
目录 1、什么是僵尸进程? 2、僵尸进程的目的 3、怎么避免僵尸进程? 4、僵尸进程的处理方法 4.1 wait()连接 4.2 waitpid()函数 1、什么是僵尸进程? 首先内核会释放终止进程(调用了 exit …...

【刷题笔记】笔记一
1.自守数牛客链接解析:1.自守数的结尾肯定是 0,1,5,62.把数字转换为string类(方便比较)3.直接find在s2 里面 使用find查找另一个即可。#include <iostream> #include<string> using namespace …...

浏览器主页被hao123劫持的解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。喜欢通过博客创作的方式对所学的知识进行总结与归纳,不仅形成深入且独到的理…...

华为OD机试题 - 热点网络统计(JavaScript)| 含代码编写思路
华为OD机试题 最近更新的博客使用说明本篇题解:热点网络统计题目输入输出描述示例一输入输出示例二输入输出Code解题思路华为OD其它语言版本最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华…...

IT项目经理的自我修养手册
在不断进步的时代,任何岗位职责都是一个责任、权力与义务的综合体,有多大的权力就应该承担多大的责任,有多大的权力和责任应该尽多大的义务,任何割裂开来的做法都会发生问题。那么作为IT项目经理的岗位职责,我大概列举…...

2023年软考中级电子商务设计师考什么?
首先,电子商务设计师属于软考中级,因此难度也不是特别大。但并不是说就完全没有难度,难度还是有的,像上午题一般把基本知识点掌握了,是没什么问题的,重点就在于下午题会比较难。 接下来我们来剖析一下考试…...

现在的00后太强了,几个问题差点给我问懵了
前言 我们公司刚入职一个00后小伙,今天在办公室交流了一下,他问我会不会自动化测试,我说懂一点,然后直接问了我几个自动化测试问题,差点直接给我问懵了! 问题如下: 我们在制定自动化测试实施…...

$3 : 水项目实战 - 水果库存系统
javase知识点复习: final关键字:http://t.csdn.cn/bvFgu 接口的定义,特性,实现,继承:http://t.csdn.cn/tbXl3 异常:http://t.csdn.cn/VlS0Z DAO的概念和角色(设计理念)&a…...

毕业设计 基于STM32单片机无线ZIGBEE智能大棚土壤湿度光照检测
基于STM32单片机无线ZIGBEE智能大棚土壤湿度光照检测1、项目简介1.1 系统构成1.2 系统功能2、部分电路设计2.1 STM32F103C8T6核心系统电路设计2.2 光敏采集电路设计2.3 温度采集电路设计3、部分代码展示3.1 读取DS18B20温度值3.2 定时器初始化1、项目简介 选题指导,…...

华为OD机试真题Java实现【相对开音节】真题+解题思路+代码(20222023)
相对开音节 题目 相对开音节构成的结构为辅音+元音(aeiou)+辅音(r除外)+e,常见的单词有bike、cake等。 给定一个字符串,以空格为分隔符,反转每个单词中的字母,若单词中包含如数字等其他非字母时不进行反转。 反转后计算其中含有相对开音节结构的子串个数(连续的子串…...

【C++】30h速成C++从入门到精通(STL容器listvector)
listlist的介绍list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。list与…...

操作系统---存储管理
存储管理 操作系统将外存的文件调入到内存中,以便CPU调用,如果调用的内容不在内存中,则会产生缺页中断;产生缺页中断后,这事需要从外存调数据到内存中,然后CPU接着从断点继续调用内存中的数据;在…...

华为OD机试题 - 好朋友(JavaScript)| 含思路
华为OD机试题 最近更新的博客使用说明本篇题解:好朋友题目输入输出示例一输入输出说明示例二输入输出说明Code解题思路华为OD其它语言版本最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典...

socket本地多进程通信基本使用方法和示例
目录 前言: socket是什么 socket基本原理框图 socket基本函数 1 socket() 函数 2 bind()函数 3 connect()函数 4 listen() 函数 5 accept() 函数 6 read() write() send() recv()函数 7 close()函数 8 字节序转换(hton) 示例代码 …...

Python 算法交易实验51 Step2 Signals 信号生成
说明 不可不读书 先从经典的一些超简单信号开始 使用移动平均指标SMA(算术) 给出了信号的产生方法,还有一些测算结果,反正看起来都是盈利的 首先使用离线方法实验一组结果,然后就使用ADBS来进行类似的处理。 内容 1 原理分析…...

app上架专用软著认证电子版权在主流应用商店的使用说明2023年最新版
软著认证电子版权在主流应用商店的使用说明 目录 一、 华为应用商店 二、 腾讯应用宝 三、 小米开放平台 小米应用提交: 小米游戏提交: 四、 OPPO开放平台 OPPO应用提交: OPPO游戏(App)提交: OPPO小游戏(快应…...

[Mybatis2]Mapper代理开发
文章目录 问题情境 代理开发 遵循的三条原则 1.定义与SQL映射文件同名的Mapper接口,并且将Mapper接口和SQL映射文件放置在同一目录下 2.设置SQL映射文件的namespace属性为Mapper接口的全限定名 3.在Mapper接口中定义方法,方法名就是SQL映射文件中sql…...

第十一届蓝桥杯大赛青少组国赛Python真题2
第十一届蓝桥杯大赛青少组Python 真题 第二题 提示信息: 杨辉三角形,是二项式系数在三角形中的一种几何排列。中国南宋数学家杨辉在 1261 年所著的《详 解九章算法》一书有明确记载。欧洲数学家帕斯卡在 1654 年发现这一规律,所以又叫做帕斯卡…...

创建springboot项目文件报红
目录 一、遇到问题 二、出现这个问题的原因 三、解决办法 三种方法 四、操作步骤 一、遇到问题 创建springboot项目的时候,会发现一些重要文件都变成红色了,但是不影响程序的运行。只是看起来会有点不舒服。 二、出现这个问题的原因 因为这个spr…...

gma 地理空间绘图:(1) 绘制简单的世界地图-3.设置地图框
内容回顾 gma 地理空间绘图:(1) 绘制简单的世界地图-1.地图绘制与细节调整 gma 地理空间绘图:(1) 绘制简单的世界地图-2.设置经纬网 方法 SetFrame(FrameColor ‘black’, FrameWidth 0.6, ShowFrame True, ShowLeft True, ShowBottom True, Sho…...

Java Web 实战 03 - 多线程基础(2)
Java Web 实战 03 - 多线程基础篇 2二 . Thread类常见方法2.1 Thread 的常见构造方法2.2 Thread 的几个常见属性getId()getName()getState()getPriority()isDaemon()案例 : 实现 getId()、getName()、 getState()、getPriority()、isDaemon()、isAlive()2.3 启动一个线程-start…...

Linux命令·cat
cat命令的用途是连接文件或标准输入并打印。这个命令常用来显示文件内容,或者将几个文件连接起来显示,或者从标准输入读取内容并显示,它常与重定向符号配合使用。 1.命令格式:cat [选项] [文件]...2.命令功…...

WPF WrapPanel、UniformGrid、DockPanel介绍
WPF WrapPanel、UniformGrid、DockPanel介绍 WrapPanel WrapPanel , 具有在有限的容器范围内, 可以自动换行, 或者换列处理。具体则取决于WrapPanel的排列方式 (Orientation)。 Orientation"Horizontal"时各控件从左至右罗列,当面板长度不够时ÿ…...