233.java

/*
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13
输出: 6 
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-digit-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/*
我们可以观察到每 1010 个数，个位上的 \text{'1'}’1’ 就会出现一次。同样的，每 100100 个数，十位上的 \text{'1'}’1’ 就会出现一次。这个规律可以用 (n/(i*10))*i(n/(i∗10))∗i 公式来表示。

同时，如果十位上的数是 \text{'1'}’1’，那么最后 \text{'1'}’1’ 的数量要加上 x+1x+1，其中 xx 是个位上的数值。如果十位上的数大于 \text{'1'}’1’，那么十位上为 \text{'1'}’1’ 的所有的数都是符合要求的，这时候最后 \text{'1'}’1’ 的数量要加 1010。

这个规律可以用公式 {\min(\max((\text{n mod (i*10)} )-i+1,0),i)}min(max((n mod (i*10))−i+1,0),i) 来表示。

我们来看一个例子吧，有一个数 n = 1234n=1234。

个位上 \text{'1'}’1’ 的数量 = 1234/101234/10 (对应 1,11,21,...1221) + \min(4,1)min(4,1) (对应 1231) = 124124

十位上 \text{'1'}’1’ 的数量 = (1234/100)*10(1234/100)∗10 (对应 10,11,12,...,110,111,...1919) + \min(21, 10)min(21,10) (对应 1210,1211,...1219) = 130130

百位上 \text{'1'}’1’ 的数量 = (1234/1000)*100(1234/1000)∗100 (对应 100,101,102,...,199) + \min(135, 100)min(135,100) (对应1100,1101...1199) = 200200

千位上 \text{'1'}’1’ 的数量 = (1234/10000)*10000(1234/10000)∗10000 + \min(235, 1000)min(235,1000) (对应1000,1001,...1234) = 235235

因此，总数 = 124+130+200+235 = 689124+130+200+235=689。

算法

将 ii 从 11 遍历到 nn，每次遍历 ii 扩大 1010 倍：
(n/(i*10))*i(n/(i∗10))∗i 表示 (i*10)(i∗10) 位上 \text{'1'}’1’ 的个数。
{\min(\max((\text{n mod (i*10)} )-i+1,0),i)}min(max((n mod (i*10))−i+1,0),i) 表示需要额外数的 (i*10)(i∗10) 位上 \text{'1'}’1’ 的个数。

作者：LeetCode
链接：https://leetcode-cn.com/problems/number-of-digit-one/solution/shu-zi-1-de-ge-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

*/

class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        for(long i=1;i<=n;i=i*10){
            long divider = i*10;
            count += (n/divider) * i + Math.min(Math.max(n%divider-i+1,0),i);
        }
        return count;
    }
}