【编程题目 | 200分】叠积木 [ 200 / 中等 ]
题目描述
有一堆长方体积木,它们的长度和宽度都相同,但长度不一。
小橙想把这堆积木叠成一面墙,墙的每层可以放一个积木,也可以将拼接多个积木,要求每层的长度相同。最少2层。
若必须用完这些积木,叠成的墙最多为多少层?
输入描述
输入为一行,为各个积木的长度,数字为正整数,并由空格分隔。积木的数量和长度都不超过5000。
输出描述
输出一个数字,为墙的最大层数,如果无法按要求叠成每层长度一致的墙,则输出-1。
示例
输入
3 6 3 3 3
讯享网
输出
讯享网3
解释:以 6 为底的墙,第一层为 6 ,第二层为 3 + 3,第三层 3 + 3。
输入
9 9 9 5 3 2 2 2 2 2
输出
讯享网5
解释:
5+2+2=9 3+2+2+2=9 9,9,9 共五层
输入
讯享网3 5
输出
-1
思路分析
这道题要求每层的长度一样,且每层可以由多个积木拼接起来。
这道题目考察了回溯法,可以参考leetcode:698. 划分为k个相等的子集。
划分k个相同子集,就是保证每个子集都相同,总共划分k个。k就相当于我们的积木层数,子集就相当于我们一层积木的长度。
因此我们只需要遍历层数,判断是否可以拼成,从第2层遍历到sum/2,对遍历的每一层,首先判断是否可以分配sum % i == 0
,如果可以则回溯判断,同时更新最大层数。
所以这道题的核心就是是否可以划分k个相同子集。
先看一下leetcode的这道题目:这道题搞明白了,上面这道题自然也就解决了。

回溯递归,代码如下:
讯享网class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
if (k == 1) return true; // 特判 Arrays.sort(nums);; int n = nums.length; int target = 0; int max = 0; for (int i : nums) target += i; if (target % k != 0) return false; // 特判 target /= k; if (target < nums[n - 1]) return false; // 特判 int[] sums = new int[k]; return dfs(nums, n - 1, 0, sums, k, target); } private boolean dfs(int[] nums, int cur, int used, int[] sums, int k, int target) {
if (cur < 0) {
return true; } if (used < k) {
sums[used] = nums[cur]; if (dfs(nums, cur - 1, used + 1, sums, k, target)) return true; sums[used] = 0; } for (int i = 0; i < used; i++) {
// 如果当前桶和上一个桶内的元素和相等,则跳过 // 原因:如果元素和相等,那么 nums[cur] 选择上一个桶和选择当前桶可以得到的结果是一致的 if (i > 0 && sums[i] == sums[i - 1]) continue; if (sums[i] + nums[cur] <= target) {
sums[i] += nums[cur]; if (dfs(nums, cur - 1, used, sums, k, target)) return true; sums[i] -= nums[cur]; } } return false; } }
参考代码
import java.util.*; public class dieJiMu {
public static void main(String[] args) {
Scanner in = new Scanner(System.in); String[] s = in.nextLine().split(" "); int[] nums = new int[s.length]; for (int i = 0; i < nums.length; i++) {
nums[i] = Integer.parseInt(s[i]); } int sum = 0; for (int num : nums) {
sum += num; } Arrays.sort(nums); int res = -1; for (int i = 2; i <= sum / 2; i++) {
if (sum % i != 0) continue; int score = sum / i; if(nums[nums.length - 1] > score){
continue; } //建立一个长度为k的桶 int[] arr = new int[i]; //桶的每一个值都是子集的和 Arrays.fill(arr, score); if (dfs (nums, nums.length - 1, 0, arr, i, score)) {
res = Math.max(res, i); } } System.out.println(res); } public static boolean dfs(int[] nums, int cur, int used, int[] arr, int k, int score){
//已经遍历到了-1说明前面的所有数都正好可以放入桶里,那所有桶的值此时都为0,说明找到了结果,返回true if(cur < 0){
return true; } if (used < k) {
arr[used] = nums[cur]; if (dfs(nums, cur - 1, used + 1, arr, k, score)) {
return true; } arr[used] = 0; } //遍历k个桶 for(int i = 0; i < used; i++){
// 如果当前桶和上一个桶内的元素和相等,则跳过 // 原因:如果元素和相等,那么 nums[cur] 选择上一个桶和选择当前桶可以得到的结果是一致的 if (i > 0 && arr[i] == arr[i - 1]) continue; if (arr[i] + nums[cur] <= score) {
arr[i] += nums[cur]; if (dfs(nums, cur - 1, used, arr, k, score)) return true; arr[i] -= nums[cur]; } } return false; } }
欢迎在评论区指正以及留下自己的更简洁的方法。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/114178.html