【Java题解】剑指 Offer 43. 1～n 整数中 1 出现的次数

【Java题解】剑指 Offer 43. 1～n 整数中 1 出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：

1 <= n < 2^31

方法一：
暴力遍历，数一下1-n的数中，每一个数中1的个数。
超时。

代码：

class Solution {
    public int countDigitOne(int n) {
        // 暴力 直接遍历，计算出每个数字上的1的个数
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            cnt += count(i);
        }
        return cnt;
    }

    int count(int i) {
        int t = 0;
        int cnt = 0;
        while (i != 0) {
            t = i % 10;
            if (t == 1) cnt++; 
            i /= 10;
        }
        return cnt;
    }
}

时间复杂度：O(Σ（a * start_a * 9）（a从1->len(n) - 1） +len(n) * k) 1-n所有的数字共有多少位，就要遍历多少次。a:是数字的长度， start：a数字对应的不同长度分组的首个数字，如1，10，100；len(n)是数字n的长度，k是n - start_n的剩余下的数字。
空间复杂度：O(1)

方法二：
数学推导。推导过程见leetcode题解
对于一个数字n，可以求所有数字上的每一位（个十百千…）上的1的出现个数，求和就是结果。

1. 对于n，从它的个位开始遍历，根据数学规律来求出该位上1的个数。大概推导过程如下。
2. 首先先定义几个变量，cur代表当前指向的数字，i代表当前指向的位数(个十百千…)，digit = 10 ^ i,代表权重，high代表在n中cur前面的数字，low代表cur后面的数字。
3. 假如一个数：n = 1203，cur 指向的十位的话，那么就是正在求十位上是1的个数。如果cur = 0, 那么1的个数就是 high * dight，这个是怎么得到的？可以把上面n这个数字想象成一个密码锁，现在固定住了十位上的0，只能拨动其他三个数字，并且它们是有限制的。那么可以得到，先把十位上的数字拨到1，0000 - 111[0-9]，1200 - 1203，n可以被分为这两段数字。由于十位数字不动，那么容易得到000 - 11[9] + 1就是结果，也就是high * digit
4. 同理，cur = 1, 可以得到，结果是：high * digit + low + 1,会多一个1
5. 同理，cur > 1，可以得到，结果是：(high + 1) * digit

代码：

class Solution {
    public int countDigitOne(int n) {
        // 暴力 直接遍历，计算出每个数字上的1的个数 O(n2) O(1) 超时
        int digit = 1, res = 0; // digit = 10 ^ i， i就是个十百千万...位数
        int high = n / 10, cur = n % 10, low = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) res += high * digit;
            else if (cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10; 
        }
        return res;
    }
}

时间复杂度：O(lgn) 循环次数为：T = log10(n) ，因为循环一次就要/10。
空间复杂度：O(1)