【Leetcode刷题篇】leetcode416 分割等和子集
发布日期:2021-06-29 15:34:50
浏览次数:3
分类:技术文章
本文共 882 字,大约阅读时间需要 2 分钟。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
解题思路:可看成背包问题,属于背包问题里面的0-1背包问题。
class Solution { public boolean canPartition(int[] nums) { // 动态规划解题 背包问题- 01背包问题 恰好问题 // 先判断构不构成 int sum = 0; for(int num:nums) { sum += num; } if(sum%2==1) { return false; } // 目标值 int target = sum/2; int length = nums.length; // 动态规划 boolean[][] dp = new boolean[length+1][target+1]; // 初始化 for(int i=0;i=0) { // 能放 当前数nums[i-1] dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]; }else { // 没容量 dp[i][j] = dp[i-1][j]; } } } return dp[length][target]; }}
转载地址:https://codingchaozhang.blog.csdn.net/article/details/110927427 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月23日 09时04分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Eureka 如何快速的、优雅的停止某个微服务
2019-04-29
Eureka 实现安全认证
2019-04-29
Nginx 反向代理、负载均衡配置、Location正则表达式
2019-04-29
SpringBoot + WebSocket 实现前后端的收发消息
2019-04-29
SpringBoot 整合 JWT 实现统一认证
2019-04-29
SpringBoot 使用 CompletableFuture 实现非阻塞异步编程
2019-04-29
即刻就业:本科毕业如何快速高薪就业?
2019-04-29
JAVA中的浮点数与二进制
2019-04-29
JAVA笔记(二)--Java初始
2019-04-29
JAVA笔记(三)--变量及运算符
2019-04-29
JAVA笔记(四)--三大结构语句
2019-04-29
JAVA语言基础(五)--数组
2019-04-29
JAVA项目案例详解带代码
2019-04-29
JAVA九种排序算法详解
2019-04-29
JAVA笔记(六)面向对象--类和对象
2019-04-29
JAVA笔记(十一)面向对象--多态
2019-04-29
webpack打包错误:Invalid configuration object. Webpack has been initialised using a configuration object
2019-04-29
TypeError: this.getOptions is not a function
2019-04-29