中山市住房和城乡建设局网站,南平建设集集团网站,wordpress用户注册怎么设置,个人兼职做网站目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出 华为OD机试 2023B卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试#xff08;JAVA#xff09;真题#xff08;A卷B卷#xff09;》… 目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出 华为OD机试 2023B卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题A卷B卷》。
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
一、题目描述
给定一个数组nums将元素分为若干个组使得每组和相等求出满足条件的所有分组中组内元素和的最小值。
二、输入描述
第一行输入 m
接着输入m个数表示此数组nums
数据范围1m50, 1nums[i]50
三、输出描述
最小拆分数组和。
四、解题思路
虽然题意很简单看着很简单其实这道题是有点难度的100分你能抽到这道题自求多福吧兄弟。
比如
4 3 2 3 5 2 1
可以组合成
4 1 3 2 3 2 5
解题思路
1、答案一定在最大值与所有数的和之间拿到这个值看是否能够满足条件
2、用深度优先搜索搜索一种方法满足子数组合能够满足target值的解
3、每次从上一次找的数后面的数开始递归这个优化非常重要不加的话会把之前的结果再找一遍例如我本次递归取了第2个数然后下面再取第5个数当我下次递归取了第5个数的时候如果不从第5个数之后来选就会搜到上面一样取到第二个数那里的结果我们之前是已经搜索过了的。
五、Java算法源码
package com.guor.od;import java.util.Scanner;
import java.util.*;public class OdTest05 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int m Integer.valueOf(sc.nextLine());int[] nums Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();Arrays.sort(nums);// 求和int sum 0;for (int i 0; i nums.length; i) {sum nums[i];}// 答案一定在最大值与所有数的和之间拿到这个值看是否能够满足条件for (int ans nums[nums.length - 1]; ans sum; ans) {if (dfs(ans, 0, nums, new HashSet(), 0)) {System.out.println(ans);break;}}}/*** 用深度优先搜索搜索一种方法满足子数组合能够满足target值的解** param target 目标值* param nowValue 当前递归中的数组和* param nums 数组* param useIndex 数组中已经使用过的数的下标* param nowIndex 上一个取的数下标用于搜索剪枝* return 是否找到了答案*/public static boolean dfs(int target, int nowValue, int[] nums, SetInteger useIndex, int nowIndex) {if (useIndex.size() nums.length nowValue 0) {//只有当数组中的值已经用完且没有剩下数的时候说明答案已经找到了return true;}//每次从上一次找的数后面的数开始递归这个优化非常重要不加的话会把之前的结果再找一遍//例如我本次递归取了第2个数然后下面再取第5个数//当我下次递归取了第5个数的时候如果不从第5个数之后来选就会搜到上面一样取到第二个数那里的结果我们之前是已经搜索过了的for (int i nowIndex; i nums.length; i) {if (useIndex.contains(i)) {//表示这个数已经被用过了continue;}//只有当当前取的数 当前的和小于目标值时才可以取if (nowValue nums[i] target) {//标记这个数已经用过了useIndex.add(i);if (nowValue nums[i] target) {//当前的和已经等于目标值这个时候我们要从头来找一个没有用过的数来继续搜索if (dfs(target, 0, nums, useIndex, 0)) {return true;}} else {//当前的和小于目标值我们还得继续找数来继续填充我们的和if (dfs(target, nowValue nums[i], nums, useIndex, i)) {return true;}}useIndex.remove(i);}}return false;}
}六、效果展示
1、输入
4 6 5 5 8 2 3 3 3 1
2、输出
8 下一篇华为OD机试 - 荒岛求生 - 栈StackJava 2023 B卷 100分
本文收录于华为OD机试JAVA真题A卷B卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
