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

每日一题8.10 lc39

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
输出: []

这道题我用递归写的,当然我觉得递归绝对不算是最优解。因为这道题目与一般递归的不同在于,它的数字可以重复出现但是相同元素的数组却不能重复出现,这就导致一个问题,即我们不能通过标记该数字是否出现来进行排除,因为所有数字都有可能再度被引用,而不能排除则会导致重复数组的出现,如第一个例子中会出现2,2,3以及2,3,2的重复答案。

要解决这个问题最好的办法就是先进行排序(ps.数组先排序在绝大多数情况都能大大简化骤),然后记录每一步的开始位置,例如循环从2开始则下一步的递归也从2开始。因为我们已经将数组排序好了,所以所有已经过循环的数字都可以确定为不会再使用。

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> list = new ArrayList<>();Stack<Integer> stack = new Stack<>();Arrays.sort(candidates);dfs(list,stack,candidates,target,0);return list;}public static void dfs(List<List<Integer>> list, Stack<Integer> stack,int[] nums,int target,int begin){int temp = target;if (temp==0){list.add(new ArrayList<>(stack));return;}for (int i=begin;i<nums.length;i++){if(temp-nums[i]<0)break;temp=temp-nums[i];stack.push(nums[i]);if (temp>=0){dfs(list,stack,nums,temp,i);}stack.pop();temp+=nums[i];}}
}

相关文章:

每日一题8.10 lc39

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

贝叶斯深度学习的温和介绍

一、说明 欢迎来到令人兴奋的概率编程世界&#xff01;本文是对这个领域的温和介绍&#xff0c;你只需要对深度学习和贝叶斯统计有一个基本的了解。如果像我一样&#xff0c;你听说过贝叶斯深度学习&#xff0c;并且你猜它涉及贝叶斯统计&#xff0c;但你不知道它是如何使用的&…...

无涯教程-Perl - glob函数

描述 此函数返回与EXPR匹配的文件的列表,这些文件将由标准Bourne shell进行扩展。如果EXPR未指定路径,请使用当前目录。如果省略EXPR,则使用$_的值。 从Perl 5.6开始,扩展是在内部完成的,而不是使用外部脚本。扩展遵循csh(以及任何派生形式,包括tcsh和bash)的扩展方式,其翻译…...

前端先行模拟接口(mock+expres+json)

目录 mock模拟数据&#xff1a;data/static.js 路由&#xff1a;index.js 服务器&#xff1a;server.js yarn /node 启动服务器&#xff1a;yarn start 客户端&#xff1a;修改代理路径(修改设置后都要重启才生效) 示例 后端框架express构建服务器 前端发起请求 静态数…...

老师如何制作学生分班信息查询系统?

即将迎来新学期的开始&#xff01;学校和老师们将忙于为我们可爱的学生做分班准备。如果有一个强大的分班查询系统&#xff0c;学生们就可以提前知道自己被分到哪个班级&#xff0c;有哪些课程&#xff0c;以及班主任是谁&#xff01; 别担心&#xff0c;我将教你如何设计一个…...

Java实战:高效提取PDF文件指定坐标的文本内容

前言 临时接到一个紧急需要处理的事项。业务侧一个同事有几千个PDF文件需要整理&#xff1a;需要从文件中的指定位置获取对应的编号和地址。 要的急&#xff0c;工作量大。所以就问到技术部有没有好的解决方案。 问技术的话就只能写个demo跑下了。 解决办法 1. 研究下PDF文档…...

centos磁盘满了,怎么清理大文件

当CentOS磁盘空间不足时&#xff0c;可以通过以下步骤清理大文件&#xff1a; 确定磁盘使用情况&#xff1a;运行以下命令查看磁盘使用情况和占用空间最大的文件或目录&#xff1a; df -h du -sh /*清理临时文件&#xff1a;运行以下命令清理临时文件夹中的过期数据&#xff…...

AIGC:【LLM(四)】——LangChain+ChatGLM:本地知识库问答方案

文章目录 一.文件加载与分割二.文本向量化与存储1.文本向量化(embedding)2.存储到向量数据库 三.问句向量化四.相似文档检索五.prompt构建六.答案生成 LangChainChatGLM项目(https://github.com/chatchat-space/langchain-ChatGLM)实现原理如下图所示 (与基于文档的问答 大同小…...

企业在线产品手册可以这样做,小白也能轻松上手

企业在线产品手册是为了方便用户了解和使用企业产品而设计的一种在线文档。它的目标是提供清晰、简洁、易于理解的产品信息&#xff0c;使用户能够轻松上手&#xff0c;并最大限度地发挥产品的功能和优势。 如何设计企业在线产品手册的建议和步骤&#xff1a; 目标用户分析&am…...

crypto-js中AES的加解密封装

在项目中安装依赖&#xff1a; npm i crypto-js在使用的页面引入&#xff1a; import CryptoJS from crypto-jscrypto-js中AES的加解密简单的封装了一下&#xff1a; //加密const KEY 000102030405060708090a0b0c0d0e0f // 秘钥 这两个需要和后端统一const IV 8a8c8fd8fe3…...

【计算机视觉】MoCo v2 讲解

在阅读本篇之前建议先学习: 【计算机视觉】MoCo 讲解 【计算机视觉】SimCLR 讲解 MoCo v2 论文信息 标题:Improved Baselines with Momentum Contrastive Learning 作者:Xinlei Chen 期刊: 发布时间与更新时间:2020.03.09 主题:计算机视觉、对比学习 arXiv:[2003.04297]…...

如何解决亚马逊银行账户验证问题?来看看这些技巧吧!

在开亚马逊店铺的过程中&#xff0c;想必不少卖家遇到了这么一个问题&#xff0c;那就是亚马逊卖家有的时候会收到亚马逊银行账户验证的消息&#xff0c;主要就是用来确保亚马逊卖家账户收款信息的安全性。 亚马逊银行账户验证是一个十分重要的问题&#xff0c;如果说这些问题…...

Android多渠道打包+自动签名工具 [原创]

多渠道打包自动签名工具 [原创] github源码&#xff1a;github.com/G452/apk-packer 如果觉得有帮助可以点个小星星支持一下&#xff0c;万分感谢&#xff01; 使用步骤&#xff1a; 1、在apk-packer.exe目录内放入打包需要的配置&#xff1a; 1&#xff09;签名文件.jks2&am…...

nodejs实现解析chm文件列表,无需转换为PDF文件格式,在线预览chm文件以及目录,不依赖任何网页端插件

特性: 1、支持任意深度的chm文件解析 2、解析后内容结构转换为tree数据呈现 3、点击树节点可以在html实时查看数据 4、不依赖任何浏览器端插件,兼容性较好 nodejs端核心代码 const $g = global.SG.$g, fs = global.SG.fs, router = global.SG.router, xlsx = global.SG.xl…...

.net core background service

之前聊过如何在.net core 中添加后台服务, 当时使用的是BackgroundService的形式&#xff0c;这里使用IHostedService接口 namespace oneModelMultiTable.BackgroundService {public class EllisTest : IHostedService, IDisposable{private readonly ILogger<EllisTest>…...

前端开发的工作职责精选【10篇】

前端开发的工作职责1 1、使用Divcss并结合Javascript负责产品的前端开发和页面制作; 2、熟悉W3C标准和各主流浏览器在前端开发中的差异&#xff0c;能熟练运用DIVCSS&#xff0c;提供针对不同浏览器的前端页面解决方案; 3、负责相关产品的需求以及前端程序的实现&#xff0c…...

SpringBoot 升级内嵌Tomcat

SpringBoot 更新 Tomcat 最近公司的一个老项目需要升级下Tomcat&#xff0c;由于这个项目我完全没有参与&#xff0c;所以一开始我以为是一个老的Tomcat项目&#xff0c;升级它的Tomcat依赖或者是Tomcat容器镜像&#xff0c;后面发现是一个SpringBoot项目&#xff0c;升级的是…...

react搭建在线编辑html的站点——引入grapes实现在线拖拉拽编辑html

文章目录 ⭐前言⭐搭建react ts项目⭐引入grapes 插件⭐结束 ⭐前言 大家好&#xff0c;我是yma16&#xff0c;本文分享关于react搭建在线编辑html的站点。 react 发展历史 React是由Facebook开发的一种JavaScript库&#xff0c;用于构建用户界面。React最初发布于2013年&…...

Nginx反向代理服务配置和负载均衡配置

nginx反向代理服务配置 node1&#xff1a;128 node2&#xff1a;135 node3&#xff1a;130 node4&#xff1a;132 node2、node3、node4已安装nginx nginx安装可查看https://blog.csdn.net/HealerCCX/article/details/132089836?spm1001.2014.3001.5502 [rootnode3 ~]# yum i…...

react钩子函数理解

React钩子&#xff08;Hooks&#xff09;是React 16.8版本引入的一种特性&#xff0c;用于在无需编写类组件的情况下&#xff0c;在函数组件中添加状态管理和其他React特性。React钩子解决了函数组件在处理状态、副作用和代码复用方面的一些问题&#xff0c;使得代码更加清晰、…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...