554. 砖墙

偏执的太偏执、 2022-10-21 01:26 93阅读 0赞

#### 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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70_pic_center]  
按照上面的思路，是会出现溢出的，因为可能的最大值是(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 来确保正确性的，因为最终溢出会被转化回来。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/177d92e08482496dbeda3ea9aa134805.png