一、题目描述
给一个数组，数组里面都是代表非负整数的字符串，将数组里所有的数值排列组合拼接起来组成一个数字，输出拼接成的最小的数字。
二、输入描述
一个数组，数组不为空，数组里面都是代表非负整数的字符串，可以是0开头。
例如：[“13”, “045”, “09”, “56”]。
数组的大小范围：[1, 50]
数组中每个元素的长度范围：[1, 30]
三、输出描述
以字符串的格式输出一个数字，如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字；如果拼接出的数字都是“0”开头，则选取值最小的，并且把开头部分的“0”都去掉再输出；如果是单位数“0”，可以直接输出“0”。
四、Java算法源码
/**
* 20 1
*
* 120
*/
static List<String> result = new ArrayList<>();
static LinkedList<String> path = new LinkedList<>();
static boolean[] used = null;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 20 1
String[] arr = sc.nextLine().split(" ");
// 当前数字是否使用过
used = new boolean[arr.length];
Arrays.fill(used, false);
dfs(arr, 0);
Collections.sort(result);
String target = null;
int i = -1;
int len = result.get(0).length();
while (target == null) {
if (i == len - 1) {
//System.out.println(0);
break;
}
i++;
for (String s : result) {
if (s.charAt(i) != '0') {
target = s;
break;
}
}
}
if (target == null) {
System.out.println(0);
} else {
System.out.println(delZero(target));
}
}
public static void dfs(String[] strArr, int depth) {
if (depth == strArr.length) {
//save
String res = getPathString(path);
result.add(res);
return;
}
for (int i = 0; i < strArr.length; i++) {
if (used[i]){
continue;
}
path.add(strArr[i]);
used[i] = true;
dfs(strArr, depth + 1);
used[i] = false;
path.removeLast();
}
}
public static String getPathString(LinkedList<String> path) {
StringBuilder builder = new StringBuilder();
for (String str : path) {
builder.append(str);
}
return builder.toString();
}
/**
* 如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字
*
* 删掉以0开头的数字
*/
public static String delZero(String target) {
char[] chars = target.toCharArray();
int pos = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] != '0') {
break;
} else {
pos++;
}
}
return target.substring(pos);
}
五、效果展示
1、输入
05 12 2
2、输出
12052
3、说明
05 12 2能组成 05122、05212、12052、12205、20512、21205。
如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字。
故还剩12052、12205、20512、21205。
其中12052最小。
🏆下一篇：华为OD机试真题 Java 实现【服务中心选址】【2023Q1 100分 】
🏆本文收录于，华为OD机试（JAVA）（2022&2023）
本专栏包含了最新最全的2023年华为OD机试真题，有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新，每天在线答疑。