【题目】
输入一个整数 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 < 2^31
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
【思想】
解题思路：
将 1 ~n 的个位、十位、百位、...的 1 出现次数相加，即为 1 出现的总次数。
设数字 n 是个 x 位数，记 n的第 i 位为 ni ，则可将 n 写为 nxnx−1⋯n2n1：
称 " ni " 为 当前位 ，记为 cur ，
将 " ni−1ni−2⋯n2n1 " 称为 低位 ，记为 low ；
将 " nxnx−1⋯ni+2ni+1 " 称为 高位 ，记为 high 。
将 10i称为 位因子 ，记为 digit。
某位中 1出现次数的计算方法：
根据当前位 curcur 值的不同，分为以下三种情况：
当 cur=0时： 此位 1 的出现次数只由高位 high 决定，计算公式为：
high×digit
如下图所示，以 n=2304 为例，求 digit=10（即十位）的 1出现次数。
当 cur=1 时： 此位 1 的出现次数由高位 high和低位 low 决定，计算公式为：
high×digit+low+1
如下图所示，以 n=2314 为例，求 digit=10 （即十位）的 1出现次数。
当 cur=2,3,⋯ ,9 时： 此位 1 的出现次数只由高位 high决定，计算公式为：
(high+1)×digit
如下图所示，以 n=2324为例，求 digit=10 （即十位）的 1 出现次数。
变量递推公式：
设计按照 “个位、十位、...” 的顺序计算，则 high/cur/low/digit应初始化为：
high = n // 10
cur = n % 10
low = 0
digit = 1 # 个位
举例
以2593为例,例子挺经典,k为5
从最后一位开始,cur表示当前位的值依次为3,9,5,2,high,low分别表示cur的前后,比如:
cur为9,high=25,low=3
下面开始分析:
cur = 3,high=259,low=0,[1,3]中不可能出现5,所以前缀只能取0,1,2,3...258,取不到259,所以5在个位出现了259次.
cur = 9,high = 25,low=3,[1-93]中可以出现5x,所以前缀可以0,1,2,3....25,5在10位出现了26x10=260次.
cur = 5,high = 2,low=93,[1-593]中可以出现5xx,所以前缀可以0,1,2,但是前缀为2时,5xx<=593,不是一个完整的序列,5在百位出现了2x100+93+1次,(为啥加1呢,0-93是94次,所以加1)
cur = 2,high = 0,low=593,[1-2593]中不能出现5xxx,因此5在千位0次.
总结规律:
base = 10^(i-1)
cur >k,结果为 (high+1)*base
cur ==k,结果为 (high)base + low + 1
cur < k,结果为 highbase
【代码】
class Solution {
public int countDigitOne(int n) {
int digit = 1, res = 0;
int high = n / 10, cur = n % 10, low = 0;
while(high != 0 || cur != 0) {
if(cur == 0) res += high * digit;
else if(cur == 1) res += high * digit + low + 1;
else res += (high + 1) * digit;
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
}
标签：10,digit,cur,Offer,43,整数,high,次数,low From： https://www.cnblogs.com/End1ess/p/17369219.html