加一算法（数组或者字符串）_数值字符串加一

1. 数字加一

    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length<=0)
            return new int[0];
        for (int i = digits.length-1; i>=0; i--){
            digits[i] ++;
            if (digits[i] == 10){
                digits[i] = 0;
            }else {
                return digits;
            }
        }
        int[] res = new int[digits.length+1];
        res[0] = 1;
        System.arraycopy(digits,0,res,1,digits.length);
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 字符串加一（倒序）

    private StringBuilder plusOne(StringBuilder s){
        for (int i = 0;i<s.length(); i++){
            char c = (char)(s.charAt(i) + 1);
            if (c > '9'){
                s.setCharAt(i,'0');
            }else {
                s.setCharAt(i,c);
                return s;
            }
        }
        return s.append('1');
    }
1
2
3
4
5
6
7
8
9
10
11
12

2.1 字符串加一的应用

剑指offer的题，描述如下：

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

考虑到没有范围限制，所以使用了字符串

    public void printNumbers_2(int n) {
        StringBuilder num = new StringBuilder("0");
        int index = 0;
        // index 为目前数字的位数，当有进位时 +1
        while (index < n){
            int carry = 0;
            //加 1 操作
            boolean hasCarry = false;
            for (int i = 0; i<num.length(); i++){
                char c = (char)(num.charAt(i) + 1);
                if (c > '9'){
                    hasCarry = true;
                    num.setCharAt(i,'0');
                }else {
                    num.setCharAt(i,c);
                    hasCarry = false;
                    break;
                }
            }
            //最后一位有产生进位时
            if (hasCarry){
                if (num.length() == n){
                // 如果产生进位，但是当前的位数已经到了n位，那么就直接break，不再进行下面操作
                    break;
                }else { 
                	//如果没有到n位，那么位字符串追加一位，长度增加1位
                    num.append('1');
                    index++;
                }
            }
            //答印字符，注意是倒序打印的
            stingNumPrint(num);
        }
    }

    private void stingNumPrint(StringBuilder num) {
        for (int i = num.length() -1 ; i >=0 ; i--){
            System.out.print(num.charAt(i));
        }
        System.out.println();
    }
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
35
36
37
38
39
40
41