华为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();
    }

	// 删除字符串前面的0
    public 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);
    }

}