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

Leetcode 39 组合总和

题意理解:

        一个 无重复元素 的整数数组 candidates 和一个目标整数 target    

        从candidates 取数字,使其和== target ,有多少种组合(candidates 中的 同一个 数字可以 无限制重复被选取

        这道题和之前一道组合的区别:这道题允许重复的数字

解题思路

        组合问题——>递归

        这道题特殊的地方,对组合内数字的和做了要求,而不是个数,一开始并不确定树的深度,组合的大小是不定的。

1.暴力回溯+剪枝优化

class Solution {List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();int sum=0;public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates,target,0);return result;}public void backtracking(int[] candidates,int target,int index){//结果收集if(sum==target){result.add(new ArrayList<>(path));return;} else if (sum>target) {//剪枝return;}//遍历分支for(int i=index;i<candidates.length;i++){path.add(candidates[i]);sum+=candidates[i];//递归backtracking(candidates,target,i);//回溯path.removeLast();sum-=candidates[i];}}
}

2.分析

时间复杂度:O(n\times 2^{n})

        n个位置,每个位置有两种可能选或不选。

        时间复杂度和树的深度有关,是所有可行解之和

空间复杂度:O(n)

相关文章:

Leetcode 39 组合总和

题意理解&#xff1a; 一个 无重复元素 的整数数组 candidates 和一个目标整数 target 从candidates 取数字&#xff0c;使其和 target &#xff0c;有多少种组合&#xff08;candidates 中的 同一个 数字可以 无限制重复被选取&#xff09; 这道题和之前一道组合的区别&am…...

Windows下使用AndroidStudio及CMake编译Android可执行程序或静态库动态库

Windows下使用AndroidStudio及CMake编译Android可执行程序或静态库动态库 文章目录 Windows下使用AndroidStudio及CMake编译Android可执行程序或静态库动态库一、前言二、编译环境三、示例C/CPP程序1、总体工程结构2、示例代码3、CMakeLists.txt&#xff08;重要&#xff09;4、…...

MySQL七 | 存储引擎

目录 存储引擎 存储引擎特点 存储引擎选择 Innodb与MyISAM区别 存储引擎 默认存储引擎:InnoDB show engines;#展示当前数据库支持的存储引擎 存储引擎特点 特点InnoDBMyISAMMemory存储限制64TB有有事务安全支持--锁机制行锁表锁表锁Btree锁支持支持 支持 Hash索引--支…...

网上下载的pdf文件,为什么不能复制文字?

不知道大家有没有到过这种情况&#xff1f;在网上下载的PDF文件打开之后&#xff0c;发现选中文字之后无法复制。甚至其他功能也都无法使用&#xff0c;这是怎么回事&#xff1f;该怎么办&#xff1f; 当我们发现文件打开之后&#xff0c;编辑功能无法使用&#xff0c;很可能是…...

Linux下apisix离线安装教程

Linux下apisix离线安装教程 一、首先需要安装etcd&#xff1a;二、通过rpm离线安装apisix三、启动apisix四、安装apisix-dashboard1、安装2、更改dashboard登录账号名和密码3、运行 一、首先需要安装etcd&#xff1a; 解压缩etcd后执行以下命令&#xff1a; tar -xvf etcd-v3.…...

基于STM32 + DMA介绍,应用和步骤详解(ADC多通道)

前言 本篇博客主要学习了解DMA的工作原理和部分寄存器解析&#xff0c;针对ADC多通道来对代码部分&#xff0c;应用部分作详细讲解&#xff0c;掌握代码编程原理。本篇博客大部分是自己收集和整理&#xff0c;如有侵权请联系我删除。 本次博客开发板使用的是正点原子精英版&am…...

openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断

文章目录 openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断144.1 背景信息144.2 前提条件 openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断 144.1 背景信息 在SQL语句执行性能不符合预期时&#xff0c;可以查看SQL语句执行信息&#xff0c;便…...

计算机毕业设计springboot+ssm停车场车位预约系统java

管理员不可以注册账号 停车位包括车位所在楼层、车位编号、车位类型(全时间开放/高峰期开放)、预定状态等 用户预约时要求支付预约时间段的停车费用 违规行为&#xff1a;1.停车超过预约时间段 2.预约未使用 于系统的基本要求 &#xff08;1&#xff09;功能要求&am…...

打破常规思维:Scrapy处理豆瓣视频下载的方式

概述 Scrapy是一个强大的Python爬虫框架&#xff0c;它可以帮助我们快速地开发和部署各种类型的爬虫项目。Scrapy提供了许多方便的功能&#xff0c;例如请求调度、数据提取、数据存储、中间件、管道、信号等&#xff0c;让我们可以专注于业务逻辑&#xff0c;而不用担心底层的…...

系列学习前端之第 2 章:一文精通 HTML

全套学习 HTMLCSSJavaScript 代码和笔记请下载网盘的资料&#xff1a; 链接: https://pan.baidu.com/s/1-vY2anBdrsBSwDZfALZ6FQ 提取码: 6666 HTML 全称&#xff1a;HyperText Markup Language&#xff08;超文本标记语言&#xff09; 1、 HTML 标签 1. 标签又称元素&#…...

SCSS Module 这样处理配置和使用太赞了

SCSS Module 只是Scss和Css Module结合&#xff0c;可以利用SCSS对代码静态处理的能力&#xff0c;使得样式处理更强大一些&#xff0c;并不是什么新的东西&#xff0c;对比css-in-js和scoped&#xff0c;个人偏向喜欢Scss Module做样式隔离&#xff0c;先说一下优点&#xff1…...

【Unity动画】Unity 2D动画创建流程

本文以2D为案例&#xff0c;讲解Unity 播放动画的流程 准备和导入2D动画资源 外部导入序列帧生成的 Unity内部制作的 外部导入的3D动画 2.创建动画过程 打开时间轴Ctrl6 选中场景中的一个未来需要播放动画的物体 回到时间轴点击Create一个新动画片段 拖动2D动画资源放入…...

【算法每日一练]-图论(保姆级教程篇12 tarjan篇)#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点

目录&#xff1a; 今天知识点 加边使得无向图图变成双连通图 找出度为0的强连通分量 加边使得有向图变成强连通图 将有向图转成DAG图进行dp POJ3352&#xff1a;道路建设 思路&#xff1a; POJ2553&#xff1a;图的底部 思路&#xff1a; POJ1236校园网络 思路&#x…...

Python数据科学视频讲解:数据挖掘与建模的注意事项

1.7 数据挖掘与建模的注意事项 视频为《Python数据科学应用从入门到精通》张甜 杨维忠 清华大学出版社一书的随书赠送视频讲解1.7节内容。本书已正式出版上市&#xff0c;当当、京东、淘宝等平台热销中&#xff0c;搜索书名即可。内容涵盖数据科学应用的全流程&#xff0c;包括…...

unity | 动画模块之循环滚动选项框

一、作者的话 评论区有人问&#xff0c;有没有竖排循环轮播选项框&#xff0c;我就写了一个 二、效果动画 如果不是你们想要的&#xff0c;就省的你们继续往下看了 三、制作思路 把移动分成里面的方块&#xff0c;还有背景&#xff08;父物体&#xff09;&#xff0c;方块自…...

TinyMPC - CMU (卡耐基梅隆大学)开源的机器人 MPC 控制器

系列文章目录 CasADi - 最优控制开源 Python/MATLAB 库 文章目录 系列文章目录前言一、机器人硬件对比1.1 Teensy 上的微控制器基准测试1.2 机器人硬件1.3 BibTeX 二、求解器三、功能&#xff08;预期&#xff09;3.1 高效3.2 鲁棒3.3 可嵌入式3.4 最小依赖性3.5 高效热启动3.…...

C++ 对象的初始化和清理:构造函数和析构函数

目录 构造函数和析构函数 构造函数 析构函数 构造函数的分类及调用 括号法 显示法 隐式转换法 拷贝构造函数的调用时机 使用一个已经创建完毕的对象来初始化一个新对象 值传递的方式给函数参数传值 以值方式返回局部对象 构造函数调用规则 初始化列表 类对象作…...

Tmux中使用Docker报错 - 解决方案

问题 进入Tmux会话后&#xff0c;在其中使用Docker可能会出现如下报错&#xff1a; Got permission denied while trying to connect to the Docker ……解决方案 退出tmux会话: tmux detach在tmux会话外部杀掉tmux进程&#xff1a; pkill -f tmux重新进入tmux&#xff1a…...

如何在WordPress中批量替换图片路径?

很多站长在使用WordPress博客或者搬家时&#xff0c;需要把WordPress文章中的图片路径进行替换来解决图片不显示的问题。总结一下WordPress图片路径批量替换的过程&#xff0c;方便有此类需求的站长们学习。 什么情况下批量替换图片路径 1、更换了网站域名 有许多网站建设初期…...

el-pagination 纯前端分页

需求&#xff1a;后端把所有数据都返给前端&#xff0c;前端进行分页渲染。 实现思路&#xff1a;先把数据存储到一个大数组中&#xff0c;然后调用方法进行切割。主要使用数组的slice方法 所有代码&#xff1a; html <template><div style"padding: 20px&qu…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...