【LeetCode】【算法】416. 分割等和子集

LeetCode 416. 分割等和子集

题目描述

给你一个 只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

思路

和LeetCode 494.目标和很相似,这道题也是用动态数组可以求解的。

  1. nums的所有元素求个sum,若sum % 2 != 0,则return false; 因为此时没办法分成两个等和子集
  2. 定义dp数组dp[nums.length][bagSize +1],其中bagSize = sum / 2;
  3. 初始化dp数组:dp[0][nums[0]]=1;
  4. 填充dp数组:嵌套循环,有两种可能性:
    I. nums[i] > j时,dp[i][j]=dp[i-1][j]
    II. 否则,求最值dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
  5. 返回:dp[nums.length-1][bagSize]==bagSize
  6. 为什么这里的递推式是求“最值”,我的理解是任何一个值都有可能是构成目标和的一部分

当然这可以用一维dp来解,因为nums[i]里面的数既是重量也是价值?但是我赶时间就没细看

代码

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if (sum % 2 != 0) return false; // 和无法评分,则无法分成两个相等的子集int bagSize = sum / 2; // 目标和的结果// 动态数组定义与初始化int[][] dp = new int[nums.length][bagSize + 1];if (nums[0] <= bagSize) dp[0][nums[0]] = 1;// 填充动态数组for (int i = 1; i < nums.length; i++) {for (int j = 1; j < bagSize + 1; j++) {if (nums[i] > j) dp[i][j] = dp[i - 1][j];else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);}}}return dp[nums.length - 1][bagSize] == bagSize;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Springboot+Vue+mysql前后端分离的Java项目部署教程

参考了网上许多文章&#xff0c;有的使用的是nginx&#xff0c;eclipse&#xff0c;其实只要是数据库或者java的软件基本都大同小异。 本人使用phpstudy对项目进行部署&#xff0c;亲测有效。 需要的软件&#xff1a; 1.Node.js安装&#xff08;ps&#xff1a;这一步我也不知道…

【MySQL】数据库整合攻略 :表操作技巧与详解

前言&#xff1a;本节内容讲述表的操作&#xff0c; 对表结构的操作。 是对表结构中的字段的增删查改以及表本身的创建以及删除。 ps&#xff1a;本节内容本节内容适合安装了MySQL的友友们进行观看&#xff0c; 实操更有利于记住哦。 目录 创建表 查看表结构 修改表结构 …

常用的c++新特性-->day03

断言和异常 断言断言的基本使用 静态断言静态断言的基本使用 异常异常基本使用c98异常案例 noexceptnoexcept简单案例 断言 断言的基本使用 #include <iostream> #include <cassert>// >>>>>>>>>>>>>>>> 断言的…

Python数据分析NumPy和pandas(二十七、数据可视化 matplotlib API 入门)

数据可视化或者数据绘图是数据分析中最重要的任务之一&#xff0c;是数据探索过程的一部分&#xff0c;数据可视化可以帮助我们识别异常值、识别出需要的数据转换以及为模型生成提供思考依据。对于Web开发人员&#xff0c;构建基于Web的数据可视化显示也是一种重要的方式。Pyth…

shell中执行hive指令以及hive中执行shell和hdfs指令语法

0. 简介 主要介绍了三种环境命令执行语法&#xff1a; shell中执行hive指令hive中执行shell指令hive中执行hdfs指令 1. shell中执行hive指令 语法&#xff1a;hive [-hiveconf xy]* [<-i filename>]* [<-f filename> | <-e query-string>] [-S] 说明&…

区块链技术入门:以太坊智能合约详解

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 区块链技术入门&#xff1a;以太坊智能合约详解 区块链技术入门&#xff1a;以太坊智能合约详解 区块链技术入门&#xff1a;以太…

【若依框架】代码生成详细教程,15分钟搭建Springboot+Vue3前后端分离项目,基于Mysql8数据库和Redis5,管理后台前端基于Vue3和Element Plus,开发小程序数据后台

今天我们来借助若依来快速的搭建一个基于springboot的Java管理后台&#xff0c;后台网页使用vue3和 Element Plus来快速搭建。这里我们可以借助若依自动生成Java和vue3代码&#xff0c;这就是若依的强大之处&#xff0c;即便你不会Java和vue开发&#xff0c;只要跟着石头哥也可…

AI与OCR:数字档案馆图像扫描与文字识别技术实现与项目案例

文末有免费工具可在线体验&#xff0c;或者网络搜索关键词“思通开源AI能力平台” 一、扫描与图像预处理 技术实现过程 在纸质档案的数字化过程中&#xff0c;首先需要使用高精度扫描仪对纸质文档进行扫描&#xff0c;生成高清的数字图像。这一步骤是整个OCR流程的基础&#xf…

科学计算服务器:如何计算算力?如何提升科学研究效率?

在现代科学研究的舞台上&#xff0c;科学计算服务器犹如一位强大的幕后英雄&#xff0c;为复杂科学计算任务的攻克提供着坚实支撑。准确计算其算力并充分发挥优势&#xff0c;对提升科学研究效率意义非凡。 服务器的中央处理器&#xff08;CPU&#xff09;计算力。在科学计算服…

Python爬虫基础-正则表达式!

前言 正则表达式是对字符串的一种逻辑公式&#xff0c;用事先定义好的一些特定字符、及这些特定字符的组合&#xff0c;组成一个“规则的字符串”&#xff0c;此字符串用来表示对字符串的一种“过滤”逻辑。正在在很多开发语言中都存在&#xff0c;而非python独有。对其知识点…

【go从零单排】迭代器(Iterators)

&#x1f308;Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 &#x1f4d7;概念 在 Go 语言中&#xff0c;迭代器的实现通常不是通过语言内置的迭代器类型&#x…

基于SpringBoot和Vue的公司文档管理系统设计与开发(源码+定制+开发)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

使用vite构建一个react网站,并部署到Netlify上

这篇教程中&#xff0c;我会教你如何用vite快速构建一个react网站&#xff0c;并把网站免费部署到Netlify上&#xff0c;让别人可以经由网址访问你的react网站。 1. 使用vite构建基础框架 npm create vitelatestcd vite-project npm install npm run dev2. 网站内容设计 3. 构…

青藤深度参编的终端安全国家标准正式发布

近日&#xff0c;国家市场监督管理总局、国家标准化管理委员会发布中华人民共和国国家标准公告&#xff0c;由TC260&#xff08;全国网络安全标准化技术委员会&#xff09;归口&#xff0c;公安部第三研究所牵头的GB/T 29240-2024《网络安全技术 终端计算机通用安全技术规范》&…

Python爬虫如何处理验证码与登录

Python爬虫如何处理验证码与登录 Python 爬虫在抓取需要登录的网站数据时&#xff0c;通常会遇到两个主要问题&#xff1a;登录验证和验证码处理。这些机制是网站用来防止自动化程序过度抓取数据的主要手段。本文将详细讲解如何使用 Python 处理登录与验证码&#xff0c;以便进…

Stream流(JAVA笔记第三十三期)

p.s.这是萌新自己自学总结的笔记&#xff0c;如果想学习得更透彻的话还是请去看大佬的讲解 目录 Stream流的使用步骤获取Stream流Stream流的中间方法Stream中的终结方法收集方法collect Stream流可以比作工厂的流水线 Stream流的概念 Stream流的使用步骤 先得到一条Stream流(…

基于python深度学习技术矩阵分解的推荐系统,通过学习隐含特征,实现推荐

实现了一个基于矩阵分解的推荐系统&#xff0c;用于预测用户对电影的评分。具体来说&#xff0c;该程序通过TensorFlow构建和训练一个模型&#xff0c;来学习用户和电影之间的隐含特征&#xff0c;并根据这些特征预测评分。以下是代码的主要功能和步骤的详细描述&#xff1a; …

Python学习从0到1 day27 第三阶段 Spark ③ 数据计算 Ⅱ

目录 一、Filter方法 功能 语法 代码 总结 filter算子 二、distinct方法 功能 语法 代码 总结 distinct算子 三、SortBy方法 功能 语法 代码 总结 sortBy算子 四、数据计算练习 需求&#xff1a; 解答 总结 去重函数&#xff1a; 过滤函数&#xff1a; 转换函数&#xff1a; 排…

「Mac玩转仓颉内测版2」入门篇2 - 编写第一个Cangjie程序

本篇详细介绍在Mac系统上创建首个Cangjie项目并编写、运行第一个Cangjie程序的全过程。内容涵盖项目创建、代码编写、程序运行与调试&#xff0c;以及代码修改后的重新运行。通过本篇&#xff0c;掌握Cangjie项目的基本操作&#xff0c;进一步巩固开发环境的配置&#xff0c;迈…

[Docker#2] 发展历史 | Namespace环境隔离 | Cgroup资源控制

目录 1.发展历史 Jail 时代 云时代 云原生时代 技术标准的确立 虚拟机 vs Docker 2. 容器化技术 2.1 Namespace 命令详解 1. dd 命令 2. mkfs 命令 3. df 命令 4. mount 命令 5. unshare 命令 实战 进程隔离 文件隔离 2.2 CGroup 相关命令 2.1 pidstat 2.…