[打卡]8.13_233.数字1的个数

题目:233. 数字 1 的个数 - 力扣(LeetCode) (leetcode-cn.com)

image-20210813023224304

参考题解:AcWing 338. 计数问题 - AcWing

AC代码:

class Solution {
public:
    int countDigitOne(int n) {
        if(!n) return 0;//如果为0,则直接是0
        int res = 0;
        int d = log10(n)+1;//计算n的位数
        for (int i = 1; i <= d; i++) {//从第1位开始枚举
            int p = pow(10, i - 1);//计算当前位数是10的几次方,用于分割左边和右边(状态1)
            int l = n / p / 10, r = n % p, di = n / p % 10;//分割左边、右边、和取到第i位 的数字
            res += l * p;//(状态二)
            if (di > 1) res += p;//如果当前数字大于1,则只有0~p种可能(状态三)
            if (di == 1) res += r + 1;//如果当前数字为1,则有0~r+1种可能(状态四)
        }
        return res;
    }
};

状态图:

image-20210813023051704

本文链接:

https://nullcode.fun/168.html
1 + 9 =
快来做第一个评论的人吧~