leetcode面试题43. 1~n整数中1出现的次数
程序员文章站
2022-06-07 10:29:32
...
题目来源
解题方法
我们可以按照从低位向高位的顺序来解
记high为高位,cur为当前位,low为低位
直接举例:5014
首先我们先看个位,此时high=501,cur=4,low=0,那么对于这种情况,高位从0-500的变化过程中,个位都会有一个1,所以有501*1个1,接着当前位是4且该位为个位,因此只会有1个1,所以个位有501+1=502个1
接着我们看十位,此时high=50,cur=1,low=4,对于这种情况,高位从0-49的变化过程中,十位都会有1个1,也就是说每次变化,都会有10-19十个1,即50*10=500个1,接着我们看cur,cur为1,那么到底有几个1呢,我们需要看低位,低位为4,说明只有10-14五个,所以结果为500+5=505
接着我们看百位,此时high=5,那么0-4的变化中,每个百位对应100个1(101-199),所以5*100=500个1,接着看cur,cur=0,说明不会有1的情况了,答案就是500
最后我们看千位,此时high=0,cur为5,low为014,那么就只有1000个1(1000-1999),答案就是1000
最终答案为502+505+500+1000=2507个
总结如下
cur为1,ans=high*i+low+1
cur为0,ans=high*i
cur大于1,ans=high*i+i
最后附上代码,注意点:要使用long存储,不然会越界
class Solution {
public:
int countDigitOne(int n) {
long i = 1;
int ans = 0;
while(n / i != 0){
long high = n/(10*i);// 记录高位
long cur = (n/i)%10;// 记录当前位
long low = n - (n/i)*i;// 记录当前位数
if(cur == 0){
ans += high * i;
} else if(cur == 1){
ans += (high * i + low + 1);
} else{
ans += (high * i + i);
}
i *= 10;
}
return ans;
}
};
上一篇: 韩信:聪明一世糊涂一时 让人想不透
下一篇: 面试题43. 1~n整数中1出现的次数
推荐阅读
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
【剑指offer】_11整数中1出现的次数
-
【LeeCode 中等 数学 python3】剑指 Offer 43. 1~n整数中1出现的次数
-
剑指offer 从1到n整数中1出现的次数
-
剑指offer32题:整数中1出现的次数(从1到n整数中1出现的次数)
-
整数中1出现的次数(从1到n整数中1出现的次数)(剑指offer第32题)
-
剑指offer:(32)时间效率 :整数中1出现的次数(从1到n整数中1出现的次数)
-
【剑指offer】从1到n整数中1出现的次数(查找)
-
剑指offer---从1到n整数中1出现的次数