通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 43. 1~n 整数中 1 出现的次数

171人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/906

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 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 < 2^31

难度:困难;标签:数学;编程语言:C++


我的解法

class Solution {
public:
    // x位数1的个数:1:1,2:20,3:300,n:n*10^(n-1)
    int countDigitOne(int n) {
        if(n <= 0)return 0;

        long dp[12] = {0};
        dp[1] = 1;
        for(int i = 2; i < 12; i++)
            dp[i] += (long)pow(10, i - 1) + 10 * dp[i - 1];

        int t = n, c = 0, h = 0;
        while(t != 0){
            c++;
            h = t % 10;
            t /= 10;
        }

        int next = countDigitOne(n - (int)pow(10, c - 1) * h);
        return h > 1 ? (int)pow(10, c - 1) + (int)dp[c - 1] * h + next : n - (int)pow(10, c - 1) + 1 + next + (int)dp[c - 1];
    }
};

如果知道1~n位数中1的个数为x,那么再增加1位,1~n+1位数中1的个数呢?如果把这一位加在右边最低位,原来n位为x个1,加的1位可取0~9,组合一下前n位1的个数扩大10倍到10x,这里没有算上最低位的1,如果最低位为1,共有10^n种情况,所以如果1~n位有x个1,那么1~n+1共有10^n+10x个1,由此可以用递归来计算,如678,从高位一位一位算,先算600,这是三位数,最高位是1,有10^2种情况(0~99),剩余两位数可取0~99有dp[2]种情况,与最高位组合,有6*dp[2]种情况,所以共有100+dp[2]*6种情况,再加上78的1的个数即可;当最高位是1时,如123,先算最高位1,有24种情况(0~23),再算剩余两位有dp[2]种情况,再算23有next种情况,所以最后的结果要return h>1 ? :


其它解法

class Solution {
public:
    int countDigitOne(int n) {
        if (!n)
            return 0;
        if (n < 10)
            return 1;
        int m = n;
        int l;
        int len = 0;
        while (m) {
            ++len;
            l = m;
            m /= 10;
        }
        int ll = l*pow(10,len-1);
        if (l == 1)
            return (n-ll+1) + (ll/10)*(len-1) + countDigitOne(n-ll);
        else
            return pow(10,len-1) + (ll/10)*(len-1) + countDigitOne(n-ll);
    }
};

一样的解法,写法也基本一样,看我的解法的解释看这个就能理解了


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告