【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));}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1486822.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

leetcode算法题之接雨水

这是一道很经典的题目&#xff0c;问题如下&#xff1a; 题目地址 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 解法1&#xff1a;动态规划 动态规划的核心就是将问题拆分成若干个子问题求解&#…

2024算法、高性能计算与人工智能国际学术会议(AHPCAI 2024)

2024算法、高性能计算与人工智能国际学术会议&#xff08;AHPCAI 2024&#xff09; 2024 International Conference on Algorithms, High Performance Computing and Artificial Intelligence 2024年8月14-16日 | 中国-郑州 2024中国算力大会正在发起“算力中国最佳学术论文…

今天我们聊聊C#的并发和并行

并发和并行是现代编程中的两个重要概念&#xff0c;它们可以帮助开发人员创建高效、响应迅速、高性能的应用程序。在C#中&#xff0c;这些概念尤为重要&#xff0c;因为该语言提供了对多线程和异步编程的强大支持。本文将介绍C#中并发和并行编程的关键概念、优点&#xff0c;并…

Langchain核心模块与实战[7]:专业级Prompt工程调教LLM[输入输出接口、提示词模板与例子选择器的协同工程]

Langchain核心模块与实战[7]:专业级Prompt工程调教LLM[输入输出接口、提示词模板与例子选择器的协同工程] 1. 大模型IO接口 任何语言模型应用的核心元素是…模型的输入和输出。LangChain提供了与任何语言模型进行接口交互的基本组件。 提示 prompts : 将模型输入模板化、动态…

【LeetCode:3096. 得到更多分数的最少关卡数目+ 前缀和】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

百度,有道,谷歌翻译API

API翻译 百度&#xff0c;有道&#xff0c;谷歌API翻译&#xff08;只针对中英相互翻译&#xff09;,其他语言翻译需要对应from&#xff0c;to的code 百度翻译 package fills.tools.translate; import java.util.ArrayList; import java.util.HashMap; import java.util.Lis…

宠物空气净化器哪款除臭效果好?质量好的养狗空气净化器排名

作为一个宠物家电小博主&#xff0c;炎炎夏日&#xff0c;家中的宠物给你带来的不仅仅是温暖的陪伴&#xff0c;还有那挥之不去的宠物异味。普通空气净化器虽然能够应对一般的空气净化需求&#xff0c;但对于养猫家庭特有的挑战&#xff0c;如宠物毛发、皮屑和异味等&#xff0…

大模型微调部署实战及类GPT工具的高效使用

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于大模型算法的研究与应用。曾担任百度千帆大模型比赛、BPAA算法大赛评委,编写微软OpenAI考试认证指导手册。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。授权多项发明专利。对机器学…

CSS3雷达扫描效果

CSS3雷达扫描效果https://www.bootstrapmb.com/item/14840 要创建一个CSS3的雷达扫描效果&#xff0c;我们可以使用CSS的动画&#xff08;keyframes&#xff09;和transform属性。以下是一个简单的示例&#xff0c;展示了如何创建一个类似雷达扫描的动画效果&#xff1a; HTM…

libtins初探-抓包嗅探

libtin 一、概述1. 可移植性2. 特性 二、基础知识1. PDU2. 地址类3. 地址范围类4. 网络接口5. 写pcap文件 三、嗅探1.嗅探基础2. 嗅探器配置3. 循环嗅探4. 使用迭代器嗅探6. 包对象7. 读取pcap文件8. 包的解析 四、发送包1. 发送网络层pdu2. 发送链路层pdu3. 发送和接收响应校验…

自训练和增量训练word2vec模型

1、自己准备训练语料文件 根据自己的业务场景准备训练数据&#xff0c;比如用户在商城上的同购行为序列或同浏览行为序列。 我们希望通过自己训练业务相关的语料word2vec模型来获得词嵌入、词相关性查询等。 1.1 准备语料库文件 # 示例&#xff1a;准备自己的一个大规模的语…

开局一个启动器:从零开始入坑ComfyUI

前几天刷某乎的时候看到了一位大佬写的好文&#xff0c;可图 IP-Adapter 模型已开源&#xff0c;更多玩法&#xff0c;更强生态&#xff01; - 知乎 (zhihu.com) 久闻ComfyUI大名&#xff0c;决定试一下。这次打算不走寻常路&#xff0c;不下载现成的一键包了&#xff0c;而是…

7.23模拟赛总结 [数据结构优化dp] + [神奇建图]

目录 复盘题解T2T4 复盘 浅复盘下吧… 7:40 开题 看 T1 &#xff0c;起初以为和以前某道题有点像&#xff0c;子序列划分&#xff0c;注意到状态数很少&#xff0c;搜出来所有状态然后 dp&#xff0c;然后发现这个 T1 和那个毛关系没有 浏览了一下&#xff0c;感觉 T2 题面…

宠物经济纵深观察:口红效应显著,呈可持续发展态势

七月以来&#xff0c;全国各地陆续开启高温模式。和人一样&#xff0c;“毛孩子们”同样也难耐高温&#xff0c;由此&#xff0c;围绕猫猫狗狗的“宠物经济”迅速升温&#xff0c;宠物冰垫、宠物饮水机、宠物烘干机......一系列宠物单品掀起夏日消费热潮。 就在几天前&#xf…

Hbase映射为Hive外表

作者&#xff1a;振鹭 Hbase对应Hive外表 (背景&#xff1a;在做数据ETL中&#xff0c;可能原始数据在列式存储Hbase中&#xff0c;这个时候&#xff0c;如果我们想清洗数据&#xff0c;可以考虑把Hbase表映射为Hive的外表&#xff0c;然后使用Hive的HQL来清除处理数据) 1. …

Java面试八股之Spring boot的自动配置原理

Spring boot的自动配置原理 Spring Boot 的自动配置原理是其最吸引人的特性之一&#xff0c;它大大简化了基于 Spring 框架的应用程序开发。以下是 Spring Boot 自动配置的基本原理和工作流程&#xff1a; 1. 启动类上的注解 Spring Boot 应用通常会在主类上使用 SpringBoot…

真实测评,霍尼韦尔、希喂、352宠物空气净化器性能对比

在快节奏的社会生活中&#xff0c;人们越来越注重精神需要&#xff0c;许多年轻人纷纷选择拥抱宠物&#xff0c;作为生活中的温馨伴侣。宠物们治愈心灵的同时也要付出一定“代价”&#xff0c;日常养护&#xff0c;如清理猫毛、管理气味以及保持宠物环境的清洁&#xff0c;都是…

webpack的基本介绍与使用

webpack基本介绍及其基础案例 概念 Webpack 是一个现代 JavaScript 应用程序的静态模块打包器&#xff08;module bundler&#xff09;。当 webpack 处理应用程序时&#xff0c;它会递归地构建一个依赖关系图&#xff0c;其中包含应用程序需要的每个模块&#xff0c;然后将所…

学习记录day16—— 数据结构 双向链表 循环链表

双向链表 1、概念 1&#xff09;就是从任意一个节点既能存储其前驱节点&#xff0c;又能存储后继节点 2)结构体中增加一个指向前驱节点的指针 //定义数据类型 typedef int datatype;//定义节点类型 typedef struct Node {union {int len;datatype data;};struct Node *prio; …

72 | 数据分析岗位招聘数据可视化

项目介绍 本项目旨在通过对智联招聘网站上发布的数据分析岗位信息的分析和可视化,帮助应届毕业生和希望进入数据分析行业的专业人士更好地理解当前的就业市场。通过收集包含职位名称、薪资范围、地点、工作经验、学历要求等关键信息的数据,项目深入探讨了数据分析岗位的多个…