LeetCode554——砖墙

554. 砖墙 - 力扣(LeetCode) (leetcode-cn.com)

大致思路:按照题目描述直接判断虚线穿过了多少道墙,需要考虑墙的边界条件等问题很难判断。但是我们可以反向思考,要让虚线穿过的砖的数目最少,等同于让虚线穿过的缝隙最多。因此我们可以求出虚线穿过的缝隙数目的最大值,再用砖块的行数减去穿过缝隙数目的最大值就是答案。

代码:

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int,int> count;
        for (auto& v : wall) {
            int sum = 0;
            for (int i = 0; i < v.size() - 1; i++) {
                sum += v[i];
                count[sum]++;
            }
        }
        int n = wall.size();
        int ans = 0;
        for (auto ite : count) {
            ans = max(ans, ite.second);
        }
        return n - ans;
    }
};
上一篇:ROS-Melodic 安装全部指令列表


下一篇:多种图形的打印(以*为例)