欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode面试题43. 1~n整数中1出现的次数

程序员文章站 2022-06-07 10:29:32
...

题目来源

leetcode面试题43. 1~n整数中1出现的次数

解题方法

我们可以按照从低位向高位的顺序来解
记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;
    }
};