题解 | #农场的奶牛分组II#
农场的奶牛分组II
https://www.nowcoder.com/practice/ae745225d12f44ca9e84486d051edbfa?tpId=354&tqId=10595842&ru=%2Fexam%2Foj&qru=%2Fta%2Finterview-202-top%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
知识点:回溯法,递归/动态规划
文字分析
本题是面试TOP202 NB137 农场的奶牛分组 的升级版，在 NB137 中，我们需要将奶牛分为两组，
这时只需保证n>=2 && sum%2==0，且存在子数组的和为target=sum/2即可，因为是分为两份，因此除去当前子数组的所有值后，余下的和必然为target。
而对于本题，需要在保证n>=3 && sum%3==0 同时将奶牛分为三组，量变已然引起质变，我们一般采用回溯法处理分为多组的问题
回溯法java代码：超时
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param weights int整型一维数组
* @return bool布尔型
*/
public boolean canPartitionII (int[] weights) {
int sum = Arrays.stream(weights).sum();
int n = weights.length;
if (sum % 3 != 0 && n < 3) {
return false;
}
int target = sum / 3;
boolean[] used = new boolean[weights.length];
return backtrack(weights, 0, 0, target, used, 0);
}
private boolean backtrack(int[] nums, int start, int currentSum, int target,
boolean[] used, int subsets) {
if (subsets == 3) {
// 找到了三个相等的子集
return true;
}
if (currentSum == target) {
// 当前子集的和等于target，递归寻找下一个子集
return backtrack(nums, 0, 0, target, used, subsets + 1);
}
for (int i = start; i < nums.length; i++) {
if (!used[i] && currentSum + nums[i] <= target) {
// 使用weights[i]
used[i] = true;
if (backtrack(nums, i + 1, currentSum + nums[i], target, used, subsets)) {
return true;
}
// 还原
used[i] = false;
}
}
return false;
}
}
遗憾的是，回溯法需要不停的递归调用，性能堪忧。在本题中，同原理的C++代码可以通过，但Java超时了
C++：（用于测试的代码实际来自@开车的阿Q的题解，本人不敢居功）
Java：
瞧瞧这差距！！
java错误通过
于是我又修改了来自@牛客周周 的C++代码：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param weights int整型vector
* @return bool布尔型
*/
bool canPartitionII(vector<int>& weights) {
int sum = 0;
for (int weight : weights) {
sum += weight;
}
if (sum % 3 != 0) {
return false;
}
int target = sum / 3;
int n = weights.size();
vector<vector<int>> dp(n+1, vector<int>(target+1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = target; j >= weights[i-1]; --j) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + weights[i-1]);
}
}
if (dp[n][target] != target) {
return false;
}
int left = target;
for (int i = n; i >= 1; --i) {
if (left >= weights[i-1] && dp[i-1][left-weights[i-1]] == left - weights[i-1]) {
left -= weights[i-1];
}
}
return left == 0;
}
};
分析:
- 首先，计算整数数组
weights的总和sum，并且获取数组的长度n。 - 如果
sum不能被3整除，或者n小于3，则返回false，表示无法将数组划分成三个和相等的子数组。 - 计算目标和
target，即sum除以3。 - 创建一个二维数组
dp，大小为(n+1) x (target+1)，用于动态规划计算每个阶段的最优解。 - 两个循环嵌套遍历了二维数组
dp。外层循环迭代变量i从1到n，内层循环迭代变量j从target递减到weights[i - 1]。（注意限定了weights[i-1]<=target）在每个循环迭代步骤中，通过比较上一行dp[i-1][j]和dp[i-1][j-weights[i-1]] + weights[i-1]的值，将较大的值赋给当前位置dp[i][j]。这里使用了动态规划的思想，逐步计算出数组中可以组成的不同和的最大值(该值最大为target)。 - 如果
dp[n][target]不等于target，则返回false，因为表示无法将数组划分成和为target的三个子数组。 - 初始化一个变量left为target，表示第二个子数组的目标和。从n开始往前遍历每个元素，如果当前元素的重量小于等于left，且使用该元素之前的子数组和等于left-weights[i-1]，则将left减去当前元素的重量。
- 最后，如果
left等于0，表示成功将数组划分成三个和相等的子数组，返回true；否则，返回false。
import java.util.*;
public class Solution {
public boolean canPartitionII (int[] weights) {
//1
int sum = Arrays.stream(weights).sum();
int n = weights.length;
//2
if (sum % 3 != 0 || n < 3 ) {
return false;
}
//3
int target = sum / 3;
//4
int[][] dp = new int[n + 1][target + 1];
//5 此处实际依然是找和为target的字数组
for (int i = 1; i <= n; ++i) {
for (int j = target; j >= weights[i - 1]; --j) {
dp[i][j] = Math.max(dp[i - 1][j],
dp[i - 1][j - weights[i - 1]] + weights[i - 1]);
}
}
//6
if (dp[n][target] != target) {
return false;
}
// 7 问题发生于此处,以下代码依旧是在计算和为target的子数组,而不是我先前想的遍历找第二个分组
// 当代码运行到此时,left==0 是必然的
int left = target;
for (int i = n; i >= 1; --i) {
if (left >= weights[i - 1] &&
dp[i - 1][left - weights[i - 1]] == left - weights[i - 1]) {
left -= weights[i - 1];
}
}
//8
return left == 0;
}
}
以上能通过全靠用例稀薄.....
感谢@新小镇做题家的评论，让我得以发现错误，
(此处推荐一下他的题解,有简洁的美感)
经再三验证以上代码虽然能通过牛客的测试用例，但无法通过
[4,5,7,7,8,11] false
[4,7,9,10,15] false
[2,7,10,11,15] false
正确且完整的Java代码和解析
解析:
既然一次动规不行那就再来一次
需要注意的是
- 数组中的每个数据只能使用一次
- 三个子数组均=target
此时存在一个字数组为target的判断方法不可行,因为无法保证余下的数据可以被均分为两份。因此我们需要在进行一次分组，并在第二次分组中去除已经使用一次的数据。(这时可以复用NB137 分为两组的代码)
正确且完整的代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param weights int整型一维数组
* @return bool布尔型
*/
public boolean canPartitionII (int[] weights) {
int sum = Arrays.stream(weights).sum();
int n = weights.length;
if (sum % 3 != 0 || n < 3 ) {
return false;
}
int target = sum / 3;
//这里使用int 而不是boolean 方便了后面找出已使用的元素
int[][] dp = new int[n + 1][target + 1];
// 第一次是否存在和为target的分组
for (int i = 1; i <= n; ++i) {
// weights中的数据不得>target
for (int j = target; j >= weights[i - 1]; --j) {
dp[i][j] = Math.max(dp[i - 1][j],
dp[i - 1][j - weights[i - 1]] + weights[i - 1]);
}
}
if (dp[n][target] != target) {
return false;
}
// 找出和为target的分组的元素,并标记
int left = target;
boolean[] flag = new boolean[n];
for (int i = n; i >= 1; --i) {
if (left >= weights[i - 1] &&
dp[i - 1][left - weights[i - 1]] == left - weights[i - 1]) {
left -= weights[i - 1];
flag[i - 1] = true;
}
}
//第二次分组
ArrayList<Integer> weights2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (!flag[i]) {
weights2.add(weights[i]);
}
}
return canPartition(weights2.stream().mapToInt(Integer::intValue).toArray());
}
private static boolean canPartition (int[] weights) {
// write code here
int n = weights.length;
int sum = Arrays.stream(weights).sum();
// 无法分为两组
if (n < 2 || sum % 2 != 0) {
return false;
}
int target = sum / 2;
// 是否存在一组的和=i
boolean[] dp = new boolean[target + 1];
// 和为0的子集存在
dp[0] = true;
for (int weight : weights) {
// 若dp[i-weight]==true,则dp[i]=true
// i<weight时,和为i的子集不存在
for (int i = target; i >= weight; --i) {
dp[i] |= dp[i - weight];
}
}
return dp[target];
}
}
面试高频TOP202 文章被收录于专栏
面试高频TOP202题解
