554. 砖墙

2021-05-02 LeetCode每日一题

链接：https://leetcode-cn.com/problems/brick-wall/

根据题意，墙的层数范围[1, 10^4]，对于每层，砖的数量[1, 10^4]，每块砖的长度范围[1, 2^31 - 1]。

最笨的方法，使用hash表记录每层，在哪些长度可以进行分割（即砖之间的缝隙在这层里处于什么位置）。循环遍历每层，就可以得到每层哪些位置可以分割，value最大的，说明需要通过最少的砖wall.length - value

class Solution {
    int max = 0;
    public int leastBricks(List<List<Integer>> wall) {
        Map<Long, Integer> map = new HashMap<>();
        for (int i = 0; i < wall.size(); i++) {
            List<Integer> list = wall.get(i);
            long sum = 0;
            for (int j = 0; j < list.size() - 1; j++) {
                sum += list.get(j);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }

        map.forEach((key, value) -> {
            if (value > max) {
                max = value;
            }
        });

        return wall.size() - max;
    }
}

image.png

按照上面的思路，是会出现溢出的，因为可能的最大值是(10^4) * (2^31 - 1)。一开始我使用的Long去装，后面发现使用Integer也是可以的。

因为当 Java 发生溢出时，会直接转成负数来处理。因此对于本题不会影响正确性（不重复溢出的话）。比如

{
    System.out.println(Integer.MIN_VALUE); // -2147483648
    
    int a = Integer.MAX_VALUE;
    System.out.println(a); // 2147483647
    a += 1;
    System.out.println(a); // -2147483648
    a -= 1;
    System.out.println(a); //2147483647
}

这意味着，如果我们在运算过程中如果只涉及「纯加减运算」，而不涉及「乘除」、「取最大值/最小值」和「数值大小判断」的话，Java 是不需要使用 Long 来确保正确性的，因为最终溢出会被转化回来。