java之從1到n整數中1出現的次數

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

解法1：

package BitCount;

import java.util.Scanner;

public class CountOneMain {
	public static int countOne(int n) {

		int num = 0;
		for (int i = 1; i <= n; i++)
			num += NumberOf1(i);
		return num;

	}

	public static int NumberOf1(int n) {
		int num = 0;
		while (n != 0) {
			if (n % 10 == 1)
				num++;
			n = n / 10;

		}

		return num;
	}

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		System.out.println(countOne(n));
	}

}
           

其時間複雜度為O(n*logn),這種情況面試官不會滿意還需要提高。

解法二：

package BitCount;

import java.util.Scanner;

public class CountOneMain1 {
   
	public static int num_of_bits(int n)
	{
	    int k = 0; //初始為0位
	    for(int m = n; m > 0; m /=10)
	        k ++;
	    return k;
	}
	//得到一個數n的第i位的數字。最低位為第0位
	static int number_of(int n, int i)
	{
	    int num = num_of_bits(n);
	    if(i < 0 || i > (num-1))
	        return 0;
	    return ((int)(n/Math.pow(10,num-i-1)));
	}
	//從0到n的所有整數中1數字出現的次數
	//實作方案1：直接利用數n每個位上的歸納算出1出現的個數
	public static int count_From_One_1( int n)
	{
	    //位數
	    int num = num_of_bits(n);
	    //跨度
	    int scale = (int)Math.pow(10, num-1);
	    //商
	    int quotient = 0;
	    //餘數
	    int remainder = 0;
	    //某一位的數的大小。
	    int bit = 0;//初始為0
	    int count = 0; //計數

	    for(int i = 0; i < num; i++)
	    {
	        count += quotient * scale;
	        bit = number_of(n,i);
	        if(bit > 1)
	            count += scale;
	        else if(bit == 1)
	        {
	            if(i == num-1)
	                remainder = 1;
	            else
	                remainder = n%scale + 1;
	            count += remainder;
	        }
	        quotient = (int)(n/scale);
	        scale /= 10;
	    }
	    return count;
	}

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		System.out.println(count_From_One_1(n));
	}

}