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

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的方案,并记录方案的最大数。

  1. 确定dp[i][j]

即dp[i][j] :在数组中下标为0~i的元素中任选,和刚好为j的方案数量

  1. 确定递推公式
    如果第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]]

  2. 如何初始化
    dp[0][0]=1 我可以都不选,那方案数就是1
    初始化第一行 dp[0][nums[0]]+=1;
    题目中提示给出nums[i]范围是可能为0,所以如果nums[0]=0,那就是dp[0][0]中都不选的方案中,再添加一种,选择元素0,那就是两个方案了!!!
    重点细节,卡了我一个上午!!!

  3. 确定遍历顺序
    先数组元素,再背包容量

  4. 模拟推导

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. 回溯算法 这题和之前做的那些排列、组合的回溯稍微有些不同&#xff0c;你不需要每次选数据时都是for遍历去选择&#xff0c;很明显这是顺序选择的 比如 数组[0,1]&#xff0c;target1&#xff1b; 递归数组&#xff0c;每个元素都 或者 - &#xff0c;然后取最后结果为0…...

滑台模组的应用有哪些?

在自动化生产中&#xff0c;我们常常会看到滑台模组的身影&#xff0c;那么&#xff0c;滑台模组究竟在自动化生产设备中起着怎样的作用呢&#xff1f; 简单点说&#xff0c;滑台模组由滑块、滚珠丝杆、导轨、主体等其它传动零件组成的自动化晋级单元&#xff0c;经过各单元的组…...

CS224W课程学习笔记(四):node2vec算法原理与说明

引言 什么是图嵌入&#xff1f; 我想从上节的deepwalk中已经有一个十分完整的轮廓了&#xff0c;这里引出deepwalk论文中的一张很形象的图&#xff08;当然&#xff0c;上节的一些实战演练&#xff0c;也将这种嵌入关系进行了模拟与可视化&#xff0c;前文为&#xff1a;&…...

扩展lucas定理

前置知识&#xff1a; lucas定理中国剩余定理 介绍 当正整数n,mn,mn,m很大&#xff0c;且质数ppp较小的时候&#xff0c;要求CnmC_n^mCnm​对ppp取模后的值&#xff0c;可以用lucas定理。 但如果ppp不是质数&#xff0c;那该怎么办呢&#xff1f;如果mmm较小&#xff0c;则…...

医疗影像工具LEADTOOLS 入门教程: 从 PDF 中提取附件 - 控制台 C#

LEADTOOLS 是一个综合工具包的集合&#xff0c;用于将识别、文档、医疗、成像和多媒体技术整合到桌面、服务器、平板电脑、网络和移动解决方案中&#xff0c;是一项企业级文档自动化解决方案&#xff0c;有捕捉&#xff0c;OCR&#xff0c;OMR&#xff0c;表单识别和处理&#…...

【LVGL】学习笔记--(1)Keil中嵌入式系统移植LVGL

一 LVGL简介最近emwin用的比较烦躁&#xff0c;同时被LVGL酷炫的界面吸引到了&#xff0c;所以准备换用LVGL试试水。LVGL(轻量级和通用图形库)是一个免费和开源的图形库&#xff0c;它提供了创建嵌入式GUI所需的一切&#xff0c;具有易于使用的图形元素&#xff0c;美丽的视觉效…...

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安装引入&#xff0c;请参考我的另一篇文章&#xff1a;vue-cli引入Element Plus&#xff08;element-ui&#xff09;&#xff0c;修改主题变量&#xff0c;定义全局样式_shawxlee的博客-CSDN博客_chalk variables 1、安装wangeditor npm i wangeditor --savewangE…...

移动办公时代,数智化平台如何赋能企业管理升级?

在传统的办公模式下&#xff0c;企业组织办公不仅时效低&#xff0c;周期长、成本高&#xff0c;且各办公系统相互独立。随着社会经济的发展&#xff0c;人们的工作生活变得多样化&#xff0c;对于办公的需求也越来越多&#xff0c;存在明显弊端的传统办公模式已不能满足企业对…...

2023“拼夕夕”为什么可以凭借简单的拼团做这么大?

2023“拼夕夕”为什么可以凭借简单的拼团做这么大&#xff1f; 2023-02-24 梦龙 大家好&#xff0c;我是你们熟悉而又陌生的好朋友梦龙&#xff0c;一个创业期的年轻人 大家都知道&#xff0c;拼夕夕背后的商业模式是拼团&#xff0c;但是大家知道为什么简单的拼团可以让拼夕…...

sqlmap工具

sqlmap Sqlmap是一个开源的渗透测试工具&#xff0c;可以用来自动化的检测&#xff0c;利用SQL注入漏洞&#xff0c;获取数据库服务器的权限。目前支持的数据库有MySQL、Oracle、PostgreSQL、Microsoft SQL Server、Microsoft Access等大多数据库 Sqlmap采用了以下5种独特的SQ…...

高/低压供配电系统设计——安科瑞变电站电力监控系统的应用

摘 要&#xff1a;在电力系统的运行过程中&#xff0c;变电站作为整个电力系统的核心&#xff0c;在保证电力系统可靠的运行方面起着至关重要的作用&#xff0c;基于此需对变电站监控系统的特点进行分析&#xff0c;结合变电站监控系统的功能需求&#xff0c;对变电站电力监控系…...

Tapdata 和 Databend 数仓数据同步实战

作者&#xff1a;韩山杰https://github.com/hantmacDatabend Cloud 研发工程师基础架构在云计算时代也发生着翻天地覆的变化&#xff0c;对于业务的支持变成了如何能利用好云资源实现降本增效&#xff0c;同时更好的支撑业务也成为新时代技术人员的挑战。 本篇文章通过&#xf…...

单核CPU, 1G内存,也能做JVM调优吗?

最近&#xff0c;笔者的技术群里有人问了一个有趣的技术话题&#xff1a;单核CPU, 1G内存的超低配机器&#xff0c;怎么做JVM调优&#xff1f;这实际上是两个问题。单核CPU的超低配机器&#xff0c;怎么充分利用CPU&#xff1f;单核CPU, 1G内存的超低配机器&#xff0c;怎么做J…...

《计算机应用研究》投稿经历和时间节点

记录四川计算机研究院《计算机应用研究》期刊投稿经历和时间节点。 日期状态周期2022.11.09上传稿件当天显示编辑部已接收稿件&#xff0c;开始初审2022.11.09 – 2022.11.15初审6天2022.11.15 – 2022.12.21外审36天2022.12.21收到退修意见&#xff08;邮件形式&#xff09;编…...

mars3d获取视窗的范围

期望效果 :1.我现在想获取到当前视窗的地图范围&#xff0c;请问有什么⽅法可以拿到吗 2.⽐如当前视窗地图范围的边界点&#xff0c;每个边界点的经纬度 回复&#xff1a;1.mars3d的API⽂档中有相关的⽅法 2.具体使⽤可以参考⽂档地址&#xff1a;http://mars3d.cn/api/Map.htm…...

《高性能MySQL》读书笔记(上)

目录 MySQL的架构 MySQL中的锁 MySQL中的事务 事务特性 隔离级别 事务日志 多版本并发控制MVCC 影响MySQL性能的物理因素 InnoDB缓冲池 MySQL常用的数据类型以及优化 字符串类型 日期和时间类型 数据标识符 MySQL的架构 默认情况下&#xff0c;每个客户端连接都…...

05-代理模式

代理模式 代理模式使用代理对象来代替真实对象的访问&#xff0c;在不修改原有对象的前提下&#xff0c;提供额外的操作&#xff0c;扩展目标对象的功能。代理模式分为静态代理和动态代理。 静态代理 手动为目标对象中的方法进行增强&#xff0c;通过实现相同接口重写方法进…...

RocketMQ源码分析之消费队列、Index索引文件存储结构与存储机制-上篇

RocketMQ 存储基础回顾&#xff1a; 源码分析RocketMQ之CommitLog消息存储机制 本文主要从源码的角度分析 Rocketmq 消费队列 ConsumeQueue 物理文件的构建与存储结构&#xff0c;同时分析 RocketMQ 索引文件IndexFile 文件的存储原理、存储格式以及检索方式。RocketMQ 的存储…...

基于Java的浏览器的设计与实现毕业设计

技术&#xff1a;Java等摘要&#xff1a;当今世界是一个以计算机网络为核心的信息时代&#xff0c;互联网为人们快速获取、发布和传递信息提供了便捷&#xff0c;而浏览器作为互联网上查找信息的重要工具&#xff0c;给人们提供了巨大而又宝贵的信息财富&#xff0c;受到了大家…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

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

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...