题目

砖墙

你的面前有一堵矩形的、由 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

---

解决方法

语言：C++
结构：哈希表

方法：
在本题中，我们需要求得穿过砖块最少的最好位置
同时，在本题中重要点是砖块除地图最右界外最右边不算砖块本身
依据此，我们可以使用统计和的方法
将砖块每一层视为一个数组求前缀和
前缀和的值便为同一层各个砖块最右边的位置
使用哈希表来存放最右边界出现的位置的次数
次数最多说明我们每层在该位置穿过，可以达到穿过的数量最少

---

代码（含注释）

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int,int> load;
        int n = wall[0].size();

        for(auto &x:wall)
        {
            int sum = 0;
            for(int i = 0;i < x.size() - 1;++i)
            {
                sum += x[i];                        //在该层求其前缀和
                load[sum]++;
            }
        }
        int ans = 0;
        for(auto &w : load)
        {
            ans = max(ans,w.second);                //判断哪个位置砖块最右边出现次数最多
        }
        return wall.size() - ans;
    }
};

---

运行结果

---

后记

最近在进行刷题练习，本题一开始看到自然会想到区间，但前缀和统计的方法不易想到，应该属于区间类题的变种，同类型题也可看我另一文章。