494.目标和

1. 回溯算法
这题和之前做的那些排列、组合的回溯稍微有些不同,你不需要每次选数据时都是for遍历去选择,很明显这是顺序选择的
比如 数组[0,1],target=1;

递归数组,每个元素都 + 或者 - ,然后取最后结果为0的即可
class Solution {public int findTargetSumWays(int[] nums, int target) {find(0,nums,target);return count;}private void find(int begin,int[] nums,int target){// 如果减完了,结束if(begin == nums.length){if(target == 0){count++;}return;}target-=nums[begin];find(begin+1,nums,target);target+=nums[begin];target+=nums[begin];find(begin+1,nums,target);target-=nums[begin]; }private int count=0;
}
2. 动态规划
这其实可以抽象为0/1背包问题。
数组中的元素,要么是前面+,要么是前面-,问计算结果为target的方案有多少种。
计算结果为0,即我们把前面为+的元素放在一个集合A中,前面为-的元素放在一个集合B中,二者之差为target即可。
我们如果知道了集合A,那么集合B自然就是数组中剩余元素组成。
可以列个简单的数学公式,假设A集合元素的和为left,B元素和为right,数组总和为sum
left + right = sum;
left - right = target;
二者一相加可以得到 left=(sum+target)/2;
由于都是正整数,left如果不是正整数,说明无解,即没有这种方案。
思路成功转换为,背包容量为left,在数组中找出和刚好为left的方案,并记录方案的最大数。
- 确定dp[i][j]
即dp[i][j] :在数组中下标为0~i的元素中任选,和刚好为j的方案数量
-
确定递推公式
如果第i个元素不选,那方案数量和dp[i-1][j]的一样
dp[i][j] = dp[i-1][j]
如果选了第i个元素,那方案就不仅仅从i-1个元素选出和为j的,从i-1个元素选出和为j-nums[i]的也可以,两种方案数相加。
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] -
如何初始化
dp[0][0]=1 我可以都不选,那方案数就是1
初始化第一行 dp[0][nums[0]]+=1;
题目中提示给出nums[i]范围是可能为0,所以如果nums[0]=0,那就是dp[0][0]中都不选的方案中,再添加一种,选择元素0,那就是两个方案了!!!
重点细节,卡了我一个上午!!! -
确定遍历顺序
先数组元素,再背包容量 -
模拟推导
class Solution {public int findTargetSumWays(int[] nums, int target) {if(nums.length == 1){return target == nums[0]?1:target == 0-nums[0]?1:0;}// 把集合分成前面放+的正集合和前面放-的负集合.正集合的和为left,负集合的和为right// left+right=sum left-right=target => left = (target+sum)/2// 即转换为问题---把背包容量为left的背包装满有多少种方案// 同时,如果left不为整数,说明不行,返回0// dp[i][j] 在下标0为~i的元素中,填满背包容量为j,有多少种方案// dp[i][j] = dp[i-1][j] 如果不装i// dp[i][j] = Math.max(dp[i-1][j-nums[i]],dp[i-1][j]) 如果装iint sum=0;for(int i:nums){sum += i;}if((target+sum)%2 != 0 ){return 0;}if(target > sum || target < -sum){return 0;}int num = (target+sum)/2;num = num < 0?-num:num;int[][] dp = new int[nums.length][num+1];// 当容量为0的时候,都不选就是一种方案for(int i=0;i<nums.length;i++){dp[i][0]=1;}// 遍历第一行,dp[0][nums[0]]+=1 因为可能第一行中nums[0]=0,此时dp[0][0]其实已经初始化为1了,但是dp[0][0]其实有两个方案的,一个是都不选,一个是选了0,这个细节决定了我们后续的遍历从第二行开始是否成功!!!if(nums[0]<num+1){dp[0][nums[0]]+=1;}for(int i=1;i<nums.length;i++){for(int j=0;j<num+1;j++){dp[i][j] = dp[i-1][j];if(j>=nums[i]){dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j]; } }}return dp[nums.length-1][num];}
}
优化成一维的
class Solution {public int findTargetSumWays(int[] nums, int target) {if(nums.length == 1){return target == nums[0]?1:target == 0-nums[0]?1:0;}// 把集合分成前面放+的正集合和前面放-的负集合.正集合的和为left,负集合的和为right// left+right=sum left-right=target => left = (target+sum)/2// 即转换为问题---把背包容量为left的背包装满有多少种方案// 同时,如果left不为整数,说明不行,返回0// dp[i][j] 在下标0为~i的元素中,填满背包容量为j,有多少种方案// dp[i][j] = dp[i-1][j] 如果不装i// dp[i][j] = Math.max(dp[i-1][j-nums[i]],dp[i-1][j]) 如果装iint sum=0;for(int i:nums){sum += i;}if((target+sum)%2 != 0 ){return 0;}if(target > sum || target < -sum){return 0;}int num = (target+sum)/2;num = num < 0?-num:num;int[]dp = new int[num+1];// 当容量为0的时候,都不选就是一种方案dp[0]=1;// 遍历第一行if(nums[0]<num+1){dp[nums[0]]+=1;}for(int i=1;i<nums.length;i++){for(int j=num;j>=nums[i];j--){dp[j] += dp[j-nums[i]]; }}return dp[num];}
}
这道题很经典,建议过段时间重复刷
相关文章:
494.目标和
1. 回溯算法 这题和之前做的那些排列、组合的回溯稍微有些不同,你不需要每次选数据时都是for遍历去选择,很明显这是顺序选择的 比如 数组[0,1],target1; 递归数组,每个元素都 或者 - ,然后取最后结果为0…...
滑台模组的应用有哪些?
在自动化生产中,我们常常会看到滑台模组的身影,那么,滑台模组究竟在自动化生产设备中起着怎样的作用呢? 简单点说,滑台模组由滑块、滚珠丝杆、导轨、主体等其它传动零件组成的自动化晋级单元,经过各单元的组…...
CS224W课程学习笔记(四):node2vec算法原理与说明
引言 什么是图嵌入? 我想从上节的deepwalk中已经有一个十分完整的轮廓了,这里引出deepwalk论文中的一张很形象的图(当然,上节的一些实战演练,也将这种嵌入关系进行了模拟与可视化,前文为:&…...
扩展lucas定理
前置知识: lucas定理中国剩余定理 介绍 当正整数n,mn,mn,m很大,且质数ppp较小的时候,要求CnmC_n^mCnm对ppp取模后的值,可以用lucas定理。 但如果ppp不是质数,那该怎么办呢?如果mmm较小,则…...
医疗影像工具LEADTOOLS 入门教程: 从 PDF 中提取附件 - 控制台 C#
LEADTOOLS 是一个综合工具包的集合,用于将识别、文档、医疗、成像和多媒体技术整合到桌面、服务器、平板电脑、网络和移动解决方案中,是一项企业级文档自动化解决方案,有捕捉,OCR,OMR,表单识别和处理&#…...
【LVGL】学习笔记--(1)Keil中嵌入式系统移植LVGL
一 LVGL简介最近emwin用的比较烦躁,同时被LVGL酷炫的界面吸引到了,所以准备换用LVGL试试水。LVGL(轻量级和通用图形库)是一个免费和开源的图形库,它提供了创建嵌入式GUI所需的一切,具有易于使用的图形元素,美丽的视觉效…...
Transformer学习笔记
Transformer学习笔记1. 参考2. 模型图3.encoder部分3.1 Positional Encoding3.2 Muti-Head Attention3.3 ADD--残差连接3.4 Norm标准化3.5 单个Transformer Encoder流程图4.decoder部分4.1 mask Muti-Head Attention4.2 Muti-Head Attention5 多个Transformer Encoder和多个Tra…...
vue-cli引入wangEditor、Element,封装可上传附件的富文本编辑器组件(附源代码直接应用,菜单可调整)
关于Element安装引入,请参考我的另一篇文章:vue-cli引入Element Plus(element-ui),修改主题变量,定义全局样式_shawxlee的博客-CSDN博客_chalk variables 1、安装wangeditor npm i wangeditor --savewangE…...
移动办公时代,数智化平台如何赋能企业管理升级?
在传统的办公模式下,企业组织办公不仅时效低,周期长、成本高,且各办公系统相互独立。随着社会经济的发展,人们的工作生活变得多样化,对于办公的需求也越来越多,存在明显弊端的传统办公模式已不能满足企业对…...
2023“拼夕夕”为什么可以凭借简单的拼团做这么大?
2023“拼夕夕”为什么可以凭借简单的拼团做这么大? 2023-02-24 梦龙 大家好,我是你们熟悉而又陌生的好朋友梦龙,一个创业期的年轻人 大家都知道,拼夕夕背后的商业模式是拼团,但是大家知道为什么简单的拼团可以让拼夕…...
sqlmap工具
sqlmap Sqlmap是一个开源的渗透测试工具,可以用来自动化的检测,利用SQL注入漏洞,获取数据库服务器的权限。目前支持的数据库有MySQL、Oracle、PostgreSQL、Microsoft SQL Server、Microsoft Access等大多数据库 Sqlmap采用了以下5种独特的SQ…...
高/低压供配电系统设计——安科瑞变电站电力监控系统的应用
摘 要:在电力系统的运行过程中,变电站作为整个电力系统的核心,在保证电力系统可靠的运行方面起着至关重要的作用,基于此需对变电站监控系统的特点进行分析,结合变电站监控系统的功能需求,对变电站电力监控系…...
Tapdata 和 Databend 数仓数据同步实战
作者:韩山杰https://github.com/hantmacDatabend Cloud 研发工程师基础架构在云计算时代也发生着翻天地覆的变化,对于业务的支持变成了如何能利用好云资源实现降本增效,同时更好的支撑业务也成为新时代技术人员的挑战。 本篇文章通过…...
单核CPU, 1G内存,也能做JVM调优吗?
最近,笔者的技术群里有人问了一个有趣的技术话题:单核CPU, 1G内存的超低配机器,怎么做JVM调优?这实际上是两个问题。单核CPU的超低配机器,怎么充分利用CPU?单核CPU, 1G内存的超低配机器,怎么做J…...
《计算机应用研究》投稿经历和时间节点
记录四川计算机研究院《计算机应用研究》期刊投稿经历和时间节点。 日期状态周期2022.11.09上传稿件当天显示编辑部已接收稿件,开始初审2022.11.09 – 2022.11.15初审6天2022.11.15 – 2022.12.21外审36天2022.12.21收到退修意见(邮件形式)编…...
mars3d获取视窗的范围
期望效果 :1.我现在想获取到当前视窗的地图范围,请问有什么⽅法可以拿到吗 2.⽐如当前视窗地图范围的边界点,每个边界点的经纬度 回复:1.mars3d的API⽂档中有相关的⽅法 2.具体使⽤可以参考⽂档地址:http://mars3d.cn/api/Map.htm…...
《高性能MySQL》读书笔记(上)
目录 MySQL的架构 MySQL中的锁 MySQL中的事务 事务特性 隔离级别 事务日志 多版本并发控制MVCC 影响MySQL性能的物理因素 InnoDB缓冲池 MySQL常用的数据类型以及优化 字符串类型 日期和时间类型 数据标识符 MySQL的架构 默认情况下,每个客户端连接都…...
05-代理模式
代理模式 代理模式使用代理对象来代替真实对象的访问,在不修改原有对象的前提下,提供额外的操作,扩展目标对象的功能。代理模式分为静态代理和动态代理。 静态代理 手动为目标对象中的方法进行增强,通过实现相同接口重写方法进…...
RocketMQ源码分析之消费队列、Index索引文件存储结构与存储机制-上篇
RocketMQ 存储基础回顾: 源码分析RocketMQ之CommitLog消息存储机制 本文主要从源码的角度分析 Rocketmq 消费队列 ConsumeQueue 物理文件的构建与存储结构,同时分析 RocketMQ 索引文件IndexFile 文件的存储原理、存储格式以及检索方式。RocketMQ 的存储…...
基于Java的浏览器的设计与实现毕业设计
技术:Java等摘要:当今世界是一个以计算机网络为核心的信息时代,互联网为人们快速获取、发布和传递信息提供了便捷,而浏览器作为互联网上查找信息的重要工具,给人们提供了巨大而又宝贵的信息财富,受到了大家…...
CANN调优工具链全景:从profiler到tensorboard的完整观测体系
CANN调优工具链全景:从profiler到tensorboard的完整观测体系 有个团队找我说,他们买了昇腾NPU集群,花了大半年才把调优工具链搭起来。每个人用不同的工具,各看各的数据,互相之间对不上。最后我帮他们梳理了一套统一的工…...
安科士(AndXe)SPF-10G-T :10G 电口模块,重塑短距网络升级性价比
数字化转型浪潮下,企业园区、数据中心对10Gbps 高速互联的需求呈爆发式增长。但传统 10G 升级方案深陷困境:光纤布线成本高昂、施工周期长且需专业运维技能,而多数企业机架内、相邻机架间及办公楼层内的链路距离普遍低于 30 米,光…...
嵌入式开发新趋势:从硬件参数到场景方案,AI与可靠性成关键
1. 展会现场与行业风向初探上周,我作为飞凌嵌入式的一名老员工,亲身参与了2024上海国际嵌入式展。这不仅仅是一次简单的产品展示,更像是一场行业同仁的“华山论剑”。从人头攒动的展台到技术论坛上激烈的讨论,你能清晰地感受到&am…...
为Hermes Agent配置自定义Provider并接入Taotoken聚合模型服务
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 为Hermes Agent配置自定义Provider并接入Taotoken聚合模型服务 Hermes Agent 是一款功能强大的智能体开发工具,它支持通…...
嵌入式核心板选型与开发实战:M28x-T与M6G2C硬件设计及AWorks平台应用
1. 项目概述:为什么我们需要“一体化”核心板?在嵌入式产品开发,尤其是工业控制、数据采集这类对稳定性和开发效率要求极高的领域,很多工程师都经历过一个痛苦的过程:选型一颗主控MCU,然后围绕它去设计DDR内…...
MATLAB实战:用冲激响应不变法设计IIR低通滤波器,手把手教你滤除信号噪声
MATLAB实战:用冲激响应不变法设计IIR低通滤波器,手把手教你滤除信号噪声 在工程实践中,信号噪声无处不在。无论是传感器采集的数据,还是音频信号中的背景干扰,噪声都会严重影响后续的分析和处理。IIR(无限脉…...
告别SDK Manager卡顿:用命令行flash.sh为Jetson TX2刷入JetPack 4.6.4系统镜像
告别SDK Manager卡顿:用命令行flash.sh为Jetson TX2刷入JetPack 4.6.4系统镜像 当你在为Jetson TX2刷写系统时,是否曾被SDK Manager的图形界面折磨得焦头烂额?网络中断、进度条卡死、"The target is in a bad state"等错误提示让本…...
《Sysinternals实战指南》ZoomIt 学习笔记(11.11):休息计时器与演讲节奏控制——倒计时、番茄钟与现场掌控力
🔥个人主页:杨利杰YJlio❄️个人专栏:《Sysinternals实战教程》《Windows PowerShell 实战》《WINDOWS教程》《IOS教程》《微信助手》《锤子助手》 《Python》 《Kali Linux》 《那些年未解决的Windows疑难杂症》🌟 让复杂的事情更…...
量子计算与人工智能融合:技术原理与应用前景
1. 量子计算与人工智能融合的技术全景量子计算与人工智能(AI)的交叉领域正在重塑计算技术的边界。作为一名长期跟踪量子计算发展的技术研究者,我见证了从早期理论构想到如今实验室原型机的演进历程。量子计算利用量子比特的叠加与纠缠特性&am…...
2026浏览器侧信道指纹检测技术研究与防护方案落地
一、引言常规浏览器指纹检测依托页面脚本读取显性设备参数,这类识别方式早已被各类虚拟浏览工具针对性规避。近两年各大互联网平台开始大规模部署侧信道指纹检测体系,跳出表层参数读取的局限,借助硬件运行损耗、指令执行耗时、内存调度特征、…...
