如何优雅地使用HashMap完成打表(记洛谷P1765的AC套路)
程序员文章站
2024-03-17 21:04:28
...
前言
本题水题一个,但是这里会结合着提一些HashMap的内容~~但不是什么深度分析,没营养的。。。
题目要求
分析
这题懒得去排着弄,突然就觉得不如打个表,这样还是很简洁滴~~
既然是Java,那就HashMap啊,泛型选<Character, Integer>,用char当key,int当value,通过char数组中的元素找出对应的value,很简单~~
AC代码(Java语言描述)
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Map<Character, Integer> map = new HashMap<>(32);
map.put('a', 1);
map.put('b', 2);
map.put('c', 3);
map.put('d', 1);
map.put('e', 2);
map.put('f', 3);
map.put('g', 1);
map.put('h', 2);
map.put('i', 3);
map.put('j', 1);
map.put('k', 2);
map.put('l', 3);
map.put('m', 1);
map.put('n', 2);
map.put('o', 3);
map.put('p', 1);
map.put('q', 2);
map.put('r', 3);
map.put('s', 4);
map.put('t', 1);
map.put('u', 2);
map.put('v', 3);
map.put('w', 1);
map.put('x', 2);
map.put('y', 3);
map.put('z', 4);
map.put(' ', 1);
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
scanner.close();
char[] chars = line.toCharArray();
int counter = 0;
for (char c : chars) {
counter += map.get(c);
}
System.out.println(counter);
}
}
About~HashMap
简单扯两句吧~~
1.建立HashMap最好指定长度,这是被强调的!!下图为Alibaba的Java开发手册内容:
如果我们不这么做,假设集合容量较大,则频繁的resize会损耗性能。
特别是HashMap,当其resize时相当于还要rehash,性能损耗不小啊。。。
除此之外,这么处理就是很慢,简单测试可知。
由于本题我们已知容量是26+1=27,那么根据HashMap的机理,内部长度被初始化为32(临近的2的幂次),而避免了默认的16→32的resize。
2.HashMap是真的快。
我们打上时间戳,用System.currentTimeMillis()这个方法,调整initialCapacity参数,给一段比较长的文字,粗劣的测试一下运行时间,结果是0……。
真快啊~~Orz
(原来整个程序又是被Scanner拖慢了,我醉了……)
3.HashMap相关的红黑树啊,链表啊,那些自己看看文档和源码吧,这只是一个巨水的OJ,懒得说咯~~
总之,本题用HashMap还是很爽的~~
上一篇: C++中的运算符重载