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

【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]) ——> 在本题目中 weightvalue 是一个东西

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 实现 题目 原题连接&#xff1a;416. 分割等和子集 1- 思路 理解为背包问题 思路&#xff1a; 能否将均分的子集理解为一个背包&#xff0c;比如对于 [1,5,11,5]&#xff0c;判断能否凑齐背包为 11 的容量…...

前端开发知识-vue

大括号里边放键值对&#xff0c;即是一个对象。 一、vue可以简化前端javascript的操作。 主要特点是可以实现视图、数据的双向绑定。 使用vue主要分为三个步骤&#xff1a; 1.javascript中引入vue.js 可以src中可以是vue的网址&#xff0c;也可以是本地下载。 2.在javasc…...

【嵌入式硬件】快衰减和慢衰减

1.引语 在使用直流有刷电机驱动芯片A4950时,这款芯片采用的是PWM控制方式,我发现他的正转、反转有两种控制方式,分别是快衰减和慢衰减。 2.理解 慢衰减:相当于加在电机(感性原件)两端电压消失,将电机两端正负短接。 快衰减:相当于加在电机(感性原件)两端电压消失,将电机…...

C语言 | Leetcode C语言题解之第275题H指数II

题目&#xff1a; 题解&#xff1a; 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 之间的关系是怎样的?

网络安全和内容交付网络&#xff08;CDN&#xff09;之间有着密切的关系。网络安全主要涉及保护网络和系统免受各种威胁和攻击&#xff0c;而CDN是一种用于提供更快速、高效和可靠的内容交付服务的技术。在当今数字化和云计算时代&#xff0c;网络安全和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中&#xff0c;骨骼动画(Skinned Mesh Renderer)是一种用于高级角色动画渲染的组件。它允许开发者将复杂的3D模型和动画应用到游戏角色上&#xff0c;实现逼真的视觉效果。本文将探讨Skinned Mesh Renderer的基本概念、使用方法以及如何优化性能。 Skinned Mesh Render…...

花几千上万学习Java,真没必要!(三十四)

1、泛型类&#xff1a; 测试代码&#xff1a; 创建一个Box类; package settest.com; public class Box<T> { // T stands for "Type" - T是一个占位符&#xff0c;用于表示具体的类型 // 类的内部可以使用T作为类型声明变量 private T t; // 构造方法&am…...

【代码】Python3|Scrapy框架初探(汽车之家大连市二手车车辆数据爬取、清洗与可视化)

本篇主要是整个项目的介绍&#xff0c;没提到太多琐碎的技术细节&#xff0c;以后有空的话会整理一下 Scrapy 和原生爬虫的差异&#xff0c;还有它坑人的一些地方&#xff0c;单发出来。 开源地址&#xff1a;https://github.com/shandianchengzi/car_home_spider 使用说明&a…...

C#中的new以及类

new关键字的用法 实例化对象&#xff1a;使用 new 关键字可以创建一个类的实例。例如&#xff1a; ​ MyClass obj new MyClass(); 指定构造函数&#xff1a;如果类有多个构造函数&#xff0c;可以使用 new 关键字指定使用哪一个构造函数来创建对象。例如&#xff1a; ​ MyC…...

Hbase简介和快速入门

一 Hbase简介 1 HBase定义 Apache HBase™ 是以hdfs为数据存储的&#xff0c;一种分布式、可扩展的NoSQL数据库。 2 HBase数据模型 HBase的设计理念依据Google的BigTable论文&#xff0c;论文中对于数据模型的首句介绍。Bigtable 是一个稀疏的、分布式的、持久的多维排序map…...

【AI落地应用实战】Amazon Bedrock +Amazon Step Functions实现链式提示(Prompt Chaining)

一、链式提示 Prompt Chaining架构 Prompt Chaining 是一种在生成式人工智能&#xff08;如大型语言模型&#xff09;中广泛使用的技术&#xff0c;它允许用户通过一系列精心设计的提示&#xff08;Prompts&#xff09;来引导模型生成更加精确、丰富且符合特定需求的内容。 P…...

vue Ref 和 Reactive 原理解析

文章目录 RefReactive Ref ref 的语义是指向一个值的引用&#xff0c;主要用于处理基本数据类型和单一值对象&#xff0c;即对值的引用进行包装和管理&#xff0c;而不是对对象的操作进行拦截&#xff0c;对于基础类型通过 getter 和 setter 实现拦截使用 Proxy 拦截对象的所有…...

【人工智能】Transformers之Pipeline(六):图像分类(image-classification)

目录 一、引言 二、图像分类&#xff08;image-classification&#xff09; 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欧姆阻抗&#xff0c;走差分线&#xff1a; 重点来了&#xff1a;...

力扣高频SQL 50题(基础版)第二十五题

文章目录 力扣高频SQL 50题&#xff08;基础版&#xff09;第二十五题619.只出现一次的最大数字题目说明实现过程准备数据实现方式结果截图 力扣高频SQL 50题&#xff08;基础版&#xff09;第二十五题 619.只出现一次的最大数字 题目说明 MyNumbers 表&#xff1a; ------…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...