剑指 Offer 43 | 1~n整数中的十进制表示中1出现的次数
输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。
例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。
示例 :
输入:n = 12
输出:5
输入:n = 13
输出:6
- 限制:
1 <= n < 231
思路:都是统计1 ~ n中各个位上1出现的次数然后相加,个位上1出现的次数 + 十位上1出现的次数 + 百位上1出现的次数+ … 。
方法一:
计算每个位数上1出现的次数时,先计算 \([0, n / 10 - 1]\) 中1出现的次数,再计算 \([n / 10, n]\) 中1出现的次数。因为 \([0, n / 10 - 1]\)中1出现的次数是有规律的:
个位上1出现的次数:
[0, 9] 1次
[0, 99] 10次
[0, 999] 100次
[0, 9999] 1000次
十位上1出现的次数:
[0, 99] 10次
[0, 999] 100次
[0, 9999] 1000次
所以当 cur = 0 时, 只需要计算 \([0, n / 10 - 1]\) 中 cur 位上1出现的次数 (这里的 n 是指最开始传入的 n;下面的代码中 n 每次循环都要除10,不是原始的 n 了)
当 cur = 1 时, 还要计算 \([n / 10, n]\) 中1出现的次数为 low + 1;
当 cur > 1 时, \([n / 10, n]\) 中1出现的次数刚好为 num;
int countDigitOne(int n) {
//高位
int low = 0, count = 0, cur;
long num = 1; // 表示个位、十位、百位
while (n != 0) {
cur = n % 10; // 从个位开始遍历
n /= 10; //
count += n * num;
if (cur == 1) count += low + 1;
else if (cur > 1) count += num;
low += cur * num; // 记录遍历过的位数上的值,当 cur = 1 时,可以组成的 cur 位上为1的数有 low + 1 个。
num *= 10;
}
return count;
}
方法二:
理解起来和方法一类似,只是求当 cur >= 1 时,计算 \([n / 10, n]\) 的部分1出现的次数的方式不同
大佬总结出来的数学公式:
\({n} \over {10^{k+1} }\) \(\times 10^k\) + min ( max ( n mod 10k+1 - 10k +1, 0), 10k)
k=0,1,2 分别表示个位、十位、百位...
int countDigitOne(int n) {
long long num = 1;
int count = 0;
while (n >= num) {
count += (n / (num * 10)) * num; // 注意:n / (num * 10) * num 不等于 n / 10
count += min(max(n % (num * 10) - num + 1, 0LL), num); // n % (num * 10) - num 为方法一中的low
num *= 10;
}
return count;
}
标签:count,10,cur,Offer,43,次数,num,出现,十进制
From: https://www.cnblogs.com/AngleLin/p/16995305.html