用自己电脑做主机做网站,wordpress的安装目录结构,wordpress 机械模板下载,wordpress使用置顶文章没用题目
分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
示例 1#xff1a;
输入#xff1a;nums [1,5,11,5] 输出#xff1a;true 解释#xff1a;数组可以分割成 [1, 5, 5] …题目
分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2
输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。
提示
1 nums.length 200 1 nums[i] 100
题解
记忆化搜索
class Solution {private int[] nums;//这里如果定义布尔数组的话将会无法存储已经遍历的路径private int[][] cache;public boolean canPartition(int[] nums) {int target 0;for (int x : nums) {target x;}if (target % 2 ! 0 || target 0) {return false;}target / 2;this.nums nums;int n nums.length;cache new int[n][target 1];for (int i 0; i n; i) {Arrays.fill(cache[i],-1);}return dfs(n - 1, target);}public boolean dfs (int i, int c) {if (i 0) {return c 0;}if (cache[i][c] ! -1) {return cache[i][c] 0 ? true : false;}if (c nums[i]) {cache[i][c] dfs(i - 1, c) ? 1 : 0;return dfs(i - 1, c);}cache[i][c] (dfs(i - 1, c) || dfs(i - 1, c - nums[i])) ? 1 : 0; return dfs(i - 1, c) || dfs(i - 1, c - nums[i]);}
}1:1递推
两个数组空间优化
class Solution {public boolean canPartition(int[] nums) {int target 0;for (int x : nums) {target x;}if (target % 2 ! 0 || target 0) {return false;}target / 2;int n nums.length;boolean[][] f new boolean[2][target 1];f[0][0] true;for (int i 0; i n; i) {for (int c 0; c target; c) {if (c nums[i]) {f[(i 1) % 2][c] f[i % 2][c];} else {f[(i 1) % 2][c] f[i % 2][c] || f[i % 2][c - nums[i]];}}}return f[n % 2][target];}
}一个数组空间优化
class Solution {public boolean canPartition(int[] nums) {int target 0;for (int x : nums) {target x;}if (target % 2 ! 0 || target 0) {return false;}target / 2;int n nums.length;boolean[] f new boolean[target 1];f[0] true;for (int x : nums) {for (int c target; c x; c--) {f[c] f[c] || f[c - x];}}return f[target];}
}
