解题思路:
首先要读明白题意(建议别看图,会先入为主),意思就是从上往下沿着砖缝能碰到最少的砖块是多少,那说白了就是统计每一层的砖缝位置,全部记录到map中,如果在位置x的砖缝最多,那么就沿着那条缝切下去即可,代码如下:
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
unordered_map<int, int> count;
for(int i = 0; i < wall.size(); i ++) {
int sum = 0;
// 注意不能从边缘穿出,所以边界条件是 wall[i].size() - 1
for(int j = 0; j < wall[i].size() - 1; j ++) {
sum += wall[i][j];
count[sum] ++;
}
}
int num = 0;
// 找出相同边界最多的次数
for(auto c : count) {
if(c.second > num) {
num = c.second;
}
}
return wall.size() - num;
}
};
/*作者:heroding
链接:https://leetcode-cn.com/problems/brick-wall/solution/c-map-by-heroding-ok80/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。*/