先放题目地址：http://poj.org/problem?id=1002
- 题目思路：每行读入之后，根据某种方式将其全部转化为数字，以“xxx-xxxx”的格式存储入表，经过判断后，以 key+value 的形式输出，如果没有重复就单独考虑。
这个思路其实很简单。。（我当时甚至还好奇为啥Ac率这么低）所以我很快就写出了第一版的代码：用replace()处理输入数据，存入hashMap，经过排序后输出
第一次提交的时候报的是WA，因为题目中的No duplicates.我忘记写进去了（审题的时候有注意到，真正写的时候却忘记了，以后要多加注意）
修改后，第二次提交竟然给我报了Time Limit Exceeded，菜鸡做题少，第一次见这样报错，有点沮丧，请老爸帮看了一下，经验丰富的他觉得问题出在replace()上（有机会去看看原码实现，看了回来更新一下）
第二天，我将translate()方法中的生成串的方式改成了str = str + "x"，（但此时没有修改最开始的line = line.replace("-","")，为持续的TLE埋下伏笔）
修改后，依旧是TLE，在csdn上搜了一下，看到其他大神使用了TreeMap<>，会不会是排序导致不够快呢？我也写了一个TreeMap的版本（后来仔细思考一下，这样想并不靠谱，Collections.sort();被内置，肯定经过了相当优化，不会慢的）
这次还是没有找到错误的根源，依旧TLE，再次研究大佬代码，发现了处理输入中大量“-”的方法：使用的是+（StringBuilder大概也行）:在生成判断时再略过"-"而不是一开始就简单粗暴的用replace()
将所有的replace()改掉之后，终于AC了，后来重新使用了之前的写法，不用TreeMap也过了
HashMap<String,Integer> myMap = new HashMap<String ,Integer>();
...
Collection<String> keyset = myMap.keySet();
List<String> list = new ArrayList<String>(keyset);
Collections.sort(list);
果然，全都是replace()的错。提交了六次，终于搞定了。。。
- 做本题时收获的细微知识点：
- replace()和replaceAll()的区别：后者支持正则而前者不支持
- TreeMap<>是一种自带排序的Map集合类
TreeMap是基于红黑树（一种自平衡的二叉查找树）实现的一个保证有序性的Map
- StringBuilder的一些使用（当时用于插入"-"以构成"xxx-xxxx"的格式），隐约记得67大帝说它比"+"更快
- 引入了字典表的概念（虽然最后没有使用）
- 代码：（包括了一些注释和心路历程，和一些导致多次提交的小错误）
import java.util.*;
//第一次提交：WA 忘记考虑No duplicates.
//第二次提交：超时惹 似乎是因为replace太慢了
//第三次提交：还在超时 这次似乎是因为把HashMap的key单独成list再拿回去遍历太慢了
//第四次提交：依旧超时 replace的问题？
//第五次提交：编译报错，虽然已经发现了replace问题，但不小心搞错了n和list.size()的关系，list.size()只算独一无二的，n则是所有输出
//第六次提交：AC了，replace属实不行，一个都不能有
//无论是用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同样通过
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);
//开始输出
// Set keyset = myMap.keySet();
// Iterator it = keyset.iterator();
boolean noDup = true;
// System.out.println(n+" "+list.size()); //检测语句！！！
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 这个动作上，建议改为新建一个 outline (String outline = null)，然后根据判断把转换出来的数字加进去(比如：outline = outline+"2")
// 关于判断，爸爸有个更简单明了的方法，就是先建立一个hashmap，保存对应关系，然后你直接 map.get(line.charAt(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("-",""); .......
// 这样你得到的就是全数字输出，中间是没有插入 "-" 字符的；排序之后，在输出的时候，再把这个 "-" 加进去
public static void initDictMap(HashMap<String,String> dictMap){
// 初始化字典表
}
//dictMap.get(ine.charAt(i))
public static String translate(String line){
// line = line.replace("-","");
String str = "";
//测试一下替换结果，因为不确定长度到底是多少，担心后续下标取错
// 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'){ //个人认为这里使用ASCII可以有简化计算，但Q和Z无映射，可以之后试试写
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;
}
}
- 参考：
