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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
3. 解法(回溯):
3.1 算法思路:
对于每个数,可以选择加上或减去它,依次枚举每一个数字,在每个数都被选择时检查得到的和是否等于目标值。如果等于,则记录结果。
需要注意的是,为了优化时间复杂度,可以提前计算出数组中所有数字的和,以及数组的长度。这样可以快速判断当前的和减去剩余的数是否已经超过了目标值target,或者当前的和加上剩下的数的和是否小于目标值target,如果满足条件,则可以直接回溯
3.2 递归流程:
-
递归结束条件:
pos与数组长度相等,判断当前状态的path是否与目标值相等,若是计数加一 -
选择当前元素进行加操作,递归下一个位置,并更新参数
path -
选择当前元素进行减操作,递归下一个位置,并更新参数
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. 题目链接:494. 目标和 2. 题目描述: 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums [2, 1] ,可…...
学习c#的第六天
目录 C# 判断 if 语句 嵌套 if 语句 switch 语句 嵌套 switch 语句 ? : 运算符 C# 循环 循环类型 while 循环 for/foreach 循环 do...while 循环 嵌套循环 循环控制语句 break 语句 continue 语句 无限循环 C# 判断 if 语句 在C#中,if语句用于根…...
第七章 :Spring Boot web开发常用注解(二)
第七章 :Spring Boot web开发常用注解(二) 前言 本章节知识重点:作者结合自身开发经验,以及觉察到的一个现象:Springboot注解全面理解和掌握的并不多,对注解进行了全面总结,共分两个章节,可以作为web开发工程师注解参考手册,SpringBoot常用注解大全,一目了然!。本…...
IOC - Google Guice
Google Guice是一个轻量级的依赖注入框架,专注于依赖注入和IoC,适用于中小型应用。 Spring Framework是一个全面的企业级框架,提供了广泛的功能,适用于大型企业应用。 是吧!IOC 容器不止Spring,还有Google Guice,来体…...
国际阿里云:Linux实例负载高问题排查和异常处理!!!
问题描述 在您使用ECS实例过程中,可能会遇到实例系统负载较高的情况,负载过高,可能会引发一系列异常问题,简单说您如下: CPU使用率或负载过高:一般来说,当CPU使用率≥80%时,定义为C…...
【数据结构】二叉树的遍历递归算法详解
二叉树的遍历 💫二叉树的结点结构定义💫创建一个二叉树结点💫在主函数中手动创建一颗二叉树💫二叉树的前序遍历💫调用栈递归——实现前序遍历💫递归实现中序和后序遍历 💫二叉树的结点结构定义 …...
百度王颖:百度文库以AI创作能力突破语言边界,促进思想碰撞和文化融通
1月9日,2023年世界互联网大会乌镇峰会“网络传播与文明交流互鉴论坛”召开。百度副总裁、互娱和垂类平台负责人王颖出席并发表“以技术搭建跨文化交流桥梁”主题演讲。她表示,在大模型的加持下,百度各个产品都在重构,通过技术助力…...
人工智能基础_机器学习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系统
下载链接:https://pan.baidu.com/s/1akLkXM2HIg3eO76jqM-LVA?pwdxvo6 提取码:xvo6 系统自带所有驱动、出厂主题壁纸、系统属性专属LOGO标志、Office办公软件、联想电脑管家等预装程序 所需要工具:16G或以上的U盘 文件格式:…...
在程序中链接静态库
现在我们把上面src目录中的add.cpp、div.cpp、mult.cpp、sub.cpp编译成一个静态库文件libcalc.a。 add_library(库名称 STATIC 源文件1 [源文件2] ...) link_libraries(<static lib> [<static lib>...]) 参数1:指定出要链接的静态库的名字 可以是全…...
TortoiseSVN 状态图标不显示的两种解决办法
文章目录 TortoiseSVN 方式解决注册表方式解决 TortoiseSVN 方式解决 在桌面或者资源管理器中鼠标右键打开 TortoiseSVN 设置选择 Icon Overlays (图标覆盖)Status cache(状态缓存) 选择 ‘Shell’ 选择 Icon Overlays(图标覆盖)…...
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文件名一致(一个class可以有多个类,但只有一个public,且与文件名一致),命名介意大驼峰;如果某个对象没有变量指向他,就成垃圾对象了(空指针)…...
【从0到1设计一个网关】性能优化---缓存
文章目录 为什么要用缓存?Caffeine Cache使用Caffeine效果演示为什么要用缓存? 首先先了解一下为什么在网关中我们需要用到缓存。 我们可以从如下几点来入手这个问题: 处理大规模流量: 网关是系统的入口,需要处理大规模的请求流量。高性能的网关能够快速而有效地处理大量…...
Typescript -尚硅谷
基础 1.ts是以js为基础构建的语言,是一个js的超集(对js进行了扩展); 2.ts(type)最主要的功能是在js的基础上引入了类型的概念; Js的类型是只针对于值而言,ts的类型是针对于变量而言 Ts可以被编译成任意版本的js,从而进一步解决了…...
以 Kubernetes 原生方式实现多集群告警
作者:向军涛、雷万钧 来源:2023 上海 KubeCon 分享 可观测性来源 在 Kubernetes 集群上,各个维度的可观测性数据,可以让我们及时了解集群上应用的状态,以及集群本身的状态。 Metrics 指标:监控对象状态的量…...
2023年A股借壳上市研究报告
第一章 借壳上市概况 1.1 定义 借壳上市作为一种独特的资本市场操作手法,历来是企业拓展融资渠道和实现市场战略目标的重要途径。具体来说,借壳上市可分为狭义与广义两种模式。在狭义的定义下,借壳上市是指一家已上市的公司的控股母公司&am…...
【TiDB】TiDB CLuster部署
目录 0 大纲 一 集群部署工具TiUP简介 1 TiUP 简介 2 TiUP使用 3 TiUP使用举例 二 TiDB Cluster安装配置需求 1 生产环境硬件需求 2 操作系统需求 三 TIDB部署 1 软硬件需求以及前置检查编辑 2 安装TiUP 组件 3 集群拓扑文件 4 执行部署命令 (1&…...
odoo16 库存初始化 excel导入问题
最近在为一家公司实施odoo时,发现库存模块实施过程中按用户实际,产品初始化就是个问题。下面一一记录下 一个新公司,产品都有上百种,甚致几千种,如何把现有产品数据录入系统就是个不小的活。odoo16是有导入导出功能不…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
