UVa 12333 – Revenge of Fibonacci [大数+字典树]

题目：给你一个数字串，判断他是哪一个Fib数的前缀，有多种答案输出最小的，不存在输出-1。

解题思路：首先题目要求在100000个Fibonacci数之内，说明数字非常大，我们要用大数的方法存储，也就是用char[]来存储每个位上的数字

还有一个关键点是查找，我们使用字典树来解决，这样才可能不超时。字典树的意思就是使用每个节点来存储0-9,节点下面又有子节点，同样存储0-9一直下去例如

-1 -》0 -》0

??? -》1 -》0

??? -》2

??? -》。

??? -》。

??? -》。

??? -》6

??? -》7

??? -》8

上面简单的树中，10这个数字，就是通过两个节点1,0构成

接下来有几个问题，一个数解决大数相加，例如{8,2,8,1}和{2,4,6}相加，因为他们是用字符数组存储的，他们分别表示数字1828,642(反过来的，这样方便我们相加)

我们先将他们每位分别相加，得到{10,6,14,1}

在逐个处理进位，从10开始，大于9，进位，后一位加一，然后再处理后一位

最后就会变成{0,7,2}得出相加结果，再反过来，得到2470

另外一个问题是节点的存储

对于2470,我们从根节点开始查找，没有2这个节点，就新增，以此类推

另外java会OOM。。。

package test;

import java.util.Arrays;
import java.util.Scanner;

public class Test{	
	static class Node{//节点，构成字典树
	    int id;
	    Node next[] = new Node[10];//每个节点下面有10个节点，分别存储0-9
	    Node(){
	        id = -1;
	        for(int i = 0; i < 10; ++i)//初始化子节点
	            next[i] = null;
	    }
	};
	static char Fib[] = new char[50];//Fib用字符数组来存储大数据，例如{1,3,4}来不是1234
	static int F[][] = new int[2][1024000];//Fibonacci数列，存储每次运算的前两个数（也就是构成下一个数的两个加数）
	static Node root = new Node();//根节点
	
	static void add_node(char[] str,int id){//添加新节点
	    Node u = root;
	    int len = 0;
	    for(;len<str.length;len++){//找到大数据的有效长度
	    	if(str[len]==''){
	    		break;
	    	}
	    }
	    
	    for(int i = 0; i < len && i <= 40; ++i){//逐个存储
	        int v = str[i] - '0';//字符减去'0',计算出对应int值
	        
	        if(u.next[v]==null)
	            u.next[v] = new Node();
	        u =  u.next[v];
	        if(u.id == -1)
	            u.id = id;
	    }
	}
	
	static int query(char[] str){//查找		
	    Node u = root;	   
	    for(int i = 0,len=str.length; i < len; ++i){
	        u = u.next[str[i]-'0'];
	        if(u==null) return -1;
	    }
	    return u.id;
	}
	
	public static void main(String[] args) {
		
		F[0][0] = F[1][0] = 1;//初始化前两个数
	    int s = 0,e = 1;//s表示字符数组的起始位置，e表示字符数组的结束位置
	    add_node(new char[]{'1'},0);//添加前两个节点
	    add_node(new char[]{'1'},1);
	    
	    for(int i = 2; i < 100000; ++i){//生成100000个Fibonacci数，并且存储
	        int p = i%2,q = (i+1)%2;//利用余数性质
	        
	        for(int j = s; j < e; ++j)
	            F[p][j] = F[p][j] + F[q][j];//将前两个数每一位都相加
	        /*
	         * 判断每一位相加后是否大于10，如果是，说明要进位；注意，这里是反向存储数字的
	         * 也就是说，{4,1}，表示的是1234
	         */
	        for(int j = s; j < e; ++j)
	            if(F[p][j]>=10){
	                 F[p][j] %= 10;
	                 F[p][j+1] += 1;
	            }
	        
	        if(F[p][e]!=0)  ++e;
	        if(e - s > 50)  ++s;
	        
	        int r = e - 1,cnt = 0;
	        Arrays.fill(Fib,'');//清空fib数组	  
	        //反向存储，就是吧{4,1}变成{1,4}存储起来
	        while(r >= 0 && cnt<45)
	            Fib[cnt++] = (char) (F[p][r--] + '0');
	        
	        add_node(Fib,i);//添加节点
	    }
	   Scanner scanner = new Scanner(System.in);
	   String line;
	   while(!"".equals((line=scanner.nextLine()))){	        
	       System.out.println(query(line.toCharArray()));
	    }
	}
}