剑指 Offer 43. 1~n 整数中 1 出现的次数
题目
输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。 例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。
示例 1:
输入:n = 12
输出:5
示例 2:
输入:n = 13
输出:6
限制:
1 <= n < 231
注意:本题与主站233题相同
题解
public int countDigitOne(int n) {
int count = 0;
// 从个位开始遍历到最高位
long i = 1;
while (n / i != 0) {
// 高于i位的数字
long high = n / (10 * i);
// i位数字
long cur = (n / i) % 10;
// 低于i位数字
long low = n - (n / i) * i;
// 当前位为0 只计算高位的0
if (cur == 0) {
count += high * i;
} else if (cur == 1) {
// 当前位为1 则高位加低位
count += high * i + (low + 1);
} else {
// 当前位大于1
count += (high + 1) * i;
}
// 进位
i *= 10;
}
return count;
}