砖墙(HashMap)

554. 砖墙

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同(也就是一个单位高)但是宽度不同。每一行砖块的宽度之和应该相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。

给你一个二维数组 wall ,该数组包含这堵墙的相关信息。其中,wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ,并且返回 穿过的砖块数量 。

示例 1:
砖墙(HashMap)

输入: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为图:

砖墙(HashMap)
首先我们假设黑色的线条为缝隙,那么我们假设:

  • 第一行的缝隙为[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());
}

砖墙(HashMap)

复杂度分析

时间复杂度

O(nm)
其中n为砖块行数,m为每行平均砖块数,你也可以说是某一行的最多砖块数,这不过是最坏情况

空间复杂度

O(nm)
每块转都会被扫描,所以还是mn

若有误,请指教!

上一篇:砖墙


下一篇:登录成功返回登录前页面js代码