有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数

package org.shaoxinglay.algorithm;

import java.math.BigInteger;

/**
 * 问题：有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。 比如f(13)=6,现在f(1)=1,问此后最大的f(n)=n的n是什么？<br/>
 * 本类提供3种不同实现算f(n)的方法，理论上能处理趋于无穷大的整数，只要计算机内存足够大，而不限于Java的整型、长整型。
 *  
 */
public class Demo {

	/**
	 * 基于字符串实现的算f(n)，原理最通俗易懂，但同时效率较为低下。不宜处理大数。
	 * 
	 * @param n
	 *            自变量n的值
	 * @param target
	 *            目标数字（0 <= target < 10）
	 * @return f(n)的值
	 */
	public static int execByString(int n, int target) {
		checkTarget(target);
		int count = 0;
		char targ = (target + "").charAt(0);
		String s = null;
		for (int i = 0; i <= n; i++) {
			s = "" + i;
			for (int j = 0; j < s.length(); j++) {
				if (s.charAt(j) == targ) {
					count++;
				}
			}
		}
		return count;
	}

	/**
	 * 与使用字符串处理一样，使用迭代的方式进行处理，时间复杂度可认为是O(n·log<sub>10</sub>n)。<br />
	 * 欲求f(n)，必要先求f(n-1)，因此效率其实不高，处理大数也是力不从心啊。
	 * 
	 * @param n
	 *            自变量n的值
	 * @param target
	 *            目标数字（0 <= target < 10）
	 * @return f(n)的值
	 */
	public static long execByIterate(int n, int target) {
		checkTarget(target);
		long count;
		int num, temp;
		count = num = temp = 0;

		while (num <= n) {
			temp = num;
			while (temp != 0) {
				if (temp % 10 == target)
					count++;
				temp /= 10;
			}
			num++;
		}
		if (target == 0) {
			count++; // 把初始的0补上
		}
		return count;
	}

	/**
	 * 使用排列组合的方式进行处理，能把时间复杂度降到O(log<sub>10</sub>n)，因此，本方法处理Long.MAX_VALUE也毫无鸭梨！
	 * 
	 * @param n
	 *            自变量n的值
	 * @param target
	 *            目标数字（0 <= target < 10）
	 * @return BigInteger表示的f(n)
	 */
	public static BigInteger execByPermutation(long n, int target) {
		checkTarget(target);
		int[] nums = getArray(n);
		int len = nums.length;

		BigInteger count = new BigInteger("0");
		BigInteger powbase = new BigInteger("10");
		long left, right;
		for (int i = 0; i < len; i++) {
			right = (long) Math.pow(10, (len - i - 1));
			if (target != 0) {
				left = (long) (n / Math.pow(10, len - i));
				if (nums[i] > (target - 1)) {
					left++;
				}
			} else {
				left = (long) (n / Math.pow(10, len - i));
				if (left > 0) {
					left = left - (long) Math.pow(10, i - 1) + 1;
				}
			}

			count = count.add(BigInteger.valueOf(right * left));
			if (nums[i] == target) {
				long temp = (long) Math.pow(10, (len - i - 1));
				long sub = temp - ((long) (n % temp)) - 1;
				count = count.subtract(BigInteger.valueOf(sub));
			}
		}

		if (target == 0) {
			count = zeroCompensate(len, count, powbase);
		}
		return count;
	}

	/**
	 * 使用排列组合的方式进行处理，能把时间复杂度降到O(log<sub>10</sub>n)，因此，本方法处理再大的数也无鸭梨！
	 * 
	 * @param n
	 *            String类型，一个整数的字符串表示，例如：5236521452145 表示为"5236521452145" <br>
	 *            注意：只能是十进制的表示法
	 * @param target
	 *            目标数字（0 <= target < 10）
	 * @return BigInteger表示的f(n)
	 */
	public static BigInteger execByPermutation(String n, int target) {
		checkTarget(target);
		BigInteger src = new BigInteger(n);

		String nstr = src.toString();
		int[] nums = new int[nstr.length()];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = Integer.parseInt(nstr.charAt(i) + "");
		}
		int len = nums.length;

		BigInteger count = BigInteger.ZERO;
		BigInteger powbase = BigInteger.TEN;
		BigInteger left = BigInteger.ZERO;
		BigInteger right = BigInteger.ZERO;

		for (int i = 0; i < len; i++) {
			right = powbase.pow(len - i - 1);
			if (target != 0) {
				left = src.divide(powbase.pow(len - i));
				if (nums[i] > (target - 1)) {
					left = left.add(BigInteger.ONE);
				}
			} else {
				left = src.divide(powbase.pow(len - i));
				if (i > 0) {
					left = left.subtract(powbase.pow(i - 1))
							.add(BigInteger.ONE);
				}
			}

			count = count.add(right.multiply(left));
			if (nums[i] == target) {
				BigInteger temp = powbase.pow(len - i - 1);
				BigInteger sub = temp.subtract(src.mod(temp)).subtract(
						BigInteger.ONE);
				count = count.subtract(sub);
			}
		}

		if (target == 0) {
			count = zeroCompensate(len, count, powbase);
		}
		return count;
	}

	private static BigInteger zeroCompensate(int len, BigInteger count,
			BigInteger powbase) {
		int bl = len - 2;
		if (bl < 1) {
			count = count.add(BigInteger.valueOf(1));
		} else if (bl == 1) {
			count = count.add(BigInteger.valueOf(10));
		} else {
			BigInteger bigI = BigInteger.valueOf(0);
			for (int i = 1; i < bl; i++) {
				bigI = bigI.add(powbase.pow(i));
			}
			BigInteger bc = BigInteger.valueOf(bl).multiply(powbase.pow(bl))
					.subtract(bigI);
			count = count.add(bc);
		}
		return count;
	}

	/**
	 * 如果目标数字没在0-9中抛出非法参数异常
	 * 
	 * @param target
	 *            目标数字
	 * @throws IllegalArgumentException
	 */
	private static void checkTarget(int target) throws IllegalArgumentException {
		if (target < 0 || target > 9) {
			throw new IllegalArgumentException("目标数字" + target + "不在0 - 9中");
		}
	}

	private final static long[] sizeTable = { 9, 99, 999, 9999, 99999, 999999,
			9999999, 99999999, 999999999, 9999999999L, 99999999999L,
			999999999999L, 9999999999999L, 99999999999999L, 999999999999999L,
			9999999999999999L, 99999999999999999L, 999999999999999999L,
			Long.MAX_VALUE };

	private static int sizeOfLong(long x) {
		for (int i = 0;; i++)
			if (x <= sizeTable[i])
				return i + 1;
	}

	private static int[] getArray(long n) {
		int len = sizeOfLong(n);
		int[] result = new int[len];
		int i = len - 1;
		while (i >= 0) {
			result[i--] = (int) (n % 10);
			n = n / 10;
		}
		return result;
	}

}

    对于f(n)=n，最大的n值是多少，可证明n是确定的，原理是当n大于某一数值时，f(n)恒大于n。