|
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-04-23
如果存在相同的月日就递增，最后找出递增值最大的！
|
| 返回顶楼 | |
|
发表时间：2008-04-23
Joo 写道 armorking 写道 对因为一般的文本中的单词来讲这个条件被满足的概率不大 你这个假设比较牵强阿呵呵 用事实说明 以下是改过的代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import org.apache.commons.collections.MultiHashMap;
public class AnagramUtil
{
/**
*
* @param String[]
* @return List＜Set＞
*/
public static List searchAnagramImproved(String[] strArray)
{
if (strArray == null
|| strArray.length == 0
){
return Collections.EMPTY_LIST;
}
MultiHashMap multiMap = new MultiHashMap();
for (int i = 0 ; i < strArray.length ; i++)
{
String word = strArray[i];
String key = convertWord4Trial(word);
multiMap.put(key, word);
}
List result = new ArrayList();
for (Iterator i = multiMap.keySet().iterator() ; i.hasNext(); )
{
String key = (String)i.next();
if ("".equals(key)
){
continue;
}
if (multiMap.size(key) < 2
){
continue;
}
Set valueSet = new HashSet(multiMap.getCollection(key));
if (valueSet.size() < 2
){
continue;
}
for (Iterator j = valueSet.iterator() ; j.hasNext() ; )
{
System.out.println(j.next());
}
System.out.println("---------------------------");
result.addAll(searchAllAnagram(valueSet));
}
return result;
}
private static String convertWord4Trial(String word)
{
if (word == null
|| word.length() == 0
){
return "";
}
int size = word.length();
int sum = 0;
for (int i = 0 ; i < size ; i++)
{
char c = word.charAt(i);
if (c < 'A'
|| (c > 'Z' && c < 'a')
|| c > 'z'
){
return "";
}
sum += (c < 'a') ? ((int)c + 32 ) : (int)c;
}
StringBuffer sb = new StringBuffer();
sb.append(String.valueOf(size)).append("-").append(String.valueOf(sum));
return String.valueOf(sb);
}
/**
*
* @param Set＜String＞
* @return List＜Set＞
*/
private static List searchAllAnagram(Set strSet)
{
if (strSet == null
|| strSet.size() == 0
){
return Collections.EMPTY_LIST;
}
MultiHashMap multiMap = new MultiHashMap();
for (Iterator i = strSet.iterator() ; i.hasNext() ; )
{
String word = (String)i.next();
String key = convertWord(word);
//这里有个bug,已修改
//multiMap.put(key, word);
multiMap.put(key, word.toLowerCase());
}
List result = new ArrayList();
for (Iterator i = multiMap.keySet().iterator() ; i.hasNext(); )
{
String key = (String)i.next();
if (multiMap.size(key) < 2
){
continue;
}
Set valueSet = new HashSet(multiMap.getCollection(key));
if (valueSet.size() < 2
){
continue;
}
result.add(valueSet);
}
return result;
}
private static String convertWord(String word)
{
if (word == null
){
return "";
}
char[] charArray = word.toLowerCase().toCharArray();
Arrays.sort(charArray);
return String.valueOf(charArray);
}
public static void main(String[] args)
{
String[] strArray = new String[]{
"Regular", "Expressions", "in", "Java", "Package", "com.stevesoft.pat",
"version", "1.5.3", "Blog", "Home", "Articles/Links", "Mugs,", "T-shirts",
"Comments/Raves", "New", "in", "1.5.3", "A", "Game", "An", "Online",
"Test", "Questions", "Copyright/License", "Download", "Free", "If", "you",
"need", "a", "non-LGPL", "version", "You", "Can", "Buy!", "Online",
"help...", "Quick", "Start", "Tutorial", "Part", "1", "Tutorial", "Part",
"2", "Tutorial", "Part", "3", "Tutorial", "Part", "4", "Tutorial", "Part",
"5", "Tutorial", "Part", "6", "Examples", "Support", "FAQ", "Documentation",
"Useful", "apps...", "Java", "Beautifier", "Code", "Colorizer", "GUI",
"Grep", "Swing", "Grep", "Other", "stuff...", "Phreida", "xmlser",
"Welcome", "Regular", "XML", "Expressions:", "Would", "a", "new",
"form", "of", "regular", "expression", "make", "searches", "of",
"xml", "and", "html", "easier?", "Please", "let", "me", "know",
"your", "opinion.", "Note:", "Many", "people", "have", "enjoyed",
"the", "tutorial", "I", "made", "for", "my", "package,", "and",
"I've", "received", "a", "few", "requests", "for", "an", "adaptation",
"to", "Sun's", "java.util.regex", "package.", "I'm", "happy", "to",
"report", "the", "tutorial", "is", "available", "as", "a", "freely",
"downloadable", "pdf.", "You", "can", "also", "buy", "a", "print",
"on", "demand", "version", "for", "which", "I", "will", "receive",
"$1.", "Regex", "Recipes", "V", "1.0", "The", "Regex", "Game",
"Print", "on", "Demand", "Book", "Note:", "Quick", "&", "dirty",
"xml", "tip", "on", "JavaWorld.", "This", "code", "is", "currently",
"in", "use", "in", "cell", "phones", "and", "streaming", "stock",
"quote", "programs.", "What", "can", "you", "do", "with", "it?",
"Note:", "Ever", "wanted", "a", "package", "pat", "mug?", "You",
"can", "now", "buy", "one", "at", "our", "Cafe", "Shop.", "But",
"that's", "not", "all", "you", "can", "get,", "there's", "some",
"science", "fiction", "theme", "t-shirts,", "and", "mouse", "pads.",
"Package", "pat", "provides", "a", "mechanism", "for", "compiling",
"and", "matching", "regular", "expressions", "in", "java.", "It",
"has", "numerous", "features:", "Online", "since", "May", "of",
"1996:", "Many", "Java", "software", "companies", "and", "packages",
"have", "come", "and", "gone", "since", "Java", "was", "invented.",
"Package", "pat", "has", "demonstrated", "persistence.", "Y2K:",
"Since", "package", "pat", "uses", "no", "internal", "representation",
"of", "dates", "it", "never", "had", "a", "Y2K", "problem.", "Support",
"for", "all", "the", "pattern", "matching", "capabilities", "of",
"Perl", "5.", "Polymorphism:", "Package", "pat", "can", "match", "on",
"a", "String,", "an", "array", "of", "characters,", "or", "a",
"RandomAccessFile.", "Support", "for", "unicode:", "Matches", "that",
"ignore", "case", "take", "into", "account", "all", "three", "cases",
"of", "unicode.", "Special", "patterns", "are", "supplied", "to",
"match", "characters", "with", "certain", "unicode", "properties",
"(read", "more).", "Support", "for", "reverse", "searching", "within",
"a", "String.", "Documentation:", "Whether", "you", "want", "javadoc",
"comments,", "a", "tutorial,", "or", "examples", "of", "use",
"it's", "all", "available", "at", "left.", "Package", "pat", "was",
"used", "to", "construct", "a", "Java", "Beautifier", "for", "use",
"in", "Borland's", "JBuilder.", "It", "will", "format", "and",
"properly", "indent", "source", "files.", "Version", "1.0", "is",
"free", "if", "you", "have", "a", "license", "for", "com.stevesoft.pat.",
"Speed:", "If", "the", "optimize()", "method", "is", "called", "package",
"pat", "uses", "a", "Boyer-Moore", "Horspool", "search", "(if", "the",
"pattern", "begins", "with", "a", "literal", "text", "string).",
"Just", "Java:", "No", "native", "code", "is", "employed", "by",
"package", "pat.", "Java", "1.0", "support:", "If", "you", "need",
"to", "restrict", "yourself", "to", "using", "java", "1.0", "you",
"can", "still", "use", "pat."
};
List result = searchAnagramImproved(strArray);
for (int i = 0 ; i < result.size() ; i++)
{
System.out.println("=========Anagram " + i + " : =========");
Set anagram = (Set)result.get(i);
for (Iterator j = anagram.iterator() ; j.hasNext() ; )
{
System.out.println(j.next());
}
}
}
}
我随便找个页面的内容作为测试文本对象: http://www.javaregex.com/ 第一次粗选结果是 regular Regular --------------------------- one few --------------------------- let GUI pat --------------------------- Online people --------------------------- you You --------------------------- New new --------------------------- No no it It on --------------------------- An an if If --------------------------- the The --------------------------- Since since --------------------------- of at --------------------------- fiction Welcome --------------------------- quote Start --------------------------- tip use --------------------------- freely native --------------------------- theme which --------------------------- that used --------------------------- demand Demand --------------------------- Package package --------------------------- --------------------------- not XML xml --------------------------- This will --------------------------- Home gone --------------------------- But was --------------------------- a A --------------------------- May for --------------------------- license receive --------------------------- some form What --------------------------- come Blog have --------------------------- Can can --------------------------- java free Java Free --------------------------- are FAQ --------------------------- account literal --------------------------- case need --------------------------- tutorial Tutorial --------------------------- examples Examples employed --------------------------- Version version --------------------------- html Many --------------------------- uses Test --------------------------- expressions Expressions --------------------------- into want --------------------------- code Code --------------------------- characters Beautifier --------------------------- happy Other --------------------------- still Swing --------------------------- 最终结果是 =========Anagram 0 : ========= no on |
| 返回顶楼 | |
|
发表时间：2008-04-23
生日题：
读文件就省了吧！直接用ruby测试了一下！
birthdays,bs = {},%w{0212 0213 0212 0115 0815 0212 0212 0212 0413 0528}
bs.each do |md|
unless birthdays["#{md}"].nil?
birthdays["#{md}"] += 1
else
birthdays["#{md}"] = 1
end
end
birthdays.each do |birthday|
puts "#{birthday[0]/#{birthday[1]}"
end
|
| 返回顶楼 | |
|
发表时间：2008-04-23
nmvr2600 写道 第一个题和论坛ruby版里那个“容易记的电话号码”有些类似
第二个，就是统计生日最多的哪一天，但是生日里面的年可以直接忽略掉，需要的就只有月日。月和日不要一起统计，先算月。先把生日最多的那个月份找到，再去统去到底是哪一天。呵呵，这样最后需要计算个数的人就少了很多了吧。直接去算每天出现的人数还是有点笨。如果数据量再多的话，可以借用下数理统计的知识。 第三个，使用正则表达式\b(?i)[s|t|o|p]{4}\b，搞定~~ 你已经被筛掉了。 |
| 返回顶楼 | |
|
发表时间：2008-04-23
1， 典型的深度优先搜索实现。 2，定义长度为1231（12月31日）的数组，用来保存每一天多少人过生日；遍历文件，忽略文件中的人名和年份，每一行只取后四位，作为数组的index，对数组中的第index位加1。最后求数组的最大值下标。 时间复杂度：对文本进行了一次遍历，对数组进行了一次遍历。 空间：使用了长度为1231的整形数组，在java中大约需要5k的空间。 3，为了提高效率，必须设计一个方法 long calc(String word)，该方法保证位置不同但字母相同的单词能返回同样的值，而字母不同的单词肯定返回不同的值（题目中没有明确说明是否考虑字母重复的情况，比如as和ass，故此方法也不考虑）。 这个方法可以利用两个不同质数的乘积是唯一的这个数学特性来实现，让字母a-z对应从3开始的质数，然后取乘积。 这样，文章中的每一个单词都有了对应的计算值，计算值相同的单词要么是重复的，要么就是anagram（变位词）。 时间复杂度：对文章进行一次遍历。 空间：需要与单词个数等大的辅助空间。 |
| 返回顶楼 | |
|
发表时间：2008-04-23
Joo 写道 这个很不错.但问题是每个字母都要转换一边是否高效? 数字不会很大怎么会溢出的? 字符本来就是数字。如果你用java可以直接乘。 不过这种做法有两个问题，一个是溢出，一个是相同字母的处理（当然原题似乎没有说如何考虑相同的字母）。 |
| 返回顶楼 | |
|
发表时间：2008-04-23
第2题解:
先读文件. 然后定义一个Map, key为生日的后4位数字. value初始为1 循环. 将所有的信息以这中形式放到 map里面. 如果存在key 则 value +1, 如果不存在则put. 完毕后 判断map 当中value值最大的一个. 便是当天的生日 |
| 返回顶楼 | |
|
发表时间：2008-04-23
GreenForest 写道 第2题
1、int birthday[12][31]。 2、将数组中所有元素初始化为0。 3、循环遍历所有人，如果当前人n月m日生日，则birthday[n-1][m-1]++。 4、找出数组中最大的值。 这才是正解！看看编程珠玑的前言吧 当然最好再加个int month int day 随时记录最多的日子，这样最后就不用再遍历了 |
| 返回顶楼 | |
|
发表时间：2008-04-23
第一题建立10×4的数组 10代表10个数字 4应该是一个数字能代表最多的字母数吧 大部分是3个就够 至少我的手机是这样，然后循环吧
|
| 返回顶楼 | |
|
发表时间：2008-04-23
第三题看下the art of java
|
| 返回顶楼 | |
