百度&必应权4, 日IP8000. 查看详情
自助收录

2023年华为OD机考真题:组合出合法最小数

算法刷题2年前 (2023)更新 江南白衣
504 0 0
2023年华为OD机考真题:组合出合法最小数

全网最全面的华为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);
        }
    }
}

 

© 版权声明

相关文章

暂无评论

暂无评论...