PAT 真题 | 1038 Recover the Smallest Number

本题属于字典序的一道变题。

字典序是最容易理解的一种顺序. 最初接触到字典序是在组合数学的课堂上。我们依次比较串中的每个字母, 出现不一样的时候就能比较大小了. 如果某个串遍历到头了还没有比较出大小，那么较长的字符串较大。如果两个字符串一样长，那么这两个字符串的字典序相等。

本题不能直接比较两个字符串的字典序，而是应该比较它们正反拼接后字符串的字典序。由于子串中可能以0开头，所以存在这样的特殊情况，比如0229和0331组成的最小数是2290331。所以读取的时候应以字符串而不是数字读取。比较的时候也是通过比较字符串字典序。在最后别忘了还要清楚前导0，更特殊的全0情况去除完后要补0.

算法的Java实现：

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = null;
        try {
            line = br.readLine();
        } catch (IOException ioe) {
            ioe.printStackTrace();
        }
        String[] segment = line.split(" ");
        int N = Integer.parseInt(segment[0]);
        if(N == 0) {
            System.out.println("0");
            return ;
        }
        Arrays.sort(segment, 1, N+1, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return (s1+s2).compareTo(s2+s1);
            }
        });
        StringBuilder builder = new StringBuilder();
        boolean leadZero = true;
        for(int i=1; i<=N; ++i) {
            if(leadZero) {
                for(int j=0; j<segment[i].length(); ++j) {
                    if(leadZero) {
                        if(segment[i].charAt(j) == '0') continue;
                        else leadZero = false;
                    }
                    builder.append(segment[i].substring(j));
                    break;
                }
            } else {
                builder.append(segment[i]);
            }
        }
        if (leadZero) { System.out.println("0");}
        else System.out.println(builder);
    }
}

注意这里使用了 java.io 包中的 BufferedReader 和 InputStreamReader 以加快读取的速度。

另外一道类似的题目参见牛客网上在线编程模块的题目 “数串”（https://www.nowcoder.com/questionTerminal/a6a656249f404eb498d16b2f8eaa2c60）.
如果某个串遍历到头了, 需要从头循环继续遍历. 如果两个串都到头了还没有比较出大小来, 说明两个串相等.
最容易出错的一个例子是比较48和484，虽然字典序484>48，但是两个字符串连起来的字典序是 484+48 < 48+484，也就是说48应该在484的前面。

所以这道题不能直接比较s1和s2的字典序，而是要进行s1+s2和s2+s1的字典序比较。

Arrays.sort(dict, (s1, s2) -> (s2+s1).compareTo(s1+s2)); // 或下面写法
Arrays.sort(dict, new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return (s2+s1).compareTo(s1+s2);
    }
}