0554. Brick Wall - kumaeki/LeetCode GitHub Wiki

554. Brick Wall

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

Input: [[1,2,2,1],
        [3,1,2],
        [1,3,2],
        [2,4],
        [3,1,2],
        [1,3,1,1]]

Output: 2

Explanation:

Note:

  • The width sum of bricks in different rows are the same and won't exceed INT_MAX.
  • The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won't exceed 20,000.

解法1

最简单的想法是,用数组保存所有可能的路径,然后遍历每一层. 但是超过限制了!!!

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        // 得到可能的路径数
        int len = -1;
        for(int val : wall.get(0))
            len += val;
        
        // 定义长度为len的数组,保存到当前层各路径所经过的砖块数
        int[] arr = new int[len];
        // 遍历每一层
        for(int i = 0; i < wall.size(); i++){
            // 默认所有路径先加1
            addOne(arr);
            List<Integer> row = wall.get(i);
            int cur = -1;
            // 遍历每个砖块, 两个砖块之间的位置减去1
            for(int val : row){
                cur += val;
                // 当不是最右侧的墙的时候才执行减1的操作
                if(cur < len)
                    arr[cur]--;
            }
        }
        
        // 遍历数组, 得到最小值
        int res = Integer.MAX_VALUE;
        for(int val : arr)
            res = Math.min(res, val);
        
        return res == Integer.MAX_VALUE ? wall.size() : res;
    }
    
    // 数组中每个元素加1
    private void addOne(int[] arr){
        for(int i = 0; i < arr.length; i++)
            arr[i]++;
    }
}

解法2

然后我就想到,既然数组不行,那么我就用map来保存之前计算的结果.
最后虽然通过的所有的case, 但是成绩非常不好.

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        // 得到墙体的宽度
        int width = 0;
        for(int val : wall.get(0))
            width += val;
        
        Map<Integer, Integer> map = new HashMap<Integer,Integer>();
        int index = 0;
        for(int val : wall.get(0)){
            index += val;
            // 当出现缝隙,并且不是在墙的边缘时
            if(index < width)
                map.put(index, 0);
        }
        
        // 遍历每一层
        for(int i = 1; i < wall.size(); i++){
            List<Integer> row = wall.get(i);
            int cur = 0;
            // 遍历每个砖块
            for(int val : row){
                cur += val;
                // 当出现缝隙,并且不是在墙的边缘时
                if(cur < width ){
                    // 如果是新的缝隙, 那么将层数加30,000, 放入map中(标记为已处理)
                    if(!map.containsKey(cur))
                        map.put(cur, i + 30000);
                    // 如果是已经出现过的缝隙, 那么将旧值加30,000,放入map中(标记为已处理)
                    else
                        map.put(cur, map.get(cur) + 30000);
                }
            }
            
            // 遍历map, 如果发现旧的缝隙没有被处理过, 那么需要加1
            for(int key : map.keySet()){
                int val = map.get(key);
                if(val >= 30000)
                    map.put(key, val - 30000);
                else
                    map.put(key, val + 1);
            }
        }
        
        // 遍历数组, 得到最小值
        int res = Integer.MAX_VALUE;
        for(Map.Entry<Integer, Integer> entry : map.entrySet() )
            res = Math.min(res, entry.getValue());
        
        return res == Integer.MAX_VALUE ? wall.size() : res;
    }
    
}

解法3

看了大家的答案之后发现是我想复杂了.
上面的两个办法都是直接计算砖块数,但是其实可以直接计算缝隙数, 然后用层数减去缝隙数就好了
果然快睡觉的时候脑子不太灵光.
(明明平时也不是很灵光的)

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int height = wall.size();
        
        Map<Integer,Integer> map = new HashMap();
        
        for(int i = 0 ; i < height; i++) {
            List<Integer> row = wall.get(i);
            int sum  = 0;
            for(int j  = 0; j < row.size() - 1; j++) {
                sum += row.get(j);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        
        int max = 0;
        for(Map.Entry<Integer, Integer> entry: map.entrySet())
            max = Math.max(max, entry.getValue());
        
        return height - max;
    }
}
⚠️ **GitHub.com Fallback** ⚠️