2025年华为机试:叠积木

华为机试:叠积木编程题目 200 分 叠积木 200 中等 题目描述 有一堆长方体积木 它们的长度和宽度都相同 但长度不一 小橙想把这堆积木叠成一面墙 墙的每层可以放一个积木 也可以将拼接多个积木 要求每层的长度相同 最少 2 层 若必须用完这些积木 叠成的墙最多为多少层

大家好,我是讯享网,很高兴认识大家。

【编程题目 | 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; } } 

欢迎在评论区指正以及留下自己的更简洁的方法。

小讯
上一篇 2025-04-01 08:50
下一篇 2025-02-26 17:53

相关推荐

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