全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。
真题库:https://www.yuque.com/codernav.com/od
题目:组合出合法最小数
知识点:数组排序
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
给一个数组,数组里面都是代表非负整数的字符串,将数组里所有的数值排列组合拼接起来组成一个数字,输出拼接成的最小的数字。
输入描述:
一个数组,数组不为空,数组里面都是代表非负整数的字符串,可以是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
解题思路:
使用经典的全排列算法。
处理完之后需要注意是否以0开头。
真机测试用例:
0 20 39 20039
00 015 08 0154 081 15015408081
00 0
123 12301 47 6 12301123476
20 02 2010 2032 698 6982 6987 0120
最后一个20 02 2010 2032 698 6982 6987 0120:
我的结果:200120022010203269826986987(没通过)
正确结果:201001200220203269826986987(感觉这是错的,但是它通过了)
代码实现一:
package com.codernav.demo.hwod.exam; import java.math.BigDecimal; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; /** * @title 组合出合法最小数 * @Description 给一个数组,数组里面都是代表非负整数的字符串,将数组里所有的数值排列组合拼接起来组成一个数字,输出拼接成的最小的数字。 * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/28 */ public class Main { public static List<BigDecimal> list = new ArrayList<>(); //非0开头的数字 public static List<BigDecimal> listZero = new ArrayList<>(); //0开头的数字 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] strings = sc.nextLine().split(" "); quanpailie(strings, 0, strings.length); if (list.size() == 0) { //说明都是以0开头的 Collections.sort(listZero); System.out.println(listZero.get(0)); } else { Collections.sort(list); System.out.println(list.get(0)); } } public static void swap(String[] strings, int a, int b) { String temp = strings[a]; strings[a] = strings[b]; strings[b] = temp; } /** * 经典全排列回溯 (不理解的可以强行背诵,用的地方很多) * * @param strings 需要排列的数组 * @param index 处理的索引 * @param end 数组长度 */ public static void quanpailie(String[] strings, int index, int end) { if (index == end) { //所有的数据都遍历完成 StringBuilder res = new StringBuilder(); for (String string : strings) { res.append(string); } if (res.toString().startsWith("0")) { //以0开头的需要分开放 listZero.add(new BigDecimal(res.toString())); } else { list.add(new BigDecimal(res.toString())); } return; } for (int i = index; i < strings.length; i++) { swap(strings, i, index); quanpailie(strings, index + 1, end); swap(strings, i, index); } } }
代码实现二:Java满分代码实现
package com.codernav.demo.hwod.exam; import java.util.Arrays; import java.util.Scanner; /** * @title 组合出合法最小数 * @Description 给一个数组,数组里面都是代表非负整数的字符串,将数组里所有的数值排列组合拼接起来组成一个数字,输出拼接成的最小的数字。 * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/28 */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String[] lines = in.nextLine().split(" "); Arrays.sort(lines, (a, b) -> ((a + b).compareTo(b + a))); String first = lines[0]; if (first.charAt(0) == '0') { for (int i = 1; i < lines.length; i++) { if (lines[i].charAt(0) != '0') { lines[0] = lines[i] + lines[0]; lines[i] = ""; break; } } } StringBuffer str = new StringBuffer(); for (String line : lines) { str.append(line); } String res = str.toString().replaceAll("^0+", ""); if (res.equals("")) { System.out.println("0"); } else { System.out.println(res); } } }