• <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)典入門題
		
            
		題意：
            給出一堆電話號(hào)碼，判斷是否存在某個(gè)號(hào)碼是另一個(gè)號(hào)碼的前綴

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

            代碼：
            

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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年12月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計(jì)
            
	
					

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

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評(píng)論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



无码国内精品久久人妻|
久久久久亚洲av无码专区导航|
思思久久99热免费精品6|
久久精品国产色蜜蜜麻豆|
久久精品视频网|
亚洲第一永久AV网站久久精品男人的天堂AV
|
免费国产99久久久香蕉|
久久本道综合久久伊人|
无码日韩人妻精品久久蜜桃|
久久狠狠一本精品综合网|
亚洲午夜久久久久久久久久
|
无码人妻少妇久久中文字幕|
亚洲∧v久久久无码精品|
久久精品国产黑森林|
亚洲国产精品无码久久一线|
久久综合视频网站|
一本大道久久a久久精品综合|
精品久久久久久国产|
品成人欧美大片久久国产欧美|
一本色综合网久久|
亚洲国产精品成人AV无码久久综合影院
|
999久久久国产精品|
精品蜜臀久久久久99网站|
亚洲日韩欧美一区久久久久我|
99久久婷婷国产一区二区|
久久精品亚洲日本波多野结衣|
一本色道久久综合狠狠躁|
国产精品久久久天天影视香蕉|
国内精品久久久久久野外|
日产精品久久久一区二区|
怡红院日本一道日本久久|
91精品国产乱码久久久久久|
五月丁香综合激情六月久久|
久久久久亚洲AV片无码下载蜜桃|
一本久久综合亚洲鲁鲁五月天|
99久久精品免费观看国产|
国产精品久久久天天影视|
精品少妇人妻av无码久久|
精品999久久久久久中文字幕|
国产亚洲婷婷香蕉久久精品|
久久精品国产69国产精品亚洲|