[Lc]233数字1的个数

题目

题解

这题可以用暴力法，即挨个数字统计，必定超时

时间复杂度：$O(n*log_{10}(n))$
1. 从 1 遍历到 n。
2. 每次遍历中，我们把整数转成字符串去数 $\text{‘1’}$ 的个数，这个过程会花费 m 的时间，其中 m 为字符串的长度，其最大值为 $log_{10}(n)$
空间复杂度：需要申请 $O(log_{10}(n))$ 个额外的空间来存储 countr 和整数转换成的字符串 $\text{str}$。

1. 数学法1

遍历每一位，统计这一位中1的个数每一位分为两块统计
- 前半部分：每i*10个数，在i位上会有i个1，比如292，前200中没100个数有10个1
- 后半部分：n%(i*10)-i+1，这里n%(i*10)是剩下的余数部分，如192统计10位的1，余下92；-i+1是去掉前10个数1，即从110~192，为83个数，前面的100到109都不在10位上有1
  1. 若后半部分大于i，比如192统计10位的1，余数为92，后半部分为83，则取10，因为100~192中10位还有10个1，110，111，112，113，114，115，116，117，118，119
  2. 若后半部分小于i且大于0，比如114统计10位的1，余数为14，后半部分为5，则取5，因为100~114中10位还有5个1，110，111，112，113，114
  3. 若后半部分小于i且小于0，比如102统计10位的1，余数为2，后半部分为-7，则取0，因为100~102中10位还有0个1
时间复杂度：$O(log_{10}(n))$，遍历的次数等于 nn 转成字符串后字符串的长度，其值为 $log_{10}(n)$。
空间复杂度：只需要 $O(1)$ 的额外空间。

class Solution {//两个数学法。1.逐位统计1法
public:
    int countDigitOne(int n) {
        int res = 0;
        for(long i=1; i<=n; i*=10){//逐位统计1的个数
            long divider = i*10;
            res += n/divider*i + min(max(n%divider-i+1,0l),i);
        }
        return res;
    }
};

2. 数学法2

也是逐位遍历，细节稍微改变以下，来自(https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/)
把当前位的大小记为cur，高位的记为high，低位的记位low，cur的数量级记为digit
按个遍历cur，统计res，cur的大小分三种情况

cur==0，res += high*digit;
cur==1，res += high*digit+low+1;
cur = 2~9，res += (high+1)*digit; 具体分析可见上述链接

时间复杂度：$O(log_{10}(n))$，遍历的次数等于 nn 转成字符串后字符串的长度，其值为 $log_{10}(n)$。
空间复杂度：只需要 $O(1)$ 的额外空间。

class Solution {//两个数学法。2.逐位判断法
public:
    int countDigitOne(int n) {
        int res = 0;//定义res存结果
        if(n<=0) return res;
        long digit = 1;//定义digit存当前数量级，1，10，100...
        int high = n/10, cur = n%10, low = 0;//定义cur是当前位，high是cur以上的部分，low是cur以下的部分
        while(high!=0 || cur!=0){//当high或cur中至少一个不为0，则继续遍历
            //下面是对cur的数值分情况讨论
            if(cur==0) res += high*digit;
            else if(cur==1) res += high*digit+low+1;
            else res += (high+1)*digit;
            //下面是更新high,cur,low,digit
            low += cur*digit;
            cur = high%10;//注意要先变cur再变highint
            high /= 10;
            digit *= 10;
        }
        return res;
    }
};

Contents

题目

题解

1. 数学法1

2. 数学法2