Leetcode 494 目标和
题意理解:
给你一个非负整数数组
nums和一个整数target。向数组中的每个整数前添加
'+'或'-',然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1],可以在2之前添加'+',在1之前添加'-',然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于
target的不同 表达式 的数目。
简单来说:就是在元素前面加‘+’或‘-’使其结果值为target。
可以将其思路转换为:将数组元素分为两部分,其差为target。
则有part1-part2=target,part1+part2=sum
part1=(sum+target)/2
固有我们需要将数组元素分为两部分,一部分较大的为part1=(sum+target)/2,较小的部分为part2=(sum-target)/2。
此时,我们再次转变思路:将其构造成0-1背包问题:
背包大小为m=(sum+target)/2
物品为[0,n]的元素,其价值和重量都是nums[]
接下来,使用动态规划中的0-1背包思路解决问题。
解题思路:
首先理解题意,将其转换为一个背包问题,使用动态规划的思路来求解。
动态规划五部曲:
(1)dp[i][j]或dp[i]的含义
(2)递推公式
(3)根据题意初始化
(4)遍历求解:先遍历包还是先遍历物品
(5)打印——debug
1.动态规划二维dp数组
- dp[i][j]表示[0,i]的元素装满大小为j的背包有多少种方法。
- 递推公式:dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]],
- 当当前物品大于当前背包的大小时,放满大小为j的背包的方法数仍就为dp[i-1][j].
- 当当前物品小于等于当前背包的大小时,放满大小为j的背包的方法数=dp[i-1][j]+dp[i-1][j-nums[i]],其中dp[i-1][j-nums[i]]是增加了物品nums[i]后增加的方法数。
- 初始化:初始化第一列,其中特别的:放满背包大小0 有多少种方法——要么什么也不放,要么放入大小为0的物品。初始化时要根据问题,具体分析。
- 遍历:由于二维数组保留了两个维度所有值,所以先便利包还是先遍历物品都可以
public int findTargetSumWays(int[] nums, int target) {int sum=0;for(int num:nums){sum+=num;}//是否能按照需求分成两部分if((sum+target)%2!=0) return 0;if((sum-target)%2!=0) return 0;//把所有值当作整数,分成两部分一正一负即可,所以如果target总保持为正数if(target<0) target=-target;int size= (int)Math.ceil((float)(sum+target)/2);int dp[][]=new int[nums.length][size+1];//初始化for(int[] temp:dp) Arrays.fill(temp,0);int countZero=0;for(int i=0;i<nums.length;i++){if(nums[i]==0) countZero++;dp[i][0]=countZero+1;}for(int j=1;j<=size;j++){if(nums[0]==j) dp[0][j]=1;else dp[0][j]=0;}//遍历顺序for(int i=1;i< nums.length;i++){for(int j=0;j<=size;j++){if(j<nums[i]){dp[i][j]=dp[i-1][j];}else{dp[i][j]=dp[i-1][j]+dp[i-1][j - nums[i]];}}}return dp[nums.length-1][size];}

2.一维滚动数组——存储压缩
- dp[j]表示装满大小为j的背包有多少种方式。
- 递推公式:dp[j]=max(dp[j],dp[j-weight[i]]+values[i])
- 初始化:右边的值总是由最左边的值推导而来,dp[0]表示使背包价值为0有多少种放置方法——要么什么也不放,要么放大小为0的物品。
- 遍历:由于以为滚动数组是二维dp数组的动态行滚动更新,所以遍历顺序总是先物品后背包。
- 注意:为了防止用同层修改过的值修改本行其他值,导致物体重复放置,故采用倒序遍历背包。
public int findTargetSumWays(int[] nums, int target) {int sum=0;for(int num:nums) sum+=num;if((sum+target)%2!=0) return 0;if((sum-target)%2!=0) return 0;if(target<0) target=-target;int size= (int)Math.ceil((float)(sum+target)/2);int dp[]=new int[size+1];//初始化Arrays.fill(dp,0);dp[0]=1;//遍历顺序for(int i=0;i< nums.length;i++){for(int j=size;j>=nums[i];j--){dp[j] += dp[j - nums[i]];}}return dp[size];}

3.分析
时间复杂度:O(
)
空间复杂度:
二维:O(n*size)
一维:O(size)
相关文章:
Leetcode 494 目标和
题意理解: 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums [2, 1] ,可以在 2 之前添加 ,在 1 之前添…...
Windows常用命令(文件相关、进程相关、网络相关、用户相关、特殊符号)
Windows常用命令 Windows常用命令 Windows常用命令0x01 基础操作0x02 文件操作0x03 进程操作0x04 网络相关0x05 用户相关0x06 特殊符号 0x01 基础操作 清屏:cls 关机:shutdown -s(关机)-r(重启) -f(强制)…...
摘:国六排放法规下的重型车车载终端的革新
系列文章目录 文章目录 系列文章目录一、国六排放法规下的重型车车载终端的革新二、使用步骤1.引入库2.读入数据 一、国六排放法规下的重型车车载终端的革新 添加链接描述 ascii码 二、使用步骤 1.引入库 代码如下(示例): import numpy a…...
java读取json文件并解析并修改
要在Java中读取和解析JSON文件,可以使用Java提供的JSON库,例如Jackson、Gson或JSON.simple。以下是使用Jackson库的示例代码: 首先,你需要添加Jackson库的依赖到你的项目中。如果你正在使用Maven,可以在pom.xml文件中…...
2024年前端面试中JavaScript的30个高频面试题之基础知识
中级 高级知识 充分准备你的下一个JavaScript面试,增强信心! 无论你是老手还是刚进入技术行业,这份2024年必备资源都将帮助你复习核心概念,从基本语言特性到高级主题。 在本文中,我汇总了30个最关键的JavaScript面试题以及详细的答案和代码示例。 深入探索这宝贵的收藏,以确…...
鸿蒙设备-开发板基础学习(BearPi-HM Micro)
theme: minimalism 每当学习一门新的编程语言或者上手一款新的开发板,在学习鸿蒙设备开发过程中,带大家写的第一个程序,通过这个程序,我们可以对鸿蒙设备开发的整个流程有一个初步的体验。BearPi-HM Micro开发板为例:…...
Oracle导入导出dump
创建目录: create directory *** as /bak; #***名称可以随便命名 需要手工创建/bak,并且此目录oracle用户有读取,目录地址空间要够用。 查看所有目录 select * from DBA_DIRECTORIES;---查询导入导出的目录 导入 impdp ****/**** direc…...
判断vector、string是否存在某个元素
1、string字符串中是否存在某个字符(char) string中find()返回值是字母在母串中的位置(下标索引),如果没有找到,那么会返回一个特别的标记npos。(返回值可以看成是一个int型的数) …...
C语言--结构体详解
C语言--结构体详解 1.结构体产生原因2.结构体声明2.1 结构体的声明2.2 结构体的初始化2.3结构体自引用 3.结构体内存对齐3.1 对齐规则3.2 为什么存在内存对齐3.3 修改默认对⻬数 4. 结构体传参 1.结构体产生原因 C语言将数据类型分为了两种,一种是内置类型…...
外卖骑手与行人之间的非零和博弈
一、背景 自2013年成立以来,美团外卖一直保持着高速增长,通过提供便捷、高效的外卖服务,满足了大量消费者的需求。美团外卖的服务不仅限于基础的送餐服务,还涵盖了多种生活服务,如超市便利、药品配送等,满…...
[AutoSar]基础部分 RTE 06 对runnable的触发和SWC的影响
目录 关键词平台说明一、runnable二、RTE的event2.1Mode类型event2.2周期触发类型2.3 数据交互触发 三、internal runnable value四、专属运行区指定五、per_instance memory 关键词 嵌入式、C语言、autosar、Rte 平台说明 项目ValueOSautosar OSautosar厂商vector芯片厂商T…...
网络层协议及IP编址与IP路由基础华为ICT网络赛道
目录 4.网络层协议及IP编址 4.1.网络层协议 4.2.IPv4地址介绍 4.3.子网划分 4.4.ICMP协议 4.5.IPv4地址配置及基本应用 5.IP路由基础 5.1.路由概述 5.2.静态路由 5.3.动态路由 5.4.路由高阶特性 4.网络层协议及IP编址 4.1.网络层协议 IPv4(Internet Protocol Versi…...
基于stm32f4的蓝牙控制小车
1. 引言 蓝牙的创始人是瑞典爱立信公司,蓝牙技术是一种无限数据与语音通信的开放性全球规范,它以低成本的近距离无线连接为基础,为固定与移动设备通信环境建立一个特别连接。手机之间通过蓝牙实现数据共享成为常理,将手机变为遥…...
基于BP神经网络的租金预测
目录 摘要 BP神经网络参数设置及各种函数选择 参数设置 训练函数 传递函数 学习函数 性能函数 显示函数 前向网络创建函数 BP神经网络训练窗口详解 训练窗口例样 训练窗口四部详解 基于BP神经网络的租金预测 代码下载:基于BP神经网络的租金预测(代码完整,数据齐全)资源-CS…...
C语言学习记录—进阶作业(通讯录文件版本)
通讯录 1. 添加一个函数,在退出通讯录的时候把信息到保存到文件中 2. 添加一个函数,在通讯录打开的时候,可以把文件中的信息加载到通讯录中 contact.h文件 #pragma once #include <string.h> #include <stdio.h> #include <…...
深度学习笔记(四)——TF2构建基础网络常用函数+简单ML分类网络实现
文中程序以Tensorflow-2.6.0为例 部分概念包含笔者个人理解,如有遗漏或错误,欢迎评论或私信指正。 截图和程序部分引用自北京大学机器学习公开课 TF2基础常用函数 1、张量处理类 强制数据类型转换: a1 tf.constant([1,2,3], dtypetf.floa…...
GPT function calling v2
原文:GPT function calling v2 - 知乎 OpenAI在2023年11月10号举行了第一次开发者大会(OpenAI DevDays),其中介绍了很多新奇有趣的新功能和新应用,而且更新了一波GPT的API,在1.0版本后的API调用与之前的0.…...
【Golang】IEEE754标准二进制字符串转为浮点类型
IEEE754介绍 IEEE 754是一种标准,用于表示和执行浮点数运算的方法。在这个标准中,单精度浮点数使用32位二进制表示,分为三个部分:符号位、指数位和尾数位。 符号位(s)用一个位来表示数的正负,0表示正数,1表…...
【开源项目】轻量元数据管理解决方案——Marquez
大家好,我是独孤风。 又到了本周的开源项目推荐。最近推荐的元数据管理项目很多,但是很多元数据管理平台的功能复杂难用。 那么有没有轻量一点的元数据管理项目呢? 今天为大家推荐的开源项目,就是一个轻量级的元数据管理工具。虽然…...
dirty file page
转自:https://www.cnblogs.com/zhiminyu/p/17330763.html 0.前言 Linux 内核Page Cache 和Buffer Cache 关系及演化历史 一文中讲过Linux 2.4之后将Page Cache和Buffer Cache 进行了融合,在buffer_head 中添加了b_page,很容易就能找到缓存的…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
麒麟系统使用-进行.NET开发
文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的,如果需要进行.NET开发,则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET,所以要进…...
Copilot for Xcode (iOS的 AI辅助编程)
Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot,它能根据上下文补全代码,快速生成常用…...
C# WPF 左右布局实现学习笔记(1)
开发流程视频: https://www.youtube.com/watch?vCkHyDYeImjY&ab_channelC%23DesignPro Git源码: GitHub - CSharpDesignPro/Page-Navigation-using-MVVM: WPF - Page Navigation using MVVM 1. 新建工程 新建WPF应用(.NET Framework) 2.…...
IP选择注意事项
IP选择注意事项 MTP、FTP、EFUSE、EMEMORY选择时,需要考虑以下参数,然后确定后选择IP。 容量工作电压范围温度范围擦除、烧写速度/耗时读取所有bit的时间待机功耗擦写、烧写功耗面积所需要的mask layer...
SFTrack:面向警务无人机的自适应多目标跟踪算法——突破小尺度高速运动目标的追踪瓶颈
【导读】 本文针对无人机(UAV)视频中目标尺寸小、运动快导致的多目标跟踪难题,提出一种更简单高效的方法。核心创新在于从低置信度检测启动跟踪(贴合无人机场景特性),并改进传统外观匹配算法以关联此类检测…...
