LeetCode[233] Number of Digit One

v1 发布于2019-08-14 14:58 / 2095人阅读

摘要：递归复杂度思路每次将一个数拆分成两部分考虑，并考虑当前最高是不是比如，将数拆分成，和，这两部分分别计算。每次抹去高位，观察重复情况。代码代表位数，代表最高的值除了高位的剩余部分

LeetCode[23] Number of Digit One

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.

递归

复杂度
O(N), ? O(1)

思路
每次将一个数拆分成两部分考虑，并考虑当前最高是不是1.
比如115，将数拆分成，15和0-100，这两部分分别计算。
如果最高位是1的数，那么一定会包括 100-115这16个数，除了那两部分之外。
每次抹去高位，观察重复情况。

代码

public int countDigitOne(int n) {
    if(n < 10) {
        return n > 0 ? 1 : 0;
    }
    // count代表位数，num代表最高的值
    int level = 10, num = 0;
    int count = 0;
    // integer overflow;
    while(n / level >= 10) {
        level *= 10;
    }
    num = n / level;
    //
    if(num == 1) {
        count += (n - level + 1) + countDigitOne(level - 1);
    }
    else if(num > 1) {
        count += num * countDigitOne(level - 1) + level;
    }
    // 除了高位的剩余部分；
    count += countDigitOne(n - level * num);
    return count;
    //return level;
}

服务器托管混合云 233服 Digit LeetCode LeetCode_String

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

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

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 2019-08-14 15:54 评论0 收藏0
leetcode233. Number of Digit One

摘要：题目要求计算所有小于等于的正整数中数字的个数。比如比小的正整数中包含的有，一共有个。因此，我们需要用更好的方法，减少这种方法的浪费。其实等价于中的的个数。题目要求 Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal...

UnixAgain 2019-08-16 11:02 评论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 2019-08-14 14:02 评论0 收藏0
leetcode486. Predict the Winner

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

王军 2019-08-19 10:25 评论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 2019-08-14 12:36 评论0 收藏0