剑指Offer题目12:打印1到最大的n位数:输入数字n,按顺序打印出从1最大的n位十进制数(Java)

998 阅读1分钟

面试题12:输入数字n,按顺序打印出从1最大的n位十进制数。比如输入3,则打印出1、2、3一直到最大的3位数即999。

Basic

凡是数字计算的,需要考虑大数场景,即溢出。

解决方案:改用字符串或字符数组来表达大数。

根据 ASCII 码表, 字符 '0'~'9' 都有对应的整数表示,从 '0' 到 '9' 加 1 递增,因此有如下算术关系:

字符和数字之间的转换:charA - '0' = numOfCharA

1 = '1' - '0'
2 = '2' - '0'
3 = '3' - '0'
···
9 = '9' - '0'

字符之间的减运算 <=> 整数之间的减运算。

'1' - '1' = 1 - 1 = 0
'9' - '8' = 9 - 8 = 1

解题思路

创建一个 StringBuilder 来拼接字符。

for循环,从个位加1算起,注意循环的中间变量进位的保存和赋值。

代码实现

    public static void print1ToMax(int n) {
        if (n < 0) {
            return;
        }
        StringBuilder numStr = new StringBuilder();
        for (int i = 0; i < n; i++) {
            numStr.append('0');
        }

        while (isIncreasing(numStr, n)) {
            print(numStr);
        }
    }

    private static void print(StringBuilder sb) {
        int start = sb.length();
        // 找到第一个不为0的索引
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) != '0') {
                start = i;
                break;
            }
        }
        // 如果全是0,就不会打印
        if (start < sb.length()) {
            System.out.print(sb.substring(start) + " ");
        }
    }

    private static boolean isIncreasing(StringBuilder numStr, int n) {
        int carry = 0;
        for (int i = n - 1; i >= 0; i--) {
            int singleNum = numStr.charAt(i) - '0' + carry;
            if (i == n - 1) {
                singleNum ++; //在个位上自增
            }

            if (singleNum == 10) {  //1. 如果有进位,则将当前位置为0,对更大的下一位加1
                if (i == 0) { //如果已经到最大的那位还有进位,则说明已经溢出,退出整个打印流程
                    return false;
                } else {
                    numStr.setCharAt(i, '0');
                    carry = 1;
                }
            } else { //2. 如果没有进位,则退出当前这个 for 循环,执行打印
                numStr.setCharAt(i, (char) (singleNum + '0'));
                break;
            }
        }
        return true;
    }

总结

暂无。