资讯专栏INFORMATION COLUMN

leetcode233. Number of Digit One

UnixAgain / 720人阅读

摘要:题目要求计算所有小于等于的正整数中数字的个数。比如比小的正整数中包含的有,一共有个。因此,我们需要用更好的方法,减少这种方法的浪费。其实等价于中的的个数。

题目要求
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

计算所有小于等于n的正整数中数字1的个数。
比如比13小的正整数中包含1的有1,10,11,12,13,一共有6个1。

思路一:找规律

如果使用暴力循环的话,那么我们只需要遍历所有小于n的正整数,计算该正整数中包含几个1并将返回这些结果的和。但是,这种方法浪费了很多不必要的计算。比如在小于n的正整数中,有很多甚至都一个1都没有。因此,我们需要用更好的方法,减少这种方法的浪费。

我们随意找一个数来入手,假设现在n为52,那么52下含有的1实际上等于50~52 + 1~49中有的1,也就等价于0~2 + 1~49中含有的1。
在这里我们很清楚的知道,当n<10时,只有1个1。因此0~2只有1个1。

我们再来拆解1~49
1~49其实等价于40~49 + 30~39 + 20~29 + 10~19 + 1~9中的1的个数。我们再分析一下就会发现,40~49, 30~39 , 20~29, 0~9中的1的个数是相同的!而特殊的情况是10~19,它的1的数量其实等于10 + 0~9

总结一下我们知道countDigitOne(52) = countDigitOne(2) + countDigitOne(9) * 5 + 10

这里其实还有一个特殊情况,就是当最高位恰好为1的时候,举个例子135。那么100~135等价于36+0~35个1,那么countDigitOne(135) = 36 + countDigitOne(35) + countDigitOne(99)

整理为代码如下:

    public int countDigitOne(int n) {
        if(n <= 0) return 0;
        if(n < 10) return 1;
        int count = 1;
        while(n / count > 9){
            count *= 10;
        }
        if(n / count == 1){
            return n % count + 1 + countDigitOne(n%count) + countDigitOne(count-1);
        }else{
            return countDigitOne(n % count) + count + (n/count) * countDigitOne(count-1);
        }
    }


想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/70939.html

相关文章

  • LeetCode[233] Number of Digit One

    摘要:递归复杂度思路每次将一个数拆分成两部分考虑,并考虑当前最高是不是比如,将数拆分成,和,这两部分分别计算。每次抹去高位,观察重复情况。代码代表位数,代表最高的值除了高位的剩余部分 LeetCode[23] Number of Digit One Given an integer n, count the total number of digit 1 appearing in alln...

    v1 评论0 收藏0
  • LeetCode 233 : Number of Digit One (java)

    摘要:题目给一个数求从到所有数中数字在各个位上出现的总次数。解法可以做循环从到挨个找。更好的是用归纳法总结出出现的次数的规律。 题目:Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. For example:...

    i_garfileo 评论0 收藏0
  • [LeetCode] Number of Digit One

    摘要:只有大于左边界才部分包含,且只有大于右边界的数才完整包含,这些中多余的。对于而言,部分包含用余数做,完整包含用进位后的商做。逐位向上累加,可得结果。千位万位,大致如此。例如个位十位百位千位 Problem Given an integer n, count the total number of digit 1 appearing in all non-negative integer...

    supernavy 评论0 收藏0
  • leetcode486. Predict the Winner

    摘要:但是,往往会有可以优化的空间。假设我们用来记录子数组之间,第一个取数字的玩家和第二个取数字的玩家之间最大的差距。再考虑初始情况,即当数组长度为时,可以得知此时玩家一和玩家二之间的差距即为该数组元素的值。 题目要求 Given an array of scores that are non-negative integers. Player 1 picks one of the numb...

    王军 评论0 收藏0
  • [Leetcode] Plus One 加一

    摘要:不过这里有个小技巧,因为我们只要加,所以不用完全模拟加法的所有规则一个数如果不是,那加以后不会对其他位产生影响。 Plus One Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most...

    shmily 评论0 收藏0

发表评论

0条评论

UnixAgain

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<