题意ref{:target=”_balnk”}
求穿过的brick最小,即穿过缝隙最多,即每行前缀和相同的个数最多,计算前缀和记得不算最后一个,因为要排除左右两遍的垂直线
C++ 代码
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
int m = wall.size(), n = wall[0].size();
unordered_map<int,int> dict;
int no_cross = 0;
for(int i=0; i<m; ++i) {
int sum = 0;
for(int j=0; j<wall[i].size()-1; ++j) {
sum += wall[i][j];
dict[sum]++;
no_cross = max(no_cross, dict[sum]);
}
}
return m - no_cross;
}
};