当前位置: 首页 > 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;受到了大家…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...