亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[LeetCode] Number of Digit One

supernavy / 2925人閱讀

摘要：只有大于左邊界才部分包含，且只有大于右邊界的數(shù)才完整包含，這些中多余的。對(duì)于而言，部分包含用余數(shù)做，完整包含用進(jìn)位后的商做。逐位向上累加，可得結(jié)果。千位萬(wàn)位，大致如此。例如個(gè)位十位百位千位

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

舉個(gè)例子，分析1212個(gè)數(shù)中1的個(gè)數(shù)。

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

到這里，看出規(guī)則了么？
前1000個(gè)數(shù)百位、十位、個(gè)位各有100個(gè)1，前100個(gè)數(shù)中個(gè)位，十位各有10個(gè)1，前10個(gè)數(shù)個(gè)位有1個(gè)1，那么不妨猜一猜前10000個(gè)數(shù)有多少個(gè)1？
4000.

下面分析一下計(jì)算過(guò)程：

首先，找哪些1？找這些1的順序是什么？上面例子采用的是逐位計(jì)數(shù)法，先從個(gè)位算起，再算十位、百位上的1。

其次，確定了次序之后，怎么找這一位的1？對(duì)于個(gè)位的1，我們可以去計(jì)算n包含多少個(gè)10，每個(gè)10一定對(duì)應(yīng)一個(gè)1，再加上0 ~ 9之間的一個(gè)1；對(duì)于十位的1，也就是計(jì)算10的個(gè)數(shù)，同理，先計(jì)算n包含多少個(gè)100，再加上n除以100的余數(shù)中包含10的個(gè)數(shù)，再加上0到100之間的那個(gè)10。

總結(jié)個(gè)位和百位的方法，都是先確定一個(gè)基數(shù)，base，再看對(duì)于每個(gè)base是否包含這一位的special case中的1（*11到19，110到119，1100到1199是specail case）。

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

對(duì)于special case而言，部分包含用余數(shù)做，完整包含用進(jìn)位后的商做。逐位向上累加，可得結(jié)果。千位萬(wàn)位，大致如此。

例如：

n = 1212

base = 1
q = 1212, r = 0
count += 122: 個(gè)位

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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64772.html

相關(guān)文章

  • LeetCode[233] Number of Digit One

    摘要：遞歸復(fù)雜度思路每次將一個(gè)數(shù)拆分成兩部分考慮，并考慮當(dāng)前最高是不是比如，將數(shù)拆分成，和，這兩部分分別計(jì)算。每次抹去高位，觀察重復(fù)情況。代碼代表位數(shù)，代表最高的值除了高位的剩余部分 LeetCode[23] Number of Digit One Given an integer n, count the total number of digit 1 appearing in alln...

    v1 評(píng)論0 收藏0

  • LeetCode 233 : Number of Digit One (java)

    摘要：題目給一個(gè)數(shù)求從到所有數(shù)中數(shù)字在各個(gè)位上出現(xiàn)的總次數(shù)。解法可以做循環(huán)從到挨個(gè)找。更好的是用歸納法總結(jié)出出現(xiàn)的次數(shù)的規(guī)律。 題目：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 評(píng)論0 收藏0

  • leetcode233. Number of Digit One

    摘要：題目要求計(jì)算所有小于等于的正整數(shù)中數(shù)字的個(gè)數(shù)。比如比小的正整數(shù)中包含的有，一共有個(gè)。因此，我們需要用更好的方法，減少這種方法的浪費(fèi)。其實(shí)等價(jià)于中的的個(gè)數(shù)。 題目要求 Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal...

    UnixAgain 評(píng)論0 收藏0

  • [Leetcode] Plus One 加一

    摘要：不過(guò)這里有個(gè)小技巧，因?yàn)槲覀冎灰?，所以不用完全模擬加法的所有規(guī)則一個(gè)數(shù)如果不是，那加以后不會(huì)對(duì)其他位產(chǎn)生影響。 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 評(píng)論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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<