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等摘要:当今世界是一个以计算机网络为核心的信息时代,互联网为人们快速获取、发布和传递信息提供了便捷,而浏览器作为互联网上查找信息的重要工具,给人们提供了巨大而又宝贵的信息财富,受到了大家…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...