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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2011年1月>
            
	
            日一二三四五六
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345
            

            

					

            導航
            

					

            統計
            
	
					

            公告
            
	
            統計系統
            

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



国产成年无码久久久久毛片|
国产成人无码精品久久久免费|
亚洲国产天堂久久综合|
久久一区二区三区免费|
亚洲伊人久久综合影院|
国内高清久久久久久|
亚洲国产精品久久久久婷婷老年|
久久午夜福利电影|
久久久精品人妻一区二区三区蜜桃
|
久久er国产精品免费观看2|
日韩一区二区久久久久久|
精品多毛少妇人妻AV免费久久|
亚洲人成无码网站久久99热国产
|
中文字幕亚洲综合久久|
欧美亚洲日本久久精品|
精品久久777|
狠狠综合久久综合88亚洲
|
伊人色综合久久天天人守人婷|
久久99久久99精品免视看动漫|
久久久久免费精品国产|
亚洲乱码精品久久久久..|
久久久久女教师免费一区|
久久电影网2021|
亚洲AV无码1区2区久久|
亚洲精品国精品久久99热|
久久www免费人成精品香蕉|
国产精品久久久久久|
人妻精品久久久久中文字幕一冢本|
久久影院亚洲一区|
欧美久久亚洲精品|
久久精品成人欧美大片|
久久av高潮av无码av喷吹|
久久免费美女视频|
麻豆精品久久精品色综合|
久久夜色精品国产亚洲|
久久99精品国产一区二区三区|
久久国产亚洲精品无码|
久久水蜜桃亚洲av无码精品麻豆|
亚洲国产另类久久久精品黑人|
热re99久久精品国99热|
久久久国产精品亚洲一区|