[LeetCode] Number of Digit One

supernavy 發布于2019-08-14 14:02 / 2865人閱讀

摘要：只有大于左邊界才部分包含，且只有大于右邊界的數才完整包含，這些中多余的。對于而言，部分包含用余數做，完整包含用進位后的商做。逐位向上累加，可得結果。千位萬位，大致如此。例如個位十位百位千位

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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