554. 砖墙
你的面前有一堵矩形的、由 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
提示:
n == wall.length
1 <= n <= 104
1 <= wall[i].length <= 104
1 <= sum(wall[i].length) <= 2 * 104
对于每一行 i ,sum(wall[i]) 应当是相同的
1 <= wall[i][j] <= 231 - 1
通过次数22,105提交次数52,120
思路分析
我相信很多同学看题目似懂非懂,再加上示例看起来非常吓人的图,就感觉这道题很难,其实这种题目有很多,只是需要我们转换一下思路。
题目让我们求出穿过最少砖块的垂直线,什么是时候穿过最少?
- 当穿过的缝隙越多,那说明穿过的砖块最少
我们以示例1为图:
首先我们假设黑色的线条为缝隙,那么我们假设:
- 第一行的缝隙为[1,3,5]
- 第二行的缝隙为[3,4]
- 第三行的缝隙为[1,4]
- 第四行的缝隙为[2]
- 第五行的缝隙为[3,4]
- 第六行的缝隙为[1,4,5]
之后我们将这先数据存在哈希表表中,缝隙值为key,每次遇到一样的缝隙值,value+1;
一个缝隙都不穿过,穿过的砖块即为砖块行数,即n,我们减去穿过最多缝隙数,即穿过最少砖块数。
java代码:
class Solution {
public int leastBricks(List<List<Integer>> wall) {
Map<Integer , Integer> map = new HashMap<Integer ,Integer>();
int n = wall.size();
//我们从第一行开始,一次记录
for (int i = 0 ; i < n ; i++) {
int sum = 0;
//记录每一行每一个数字
for (int curN : wall.get(i)) {
//每次记录完一行一定要记得清零
sum += curN;
map.put(sum , map.getOrDefault(sum , 0) + 1);
}
//最后一列不算,所以我们去掉
map.remove(sum);
}
//我们在这里求得是穿过最多缝隙的垂直线,所以还有转换为题目要求的最少砖块
int result = n;
for (int key : map.keySet()) {
int value = map.get(key);
result = Math.min(result , n - value);
}
return result;
}
}
或许有同学不知道keySet()这个方法是干什么的,就是获取key键的名称的方法,为什么说是名称呢,因为key不一定是数字,网上那些什么乱七八糟的说半天都说不明白什么意思,其实就这么简单,想要深入了解还得看源码。
当然迭代key值不仅仅只有这一种办法,我们还可以这样写:
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
result = Math.min(result , n - entry.getValue());
}
复杂度分析
时间复杂度
O(nm)
其中n为砖块行数,m为每行平均砖块数,你也可以说是某一行的最多砖块数,这不过是最坏情况
空间复杂度
O(nm)
每块转都会被扫描,所以还是mn
若有误,请指教!