LeetCode刷题【剑指 Offer 43】1～n 整数中 1 出现的次数

输入：n = 12
输出：5

输入：n = 13
输出：6

按位计算统计，(【左侧数值】当前位1【右侧数值】)
直接拿一个数字31261分析下，过程如下

    3      1      2      6      1
                                3126 + 1
                         3130
                  3200
            3000 + 261 + 1
    10000

1. 最低位当前数字是1，这个位置上1粗线的次数由他前面的数字决定，所以我们可以非常明白的知道，这个时候这一位一共出现了3127次字符1，
   • 分别为有前缀的3126 次
   • 和无前缀的 当数字n = 1的时候的1次
2. 倒数第二位数字6，这个数字大于1，根据上面算最低位的时候的情况分析依据，我们可以知道这个位置一共出现了3130次，这个结果可以也可以分为两部分
   • 有前缀的时候3120种情况，数字xxx1x的情况，当前位前面有312种情况，而又因为当前位大于1，后面一位的0-9的10种情况，即为3120种
   • 无前缀的时候10到19的10种情况
   • 这样，我们暂时把这部分换为另外一种算法，即为( 312 + 1 ) * 10 种。
3. 再往前一位数字2,同前面的数字6的情况，因为大于1所以结果为(31 + 1) * 100种
4. 再次往前一位，数字1，虽然前面为1的情况我们已经分析过了，但是那个是不完整的，在这里，我们将完整分析下为1的时候的情况
   • 因为后面还有其他数字，整个31xxx区段是还没完全结束的，所以我们不能直接得到结果为4000
   • 那么前面部分的情况为0，1，2的3000种情况，也可以认为如果左侧数字是k，那么现在就有k000次
   • 又因为之前说了这个31xxx区段是还没完全结束，所以应当还有当前位后面部分的261种情况，外加如果后面都为0的情况
   • 那么这个位置数字1出现的次数就是3000 + 261 + 1 = 3262
5. 最高位为3，大于1，可以直白的知道有10000次出现了字符1，那么按照前面的规律，我们假定最高位为0，按照之前的方法可以得到( 0 + 1 ) * 10000
6. 举例数据中没有出现的当前位为0的情况，这个就比较简单了，直接就是左侧数据出现的次数了
   • 如 30261 中0的位置，
   • 就是数字1xxx,11xxx,21xxx的3000种情况

计算中间的问题

我们在计算中使用了一个辅助变量10,100,1000，10000，这个数值是比入参数字大一位的

又因为题目给的入参条件1 <= n < 2^31

所以中间计算过程我就偷了个懒给转成了long型数据

另外，葱低往高取每一位的数字的时候可以直接用余10，之后再除10的方法，我这边一开始是准备转成数组直接根据数组计算左右侧数据影响的当前位置1出现次数的，最后就还是没改了

代码

class Solution {
    /*
    3      1      2      6      1
                                3127
                         3130
                  3200
            3000 + 261 + 1
     10000
     */


    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
            99999999, 999999999, Integer.MAX_VALUE };

    public int countDigitOne(int n) {
        long ans = 0;
        long num = (long) n;
        int size = numSize(n);
        int[] arr = new int[size];
        int idx = size-1;
        while (n != 0){
            arr[idx] = n%10;
            n /= 10;
            idx--;
        }
        idx = size-1;
        long tmp = 10;
        while (idx >= 0){
            long r = 0;
            if (arr[idx] == 0){
                r = ( num / tmp ) * ( tmp / 10 );
            }
            if (arr[idx] == 1){
                r = ( num / tmp ) * ( tmp / 10 ) + ( num % (tmp / 10) ) + 1;
            }
            if (arr[idx] > 1){
                r = ( (num / tmp)+1 ) * ( tmp / 10 );
            }
            ans += r;
            tmp *= 10;
            idx--;
        }

        return (int)ans;
    }



    static int numSize(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }
}