• <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 
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2025年7月>
            
	
            日一二三四五六
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789
            

            

					

            導航
            

					

            統計
            
	
					

            公告
            
	
            統計系統
            

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



精品人妻伦九区久久AAA片69
|
超级97碰碰碰碰久久久久最新|
一本久久久久久久|
久久精品无码一区二区日韩AV|
97视频久久久|
久久最新精品国产|
久久99精品久久久大学生|
国产91色综合久久免费分享|
久久综合一区二区无码|
久久精品麻豆日日躁夜夜躁|
久久精品成人|
69久久夜色精品国产69|
香蕉aa三级久久毛片|
99精品久久精品|
国产A三级久久精品|
韩国三级中文字幕hd久久精品|
一本一本久久a久久综合精品蜜桃|
亚洲国产精品久久久久久|
日产精品久久久久久久性色|
久久久精品无码专区不卡|
99999久久久久久亚洲|
日本强好片久久久久久AAA
|
色综合久久88色综合天天|
奇米影视7777久久精品人人爽|
国产精品久久久天天影视香蕉
|
97精品国产91久久久久久|
亚洲精品美女久久777777|
怡红院日本一道日本久久|
热re99久久6国产精品免费|
伊人久久大香线蕉精品不卡
|
一本久久综合亚洲鲁鲁五月天|
大香网伊人久久综合网2020|
97久久久久人妻精品专区|
亚洲AV日韩精品久久久久久久|
色狠狠久久综合网|
久久精品极品盛宴观看|
人妻无码αv中文字幕久久琪琪布|
久久亚洲精品国产亚洲老地址|
欧美日韩精品久久久免费观看|
亚洲国产日韩欧美久久|
国产精品久久久久久久人人看|