有一个整数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;}}