LeetCode 554. 砖墙

Categories:

题目描述
思路分析
1. 解法一：哈希表统计缝隙（推荐）
相似题目

题目描述

✅ 554. 砖墙

思路分析

解法一：哈希表统计缝隙（推荐）

核心思路：

穿过砖墙的垂直线要穿过最少的砖块，等价于经过最多的砖缝。

对每一行，统计各列位置的砖缝数量（不含最左和最右端点）。

用哈希表记录每个位置的砖缝出现次数，找出出现次数最多的位置。

最终答案 = 总行数 - 最多砖缝数。

复杂度分析：

时间复杂度：O(n × m)，其中 n 表示砖墙的行数，m 表示每行砖块的平均数量。

空间复杂度：O(k)，其中 k 表示所有行中不同的砖缝位置数量。

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        // key: 缝隙所在列位置，value: 该列出现缝隙的行数
        Map<Integer, Integer> edgeCount = new HashMap<>();
        int maxEdge = 0;

        for (List<Integer> row : wall) {
            int pos = 0;
            // 遍历到倒数第二块砖，不统计最右端点
            for (int i = 0; i < row.size() - 1; i++) {
                pos += row.get(i);
                // 累加当前列的缝隙次数
                int count = edgeCount.getOrDefault(pos, 0) + 1;
                edgeCount.put(pos, count);
                if (count > maxEdge) {
                    maxEdge = count;
                }
            }
        }

        // 穿过砖块数 = 总行数 - 最多缝隙数
        return wall.size() - maxEdge;
    }
}

func leastBricks(wall [][]int) int {
    // key: 缝隙所在列位置，value: 该列出现缝隙的行数
    edgeCount := make(map[int]int)
    maxEdge := 0

    for _, row := range wall {
        pos := 0
        // 遍历到倒数第二块砖，不统计最右端点
        for i := 0; i < len(row)-1; i++ {
            pos += row[i]
            edgeCount[pos]++
            if edgeCount[pos] > maxEdge {
                maxEdge = edgeCount[pos]
            }
        }
    }

    // 穿过砖块数 = 总行数 - 最多缝隙数
    return len(wall) - maxEdge
}

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	哈希表、前缀和
1. 两数之和	简单	哈希表
525. 连续数组	中等	哈希表、前缀和
974. 和可被 K 整除的子数组	中等	哈希表、前缀和
523. 连续的子数组和	中等	哈希表、前缀和
1590. 使数组和能被 P 整除	中等	哈希表、前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/99048587