代码拉取完成,页面将自动刷新
package code;
import java.util.HashSet;
/*
* 416. Partition Equal Subset Sum
* 题意:一个数组,可否分成和相等的两部分
* 难度:Medium
* 分类:Dynamic Programming
* 思路:题意可以转换为用任意个元素组成的和等于数组和/2。可以和 lc1, lc15 3-Sum 对比。
* dfs过不了,2^n
* 0,1背包问题,递推比较简单,所以空间可以压缩成一维
* 自己想的思路其实和压缩后的0,1背包类似,但没想到该问题可以抽象为0,1背包
* dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
* i表示数组长度,j表示求和为j
* Tips:lc416, lc494
*/
public class lc416 {
public static void main(String[] args) {
int[] nums = {1, 2, 5};
System.out.println(canPartition(nums));
}
public static boolean canPartition(int[] nums) { //自己写的不知道什么,回头看已经看不懂自己的代码了。。。
int sum = 0;
for (int i : nums) {
sum+=i;
}
if(sum%2==1)
return false;
sum/=2;
HashSet<Integer> s = new HashSet();
for (int i = 0; i < nums.length ; i++) {
if(nums[i]==sum)
return true;
HashSet<Integer> s2 = new HashSet(); // 新建一个set,用以存放这一轮的结果
s2.add(nums[i]);
for(int j: s){
if(j+nums[i]==sum)
return true;
s2.add(j+nums[i]);
}
s.addAll(s2);
}
return false;
}
public boolean canPartition2(int[] nums) {
// check edge case
if (nums == null || nums.length == 0) {
return true;
}
// preprocess
int volumn = 0;
for (int num : nums) {
volumn += num;
}
if (volumn % 2 != 0) {
return false;
}
volumn /= 2;
// dp def
boolean[] dp = new boolean[volumn + 1];
// dp init
dp[0] = true;
// dp transition
for (int i = 1; i <= nums.length; i++) {
for (int j = volumn; j >= nums[i-1]; j--) { //从后往前更新,压缩空间
dp[j] = dp[j] || dp[j - nums[i-1]];
}
}
return dp[volumn];
}
public boolean canPartition3(int[] nums) {
int sum = 0;
for(int i: nums) sum+=i;
if(sum%2==1) return false;
sum = sum/2;
boolean[][] dp = new boolean[nums.length+1][sum+1];
for(int i =0; i<=nums.length; i++) dp[i][0]=true; //注意赋值0
for(int i=1; i<=nums.length; i++){
for(int j=1; j<=sum; j++){
dp[i][j] = dp[i-1][j];
if(j>=nums[i-1]) dp[i][j]= dp[i][j] || dp[i-1][j-nums[i-1]]; //注意判断index是否合法
}
}
return dp[nums.length][sum];
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。