CalculateNumberOfOnes

/*
回忆去年的一道Google笔试题(搜索算法的剪枝优化)
2007-04-07 01:21
这个题目的英文原题是:
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?
翻译过来大体是这样：
有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？

为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.


*/
import java.util.HashMap;
import java.util.Map;

/**
* @author Kevin
*/
public class CalculateNumberOfOnes {
//存储已经检查过的符合条件的f(n)
static Map treeNodeOKcache = new HashMap();
private int currentSize = 0;

//private int maxValue = Integer.MAX_VALUE;//2147483647
private int maxTestValue = 40000000;

public void getNextNum(int n){

n = n<=1?1:n ; /* * 说明当前没有计算过 */ if(0 == currentSize){ //f(1) = 1 currentSize = 1; treeNodeOKcache.put(String.valueOf(1),String.valueOf(1)); } /* * f(n+1) = f(n) + fs(n+1); * 计算本次fs(n+1)的结果 */ for(int i=2;i 0 ){
//模除10
int mod = n%10;
if ( mod == 1 )
count++;
n = n/10;
}
return count;
}

public static void main(String[] args){
CalculateNumberOfOnes instance = new CalculateNumberOfOnes();
long start = System.currentTimeMillis();
instance.getNextNum(0);
System.out.println("satisfy condition num is ="+treeNodeOKcache.size());
System.out.println(" total spent "+(System.currentTimeMillis()-start)+"ms used!");
}

}