- 浏览: 584615 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
poj2503题意:
给出一个最多有100000对单词的英语和外语的字典,然后给你一个外语单词 要求你查字典翻译成英语,如果词典里查不到就输出eh。
样例:
Sample Input
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
Sample Output
cat
eh
loops
解法一:使用jdk中的Hashtable(或HashMap)
方法二:使用字典树
思路:用所有的外语单词去建一棵字典树,然后向这棵字典树中查找给出的单词
给出一个最多有100000对单词的英语和外语的字典,然后给你一个外语单词 要求你查字典翻译成英语,如果词典里查不到就输出eh。
样例:
Sample Input
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
Sample Output
cat
eh
loops
解法一:使用jdk中的Hashtable(或HashMap)
import java.util.Scanner; import java.util.Hashtable; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); Hashtable< String,String> table = new Hashtable< String, String>(); String input; String [] array=new String[2]; while(in.hasNext()){ input=in.nextLine(); if(input.length()==0)break; array=input.split(" "); table.put(array[1],array[0]); } while(in.hasNext()){ input=in.nextLine(); if(table.get(input)!=null) System.out.println(table.get(input)); else System.out.println("eh"); } } }
方法二:使用字典树
思路:用所有的外语单词去建一棵字典树,然后向这棵字典树中查找给出的单词
import java.util.Scanner; import java.text.DecimalFormat; class Trie{ //字典树 Trie next[] = new Trie[26];//所有儿子节点 String enWord;// 用于记录对应的英语单词 public Trie(){ enWord=null; } } public class Main{ Trie root = new Trie(); void solve() { Scanner in = new Scanner(System.in); String input; String [] array=new String[2]; while(in.hasNext()){//用所有外文字符串,构造字典树 input = in.nextLine(); if(input.length()==0) break; array=input.split(" "); insert(array[1],array[0]); } while(in.hasNext()){ input=in.nextLine(); System.out.println(search(input)); } } //建立字典树 public void insert(String str,String enWord) { //将一个外文字符串插入字典树 if (str == null || str.length() == 0) { return ; } Trie node = root; char[] letters=str.toCharArray(); for (int i = 0; i < str.length(); i++) { int pos = letters[i] - 'a'; if (node.next[pos] == null) { node.next[pos] = new Trie(); //node.son[pos].val = letters[i]; } node = node.next[pos]; } //外文字符串的最后一个节点,根节点到此节点构成了一个外文单词,此单词对应的英文单词为enWord; node.enWord = enWord; } // 在字典树中查找一个完全匹配的外文单词,返回其对应的英文单词. public String search(String str) { if (str == null || str.length() == 0) { return null; } Trie node = root; char[] letters=str.toCharArray(); for (int i = 0, len = str.length(); i < len; i++) { int pos = letters[i] - 'a'; if (node.next[pos] != null) { node = node.next[pos]; } else { return "eh"; } } return node.enWord; } public static void main(String[] args) { Main test = new Main(); test.solve(); } }
- main2503.zip (1.3 KB)
- 下载次数: 7
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3664题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1528POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2983POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1432POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1855题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1595关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1824关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1809POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1831POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1726POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1566分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2177接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1502关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1356接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1769关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1677关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1753关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2024POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
线段树练习POJ 3264
2012-12-03 21:16 1286问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分 ... -
在POJ中使用StreamTokenizer从命令行获取输入
2012-12-03 12:21 2105在http://poj.org/上用JAVA解题一般用 ...
相关推荐
实现了链表法(Chaining)和开放地址寻址(Open Addressing)中的Hash表实现,开放地址寻址采用双重散列解决冲突
java Hashtable的泛型化 java Hashtable的泛型化 java Hashtable的泛型化
C#之Json字符串转换Hashtable,DataTable,DataSet方法和反转换方法.
经典讲解List和ArrayList和Vector和HashTable和HashMap区别
Java集合专题总结:HashMap 和 HashTable 源码学习和面试总结
记得刚毕业那会准备面试,看过不少面试题,里面有个说出HashMap和HashTable不同的题目,我那会面试的时候也遇到不少次这个问题,还隐约记得当时的回答是这样的: HashTable是比较旧的版本;HashTable是线程安全的,...
HashMap和Hashtable的区别Java开发Java经验技巧共2页.pdf.zip
·课程中,Eclipse和IDEA这两种企业一线开发环境都使用到了 3.技术讲解更深入、更全面: ·课程共30天,715个知识视频小节,涉及主流Java使用的方方面面,全而不冗余 ·全程内容涵盖数据结构、设计模式、JVM内存...
Java课上老师留得小作业,关于Hashtable,Vector,interface,String的简单使用方法
hashMap和hashTable的区别,大家可以下载学习学习。
Hashtable是Java中的一种散列表实现,它可以存储键值对,并根据键的哈希值来快速查找和访问值。
于是,本人使用JavaScript的数组模拟Hashtable集合,说明JavaScript数组的特别之外。 环境:Windows XP Professional, IE 6.0 阅读对象:所有学习JavaScript的学员。 注:本示例代码注释非常详细,请仔细阅读体会...
HashTable源码
什么是HashSet? HashSet实现了Set接口,它不允许集合中有重复的值,当我们提到HashSet时,第一件事情就是在将对象存储在HashSet之前,要先确保对象重写...如果我们没有重写这两个方法,将会使用这个方法的默认实现。。
浅谈Java web中基于Hashtable的数据库操作
Hashtable和HashMap的区别: 1.Hashtable是Dictionary的子类,HashMap是Map接口的一个实现类; 2.Hashtable中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。即是说,在多线程应用程序中,不用专门的...
哈希表 哈希表_使用Java开发的哈希表_HashTable
HashTable不支持空键值对! 而HashMap支持空键值对!
WinFormHashTable最简单用法,.net hashtable ,hashtable ,hashtable用法