[LeetCode] Number of Digit One

supernavy 发布于2019-08-14 14:02 / 2851人阅读

摘要：只有大于左边界才部分包含，且只有大于右边界的数才完整包含，这些中多余的。对于而言，部分包含用余数做，完整包含用进位后的商做。逐位向上累加，可得结果。千位万位，大致如此。例如个位十位百位千位

Problem

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.

Hint:

Beware of overflow.

Note

举个例子，分析1212个数中1的个数。

0 - 9:                             1(个位)
10 - 19：                10(十位) + 1(个位)
20 - 99:                           8(个位)
100 - 199:   100(百位) + 10(十位) + 10(个位)
200 - 999：              80(十位) + 80(个位)
1000 - 1199: 200(千位) + 120(同100 - 199)

到这里，看出规则了么？
前1000个数百位、十位、个位各有100个1，前100个数中个位，十位各有10个1，前10个数个位有1个1，那么不妨猜一猜前10000个数有多少个1？
4000.

下面分析一下计算过程：

首先，找哪些1？找这些1的顺序是什么？上面例子采用的是逐位计数法，先从个位算起，再算十位、百位上的1。

其次，确定了次序之后，怎么找这一位的1？对于个位的1，我们可以去计算n包含多少个10，每个10一定对应一个1，再加上0 ~ 9之间的一个1；对于十位的1，也就是计算10的个数，同理，先计算n包含多少个100，再加上n除以100的余数中包含10的个数，再加上0到100之间的那个10。

总结个位和百位的方法，都是先确定一个基数，base，再看对于每个base是否包含这一位的special case中的1（*11到19，110到119，1100到1199是specail case）。

只有大于左边界(10、110、1100)才部分包含，且只有大于右边界20、200的数（29, 150, 1300）才完整包含，这些special case中多余的1。

对于special case而言，部分包含用余数做，完整包含用进位后的商做。逐位向上累加，可得结果。千位万位，大致如此。

例如：

n = 1212

base = 1
q = 1212, r = 0
count += 122: 个位

base = 10
q = 121, r = 2
count += 120 + 3: 十位

base = 100
q = 12, r = 12
count += 200: 百位

base = 1000
q = 1, r = 212
count += 213: 千位

Solution

public class Solution {
    public int countDigitOne(int n) {
      int count = 0;
      for (long base = 1; base <= n; base *= 10) {
        long q = n/base, r = n%base;
        count += (q+8) / 10 * base + (q%10 == 1 ? r+1 : 0);
      }
      return count;
    }
}

云服务器 GPU云服务器 Digit LeetCode LeetCode_String leetcode_35_SearchIn

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

转载请注明本文地址：https://www.ucloud.cn/yun/64772.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 2019-08-14 14:58 评论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 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] 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
[LeetCode/LintCode] Plus One

Problem Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. Example Given [1,2...

sunsmell 2019-08-14 15:17 评论0 收藏0