青鸟热潮 LeetCode逐日一题

凭据题意，墙的层数畛域[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; }}

按照上头的念念路，是会出现溢出的，因为可能的最大值是(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 来确保正确性的，因为最终溢出会被回荡追念。