No.233 数字1的个数

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

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

提示：

• 0 <= n <= 2 * 109

思路分析

令a=n/i,b=n%i;
举例分析，假设n=12345，i=100; 此时a=123,b=45：
1）当a的个位大于1时（也就是n的百位），百位为1的数总共出现了(a/10+1)*100次
2）当a为1的时候，百位为1的数总共出现了(a/10)*100+(b+1);
3）当a为0的时候，百位为1的数出现了(a/10)*100次；
因此可以根据a的个位是否为1分成2中情况计算，可以使用一个表达式合并以上三个式子。
a.   9=>(a个位)>=2和0=<(a个位<=1)时的(a/10+1),(a/10)表达式与(a+8)/10等价；
b.  （a>=2时（a+8）/10的结果与a/10+1相同，a==1或a==0时（a+8）/10的结果等价a/10。
c.   当a个位为1时需要加上（b+1）与(a%10==1)*(b+1)等价。因此合并后百位为1的数的个数为
(a+8)/10*i+(a%10==1)*(b+1);
然后令i从个位到最高位遍历即可计算每一位含1的个数；

Rust代码

#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn count_digit_one(n: i32) -> i32 {
        let mut cnt = 0;
        let mut i = 1;
        while i <= n {
            let a = n / i;
            let b = n % i;
            cnt += (a + 8) / 10 * i + if a % 10 == 1 {b + 1} else {0};
            i *= 10;
        }
        cnt
    }
}
}