OD华为机试 32

组成最大数

描述

小组中每位都有一张卡片，卡片上是6位内的正整数，将卡片连起来可以组成多种数字，计算组成的最大数字。

输入描述
“,”号分割的多个正整数字符串，不需要考虑非数字异常情况，小组最多25个人

输出描述
最大的数字字符串

示例一：
输入

22,221  
1

输出

22221
1

示例二：
输入

4589,101,41425,9999
1
1
2

输出

9999458941425101
1

法一

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] str = sc.nextLine().split(",");
            Comparator<String> myComparator = (left, right) -> {

                String leftAndRight = left + right;
                String rightAndLeft = right + left;
                return rightAndLeft.compareTo(leftAndRight);
            };
            String collect = Arrays.stream(str).sorted(myComparator).collect(
                                 Collectors.joining(""));
            System.out.println(collect);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

法二

package com.sc.august.day2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;

public class Compare {
    public static void main(String[] args) throws IOException {
        System.out.println("请输入数组，以逗号相隔：");
        //BufferedReader父类是InputStreamReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        //这里尝试把readline赋值给str放到外面，然后会一直打印停不下来
        while ((str = br.readLine()) != null) {
            //将输入的字符串用split,将字符串转化为字符数组
            String[] temp = str.split(",");
            //将字符数组转为类型为String的list
            List<String> list = Arrays.asList(temp);
            //重写list的sort方法，比如12 23
            //如果长度相等，就取 23 拼 12, 也即顺序从升序变为降序，所以顺序从(first , second)变成second.compare(first)
            //长度不相等先拼接起来，然后再比较
            list.sort((first, second) -> first.length() == second.length() ? second.compareTo(first) :
                    (second + first).compareTo(first + second));
            //创建字符串接收list排序好的最大数字
            StringBuffer sb = new StringBuffer();
            for (String s : list) {
                sb.append(s);
            }
            System.out.println(sb);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

算法实现

本质上是一种排序，但是排序规则如何定义？

对于22,221 可以组成22221 和22122 显然22221更大应该排在前面

对于5 51 可以组成551 和 515 显然551更大应该排在前面

所以在比较两个数大小的规则应该将两个数链接起来后再比较大小

对于两个字符串：left、right

我们应该比较：leftAndRight 和rightAndLeft 的大小

我们自定义一个比较器，来实现两个字符串大小的比较，字符串leftAndRight来自left和right的拼接，字符串rightAndLeft来自right和left的拼接。

题目要求拼接出来的最大数字，那么字符串的大小比较应该按照从大到小的升序规则进行排序，所以应当使用rightAndLeft.compareTo(leftAndRight)的结果作为返回值，同理，如果题目要求的是拼接出来的最小数字，则应该按照leftAndRight.compareTo(rightAndLeft)来作为返回值。

Comparator<String> myComparator = (left, right) -> {
            
                String leftAndRight = left + right;
                String rightAndLeft = right + left;
                return rightAndLeft.compareTo(leftAndRight);
            };
1
2
3
4
5
6

后面的内容就是根据自定义比较器对Array数组进行排序，并且按照指定的分隔符来进行拼接，这块建议直接使用Stream流进行处理，比较简洁：

 String collect = Arrays.stream(split).sorted(myComparator).collect(Collectors.joining(""));
 System.out.println(collect);
1
2