当前位置: 首页 > 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;使得代码更加清晰、…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...