国产最新精品精品你懂的,国产一区在线观看视频,欧美大片免费观看

江蘇大學

pku3630 Phone List 字典樹+判斷前綴經典入門題

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

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

代碼：

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

只有注冊用戶登錄后才能發表評論。


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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理