• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku3630 Phone List 字典樹+判斷前綴 經(jīng)典入門題
		
            
		題意：
            給出一堆電話號碼，判斷是否存在某個號碼是另一個號碼的前綴

            題解：
            還是通過字典樹，不過判斷的時候不能夠僅僅判斷當前待插入字符串的路徑上是否包含結束標記（如果事先對字符轉進行了按長短排序就沒問題了），而需要記錄每個節(jié)點包含的路徑條數(shù)，如果在待插入字符串的尾節(jié)點（即結束標記節(jié)點上通過的路徑數(shù)大于1，則說明有路徑覆蓋了這個節(jié)點，即有一個字符轉以當前字符串為前綴，故不可能）

            代碼：
            

             1import java.io.*;
             2class Dic_Tree
             3{
             4    class node
             5    {
             6        node nxt[]=new node[10];
             7        boolean end=false;
             8        int count=0;
             9    }
            10    node head=null;
            11    void clear()
            12    {
            13        head=new node();
            14    }
            15    boolean insert(String str)
            16    {
            17        node p=head;
            18        for(int i=0;i<str.length();i++)
            19        {
            20            p.count++;
            21            if(p.end) return false;
            22            if(p.nxt[str.charAt(i)-48]==null)
            23                p.nxt[str.charAt(i)-48]=new node();
            24            p=p.nxt[str.charAt(i)-48];
            25        }
            26        p.count++;
            27        if(p.count>1) return false;
            28        p.end=true;
            29        return true;
            30    }
            31    
            32}
            33public class Main {
            34
            35    /**
            36     * @param args
            37     */
            38    static Dic_Tree data=new Dic_Tree();
            39    public static void main(String[] args) throws IOException{
            40        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
            41        int test=Integer.parseInt(in.readLine());
            42        while((test--)!=0)
            43        {
            44            int num=Integer.parseInt(in.readLine());
            45            boolean flag=true;
            46            data.clear();
            47            while((num--)!=0)
            48              if(flag)
            49              {
            50                if(!data.insert(in.readLine())) flag=false;
            51              }
            52              else
            53                  in.readLine();
            54            if(flag) System.out.println("YES");
            55            else System.out.println("NO");
            56            
            57        }
            58
            59    }
            60
            61}
            62
            

		
            
			posted on 2011-01-12 00:11 yzhw 閱讀(371) 評論(0)  編輯 收藏 引用  所屬分類: data struct 
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年10月>
            
	
            日一二三四五六
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456
            

            

					

            導航
            

					

            統(tǒng)計
            
	
					

            公告
            
	
            統(tǒng)計系統(tǒng)
            

					

            留言簿(1)
            


		
            隨筆分類(227)
            
		
				
			
	
		
            文章分類(2)
            
		
				
			
	
		
            OJ
            
		
				
			
	


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久99精品九九九久久婷婷|
久久久久免费视频|
久久亚洲AV成人无码软件|
狠狠色丁香久久婷婷综合图片
|
国产69精品久久久久观看软件|
婷婷久久综合九色综合98|
亚洲&#228;v永久无码精品天堂久久|
99久久国产主播综合精品|
欧美一级久久久久久久大片
|
少妇熟女久久综合网色欲|
久久久精品国产免大香伊|
久久综合狠狠综合久久综合88|
久久香蕉国产线看观看乱码|
国产免费久久精品丫丫|
一本久久a久久精品综合香蕉|
久久久久亚洲国产|
久久国产精品无码网站|
久久亚洲精品人成综合网|
久久久久亚洲av毛片大|
国产精品一区二区久久|
亚洲国产综合久久天堂|
蜜桃麻豆www久久|
久久国产热精品波多野结衣AV|
伊人久久大香线蕉AV一区二区
|
99久久国产综合精品网成人影院|
一级A毛片免费观看久久精品|
国产精品成人精品久久久
|
国产精品岛国久久久久|
精品国产日韩久久亚洲|
久久人人爽人爽人人爽av|
欧美久久综合性欧美|
久久精品国产精品亚洲毛片|
精品久久久无码人妻中文字幕|
欧美性大战久久久久久|
久久亚洲中文字幕精品一区四|
9999国产精品欧美久久久久久|
蜜臀久久99精品久久久久久小说|
97精品国产97久久久久久免费
|
久久这里只精品国产99热|
亚洲精品高清国产一线久久|
精品综合久久久久久97|