国产精品永久免费观看,99香蕉国产精品偷在线观看,在线精品国产欧美

江蘇大學(xué)

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

題意：
給出一堆電話號(hào)碼，判斷是否存在某個(gè)號(hào)碼是另一個(gè)號(hào)碼的前綴

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

代碼：

1

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

32

}
33

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

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


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

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