力扣题416分割等和子集
发布日期:2022-03-04 11:48:18
浏览次数:8
分类:技术文章
本文共 2600 字,大约阅读时间需要 8 分钟。
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2:输入:nums = [1,2,3,5]
输出:false 解释:数组不能分割成两个元素和相等的子集。1.如果直接去思考两个子集中要存入哪些元素,会发现时很困难的,想不到什么解决的办法。因此转换一种思路,给定一个只包含正整数的非空数组nums[0],判断是否可以从数组中选出一些数字,使得这些数字的和等于整个数组的元素和的一半,就把问题转换成了0-1背包问题。因此可以使用动态规划求解。
dp[i][j]表示在[0,i]的取数范围内是否能达到数字j。
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; if (n < 2) {//如果数字小于2,肯定不能分,直接返回false return false; } int sum = 0; int maxNum = 0; //求出整个数组的和及最大值 for (int i = 0;i < n;i++) { sum += nums[i]; maxNum = Math.max(maxNum,nums[i]); } if (sum % 2 != 0) {//如果时奇数的话,就肯定不能分,直接返回false return false; } int target = sum / 2;//目标值 if (maxNum > target) {//如果最大值大于目标值,那么剩下的值的和肯定小于目标值,直接返回false return false; } boolean[][] dp = new boolean[n][target + 1]; //边界条件 for (int i = 0;i < n;i++) { dp[i][0] = true;//所有范围内达到目标值0都是true } dp[0][nums[0]] = true;//对于第一个数字达到目标值nums[0]也是true for (int i = 1;i < n;i++) { for (int j = 1;j <= target;j++) { if (j >= nums[i]) {//如果目标值大于当前值,那么分成两种情况,取当前值或这不取当前值 dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]]; } else {//如果目标值小于当前值,那么肯定不能取当前值了。只有1种情况。 dp[i][j] = dp[i - 1][j]; } } } return dp[n - 1][target]; }}
优化:代码中发现不需要把所有范围的都存储下来,每一行的dp值都只与上一行的dp值有
关,dp[i-1]的状态是不需要存储的,因此可以对代码进行优化,只需要保存dp[j]和dp[j-nums[i]]
即可。需要注意的是第二层的循环我们需要从大到小计算,因为如果我们从小到大更新dp值,
那么在计算dp[j]值的时候,dp[j−nums[i]]已经是被更新过的状态,不再是上一行的dp值。
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; if (n < 2) {//如果数字小于2,肯定不能分,直接返回false return false; } int sum = 0; int maxNum = 0; //求出整个数组的和及最大值 for (int i = 0;i < n;i++) { sum += nums[i]; maxNum = Math.max(maxNum,nums[i]); } if (sum % 2 != 0) {//如果时奇数的话,就肯定不能分,直接返回false return false; } int target = sum / 2;//目标值 if (maxNum > target) {//如果最大值大于目标值,那么剩下的值的和肯定小于目标值,直接返回false return false; } boolean[] dp = new boolean[target + 1]; //边界条件 dp[0] = true;//达到目标值nums[0]是true for (int i = 1;i < n;i++) { for (int j = target;j >= nums[i];j--) { dp[j] = dp[j] | dp[j - nums[i]]; } } return dp[target]; }}
题源:
转载地址:https://blog.csdn.net/xxyneymar/article/details/122209538 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年03月19日 06时08分12秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
c语言 实现sizeof功能,C语言简单实现sizeof功能代码
2019-04-21
c语言sin函数近似值,用泰勒公式求sin(x)的近似值
2019-04-21
c 语言登录系统源代码,c语言源代码---------------个人图书管理系统
2019-04-21
android线程通信方式,Android 主线程和子线程通信问题
2019-04-21
cps1 cps2 android,图文教程:CPS1和CPS2模拟器使用
2019-04-21
在线设计 html5 表单,html5注册表单制作-表单制作-小程序表单制作
2019-04-21
android小闹钟课程设计,《小闹钟》教学设计
2019-04-21
mysql文件系统_MySQL文件系统先睹为快(1)
2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块
2019-04-21
grouping函数 mysql_sql聚合函数有哪些
2019-04-21
java文档生成_Java文档自动生成
2019-04-21
java 共享目录_java 操作windows 共享目录方法介绍
2019-04-21
java 监控 宕机_JAVA监测tomcat是否宕机,控制重启
2019-04-21
catch that cow java_POJ3278——Catch That Cow
2019-04-21
java integer 不变模式_Java代码的变与不变
2019-04-21
java guava 使用_Java8-Guava实战示例
2019-04-21