华为OD面试题：如何找出合法的最小数组合？

组合出合法最小数

问题描述

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

输入描述

一个数组，数组不为空，数组里面都是代表非负整数的字符串，可以是0开头，例如：[“13”, “045”, “09”, “56”]。

数组的大小范围：[1, 50]

数组中每个元素的长度范围：[1, 30]

输出描述

以字符串的格式输出一个数字，如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字；

如果拼接出的数字都是“0”开头，则选取值最小的，并且把开头部分的“0”都去掉再输出；如果是单位数“0”，可以直接输出“0”

示例

输入

20 1

输出

120

解题思路

已知条件：

1. 数组元素长度范围1～30，基本数据类型长度无法支持；
2. 数组里面的元素都是非负整数；
3. 元素可能以0开头；
4. 优先输出非0开头的最小数字，如果都是以0开头，则选取值最小的；
5. 需要组合的数字最小；

处理方式
对数组进行排序，字符串对比大小时先对比字符，后根据字符长度对比，以0起始的数字必定排在前面；
然后需要解决的是确定两个相邻的数字整合时数字最小；

代码示例

public String minNum(String[] arr) {
	// 核心功能
    Arrays.sort(arr, (a, b) -> (a + b).compareTo(b + a));
    // 遍历定为首个起始位不为 0 的数字
    boolean appendFirst = true;
    StringBuilder res = new StringBuilder();
    for(String str : arr) {
        // 以0开头直接添加
        if(str.startsWith("0")) {
            res.append(str);
            continue;
        }
		// 首次非0开头数字时添加在首位
        if(appendFirst) {
            res.insert(0, str);
            appendFirst = false;
            continue;
        }

        res.append(str);
    }
    // 去除前缀 0
    if(appendFirst) {
        for(int i = 0, l = res.length() - 1; i < l; i++) {
            if(res.charAt(i) != '0') {
                return res.substring(i);
            }
        }
		// 前缀全为0，保留最后一位
        return res.substring(res.length() - 1);
    }

    return res.toString();
}