劍指offer(43 1~n整數中1出現的次數) 題解

劍指offer-43 1~n整數中1出現的次數

微信搜尋【程式員畫工師】關注更多Java程式設計技術、資料結構與算法、面試題相關内容。

題目

輸入一個整數n，求1~ n這n個整數的十進制表示中1出現的次數。例如輸入12，包含1的數字有1、10、11、12，一共出現了5次。

思路1

依次周遊每個數，判斷每個數裡面是否包含1。

上代碼

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if(n == 0){
            return 0;
        }
        int countSum = 0;
        int count = 0;
        for(int i = 1;i <= n;i++){
            count = numberOf1(i);
            countSum += count;
        }
        return countSum;
    }
    public int numberOf1(int n){
        int count = 0;
        while(n>=1){
            if(n % 10 ==1){
                count ++;
            }
            n = n /10;
        }
        return count;
    }
}
           

這樣的話，就需要對每個數字都要做除法和求餘運算，以求出該數字中1出現的次數。如果輸入數字n，n有O(nlogn)位，就需要判斷每一位是不是1，時間複雜度為O(nlogn)。

思路2-分析數字規律

牛客網的讨論區裡有個很好也便于了解的思路：分析數字的規律來找到解法。

例如n=abcde五位數，我們分析百位的c，主要有以下三種情況：

1）當c == 0的時候，比如13013，此時百位出現1的是：00 100 ~ 00 199， 01 10001 199，……，11 100 11 199，1210012199共1300個，顯然這個由高位數字決定，并且受目前位數影響，結果為：（高位數字）乘以（目前位數）；

2）當c == 1的時候，比如13113，此時百位出現1的肯定包括c=0的情況，另外還需要考慮低位的情況即：00100 ~ 00113共114個，結果為：（高位數字）乘以（目前位數）+（低位數字）+1；

3）當c >= 2的時候，比如13213，此時百位出現1的是：00 100 ~ 00 199， 01 10001 199，……，11 100~ 11 199，12 100 ~ 12 199，13100~13199，共1400個，這個僅由高位數字決定，結果為：（高位數字+1）乘以目前位數。

上代碼

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        int cur = 0, before = 0, after = 0;
        for (int i = 1; i <= n; i *= 10) {
            before = n/(i*10);
            cur = (n/i)%10;
            after = n - n/i*i;
            if(cur == 0){
                // 如果為0,出現1的次數由高位決定,等于高位數字 * 目前位數
                res += before * i;
            }else if(cur == 1){
                // 如果為1, 出現1的次數由高位和低位決定,高位*目前位+低位+1
                res += before * i + after + 1;
            }else{
                // 如果大于1, 出現1的次數由高位決定,（高位數字+1）* 目前位數
                res += (before + 1) * i;
            }
        }
        return res;
    }
}
           

思路3-劍指

劍指offer中也提供了一種基于數字規律入手的解法，也很新穎和獨到，但是可能不是很容易想到，有興趣的讀者可以參考。

References

[1] 《劍指offer(第二版)》 何海濤著

程式員畫工師公衆号，擷取更多詳細Java、Python、C、前端、小程式、産品相關學習資料，歡迎交流