一、题目

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

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

提示：

• 0 <= n <= 2 * 10^9

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

二、分析及代码

1. 逐位统计

（1）思路

依次统计所有小于等于 n 的非负整数中，在各个数位上 1 的出现次数。则对于第 x 位，设 digit = 10 ^ (x - 1)，则：

• 由更高数位的值产生的当前数位 1 的出现次数，为 n / (digit * 10) * digit
  • 如对整数 12145 的百位，由更高数位产生的部分，每 1000 个数中会出现 100 个百位的 1，即共有 12145 / 1000 * 100 = 12 * 100
• 由更低数位的值产生的当前数位 1 的出现次数，为 Math.min(Math.max((n % (digit * 10) - digit + 1), 0), digit)
  • 如对整数 12145 的百位，由更低数位产生的部分，为 [100, 145] 共 46 个，即 Math.min(Math.max(12145 % 1000 - 100 + 1, 0), 100) = 46

（2）代码

class Solution {
    public int countDigitOne(int n) {
        long digit = 1L;//值为1, 10, 100, ..., 表示当前处理的十进制数位
        int ans = 0;
        while (n >= digit) {//枚举每一数位上1的个数
            int cnt1 = (int)(n / (digit * 10) * digit);//由更高数位的值产生的当前数位1的出现次数
            int cnt2 = Math.min(Math.max((int)(n % (digit * 10) - digit + 1), 0), (int)digit);//由更低数位的值产生的当前数位1的出现次数
            ans += cnt1 + cnt2;//统计
            digit *= 10L;//十进制数位左移1位
        }
        return ans;
    }
}

（3）结果

执行用时 ：0 ms，在所有 Java 提交中击败了 100.00% 的用户；
内存消耗 ：35.2 MB，在所有 Java 提交中击败了 35.70% 的用户。

三、其他

暂无。