LeetCode[233] Number of Digit One

v1 發布于2019-08-14 14:58 / 2420人閱讀

摘要：遞歸復雜度思路每次將一個數拆分成兩部分考慮，并考慮當前最高是不是比如，將數拆分成，和，這兩部分分別計算。每次抹去高位，觀察重復情況。代碼代表位數，代表最高的值除了高位的剩余部分

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

云服務器 GPU云服務器 233服 Digit LeetCode LeetCode_String

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

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