华为OD机试102-叠积木

这个题目很有难度，解题思路大概分为两大步
第一步，算出可能的层数
第二步，利用递归来判断当前层数是否成立
其中第一步比较简单,以例题为例 3,6,6,3.总共四个数字
先将4个数字加起来 3+6+6+3 = 18
4个数字最多就是4层，其实是 3层，2层。先看 4层是否成立
18/4 结果不是整数，显然不行。 18/3 = 6 .而且6大于或等于所有元素，
说明3层是有希望的。同理 18/2=9 ，而且9大于或等于所有元素，说明9也是有希望的。
那么3层和2层都是候选层。这是第一步。
第二步稍微有点复杂。其实第二步的算法和力扣 698题， 划分为k个相等的子集是一样的，
可以参考力扣解法https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/description/。
我这里的解法是将层数比作桶，比如三层，就相当于3个桶。4个数字就
相当于4个带分数的球。然后这4个球要放入3个桶，并且保证每个桶里面球的分数是6分。
具体代码如下

public class Demo102 {public static void main(String[] args) {int[] a = {3, 6, 6, 3, 6};System.out.println(maxFloor(a));}public static int maxFloor(int[] a) {int sum = 0;// 算出所有元素的和for (int i = 0; i < a.length; i++) {sum = sum + a[i];}// 这个排序是为了 sum / i >= a[a.length - 1]的比较Arrays.sort(a);/* 计算可能的层数* 比如有4个数,那我们依次假设可能的层数就是 4,3,2* 然后再看假设是否可能成立* sum % i == 0 看是否能整除* sum / i >= a[a.length - 1] 平均值要等于或大于最大元素*/List maybeFloors = new ArrayList();for (int i = a.length; i >= 2; i--) {if (sum % i == 0 && sum / i >= a[a.length - 1]) {maybeFloors.add(i);}}if (maybeFloors.size() == 0) {return -1;}for (int i = 0; i < maybeFloors.size(); i++) {int k = maybeFloors.get(i);//依次尝试每一层是否可能if (canPartition(sum, a, k)) {return k;}}return -1;}public static boolean canPartition(int sum, int[] nums, int k) {int average = sum / k;int[] bucket = new int[k];return canPartition(nums, 0, bucket, average);}public static boolean canPartition(int[] nums, int index, int[] bucket, int average) {/** index == nums.length说明都放完了* 如何证明都放完了的时候每个桶的数值恰好是average* 反证法* 首先 average * bucket.length = nums元素总和* 根据程序逻辑* 对于任意i,当 0<=i 0 && bucket[i] == bucket[i - 1]) {continue;}// 满足条件才能放入if (bucket[i] + nums[index] <= average) {// 放入bucket[i] = bucket[i] + nums[index];// 后续递归放入剩余的球if (canPartition(nums, index + 1, bucket, average)) {return true;}// 上面的策略失败了,就回退,继续尝试后面的策略bucket[i] = bucket[i] - nums[index];}}return false;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！