砖墙题

这题一开始没有想到思路，一开始还想着用枚举法做/笑哭
后来看了题解，原来就是哈希表的题目呀。

说到哈希表，这里有个八股需要记一下：
HashMap和HashTable的区别

1. 线程是否安全：HashMap线程不安全 HashTable线程安全，几乎所有方法都用synchronized修饰。
2. 效率：HashMap要比HashTable效率高一些。
3. 对null key和null value的支持：HashTable不允许出现null键和值。
4. 初始容量大小和扩容不同：
   初始时不指定容量大小：HashMap：16 之后每次扩容变成原来的2倍 ； HashTable：11 之后每次变成原来的2n+1
   初始时指定容量大小：HashMap：将其扩容为2的n次方 ；HashTable：直接用你输入的值
5. 底层数据结构：HashMap：jdk8后，在解决哈希冲突的时候，当链表长度大于8的时候，转换为红黑树；HashTable没有这个机制。

那么回到这一题：
一个思想流程就是，使用哈希表统计所有右边缝出现的次数，然后统计这些右边缝哪个出现的多，需要注意的是，右边缝不能包含最右边的边缝，所以在循环内层列表的时候，不能计算最后一块砖的长度。流程如下：

代码如下：

    public int leastBricks(List<List<Integer>> wall) {
        //使用哈希表进行求解
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int height =1; //计算砖墙的高度  也可以使用wall.size()直接得到
        //使用哈希表统计每一行出现的缝隙 除去最后一列的砖墙
        for (List<Integer> list : wall) {
            height++;
            int n = list.size();
            int sum = 0;
            for (int j = 0; j < n-1; j++) {
                sum += list.get(j);
                hashMap.put(sum,hashMap.getOrDefault(sum,0)+1);
            }
        }

        //统计哈希表中哪个缝隙出现次数
        int max = 0;
        for (Map.Entry<Integer,Integer> entry: hashMap.entrySet()) {
            max = Math.max(max,entry.getValue());
        }
        return height-max;
    }