算法leetcode|39. 组合总和(rust重拳出击)
文章目录
- 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 <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同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 解华为机试题 | 机试宝典...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
