Cracking the coding interview--Q20.4

题目

原文：

Write a method to count the number of 2s between 0 and n.

译文：

写一个方法计算0到n的数出现的2的个数。

解答

ctci解法:

观察下面数列：

   0     1    2     3     4   5     6     7     8    9
 10   11   12   13   14  15   16   17   18   19
 20   21   22   23   24  25   26   27   28   29
...
110 111 112 113 114 115 116 117 118  119

最后位数字将会每10个数字重复一次，最后两位数字每10^2个数字重复一次，最后三位数字每10^3个数字重复一次，……

所以，如果在0到99间有x个2，则我们知道在0到199间有2x个2,；在0到299间对于最后两位有3x个2，再加上对于第一位的100个2

换句话说，我们可以分析一个数像这样：

f(513)=5*f(99)+f(13)+100

具体分析如下：

1)最后两位数重复5次，所以加5*f(99)

2)再计算500到513的最后两位，所以加上f(13)

3)最后计算200到299的第一位，所以加上100

当然，如果n特殊的，比如279，我们的计算就稍微有点不同：

f(279)=2*f(99)+f(79)+79+1

具体分析：

1)最后两位数重复2次，所以加2*f(99)

2)200到279的最后两位，所以加上f(79)

3)最后计算200到279的第一位，所以加上79+1

递归方法：

	public static int count2sR(int n){
		if(n==0) return 0;
		int power=1;
		while(10*power<n)
			power*=10;
		int first=n/power;
		int remainder=n%power;

		//counts 2s from first digit
		int nTwosFirst=0;
		if(first>2) 
			nTwosFirst+=power;
		else if(first==2)
			nTwosFirst+=remainder+1;

		//count 2s from all other digits
		int nTwosOther=first*count2sR(power-1)+count2sR(remainder);

		return nTwosFirst+nTwosOther;
	}

用算法迭代：

public static int count2sI(int num){
		int countof2s=0,digit=0;
		int j=num,seendigits=0,position=0,pow10_pos=1;

		while(j>0){
			digit=j%10;
			int pow10_posMinus1=pow10_pos/10;
			countof2s+=digit*position*pow10_posMinus1;

			if(digit==2){
				countof2s+=pow10_pos;
			}
			seendigits=seendigits+pow10_pos*digit;
			pow10_pos*=10;
			position++;
			j=j/10;
		}
		return countof2s;
	}

完整代码：

class Q20_4{
	public static void main(String[] args){
		System.out.println(count2sR(279));
		System.out.println(count2sI(2540));
	}

	public static int count2sR(int n){
		if(n==0) return 0;
		int power=1;
		while(10*power<n)
			power*=10;
		int first=n/power;
		int remainder=n%power;

		//counts 2s from first digit
		int nTwosFirst=0;
		if(first>2) 
			nTwosFirst+=power;
		else if(first==2)
			nTwosFirst+=remainder+1;

		//count 2s from all other digits
		int nTwosOther=first*count2sR(power-1)+count2sR(remainder);

		return nTwosFirst+nTwosOther;
	}

	public static int count2sI(int num){
		int countof2s=0,digit=0;
		int j=num,seendigits=0,position=0,pow10_pos=1;

		while(j>0){
			digit=j%10;
			int pow10_posMinus1=pow10_pos/10;
			countof2s+=digit*position*pow10_posMinus1;

			if(digit==2){
				countof2s+=pow10_pos;
			}
			seendigits=seendigits+pow10_pos*digit;
			pow10_pos*=10;
			position++;
			j=j/10;
		}
		return countof2s;
	}
}

---EOF---

Cracking the coding interview--Q20.4,布布扣,bubuko.com

Cracking the coding interview--Q20.4

原文：http://blog.csdn.net/navyifanr/article/details/24286193