博客最近在备案，文章不定期删除，等待备案结束将会转移数据！
上篇文章水成狗，这篇虽水，但至少比上篇要好上一些。
前几天，群里有个小朋友发了一道 ACM 题，好像自己很搞不定的样子，作为 90 后空巢老人，几年没碰 ACM 题瞬间有点手痒，关键看上去还很简单有木有，装逼之心瞬起，所以本着沉迷游戏终于自拔后，我决定付出自己微薄的力量。
好啦，看题。
题目描述
在成功解决他的数学作业之后，熊孩子感到很无聊，于是他造了 N 个大整数。
在这 N 个整数中，他喜欢某些对整数，但不喜欢另一些。
熊孩子称他喜欢的那些对整数为友好整数 (Pals)。
两个整数被称为友好整数 (Pals) 当且仅当这两个数至少有一个数字相同(不一定在同一位置)。
请帮助熊孩子计算出在他的整数中有多少对友好整数 (Pals)。
输入
输入包含多组测试用例。
每组数据第一行包含一个整数 N(1⩽N⩽106)，表示熊孩子的整数个数。
接下来 N 行，每行一个整数 Ai(1⩽Ai⩽1018)，每个整数互不相同。
输出
每组数据输出一行，表示 Pals 的对数。
样例输入
3 4 20 44 4 32 51 123 282
样例输出
1 4
资源限制
时间限制: 1 Sec
内存限制: 128 MB
好啦，题目就是这样，刚开始没怎么仔细看题，然后哼哧哼哧写了一会，样例输入啥的感觉没啥问题，但据小朋友说超时，后来他把测试用例拿给我我才发现。。尼玛。。果然符合那个破范围。。。整整 25W 行的数据
一般的方法果然是不行的啊，然后下午出门的时候想了一个方案，跟他说完以后，晚上洗完澡就顺便写了出来。
最初用的方法是直接双层 for 循环遍历，对于测试数据小的时候没什么问题，测试数据一大，就特么崩溃了。所以，想来想去还是先把数字归类，毕竟在这个题目里，数字里面，或者说字符串里的数字有哪些是重要的，其他的诸如数字的排列、每种数字的个数等是不许要考虑的。
所以，对每一个数字，都把它当成字符串来看待，这样也就不用考虑 18 位数字用什么类型存够用的问题，因为根本就没有涉及到计算，然后，对于每一个数字，读入以后，对其进行去重和排序操作，然后将去重排序后的值作为 Key 存储到一个 Map 里，值就是 Key 相同的数字的个数。
例如：
142312321
经过去重加排序后的结果为：
1234
这个数字即为 Key。
把所有数字处理完后，再像之前那样双层遍历，计算总的 Pals 的数量。只是计算的方式会略有差别。
懒得说了
看代码吧。。。
import java.util.*; /**
* Author : Hran
* Date : 2017/5/27
* Version :
* Description:
*/ public class Pals { public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); int totalNum = Integer.parseInt(scanner.nextLine()); long start = System.currentTimeMillis();
Map<String, Integer> sumTests = new HashMap<>(1024);
String number; for (int i = 0; i < totalNum; i++) {
StringBuilder sb = new StringBuilder();
scanner.nextLine().chars().distinct().sorted().forEach(value -> sb.append((char) value));
number = sb.toString();
sumTests.put(number, sumTests.getOrDefault(number, 0) + 1);
} long palsNum = 0;
String[] keys = new String[sumTests.size()];
sumTests.keySet().toArray(keys); int sumA, sumB; for (int i = 0; i < keys.length; i++) {
sumA = sumTests.get(keys[i]);
palsNum += sumA * (sumA - 1) / 2; for (int j = i + 1; j < keys.length; j++) { if (isPals(keys[i], keys[j])) {
sumB = sumTests.get(keys[j]);
palsNum += sumA * sumB;
}
}
}
System.out.println(palsNum);
System.out.println("Time: " + (System.currentTimeMillis() - start) + "ms");
} private static boolean isPals(String a, String b) {
String gege; char[] didi; if (a.length() < b.length()) {
gege = a;
didi = b.toCharArray();
} else {
gege = b;
didi = a.toCharArray();
} for (char c : didi) { if (gege.contains(String.valueOf(c))) { return true;
}
} return false;
}
}
大概就是这个样子，然后测试用例在这里：
@(太开心)