题解 | #农场的奶牛分组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题解