• <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 字典樹+判斷前綴 經典入門題
		
            
		題意：
            給出一堆電話號碼，判斷是否存在某個號碼是另一個號碼的前綴

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

            代碼：
            

             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 閱讀(365) 評論(0)  編輯 收藏 引用  所屬分類: data struct 
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

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

            

					

            導航
            

					

            統計
            
	
					

            公告
            
	
            統計系統
            

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久丫精品国产亚洲av不卡|
久久91精品国产91|
久久99久久99精品免视看动漫|
久久久久99精品成人片牛牛影视
|
精品久久久久久国产牛牛app|
久久久久久亚洲AV无码专区
|
国产日产久久高清欧美一区|
国产精品gz久久久|
久久人人超碰精品CAOPOREN|
久久亚洲AV成人无码电影|
97热久久免费频精品99|
亚洲第一永久AV网站久久精品男人的天堂AV
|
中文字幕亚洲综合久久菠萝蜜|
国产精品中文久久久久久久|
久久人人爽人人爽人人片AV不|
久久国产亚洲精品|
欧美精品一区二区久久|
久久精品二区|
中文字幕无码av激情不卡久久|
久久久99精品成人片中文字幕
|
久久久久久久综合狠狠综合|
亚洲国产另类久久久精品
|
亚洲伊人久久成综合人影院|
伊人久久大香线蕉综合5g|
久久中文字幕视频、最近更新|
亚洲国产另类久久久精品黑人|
一本色综合网久久|
久久99毛片免费观看不卡|
久久婷婷色综合一区二区|
久久精品一区二区国产|
久久精品欧美日韩精品|
色偷偷偷久久伊人大杳蕉|
精品久久久久成人码免费动漫|
婷婷久久综合|
国产精品久久久久jk制服|
亚洲乱亚洲乱淫久久|
国产精品激情综合久久|
国产精品99久久久精品无码|
伊人久久亚洲综合影院|
久久青青草原综合伊人|
久久无码人妻精品一区二区三区|