[打卡]8.13_233.数字1的个数
题目:233. 数字 1 的个数 - 力扣(LeetCode) (leetcode-cn.com)
参考题解: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;
}
};