劍指offer之面試題43：1~n整數中1出現的次數

面試題43：1~n整數中1出現的次數

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

思路1：暴力解法，累加1-n中每個整數中1出現的次數。

代碼實作：

package Question43;

public class T01 {
    public static void main(String[] args) {
        int n = 12;
        System.out.println(solve(n));
    }

    public static int solve(int n) {
        int count = 0;
        for(int i = 1; i <= n; i++) {
            int temp = i;
            while(temp > 0) {
                if(temp % 10 == 1) count++;
                temp /= 10;
            }
        }
        return count;
    }
}
           

思路2：數位統計

• 以12345為例，假設要統計千位上的1的出現次數，即_ _x _ _
• 若前兩位為 0-11，後兩位可以為0-99，是以出現次數為 12*100。
• 若前兩位為 12，則後兩位隻能為 0-45，是以出現次數為 46
• 是以千位上能出現 1 的次數是1246。
• 将所有位進行上述的計算即可。
• 實際的情況更為複雜，以代碼為主！！

代碼實作：

package Question43;

public class T02 {
    public static void main(String[] args) {
        int n  = 999;
        System.out.println(solve(n));
    }

    public static int solve(int n) {
        if(n >= 0 && n <= 9) return n >= 1 ? 1 : 0;
        int count = 0;
        String num = String.valueOf(n);
        for(int i = 0; i < num.length(); i++) {
            if(i == 0) {
                String temp = num.substring(1);
                count += num.charAt(0) > '1' ? (int)Math.pow(10, temp.length()) : Integer.parseInt(temp) + 1;
            } else if(i == num.length() - 1) {
                String temp = num.substring(0, i);
                count += num.charAt(i) >= '1' ? Integer.parseInt(temp) + 1 : Integer.parseInt(temp);
            } else {
                int lval = Integer.parseInt(num.substring(0, i));
                int rval = Integer.parseInt(num.substring(i+1));
                count += lval * (int)Math.pow(10, num.substring(i+1).length());
                if(num.charAt(i) > '1') count += (int)Math.pow(10, num.substring(i+1).length());
                else count += num.charAt(i) == '1' ? rval + 1 : 0;
            }
        }
        return count;
    }
}