先放題目地址：http://poj.org/problem?id=1002
- 題目思路：每行讀入之后傻丝，根據(jù)某種方式將其全部轉(zhuǎn)化為數(shù)字命贴，以“xxx-xxxx”的格式存儲(chǔ)入表攘烛，經(jīng)過(guò)判斷后让禀，以 key+value 的形式輸出，如果沒(méi)有重復(fù)就單獨(dú)考慮庙洼。
這個(gè)思路其實(shí)很簡(jiǎn)單顿痪。。（我當(dāng)時(shí)甚至還好奇為啥Ac率這么低）所以我很快就寫(xiě)出了第一版的代碼：用replace()處理輸入數(shù)據(jù)油够，存入hashMap蚁袭，經(jīng)過(guò)排序后輸出
第一次提交的時(shí)候報(bào)的是WA，因?yàn)轭}目中的No duplicates.我忘記寫(xiě)進(jìn)去了（審題的時(shí)候有注意到石咬，真正寫(xiě)的時(shí)候卻忘記了揩悄，以后要多加注意）
修改后，第二次提交竟然給我報(bào)了Time Limit Exceeded鬼悠，菜雞做題少删性，第一次見(jiàn)這樣報(bào)錯(cuò)亏娜，有點(diǎn)沮喪，請(qǐng)老爸幫看了一下蹬挺，經(jīng)驗(yàn)豐富的他覺(jué)得問(wèn)題出在replace()上（有機(jī)會(huì)去看看原碼實(shí)現(xiàn)维贺，看了回來(lái)更新一下）
第二天，我將translate()方法中的生成串的方式改成了str = str + "x"巴帮，（但此時(shí)沒(méi)有修改最開(kāi)始的line = line.replace("-","")溯泣，為持續(xù)的TLE埋下伏筆）
修改后，依舊是TLE榕茧，在csdn上搜了一下垃沦，看到其他大神使用了TreeMap<>，會(huì)不會(huì)是排序?qū)е虏粔蚩炷赜醚海课乙矊?xiě)了一個(gè)TreeMap的版本（后來(lái)仔細(xì)思考一下肢簿，這樣想并不靠譜，Collections.sort();被內(nèi)置蜻拨，肯定經(jīng)過(guò)了相當(dāng)優(yōu)化池充，不會(huì)慢的）
這次還是沒(méi)有找到錯(cuò)誤的根源，依舊TLE官觅，再次研究大佬代碼纵菌，發(fā)現(xiàn)了處理輸入中大量“-”的方法：使用的是+（StringBuilder大概也行）:在生成判斷時(shí)再略過(guò)"-"而不是一開(kāi)始就簡(jiǎn)單粗暴的用replace()
將所有的replace()改掉之后，終于AC了休涤，后來(lái)重新使用了之前的寫(xiě)法咱圆，不用TreeMap也過(guò)了
HashMap<String,Integer> myMap = new HashMap<String ,Integer>();
...
Collection<String> keyset = myMap.keySet();
List<String> list = new ArrayList<String>(keyset);
Collections.sort(list);
果然，全都是replace()的錯(cuò)功氨。提交了六次序苏，終于搞定了。捷凄。忱详。
- 做本題時(shí)收獲的細(xì)微知識(shí)點(diǎn)：
- replace()和replaceAll()的區(qū)別：后者支持正則而前者不支持
- TreeMap<>是一種自帶排序的Map集合類(lèi)
TreeMap是基于紅黑樹(shù)（一種自平衡的二叉查找樹(shù)）實(shí)現(xiàn)的一個(gè)保證有序性的Map
- StringBuilder的一些使用（當(dāng)時(shí)用于插入"-"以構(gòu)成"xxx-xxxx"的格式），隱約記得67大帝說(shuō)它比"+"更快
- 引入了字典表的概念（雖然最后沒(méi)有使用）
- 代碼：（包括了一些注釋和心路歷程跺涤，和一些導(dǎo)致多次提交的小錯(cuò)誤）
import java.util.*;
//第一次提交：WA 忘記考慮No duplicates.
//第二次提交：超時(shí)惹 似乎是因?yàn)閞eplace太慢了
//第三次提交：還在超時(shí) 這次似乎是因?yàn)榘袶ashMap的key單獨(dú)成list再拿回去遍歷太慢了
//第四次提交：依舊超時(shí) replace的問(wèn)題匈睁？
//第五次提交：編譯報(bào)錯(cuò)，雖然已經(jīng)發(fā)現(xiàn)了replace問(wèn)題桶错，但不小心搞錯(cuò)了n和list.size()的關(guān)系航唆，list.size()只算獨(dú)一無(wú)二的，n則是所有輸出
//第六次提交：AC了院刁，replace屬實(shí)不行糯钙，一個(gè)都不能有
//無(wú)論是用TreeMap還是用第三次提交的方法都可以，不replace就可以！
public class Main {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
input.nextLine();
// Map<String,Integer> myMap = new TreeMap<String, Integer>(); //使用TreeMap同樣通過(guò)
HashMap<String,Integer> myMap = new HashMap<String ,Integer>();
// HashMap<String,String> mydictMap = new HashMap<String,String>(); //
// initDictMap(dictMap);
for(int i=0;i<n;i++){
String outcome = translate(input.nextLine());
if(myMap.get(outcome) == null){
myMap.put(outcome,1);
}else {
myMap.put(outcome,myMap.get(outcome)+1);
}
}
Collection<String> keyset = myMap.keySet();
List<String> list = new ArrayList<String>(keyset);
Collections.sort(list);
//開(kāi)始輸出
// Set keyset = myMap.keySet();
// Iterator it = keyset.iterator();
boolean noDup = true;
// System.out.println(n+" "+list.size()); //檢測(cè)語(yǔ)句Ｈ伟丁Ｔ匍！
for(int i=0;i<list.size();i++){
if(myMap.get(list.get(i)) != 1){
noDup = false;
String str = list.get(i);
// StringBuilder sb = new StringBuilder(str);
// sb.insert(3,"-");
// str = sb.toString();
// str = str.substring(0,3) + "-" + str.substring(3);
System.out.println( str+ " " + myMap.get(list.get(i)));
}
}
// while(it.hasNext()){
// String str = it.next().toString();
// int value = myMap.get(str);
// if(value > 1){
// noDup = false;
// System.out.println(str + " " + value);
// }
// }
if(noDup == true){
System.out.println("No duplicates.");
}
}
// 爸爸看了一下代碼享潜，速度慢在 replace 這個(gè)動(dòng)作上困鸥，建議改為新建一個(gè) outline (String outline = null)，然后根據(jù)判斷把轉(zhuǎn)換出來(lái)的數(shù)字加進(jìn)去(比如：outline = outline+"2")
// 關(guān)于判斷米碰，爸爸有個(gè)更簡(jiǎn)單明了的方法窝革，就是先建立一個(gè)hashmap购城，保存對(duì)應(yīng)關(guān)系吕座，然后你直接 map.get(line.charAt(i))，就是轉(zhuǎn)換出來(lái)的值
// 比如： HashMap<String,String> dictMap = new HashMap<String ,String>();
// 然后： dictMap.put("A","2"); dictMap.put("B","2"); dictMap.put("C","2"); dictMap.put("D","3"); ....... dictMap.put("0","0"); dictMap.put("-",""); .......
// 這樣你得到的就是全數(shù)字輸出瘪板，中間是沒(méi)有插入 "-" 字符的吴趴；排序之后，在輸出的時(shí)候侮攀，再把這個(gè) "-" 加進(jìn)去
public static void initDictMap(HashMap<String,String> dictMap){
// 初始化字典表
}
//dictMap.get(ine.charAt(i))
public static String translate(String line){
// line = line.replace("-","");
String str = "";
//測(cè)試一下替換結(jié)果锣枝，因?yàn)椴淮_定長(zhǎng)度到底是多少，擔(dān)心后續(xù)下標(biāo)取錯(cuò)
// System.out.println(line + " " + line.length());
for(int i=0;i<line.length();i++){
// if(line.charAt(i)<'0' || line.charAt(i)>'9'){ //編譯器似乎不支持switch兰英，那就用if了
if(line.charAt(i)=='A' || line.charAt(i)=='B' || line.charAt(i)=='C'){ //個(gè)人認(rèn)為這里使用ASCII可以有簡(jiǎn)化計(jì)算撇叁，但Q和Z無(wú)映射，可以之后試試寫(xiě)
str = str + "2";
// line = line.replace(String.valueOf(line.charAt(i)),"2");
}else if(line.charAt(i)=='D' || line.charAt(i)=='E' || line.charAt(i)=='F'){
str = str + "3";
// line = line.replace(String.valueOf(line.charAt(i)),"3");
}else if(line.charAt(i)=='G' || line.charAt(i)=='H' || line.charAt(i)=='I'){
str = str + "4";
// line = line.replace(String.valueOf(line.charAt(i)),"4");
}else if(line.charAt(i)=='J' || line.charAt(i)=='K' || line.charAt(i)=='L'){
str = str + "5";
// line = line.replace(String.valueOf(line.charAt(i)),"5");
}else if(line.charAt(i)=='M' || line.charAt(i)=='N' || line.charAt(i)=='O'){
str = str + "6";
// line = line.replace(String.valueOf(line.charAt(i)),"6");
}else if(line.charAt(i)=='P' || line.charAt(i)=='R' || line.charAt(i)=='S'){
str = str + "7";
// line = line.replace(String.valueOf(line.charAt(i)),"7");
}else if(line.charAt(i)=='T' || line.charAt(i)=='U' || line.charAt(i)=='V'){
str = str + "8";
// line = line.replace(String.valueOf(line.charAt(i)),"8");
}else if(line.charAt(i)=='W' || line.charAt(i)=='X' || line.charAt(i)=='Y'){
str = str + "9";
// line = line.replace(String.valueOf(line.charAt(i)),"9");
}else if(line.charAt(i)=='-'){
}else {
str = str + String.valueOf(line.charAt(i));
}
// }
}
str = str.substring(0,3) + "-" + str.substring(3);
// System.out.println(str);
return str;
}
}
- 參考：
