华为OD机试真题【组合出合法最小数】

1、题目描述

【组合出合法最小数】
给一个数组，数组里面都是代表非负整数的字符串，将数组里所有的数值排列组合拼接起来组成一个数字，输出拼接成的最小的数字。

【输入描述】
一个数组，数组不为空，数组里面都是代表非负整数的字符串，可以是0开头，例如：[“13”, “045”, “09”, “56”]。
数组的大小范围：[1, 50] ；数组中每个元素的长度范围：[1, 30]

【输出描述】
以字符串的格式输出一个数字，如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字；如果拼接出的数字都是“0”开头，则选取值最小的，并且把开头部分的“0”都去掉再输出；如果是单位数“0”，可以直接输出“0”

【示例1】
输入：
20 1
输出：
120
说明：[“20”, “1”]能组成 201和120，其中120比较小

【示例2】
输入：
08 10 2
输出：
10082
说明：[“08”, “10”, “2”]能组成 08102、 08210、10082、10208、20810、21008等数字，其中"0"开头的08102和08201排除，选择最小的10082输出

【示例3】
输入：
01 02
输出：
102
说明：[“01”, “02”]能拼接成0102和0201，都是“0”开头，选取较小的0102，去掉前面的0，输出102

2、解题思路

该题运用了两种解题方式，一种是先排序后组合，及将数组从小到大排序，依次遍历拼接，如果存首位不为0的数值，将第一个首位不为0的数值放在最前面，该组合得到的数值即为不是0开头中最小的，或全为0开头中最小的；
第二种解题方式是先组合后排序，运用回溯算法遍历得到所有的组合，再将组合的数值排序，排序后的数值中最后一个数是以0开头的，则排序组合这第一个即为最小的结果，否则往前遍历到第一个首位不为0的数值即为最小的结果

3、参考代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;/*** @Author* @Date 2023/5/4 23:53*/
public class 组合出合法最小数 {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {String[] arrays = in.nextLine().split(" ");System.out.println(method1(arrays));  // 方法一System.out.println(minNum(arrays));  // 方法二}}// 方法一:排序public static String minNum(String[] arrays) {Arrays.sort(arrays, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));boolean appendFirst = true;  // 遍历定为首个起始位不为 0 的数字StringBuilder sb = new StringBuilder();for (String arr : arrays) {if (arr.startsWith("0")) {sb.append(arr);continue;}if (appendFirst) {  // 如果存首位不为0的数值，将第一个首位不为0的数值放在最前面sb.insert(0, arr);appendFirst = false;continue;}sb.append(arr);}if (appendFirst) {return delZero(sb.toString());}return sb.toString();}// 方法二:回溯遍历组合static List<String> path = new ArrayList<>();static List<String> result = new ArrayList<>();static boolean[] used;public static String method1(String[] arrays) {path.clear();result.clear();used = new boolean[arrays.length];Arrays.fill(used, false);dfs(arrays, 0);Collections.sort(result);String target = null;int right = result.size() - 1;while (right >= 0) {if (right == (result.size() - 1 ) && result.get(right).startsWith("0")) {target = delZero(result.get(0));break;}if (result.get(right).startsWith("0")) {break;}target = result.get(right);right--;}return target;}public static void dfs(String[] arrays, int count) {if (count == arrays.length) {String res = getPathString(path);result.add(res);return;}for (int i = 0; i < arrays.length; i++) {if (used[i]) {continue;}path.add(arrays[i]);used[i] = true;dfs(arrays, count + 1);used[i] = false;path.remove(path.size() - 1);}}public static String getPathString(List<String> path) {StringBuilder sb = new StringBuilder();for (String str : path) {sb.append(str);}return sb.toString();}// 删除字符串前面的0public static String delZero(String target) {int pos = 0;for (int i = 0; i < target.length() - 1; i++) {if (target.charAt(i) != '0') {break;} else {pos++;}}return target.substring(pos);}}