栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode 698. 划分为k个相等的子集

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode 698. 划分为k个相等的子集

698. 划分为k个相等的子集

【回溯法】用回溯法来思考这个问题的话其实思路是很简单的,还是以样例1为例:

4,3,2,3,5,2,1分成4组

首先计算sum/4 = 5,这样就可以创造出四个容量为5的桶bucket,我们可以创建一个int[]类型的数组bucket全部初始化为5来记录每个桶剩下的容量。下面开始从t=0,也就是第一个元素开始对数和桶进行回溯。

1.t = 0时,也就是所对于第一个元素4,他有四种选择,0-3号桶他都可以放,因此用i遍历这三个桶,当放进一个桶时,就把他的容量bucket[i] - nums[t],然后继续进t + 1层,同时不要忘记回到当前层时再把bucket[i] + 回去,然后i继续向后走,把第t个放进新的i桶中,继续t+1层以及回溯bucket。

2.t = 1时,已经进入到下一层,继续对第二个元素这样操作,同时这里可以稍微进行一点剪枝:当bucket[i] < nums[t]很明显已经不符合条件了,这里直接就可以不用继续向下了。

3.直到t = nums.length,也就是对每个元素都放好了桶时,就可以判断此时每个bucket是否都是0了,如果是0,就说明平分好了。

于是第一版的基础回溯就做出来

class Solution {

    public boolean backTrack(int[] nums, int t, int n, int k, int[] bucket){
        if(t == n){
            // for(var i: bucket) System.out.print(i + " ");
            // System.out.println();
            for(var i: bucket) if(i != 0) return false;
            return true;
        }else{
            boolean ret = false;
            for(var i = 0; i < k; i++){
                if(nums[t] <= bucket[i]){
                    bucket[i] -= nums[t];
                    boolean tmp = backTrack(nums, t + 1, n, k, bucket);
                    ret = tmp || ret;
                    bucket[i] += nums[t];
                }
            }
            return ret;
        }

    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(var i: nums) sum += i;
        if(sum % k != 0) return false;
        int[] bucket = new int[k];
        int m = sum / k, n = nums.length;
        for(var i = 0; i < k; i++){
            bucket[i] = m;
        }
        return backTrack(nums, 0, n, k, bucket);
    }
}

但是很遗憾,超大时了。

【优化】下面对这个回溯法进行优化,首先可以先对nums就行排序,这样可以先将大的元素安排好,这样的好处在于用大的元素占据前面的桶之后,我们可以通过if(bucket[i] >= nums[t])这个条件率先进行一些剪枝;另外当t == n的时候其实不需要判断每个bucket是否为0了,因为前面已经对bucket进行平分且有bucket[i] >= nums[t]这个条件,所以最后能到达的一定是符合定义的。

然后这里对int[]类型的数组从大到小排序需要用到stream,具体方法为:nums = Arrays.stream(nums).boxed().sorted((a, b) -> b - a).mapToInt(t -> t).toArray();

class Solution {

    public boolean backTrack(int[] nums, int t, int n, int k, int[] bucket){
        if(t == n){
            // for(var i: bucket) System.out.print(i + " ");
            // System.out.println();
            // for(var i: bucket) if(i != 0) return false;
            return true;
        }else{
            boolean ret = false;
            for(var i = 0; i < k; i++){
                if(nums[t] <= bucket[i]){
                    bucket[i] -= nums[t];
                    boolean tmp = backTrack(nums, t + 1, n, k, bucket);
                    if(tmp == true) return true;
                    ret = tmp || ret;
                    bucket[i] += nums[t];
                }
            }
            return ret;
        }

    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(var i: nums) sum += i;
        if(sum % k != 0) return false;
        int[] bucket = new int[k];
        int m = sum / k, n = nums.length;
        for(var i = 0; i < k; i++){
            bucket[i] = m;
        }
        nums = Arrays.stream(nums).boxed().sorted((a, b) -> b - a).mapToInt(t -> t).toArray();
        return backTrack(nums, 0, n, k, bucket);
    }
}

虽然还是超时了,但是已经过了大部分的样例了

【剪枝】我们发现放进每个桶其实这个和顺序是没有关系的,也就是说我们虽然对桶从0-3进行了标号,但是划分的四个子集顺序是没有关系的,但是很明显刚才我们的代码是考虑了顺序的

(5),(1,4),(2,3),(2,3)

以t = 0时4个元素为例子,我们在for循环i的时候,会把4分别放进0-3这三个桶中然后再继续下一层,但是很显然这是没必要的,所以当两个桶的容量一样的时候,我们只需要放进其中一个桶就行了。所以这里加上一个剪枝来把顺序给去掉 if(i != 0 && bucket[i] == bucket[i - 1]) continue;

class Solution {

    public boolean backTrack(int[] nums, int t, int n, int k, int[] bucket){
        if(t == n){
            // for(var i: bucket) System.out.print(i + " ");
            // System.out.println();
            // for(var i: bucket) if(i != 0) return false;
            return true;
        }else{
            boolean ret = false;
            for(var i = 0; i < k; i++){
                if(i > 0 && bucket[i] == bucket[i - 1]) continue;
                if(nums[t] <= bucket[i]){
                    bucket[i] -= nums[t];
                    boolean tmp = backTrack(nums, t + 1, n, k, bucket);
                    if(tmp == true) return true;
                    ret = tmp || ret;
                    bucket[i] += nums[t];
                }
            }
            return ret;
        }

    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(var i: nums) sum += i;
        if(sum % k != 0) return false;
        int[] bucket = new int[k];
        int m = sum / k, n = nums.length;
        for(var i = 0; i < k; i++){
            bucket[i] = m;
        }
        nums = Arrays.stream(nums).boxed().sorted((a, b) -> b - a).mapToInt(t -> t).toArray();
        return backTrack(nums, 0, n, k, bucket);
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/946554.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号