【Hot100】LeetCode—416. 分割等和子集
目录
- 题目
- 1- 思路
- 2- 实现
- ⭐152. 乘积最大子数组——题解思路
- 3- ACM 实现
题目
- 原题连接:416. 分割等和子集
1- 思路
理解为背包问题
- 思路: 能否将均分的子集理解为一个背包,比如对于
[1,5,11,5],判断能否凑齐背包为11的容量 - 在本题中,背包中的物品是不可以重用的
1.定义 dp 数组
dp[j]代表容量为 j 的数组的最大价值,在本题中,容量就是价值。重量为 5 的石头,价值就是 5- 可划分条件:
dp[target] == target也就是装满 target 的最大价值刚好是 target 这时候就可以划分
2.递推公式
dp[j] = Math.max(dp[j],dp[j-weight[i]]+values[i])——> 在本题目中weight和value是一个东西
3.初始化
2- 实现
⭐152. 乘积最大子数组——题解思路

class Solution {public boolean canPartition(int[] nums) {// 求targetint sum = 0;for(int s:nums){sum+=s;}//总和为奇数,不能平分if(sum % 2 != 0) return false;int target = sum / 2;// 1. 定义dpint[] dp = new int[target+1];// 2. 递推公式// dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);// 3.初始化,都为 0dp[0] = 0;// 4. 先遍历物品,后遍历背包(逆序)for(int i = 0 ;i < nums.length;i++){for(int j = target;j>=nums[i];j--){dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);if(dp[j] == target){return true;}}}return false;}
}
3- ACM 实现
public class splitNums {public static boolean splitNums(int[] nums){// 先求 targetint len = nums.length;int sum = 0;for(int i:nums){sum+=i;}if(sum%2==1) return false;int target = sum/2;// 1. 定义 dp 数组int[] dp = new int[target+1];// 2. 递推公式// dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);dp[0] = 0;// 3.初始化// 4. 遍历顺序,先遍历物品后遍历背包for(int i = 0 ; i < nums.length;i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);if (dp[j] == target) {return true;}}}return false;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组长度");int n = sc.nextInt();int[] nums = new int[n];for(int i = 0 ; i < n ; i++){nums[i] = sc.nextInt();}System.out.println("结果是"+splitNums(nums));}
}相关文章:
【Hot100】LeetCode—416. 分割等和子集
目录 题目1- 思路2- 实现⭐152. 乘积最大子数组——题解思路 3- ACM 实现 题目 原题连接:416. 分割等和子集 1- 思路 理解为背包问题 思路: 能否将均分的子集理解为一个背包,比如对于 [1,5,11,5],判断能否凑齐背包为 11 的容量…...
前端开发知识-vue
大括号里边放键值对,即是一个对象。 一、vue可以简化前端javascript的操作。 主要特点是可以实现视图、数据的双向绑定。 使用vue主要分为三个步骤: 1.javascript中引入vue.js 可以src中可以是vue的网址,也可以是本地下载。 2.在javasc…...
【嵌入式硬件】快衰减和慢衰减
1.引语 在使用直流有刷电机驱动芯片A4950时,这款芯片采用的是PWM控制方式,我发现他的正转、反转有两种控制方式,分别是快衰减和慢衰减。 2.理解 慢衰减:相当于加在电机(感性原件)两端电压消失,将电机两端正负短接。 快衰减:相当于加在电机(感性原件)两端电压消失,将电机…...
C语言 | Leetcode C语言题解之第275题H指数II
题目: 题解: int hIndex(int* citations, int citationsSize) {int left 0, right citationsSize - 1;while (left < right) {int mid left (right - left) / 2;if (citations[mid] > citationsSize - mid) {right mid - 1;} else {left mi…...
速盾:网络安全和 CDN 之间的关系是怎样的?
网络安全和内容交付网络(CDN)之间有着密切的关系。网络安全主要涉及保护网络和系统免受各种威胁和攻击,而CDN是一种用于提供更快速、高效和可靠的内容交付服务的技术。在当今数字化和云计算时代,网络安全和CDN之间的关系变得更加紧…...
数据库安全:MySQL安全配置,MySQL安全基线检查加固
「作者简介」:冬奥会网络安全中国代表队,CSDN Top100,就职奇安信多年,以实战工作为基础著作 《网络安全自学教程》,适合基础薄弱的同学系统化的学习网络安全,用最短的时间掌握最核心的技术。 这一章节我们需要知道MySQL的安全基线标准和加固方式。 MySQL基线检查 1、更新…...
【SpringBoot】参数传递
1.定义URL变量 RequestMapping("/user/{username}") ResponseBody public String userProfile(PathVariable String username){ return "user:"username; } 2.定义多个URL变量 RequestMapping("/user/{username}/blog/{blogId}") Response…...
Unity 骨骼动画(Skinned Mesh Renderer): 角色动画的高级渲染
在Unity中,骨骼动画(Skinned Mesh Renderer)是一种用于高级角色动画渲染的组件。它允许开发者将复杂的3D模型和动画应用到游戏角色上,实现逼真的视觉效果。本文将探讨Skinned Mesh Renderer的基本概念、使用方法以及如何优化性能。 Skinned Mesh Render…...
花几千上万学习Java,真没必要!(三十四)
1、泛型类: 测试代码: 创建一个Box类; package settest.com; public class Box<T> { // T stands for "Type" - T是一个占位符,用于表示具体的类型 // 类的内部可以使用T作为类型声明变量 private T t; // 构造方法&am…...
【代码】Python3|Scrapy框架初探(汽车之家大连市二手车车辆数据爬取、清洗与可视化)
本篇主要是整个项目的介绍,没提到太多琐碎的技术细节,以后有空的话会整理一下 Scrapy 和原生爬虫的差异,还有它坑人的一些地方,单发出来。 开源地址:https://github.com/shandianchengzi/car_home_spider 使用说明&a…...
C#中的new以及类
new关键字的用法 实例化对象:使用 new 关键字可以创建一个类的实例。例如: MyClass obj new MyClass(); 指定构造函数:如果类有多个构造函数,可以使用 new 关键字指定使用哪一个构造函数来创建对象。例如: MyC…...
Hbase简介和快速入门
一 Hbase简介 1 HBase定义 Apache HBase™ 是以hdfs为数据存储的,一种分布式、可扩展的NoSQL数据库。 2 HBase数据模型 HBase的设计理念依据Google的BigTable论文,论文中对于数据模型的首句介绍。Bigtable 是一个稀疏的、分布式的、持久的多维排序map…...
【AI落地应用实战】Amazon Bedrock +Amazon Step Functions实现链式提示(Prompt Chaining)
一、链式提示 Prompt Chaining架构 Prompt Chaining 是一种在生成式人工智能(如大型语言模型)中广泛使用的技术,它允许用户通过一系列精心设计的提示(Prompts)来引导模型生成更加精确、丰富且符合特定需求的内容。 P…...
vue Ref 和 Reactive 原理解析
文章目录 RefReactive Ref ref 的语义是指向一个值的引用,主要用于处理基本数据类型和单一值对象,即对值的引用进行包装和管理,而不是对对象的操作进行拦截,对于基础类型通过 getter 和 setter 实现拦截使用 Proxy 拦截对象的所有…...
【人工智能】Transformers之Pipeline(六):图像分类(image-classification)
目录 一、引言 二、图像分类(image-classification) 2.1 概述 2.2 技术原理 2.3 应用场景 2.4 pipeline参数 2.4.1 pipeline对象实例化参数 2.4.2 pipeline对象使用参数 2.4 pipeline实战 2.5 模型排名 三、总结 一、引言 pipeline&#x…...
编程语言漫谈之「初始化与赋值」——以C++和汇编语言为示例
编程语言漫谈之「初始化与赋值」——以C和汇编语言为示例 1. 赋值时汇编做了什么2. 在变量定义时做初始化, 与在使用时才进行初始化, 有区别吗? 1. 赋值时汇编做了什么 当我们在C中写下如下代码: int main() {int a 10;return 0; }这是一个简单的整数类型变量a的初始化赋值…...
windows使用ssh-agent管理私钥
主要有以下几个方面: 开启openssh 的 ssh-agent 服务 打开powershell 输入 Get-Service -Name ssh-agent 查看服务是否起来Start-Service ssh-agent 启动服务Stop-Service ssh-agent 关闭服务将私钥添加到ssh-agent 添加私钥 ssh-add ~/.ssh/id_rsa查询添加哪些私钥 ssh-add -…...
PostgreSQL 之 to_timestamp函数
to_timestamp 是 PostgreSQL 中的一个函数,用于将字符串或数字转换为时间戳。以下是关于 to_timestamp 的详细介绍: 引入版本 to_timestamp 函数在 PostgreSQL 7.3 版本中引入。 语法 to_timestamp 有两种主要的用法: 1.将字符串转换为时间戳 to_timestamp(text, text)第…...
USB3.0的等长要求到底是多少?
USB2.0与USB3.0接口的PCB布局布线要求PCB资源PCB联盟网 - Powered by Discuz! (pcbbar.com) 90欧姆阻抗,走差分线: 重点来了:...
力扣高频SQL 50题(基础版)第二十五题
文章目录 力扣高频SQL 50题(基础版)第二十五题619.只出现一次的最大数字题目说明实现过程准备数据实现方式结果截图 力扣高频SQL 50题(基础版)第二十五题 619.只出现一次的最大数字 题目说明 MyNumbers 表: ------…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
