LeeCode 554. 砖墙

LeeCode 554. 砖墙

思路：

贪心策略，统计每一行出现的和的次数，最后和次数出现最多的即为答案。
参考

代码：

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        int sum = 0;
        for(auto x : wall[0]) sum += x;
        unordered_map<int,int> hash;

        for(auto vec : wall){
            int tmp = 0;
            for(auto x : vec){
                tmp += x;
                hash[tmp]++;
            }
        }
        int ans = 0;
        for(auto vec : wall){
            int tmp = 0;
            for(auto x : vec){
                tmp += x;
                if(tmp != sum) ans = max(ans, hash[tmp]);
            }
        }
        return wall.size() - ans;
    }
};