美团-数字字符

2018/03/24 刷题 美团 数字字符
  本文为「原创」内容,如需转载请注明出处!             
本文共 1833 字,需 22 分钟阅读

题目

在十进制中,任意一个正整数都可以用字符 ‘0’ - ‘9’ 表示出来,但是当 ‘0’ - ‘9’ 这些字符每种字符的数量有限时,可能有些正整数就无法表示出来了,比如你有两个 ‘1’,一个 ‘2’,那么你能表示出来 11, 12, 121 等等,但是无法表示出 10,122,200 等数。
现在你手上拥有一些字符,它们都是 ‘0’ - ‘9’ 的字符,你可以选出其中一些字符然后将它们组合成一个数字,那么你无法组成的最小正整数是多少?

输入

第一行包含一个由字符 '0' - '9' 组成的字符串,表示可以使用的字符。
1 ≤ 字符串长度 ≤ 1000

样例输入

55

样例输出

1

Hint

Input Sample 2
123456789
Output Sampe 2
10

思路

  1. 题目要求的是无法组成的最小正整数,所以如果给定的字符没有完全包含 ‘1’ - ‘9’ 则应返回第一个没有包含的数。
  2. 如果出现次数最小的数是 0 ,则返回 \(10^n\), n 为 0 出现的次数 + 1
  3. 如果出现次数最小数非 0 或者次数等于 0 的次数 ,则返回只有该数组成的数,个数未该数的个数 + 1

实现

   /**
     * str 全为 '0'-'9' 的字符,求其不能组成的最小正整数
     * 如:str 为 1123456789 则不能组成的最小正整数为 10
     *
     * @param str 由多个 '0'-'9' 的字符组成
     * @return 不能组成的最小正整数
     */
    public String minIntegral(String str) {
        StringBuilder builder = new StringBuilder();
        int[] nums = new int[10];

        //统计每个字符出现的次数
        for (int i = 0; i < str.length(); i++) {
            nums[str.charAt(i) - '0'] += 1;
        }
        //找到 '1'-'9' 中第一个出现最少的数字及次数
        int leastNum = 0, leastCount = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            if (leastCount > nums[i]) {
                leastCount = nums[i];
                leastNum = i;
            }
        }
        //如果一次没有出现,则最小数为没有出现的字符
        if (leastCount == 0) {
            builder.append(leastNum);
        } else {
            //'0' 的个数是最少的,则相应的最少数为 100..
            // 比如 '0' 只出现了 2 次,而其它数字出现均多余 2 次,则最小数为 100
            if (nums[0] < leastCount) {
                builder.append("1");
                for (int i = 0; i <= leastCount; i++) {
                    builder.append("0");
                }
                //非 '0' 数出现次数最少,则相应的最小数为将该数全部取出组成的数字
            } else {
                for (int i = 0; i <= leastCount; i++) {
                    builder.append(leastNum);
                }
            }
        }
        return builder.toString();
    }

搜索

    文章目录