LeetCode 416. 分割等和子集(动态规划)
发布日期:2021-07-01 03:25:54
浏览次数:3
分类:技术文章
本文共 2330 字,大约阅读时间需要 7 分钟。
1. 题目
给定一个只包含正整数的非空数组。
是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200示例 1:输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2:输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集.
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/partition-equal-subset-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
类似题目:
- 每个元素取或者不取,动态规划,求解所有可能的和情况
class Solution { public: bool canPartition(vector & nums) { if(nums.size() <= 1) return false; int sum = 0, i, j; for(i = 0 ; i < nums.size(); ++i) sum += nums[i]; if(sum&1) return false;//奇数不可分 //dp求解,每个元素拿或者不拿,求解所有的状态 set state; state.insert(0);//初始化 state.insert(nums[0]); for(i = 1; i < nums.size(); ++i) { for(auto it = state.rbegin(); it != state.rend(); ++it) { //用set,不能用哈希set,且必须逆序遍历,新插入的不会被本次遍历到 state.insert(*it+nums[i]); } if(state.count(sum>>1)) return true; } return false; }};
936 ms 16.3 MB
- 采用数组实现dp
class Solution { public: bool canPartition(vector & nums) { if(nums.size() <= 1) return false; int sum = 0, i, j; for(i = 0 ; i < nums.size(); ++i) sum += nums[i]; if(sum&1) return false;//奇数不可分 //dp求解,每个元素拿或者不拿,求解所有的状态 vectorstate(sum+1, false); state[0] = true;//初始化 state[nums[0]] = true; for(i = 1; i < nums.size(); ++i) { for(j = sum; j >= 0; --j) { if(state[j]) state[j+nums[i]] = true; } if(state[sum>>1]) return true; } return false; }};
312 ms 8.9 MB
- 再优化下存储空间,只查找到 sum/2 的状态,超过的忽略
- 以下代码有bug
[99,1]
这个例子,第一个数会越界
class Solution { public: bool canPartition(vector & nums) { if(nums.size() <= 1) return false; int sum = 0, i, j; for(i = 0 ; i < nums.size(); ++i) sum += nums[i]; if(sum&1) return false;//奇数不可分 //dp求解,每个元素拿或者不拿,求解所有的状态 sum >>= 1; vectorstate(sum+1, false); state[0] = true;//初始化 state[nums[0]] = true; for(i = 1; i < nums.size(); ++i) { for(j = sum; j >= 0; --j) { if(state[j] && j+nums[i] <= sum) state[j+nums[i]] = true; } if(state[sum]) return true; } return false; }};
164 ms 8.8 MB
转载地址:https://michael.blog.csdn.net/article/details/106216416 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月14日 03时28分19秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【语言-c#】C# 注释详细介绍说明
2019-05-02
MySQL 内存模型
2019-05-02
node.js 实现一个简单的登录拦截器
2019-05-02
c++抽象类、纯虚函数以及巧用纯虚析构函数实现接口类【转】
2019-05-02
Caffe 安装错误记录及解决办法【转】
2019-05-02
Android用类继承Application的全局变量使用注意
2019-05-02
算法排序之桶排序
2019-05-02
lambda表达式初探
2019-05-02
C++ Template类模板的特化(3.3节, 3.4节)
2019-05-02
第05章 函数
2019-05-02
第08章 输入和输出
2019-05-02
QT中文乱码的解
2019-05-02
网上Qt多线程同步的一种普遍误识
2019-05-02
libcurl smtp发送邮件附件大小限制问题
2019-05-02
Qt中用QuaZip来压缩和解压缩文件
2019-05-02
第13章 Windows内存体系结构
2019-05-02
windows 和 linux 下c/c++内存分布(整理)
2019-05-02
Qt解析XML文件(QDomDocument)
2019-05-02
Qt图形视图框架
2019-05-02
Qt5中表格处理大数据量
2019-05-02