LeetCode 233 : Number of Digit One (java)

i_garfileo 發布于2019-08-14 15:54 / 2905人閱讀

摘要：題目給一個數求從到所有數中數字在各個位上出現的總次數。解法可以做循環從到挨個找。更好的是用歸納法總結出出現的次數的規律。

題目：
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.

給一個數n,求從1到n所有數中數字1在各個位上出現的總次數。

解法：

可以做循環從1到n挨個找。慢。

更好的是用歸納法總結出1出現的次數的規律。

假設n=abcde五位數字的時候，我們分析百位c，有三種情況：

1）c == 0的時候，比如12013，此時百位出現1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，共1200個，顯然這個有高位數字決定，并且受當前位數影響；個數就是 ab*100

2）c == 1的時候，比如12113，此時百位出現1的肯定包括c=0的情況，另外還需要考慮低位的情況即：00100 ~ 00113共14個; 個數等于ab*100+ de + 1

3）c >= 2的時候，比如12213，此時百位出現1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，12 100 ~ 12 199，共1300個，這個有高位數字決定，其實是加一，并且乘以當前位數; 個數就是 (ab+1)*100

總結起來，對于一個 n = abcde 來說，百位出現1的個數計算方法為：

if(c==0) ans = ab*100;
if(c==1) ans = ab*100+cd+1
if(c>1) ans = (ab+1)*100

代碼：

public class Solution {
    public int countDigitOne(int n) {
        if(n <= 0) return 0;
        int q = n; int x = 1; int ans = 0; int temp = 0;
        do{
            temp = q%10;
            q/=10;
            if(temp == 0) ans+=q*x;
            else if(temp == 1) ans+=q*x + n%x + 1;
            else
                ans+=(q+1)*x;
            x*=10;
        } while (q > 0);
        return ans;
    }
}

Ref：

java one pass easy understand

leetcode 233

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66097.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
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
Leetcode加一（java、python3）

摘要：加一給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。示例輸入輸出解釋輸入數組表示數字。思路指針從最后往前移動，若值為逐個加一，并賦值。不等于則退出循環。首位如果為是則證明需要進一。只需首位賦值即可。加一給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。最高位數字存放在數組的首位，數組中每個元素只存儲一個數字。你可以假設除了整數 0 之外，這個...

沈建明 2019-07-31 10:30 評論0 收藏0
Leetcode加一（java、python3）

摘要：加一給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。示例輸入輸出解釋輸入數組表示數字。思路指針從最后往前移動，若值為逐個加一，并賦值。不等于則退出循環。首位如果為是則證明需要進一。只需首位賦值即可。加一給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。最高位數字存放在數組的首位，數組中每個元素只存儲一個數字。你可以假設除了整數 0 之外，這個...

Apollo 2019-08-16 17:51 評論0 收藏0