java分割等和子集(力扣Leetcode416)
分割等和子集
力扣原题链接
给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
01背包理论 (解决能不能装满背包的问题)
分析
- 分成两个子集,且元素和相同,可以看成将原来的所有元素加和除以2,这不就分成两个子集元素和相同了嘛。然后确定一个子集里的元素和是一半,另一个子集自动旧是另一半。
- 然后,我们可以将数组中的每个元素看作是一种物品,每个物品的价值(value)等于它的数值,而背包的容量(capacity)等于数组元素的和的一半。
- 我们的目标是尝试将这些物品放入背包中,使得背包的价值恰好等于容量的一半。
- 注意如果元素和本来就不能分成两份,那么直接返回·false·。

状态定义
我们定义一个二维的动态规划数组 dp,其中 dp[i][j] 表示在前 i 个物品中,能否选取一些物品使得它们的总和等于 j。
状态转移方程
在状态转移方程中,我们需要考虑当前物品是否放入背包中的两种情况:
- 如果不放入当前物品
nums[i - 1],则dp[i][j] = dp[i - 1][j]; - 如果放入当前物品
nums[i - 1],则dp[i][j] = dp[i - 1][j - nums[i - 1]]。
综合以上两种情况,状态转移方程为:
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
初始化
我们需要对动态规划数组进行初始化,当没有物品或背包容量为0时。
Java解题
class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int a : nums){sum +=a;}if(sum % 2 !=0){return false;}int t = sum/2;int dp [] = new int[t+1];for(int i = 0 ;i < nums.length ;i ++){//遍历物品for (int j =t ; j >=nums[i] ;j--){//遍历背包 ! 倒序!dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);//背包最大价值的递推公式}}if(dp[t] == t ){//判断背包是否装满return true;}else{return false;}}
}
解题思路总结
通过以上步骤,我们可以分析出解决该问题的关键步骤,并用动态规划的思想进行解决。首先计算数组的总和,然后判断是否为偶数,如果不是偶数则返回false。接着根据动态规划的思想初始化dp数组,然后按照状态转移方程进行状态转移,最终返回dp数组的最后一个值。
相关文章:
java分割等和子集(力扣Leetcode416)
分割等和子集 力扣原题链接 给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] …...
383. 赎金信
给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以,返回 true ;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 func canConstruct(ransomNote …...
【二】【单片机】有关独立按键的实验
自定义延时函数Delay 分别用Delay.c文件存储Delay函数。用Delay.h声明Delay函数。每次将这两个文件复制到工程中,直接使用。 //Delay.c void Delay(unsigned int xms) //11.0592MHz {while(xms--){unsigned char i, j;i 2;j 199;do{while (--j);}…...
AJAX踩坑指南(知识点补充)
JWT JSON Web Token是目前最为流行的跨域认证解决方案 如何获取:在使用JWT身份验证中,当用户使用其凭据成功登录时,将返回JSON Web Token(令牌) Token本质就是一个包含了信息的字符串 如何获取Token:登录成功之后,服务…...
备战蓝桥杯Day29 - 拼接最大数字问题
问题描述 有n个非负整数,将其按照字符串拼接的方式拼接为一个整数如何拼接可以使得得到的整数最大? 例: 32,94,128,1286,6,71可以拼接除的最大整数为 94716321286128。 问题思路 1.比较两个字符串的第一个数字,数值大的在前面,数值小的在…...
基于springboot的mysql实现读写分离
前言: 首先思考一个问题:在高并发的场景中,关于数据库都有哪些优化的手段?常用的有以下的实现方法:读写分离、加缓存、主从架构集群、分库分表等,在互联网应用中,大部分都是读多写少的场景,设置两个库,主库和读库,主库的职能是负责写,从库主要是负责读…...
Python爬虫之Scrapy框架系列(24)——分布式爬虫scrapy_redis完整实战【XXTop250完整爬取】
目录: 每篇前言:1.使用分布式爬取豆瓣电影信息(1)settings.py文件中的配置:(2)spider文件的更改:(3)items.py文件(两个项目一致!&…...
提升效率,稳定可靠:亚信安慧AntDB的企业价值
亚信安慧AntDB分布式数据库凭借平滑扩展、高可用性和低成本三大核心优势,在业界获得了极高的评价和认可。这些优点不仅为AntDB提供了巨大的市场发展潜力,也使其成为众多企业在数据管理上的首选解决方案。 AntDB的平滑扩展特性极大地提升了企业的灵活性和…...
洛谷入门——P1567 统计天数
统计天数 题目描述 炎热的夏日,KC 非常的不爽。他宁可忍受北极的寒冷,也不愿忍受厦门的夏天。最近,他开始研究天气的变化。他希望用研究的结果预测未来的天气。 经历千辛万苦,他收集了连续 N ( 1 ≤ N ≤ 1 0 6 ) N(1 \leq N …...
C++概述
目录 一、C关键字(63个) 二、C几个关键点: 三、C语言缺陷一:命名冲突 四、C新概念:命名空间(namespace) 五、命名空间的嵌套: 六、展开命名空间:(using …...
Linux学习笔记16 - 系统命令
1. Linux 常见系统管理命令 命令含义格式su切换用户su [选项] [用户名]ps显示系统由该用户运行的进程列表ps [选项]top动态显示系统中运行的程序(一般为每隔 5s)topkill输出特定的信号给指定 PID(进程号)的进程,并根据…...
读书笔记--阅读华为数据治理之旅有感
通过阅读华为的数据治理之旅,了解到华为公司作为高科技企业的引领者,在数据治理工作、数字化智能化转型方面的确有许许多多值得大家学习的地方,华为公司的业务范围广泛,市场竞争压力大,迫切需要用一些高效的手段来减轻员工的工作量,让员工各司其职,在各自承担的主营业务…...
网络安全协议基本问题
Http和Https协议的端口号: Http:80 Https:443 网络监听: 网络监听是一种监视网络状态、数据流程以及网络上信息传输的工具,它可以将网络界面设定成监听模式,并且可以截获网络上所传输的信息。但是网络监…...
面试(一)
一. 说一下进程和线程的区别? (1)进程是资源分配的最小单位,线程是CPU调度的最小单位。 (2)线程是进程的一部分,一个线程只能属于一个进程,一个进程可以有多个线程,但至少有一个线程。 (3)进程有自己独立地址空间&a…...
libVLC windows开发环境搭建
1.简介 LibVLC是一个强大的开源库,它构成了VLC媒体播放器的核心部分。 LibVLC提供了一系列的功能接口,使得VLC能够处理流媒体的接入、音频和视频输出、插件管理以及线程系统等核心任务。 跨平台性:VLC作为一个跨平台的多媒体播放器&#x…...
【Netty】Netty的使用和常用组件详解
目录 一、简述 1.1 什么是Netty 1.2 Netty 的优势 1.3 为什么不用 Netty5? 1.4 为什么 Netty 使用 NIO 而不是 AIO? 1.5 为什么不用 Mina? 二、第一个 Netty 程序 2.1 Bootstrap、EventLoop(Group) 、Channel 2.1.1 Bootstrap 2.1.…...
Legacy|电脑Windows系统如何迁移到新安装的硬盘?系统迁移详细教程!
前言 前面讲了很多很多关于安装系统、重装系统的教程。但唯独没有讲到电脑换了新的硬盘之后,怎么把旧系统迁移到新的硬盘上。 今天小白就来跟各位小伙伴详细唠唠: 开始之前需要把系统迁移的条件准备好,意思就是在WinPE系统下,可…...
Windows 11 安装 Scoop
[Windows 11 安装 Scoop](Windows 11 安装 Scoop) 0. 引言 Scoop 从命令行安装您熟悉和喜爱的程序,差异最小。 它的主要功能如下: 消除权限弹出窗口 隐藏 GUI 向导样式的安装程序 防止PATH污染安装大量程序 避免安装和卸载程序的意外副作用 自动查…...
新能源汽车小三电系统
小三电系统 新能源电动汽车的"小三电"系统,一般指车载充电机(OBC)、车载 DC/DC 变换器,和高压直流配电盒(PDU)。一辆纯电动汽车一般配备一台OBC 和一台车载 DC/DC 变换器。OBC将外部输入的交流电转化为直流电输出给电池,DC/DC衔接…...
面试问答示范
文章目录 请做个自我介绍您的学历是统招吗?可以在学信网查询吗是全日制吗是双证吗?请介绍一下你上家公司的情况。介绍一下你们公司的服务器架构(网络架构)。说说你在工作中处理过的最棘手的技术问题讲一讲上家公司做过的项目为什么…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
