欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

如何优雅地使用HashMap完成打表(记洛谷P1765的AC套路)

程序员文章站 2024-03-17 21:04:28
...

前言

本题水题一个,但是这里会结合着提一些HashMap的内容~~但不是什么深度分析,没营养的。。。

题目要求

P1765题目链接
如何优雅地使用HashMap完成打表(记洛谷P1765的AC套路)

分析

这题懒得去排着弄,突然就觉得不如打个表,这样还是很简洁滴~~

既然是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开发手册内容:
如何优雅地使用HashMap完成打表(记洛谷P1765的AC套路)

如果我们不这么做,假设集合容量较大,则频繁的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还是很爽的~~

相关标签: # 菜鸡逛洛谷