力扣题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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:力扣题399除法求值
下一篇:力扣题406根据身高重建队列

发表评论

最新留言

网站不错 人气很旺了 加油
[***.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
nums在python_程序找到一对(i,j),其中nums [i] + nums [j] +(i -j)在Python中最大化?... 2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块 2019-04-21
grouping函数 mysql_sql聚合函数有哪些 2019-04-21
python os.walk如何不遍历隐藏文件_python 获取文件下所有文件或目录os.walk()的实例... 2019-04-21
python 股票估值_【中金固收·固收+】隐藏价值的角落:限售股AAP估值及Python实现方法(上)... 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
python barrier option pricing_《Python金融数据分析》书内代码实战与讲解(二)金融衍生物定价... 2019-04-21