当前位置: 首页 > 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; ------…...

基于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;积分&…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...