香蕉久久一区二区不卡无毒影院,久久久SS麻豆欧美国产日韩,午夜天堂av天堂久久久

pku3630 Phone List 字典樹+判斷前綴經(jīng)典入門題

題意：
給出一堆電話號碼，判斷是否存在某個號碼是另一個號碼的前綴

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

代碼：

import java.io.*;
2

class 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

}
33

public class Main {
34

/**
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

}
58

}
60

}
62

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

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關文章: pku3908 并查集的一點小變通 pku 3943 Digits on the Floor 并查集的活用（重點）+數(shù)字識別 2010 天津賽區(qū)G hdu 3726 splay 2010 ICPC天津賽區(qū) J hdu 3727 劃分樹的理解 pku 3225 區(qū)間我對線段樹延遲標記的一些理解 pku1916 Rat Attack 動態(tài)統(tǒng)計之經(jīng)典好題 pku3168 Barn Expansion 排序+區(qū)間重疊判斷 pku1944 Fiber Communications 圖論好題！總體上的觀察，算法不難 pku1894-1903 Northeastern Europe 2003 解題報告 pku2902 Intercepting Missiles 線段樹+離散化+二分圖匹配，注意C++短路

網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku3630 Phone List 字典樹+判斷前綴經(jīng)典入門題

導航

統(tǒng)計

公告

留言簿(1)

隨筆分類(227)

文章分類(2)

OJ

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

pku3630 Phone List 字典樹+判斷前綴 經(jīng)典入門題

導航

統(tǒng)計

公告

留言簿(1)

隨筆分類(227)

文章分類(2)

OJ

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

pku3630 Phone List 字典樹+判斷前綴經(jīng)典入門題