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

Leetcode刷题详解—— 目标和

1. 题目链接:494. 目标和

2. 题目描述:

给你一个非负整数数组 nums 和一个整数 target

向数组中的每个整数前添加 '+''-' ,然后串联起所有整数,可以构造一个 表达式

  • 例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1"

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:

输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2:

输入:nums = [1], target = 1
输出:1

提示:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

3. 解法(回溯):

3.1 算法思路:

对于每个数,可以选择加上或减去它,依次枚举每一个数字,在每个数都被选择时检查得到的和是否等于目标值。如果等于,则记录结果。

需要注意的是,为了优化时间复杂度,可以提前计算出数组中所有数字的和,以及数组的长度。这样可以快速判断当前的和减去剩余的数是否已经超过了目标值target,或者当前的和加上剩下的数的和是否小于目标值target,如果满足条件,则可以直接回溯

3.2 递归流程:

  1. 递归结束条件:pos与数组长度相等,判断当前状态的path是否与目标值相等,若是计数加一

  2. 选择当前元素进行加操作,递归下一个位置,并更新参数path

  3. 选择当前元素进行减操作,递归下一个位置,并更新参数path

请添加图片描述

3.3 C++算法代码:

class Solution {int ret, aim; // ret用于记录满足条件的路径数量,aim用于存储目标和
public:int findTargetSumWays(vector<int>& nums, int target) {aim = target; // 初始化目标和dfs(nums, 0, 0); // 从数组的第一个元素开始搜索return ret; // 返回满足条件的路径数量}void dfs(vector<int>& nums, int pos, int path) {if (pos == nums.size()) { // 如果已经遍历完数组if (path == aim) ret++; // 如果当前路径的和等于目标和,则增加满足条件的路径数量return; // 结束当前递归}dfs(nums, pos + 1, path + nums[pos]); // 选择当前元素,将其加入路径中,继续搜索下一个元素dfs(nums, pos + 1, path - nums[pos]); // 不选择当前元素,将当前元素从路径中移除,继续搜索下一个元素}
};

相关文章:

Leetcode刷题详解—— 目标和

1. 题目链接&#xff1a;494. 目标和 2. 题目描述&#xff1a; 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - &#xff0c;然后串联起所有整数&#xff0c;可以构造一个 表达式 &#xff1a; 例如&#xff0c;nums [2, 1] &#xff0c;可…...

学习c#的第六天

目录 C# 判断 if 语句 嵌套 if 语句 switch 语句 嵌套 switch 语句 ? : 运算符 C# 循环 循环类型 while 循环 for/foreach 循环 do...while 循环 嵌套循环 循环控制语句 break 语句 continue 语句 无限循环 C# 判断 if 语句 在C#中&#xff0c;if语句用于根…...

第七章 :Spring Boot web开发常用注解(二)

第七章 :Spring Boot web开发常用注解(二) 前言 本章节知识重点:作者结合自身开发经验,以及觉察到的一个现象:Springboot注解全面理解和掌握的并不多,对注解进行了全面总结,共分两个章节,可以作为web开发工程师注解参考手册,SpringBoot常用注解大全,一目了然!。本…...

IOC - Google Guice

Google Guice是一个轻量级的依赖注入框架&#xff0c;专注于依赖注入和IoC&#xff0c;适用于中小型应用。 Spring Framework是一个全面的企业级框架&#xff0c;提供了广泛的功能&#xff0c;适用于大型企业应用。 是吧&#xff01;IOC 容器不止Spring,还有Google Guice,来体…...

国际阿里云:Linux实例负载高问题排查和异常处理!!!

问题描述 在您使用ECS实例过程中&#xff0c;可能会遇到实例系统负载较高的情况&#xff0c;负载过高&#xff0c;可能会引发一系列异常问题&#xff0c;简单说您如下&#xff1a; CPU使用率或负载过高&#xff1a;一般来说&#xff0c;当CPU使用率≥80%时&#xff0c;定义为C…...

【数据结构】二叉树的遍历递归算法详解

二叉树的遍历 &#x1f4ab;二叉树的结点结构定义&#x1f4ab;创建一个二叉树结点&#x1f4ab;在主函数中手动创建一颗二叉树&#x1f4ab;二叉树的前序遍历&#x1f4ab;调用栈递归——实现前序遍历&#x1f4ab;递归实现中序和后序遍历 &#x1f4ab;二叉树的结点结构定义 …...

百度王颖:百度文库以AI创作能力突破语言边界,促进思想碰撞和文化融通

1月9日&#xff0c;2023年世界互联网大会乌镇峰会“网络传播与文明交流互鉴论坛”召开。百度副总裁、互娱和垂类平台负责人王颖出席并发表“以技术搭建跨文化交流桥梁”主题演讲。她表示&#xff0c;在大模型的加持下&#xff0c;百度各个产品都在重构&#xff0c;通过技术助力…...

人工智能基础_机器学习023_理解套索回归_认识L1正则---人工智能工作笔记0063

然后上一节我们说了L1,L2正则是为了提高,模型的泛化能力, 提高泛化能力,实际上就是把模型的公式的w,权重值,变小对吧. 然后我们这里首先看第一个L1正则,是怎么做到把w权重变小的 可以看到最上面是线性回归的损失函数,然后 L1可以看到,这个正则,就是在损失函数的基础上给损失…...

Learning an Animatable Detailed 3D Face Model from In-The-Wild Images论文笔记

Learning an Animatable Detailed 3D Face Model from In-The-Wild Images论文笔记 论文目标:提出一个端到端的框架,可以从非受控的图片中学习高质量、可动画的3D人脸模型。论文方法:论文结果:论文意义: 论文目标:提出一个端到端的框架,可以从非受控的图片中学习高质量、可动画…...

Lenovo联想小新Air-14笔记本2021款AMD锐龙ALC版(82LM)原装出厂Win10镜像和Windows11预装OEM系统

下载链接&#xff1a;https://pan.baidu.com/s/1akLkXM2HIg3eO76jqM-LVA?pwdxvo6 提取码&#xff1a;xvo6 系统自带所有驱动、出厂主题壁纸、系统属性专属LOGO标志、Office办公软件、联想电脑管家等预装程序 所需要工具&#xff1a;16G或以上的U盘 文件格式&#xff1a;…...

在程序中链接静态库

现在我们把上面src目录中的add.cpp、div.cpp、mult.cpp、sub.cpp编译成一个静态库文件libcalc.a。 add_library(库名称 STATIC 源文件1 [源文件2] ...) link_libraries(<static lib> [<static lib>...]) 参数1&#xff1a;指定出要链接的静态库的名字 可以是全…...

TortoiseSVN 状态图标不显示的两种解决办法

文章目录 TortoiseSVN 方式解决注册表方式解决 TortoiseSVN 方式解决 在桌面或者资源管理器中鼠标右键打开 TortoiseSVN 设置选择 Icon Overlays (图标覆盖)Status cache&#xff08;状态缓存&#xff09; 选择 ‘Shell’ 选择 Icon Overlays&#xff08;图标覆盖&#xff09;…...

NSSCTF-Crypto入门题 练习记录贴 ‘‘一‘‘

文章目录 前言001[鹤城杯 2021]easy_crypto002[强网拟态 2021]拟态签到题003[SWPUCTF 2021 新生赛]crypto8004[SWPUCTF 2021 新生赛]crypto7005[SWPUCTF 2021 新生赛]crypto6006[SWPUCTF 2021 新生赛]ez_caesar007[SWPUCTF 2021 新生赛]crypto10008[鹤城杯 2021]A_CRYPTO009[SW…...

Day03:注意事项、this关键字、构造器、JavaBean、String、ArrayList

OOP的注意事项 类名要跟class文件名一致&#xff08;一个class可以有多个类&#xff0c;但只有一个public&#xff0c;且与文件名一致&#xff09;&#xff0c;命名介意大驼峰&#xff1b;如果某个对象没有变量指向他&#xff0c;就成垃圾对象了&#xff08;空指针&#xff09…...

【从0到1设计一个网关】性能优化---缓存

文章目录 为什么要用缓存?Caffeine Cache使用Caffeine效果演示为什么要用缓存? 首先先了解一下为什么在网关中我们需要用到缓存。 我们可以从如下几点来入手这个问题: 处理大规模流量: 网关是系统的入口,需要处理大规模的请求流量。高性能的网关能够快速而有效地处理大量…...

Typescript -尚硅谷

基础 1.ts是以js为基础构建的语言&#xff0c;是一个js的超集(对js进行了扩展)&#xff1b; 2.ts(type)最主要的功能是在js的基础上引入了类型的概念; Js的类型是只针对于值而言&#xff0c;ts的类型是针对于变量而言 Ts可以被编译成任意版本的js&#xff0c;从而进一步解决了…...

以 Kubernetes 原生方式实现多集群告警

作者&#xff1a;向军涛、雷万钧 来源&#xff1a;2023 上海 KubeCon 分享 可观测性来源 在 Kubernetes 集群上&#xff0c;各个维度的可观测性数据&#xff0c;可以让我们及时了解集群上应用的状态&#xff0c;以及集群本身的状态。 Metrics 指标&#xff1a;监控对象状态的量…...

2023年A股借壳上市研究报告

第一章 借壳上市概况 1.1 定义 借壳上市作为一种独特的资本市场操作手法&#xff0c;历来是企业拓展融资渠道和实现市场战略目标的重要途径。具体来说&#xff0c;借壳上市可分为狭义与广义两种模式。在狭义的定义下&#xff0c;借壳上市是指一家已上市的公司的控股母公司&am…...

【TiDB】TiDB CLuster部署

目录 0 大纲 一 集群部署工具TiUP简介 1 TiUP 简介 2 TiUP使用 3 TiUP使用举例 二 TiDB Cluster安装配置需求 1 生产环境硬件需求 2 操作系统需求 三 TIDB部署 1 软硬件需求以及前置检查​编辑 2 安装TiUP 组件 ​3 集群拓扑文件 4 执行部署命令 &#xff08;1&…...

odoo16 库存初始化 excel导入问题

最近在为一家公司实施odoo时&#xff0c;发现库存模块实施过程中按用户实际&#xff0c;产品初始化就是个问题。下面一一记录下 一个新公司&#xff0c;产品都有上百种&#xff0c;甚致几千种&#xff0c;如何把现有产品数据录入系统就是个不小的活。odoo16是有导入导出功能不…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

leetcode_69.x的平方根

题目如下 &#xff1a; 看到题 &#xff0c;我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历&#xff0c;我们是整数的平方根&#xff0c;所以我们分两…...

欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!

多连接 BLE 怎么设计服务不会乱&#xff1f;分层思维来救场&#xff01; 作者按&#xff1a; 你是不是也遇到过 BLE 多连接时&#xff0c;调试现场像网吧“掉线风暴”&#xff1f; 温度传感器连上了&#xff0c;心率带丢了&#xff1b;一边 OTA 更新&#xff0c;一边通知卡壳。…...

SOC-ESP32S3部分:30-I2S音频-麦克风扬声器驱动

飞书文档https://x509p6c8to.feishu.cn/wiki/SKZzwIRH3i7lsckUOlzcuJsdnVf I2S简介 I2S&#xff08;Inter-Integrated Circuit Sound&#xff09;是一种用于传输数字音频数据的通信协议&#xff0c;广泛应用于音频设备中。 ESP32-S3 包含 2 个 I2S 外设&#xff0c;通过配置…...