1的数目

来源：编程之美2.4

题目：给定一个十进制正整数N,写下从1开始，到N的所有整数，然后 数一下其中出现的所有'1'的个数。

       1.写一个函数f(N)，返回1到N之间出现的‘1’的个数，比如f(12)=5;

       2.求满足‘f(N)=N'的最大的N是多少

这个题比较难，需要好好的找规律

public class NumbersOfOne2_4 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		System.out.println(f(12));
		System.out.println(Sum1s(999999999));
	}

	//解法一
	public static int f(int n){
		int count=0;
		for(int i=1;i<=n;i++)count+=countOfOne(i);
		return count;
	}

	private static int countOfOne(int i) {
		int nums=0;
		while(i!=0){
			if(i%10==1)nums++;
			i/=10;
		}
		return nums;
	}
	
	//解法2，很难想，得不断试验找规律
	//当前位1的个数不仅和当前位的数值有关还各高位及低位有关
	public static long Sum1s(long n)

	{

	     long iCount=0;//出现1的总数
	     long iFactor=1;//乘法因子，1，10，100.。。可以获得其它位的数
	     long iLowerNum=0;//比当前位低的数据
	     long iCurrNum=0;//当前位的数
	     long iHigherNum=0;//比当前位高的数据
	     while(n/iFactor!=0)

	     {
	          iLowerNum=n-(n/iFactor)*iFactor;
	          iCurrNum=(n/iFactor)%10;
	          iHigherNum=n/(iFactor*10);
	          switch((int)iCurrNum)
	          {
	               case 0://当前位为0，1的个数等于高位数*10
	                    iCount+=iHigherNum*iFactor;
	                    break;
	               case 1://当前位为1，还要考虑低们为1的数
	                    iCount+=iHigherNum*iFactor+iLowerNum+1;
	                    break;
	               default://其它情况
	                    iCount+=(iHigherNum+1)*iFactor;
	                    break;
	          }
	          iFactor*=10;

	     }

	     return iCount;

	}
}