0554-砖墙

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。
你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线
穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

示例 1：

**输入：** wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
**输出：** 2

示例 2：

**输入：** wall = [[1],[1],[1]]
**输出：** 3

提示：

  • n == wall.length
  • 1 <= n <= 104
  • 1 <= wall[i].length <= 104
  • 1 <= sum(wall[i].length) <= 2 * 104
  • 对于每一行 i ，sum(wall[i]) 是相同的
  • 1 <= wall[i][j] <= 231 - 1

方法一：哈希表

思路及算法

由于砖墙是一面矩形，所以对于任意一条垂线，其穿过的砖块数量加上从边缘经过的砖块数量之和是一个定值，即砖墙的高度。

因此，问题可以转换成求「垂线穿过的砖块边缘数量的最大值」，用砖墙的高度减去该最大值即为答案。

虽然垂线在每行至多只能通过一个砖块边缘，但是每行的砖块边缘也各不相同，因此我们需要用哈希表统计所有符合要求的砖块边缘的数量。

注意到题目要求垂线不能通过砖墙的两个垂直边缘，所以砖墙两侧的边缘不应当被统计。因此，我们只需要统计每行砖块中除了最右侧的砖块以外的其他砖块的右边缘即可。

具体地，我们遍历砖墙的每一行，对于当前行，我们从左到右地扫描每一块砖，使用一个累加器记录当前砖的右侧边缘到砖墙的左边缘的距离，将除了最右侧的砖块以外的其他砖块的右边缘到砖墙的左边缘的距离加入到哈希表中。最后我们遍历该哈希表，找到出现次数最多的砖块边缘，这就是垂线经过的砖块边缘，而该垂线经过的砖块数量即为砖墙的高度减去该垂线经过的砖块边缘的数量。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> cnt;
        for (auto& widths : wall) {
            int n = widths.size();
            int sum = 0;
            for (int i = 0; i < n - 1; i++) {
                sum += widths[i];
                cnt[sum]++;
            }
        }
        int maxCnt = 0;
        for (auto& [_, c] : cnt) {
            maxCnt = max(maxCnt, c);
        }
        return wall.size() - maxCnt;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (List<Integer> widths : wall) {
            int n = widths.size();
            int sum = 0;
            for (int i = 0; i < n - 1; i++) {
                sum += widths.get(i);
                cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
            }
        }
        int maxCnt = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            maxCnt = Math.max(maxCnt, entry.getValue());
        }
        return wall.size() - maxCnt;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int LeastBricks(IList<IList<int>> wall) {
        Dictionary<int, int> cnt = new Dictionary<int, int>();
        foreach (IList<int> widths in wall) {
            int n = widths.Count;
            int sum = 0;
            for (int i = 0; i < n - 1; i++) {
                sum += widths[i];
                if (!cnt.ContainsKey(sum)) {
                    cnt.Add(sum, 1);
                } else {
                    cnt[sum]++;
                }
            }
        }
        int maxCnt = 0;
        foreach (var entry in cnt) {
            maxCnt = Math.Max(maxCnt, entry.Value);
        }
        return wall.Count - maxCnt;
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var leastBricks = function(wall) {
    const cnt = new Map();
    for (const widths of wall) {
        const n = widths.length;
        let sum = 0;
        for (let i = 0; i < n - 1; i++) {
            sum += widths[i];
            cnt.set(sum, (cnt.get(sum) || 0) + 1);
        }
    }
    let maxCnt = 0;
    for (const [_, c] of cnt.entries()) {
        maxCnt = Math.max(maxCnt, c);
    }
    return wall.length - maxCnt;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func leastBricks(wall [][]int) int {
    cnt := map[int]int{}
    for _, widths := range wall {
        sum := 0
        for _, width := range widths[:len(widths)-1] {
            sum += width
            cnt[sum]++
        }
    }
    maxCnt := 0
    for _, c := range cnt {
        if c > maxCnt {
            maxCnt = c
        }
    }
    return len(wall) - maxCnt
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct HashTable {
    int key, val;
    UT_hash_handle hh;
};

int leastBricks(int** wall, int wallSize, int* wallColSize) {
    struct HashTable* cnt = NULL;
    for (int i = 0; i < wallSize; i++) {
        int n = wallColSize[i];
        int sum = 0;
        for (int j = 0; j < n - 1; j++) {
            sum += wall[i][j];
            struct HashTable* tmp;
            HASH_FIND_INT(cnt, &sum, tmp);
            if (tmp == NULL) {
                tmp = malloc(sizeof(struct HashTable));
                tmp->key = sum, tmp->val = 1;
                HASH_ADD_INT(cnt, key, tmp);
            } else {
                tmp->val++;
            }
        }
    }
    int maxCnt = 0;
    struct HashTable *iter, *tmp;
    HASH_ITER(hh, cnt, iter, tmp) {
        maxCnt = fmax(maxCnt, iter->val);
    }
    return wallSize - maxCnt;
}

复杂度分析

  • 时间复杂度：O(nm)，其中 n 是砖墙的高度，m 是每行砖墙的砖的平均数量。我们需要遍历每行砖块中除了最右侧的砖块以外的每一块砖，将其右侧边缘到砖墙的左边缘的距离加入到哈希表中。

  • 空间复杂度：O(nm)，其中 n 是砖墙的高度，m 是每行砖墙的砖的平均数量。我们需要将每行砖块中除了最右侧的砖块以外的每一块砖的右侧边缘到砖墙的左边缘的距离加入到哈希表中。

 Comments
On this page
0554-砖墙