554. Brick Wall - Medium

前往題目

想法

• 如何找出gap?

思路

找出Gap很簡單，直接給他們index代表他們就好

1. HashMap儲存gap編號以及數量
2. 疊代每道牆，但忽略最後一個磚塊，不然會算到最右邊的cut(穿過0個磚塊)
3. 更新gap的數量以及紀錄最大值
4. 回傳牆的大小減去最大值，就是穿過的磚塊數

Code

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        // gap index -> count
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        
        // Go through all the walls
        for (List<Integer> r : wall) {
            // gap index
            int total = 0;
            
            // Ignore the last brick, can't include the right most cut
            for (int i = 0; i < r.size() - 1; ++i) {
                // Calculate the gap index
                total += r.get(i);
                // Record the maximum
                res = Math.max(res, map.getOrDefault(total, 0) + 1);
                // Update the count
                map.put(total, map.getOrDefault(total, 0) + 1);
            }
        }

        return wall.size() - res;
    }
}