Trie树提供给了一种能够在字符串的长度n时间内判断出来是否在已有集合中已经存在这个字符串了。POJ 1056是判断前缀码的问题。如果所有字符串都不是其他的字符串的前缀的话,那么就是可以直接编码的。
POJ 1056题目大意:
给你几个二进制代码,如果有其中一个代码是另一个的前缀,输出is not immediately decodable,反之,输出immediately decodable。
样例:
Sample Input
01
10
0010
0000
9
01
10
010
0000
9
Sample Output
Set 1 is immediately decodable
Set 2 is not immediately decodable
import java.util.Scanner;
class Trie{
class Node{//字典树节点
Node nxt[]=new Node[10];//儿子节点
boolean end=false;//是否是一个二进制代码的最后一个节点
int count=0;//此节点上通过的字符(数字)个数
}
Node head=null;//字典树的根节点
void clear(){
head=new Node();
}
boolean insert(String str){//构造字典树
Node p=head;
for(int i=0;i< str.length();i++){
p.count++;
if(p.end) return false;//存在前缀
if(p.nxt[str.charAt(i)-'0']==null)
p.nxt[str.charAt(i)-'0']=new Node();
p=p.nxt[str.charAt(i)-'0'];
}
p.count++;
if(p.count>1) return false;//存在前缀
p.end=true;
return true;
}
}
public class Main {
public static void main(String[] args) {
Trie tree=new Trie();
Scanner in=new Scanner(System.in);
int count=0;
while(in.hasNext())
{
String s = in.next();
count++;
tree.clear();
int flag=0;
while (!s.equals("9")) {
if(!tree.insert(s)) flag++;
s = in.next();
}
if (flag!=0) {// 如果存在前缀,输出
System.out.println("Set "+count+" is not immediately decodable");
}
else {// 如果不存在前缀,输出
System.out.println("Set " +count+" is immediately decodable");
}
}
}
}
源码下载:
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1746750
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1745671
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1754177
NULL 博文链接:https://128kj.iteye.com/blog/1753387
NULL 博文链接:https://128kj.iteye.com/blog/1748635
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
NULL 博文链接:https://128kj.iteye.com/blog/1749213
供初学编程基本算法的人练习使用,在poj.grids.cn上
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告