专栏首页程序生活LeetCode-中等 砖墙

LeetCode-中等 砖墙

题目描述

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

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

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

链接:https://leetcode-cn.com/problems/brick-wall

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

思路

观察垂直线的特点, 如果穿过每行砖块对齐的缝隙越多, 那么穿过砖块的数量就会越少!

怎么找到每行的砖块都恰好对齐的那些缝隙呢? 可以用额外的存储空间来辅助一下~, 比如 Hashmap 怎么把计算对齐的缝隙转化成可操作的代码呢? 计算每一行砖块宽度的前缀和! 在计算某一行砖块的时候, 将砖块的宽度和进行累计, 每一个累计砖块的宽度和都作为 hashmap 的 key, value就是这个key出现的次数. 怎么求穿过的最少砖块数? 一个垂直的线最多穿过的砖块数就是这堵墙的行数, 减去出现次数/频数最高的砖块的宽度和, 就相当于找到了砖块对齐的缝隙最多的那一条垂直线了! 链接:https://leetcode-cn.com/problems/brick-wall/solution/chi-xiao-dou-xun-lian-jie-ti-si-lu-rang-wbgfx/

代码实现

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        res = {0: 0}
        for lvl in wall:
            pos = 0
            for brick in lvl[:-1]:
                pos += brick
                res[pos] = res.get(pos, 0) +1
        return len(wall)-max(res.values())

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 554. 砖墙(map计数)

    你的面前有一堵方形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。

    Michael阿明
  • Golang Leetcode 554. Brick Wall.go

    我们可以拿砖缝左侧砖块的总长度来标记每个砖缝,这样遍历每一行的砖块将所有砖缝位置计数后存入Hash Table中,最终遍历Hash Table找出同一纵向位置砖...

    anakinsun
  • 力扣(LeetCode)刷题,简单+中等题(第34期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • AdGuard主页:广告屏蔽墙中的另一块砖

    Canonical的AdGuard Home Ubuntu设备是其设备等级的新成员。 使用此产品,用户可以快速实施现成的解决方案,以在家庭网络的网络级别上阻止令...

    YH
  • 《离职留给小徒弟保姆教程》Idea 必装插件,墙裂推荐!!!

    idea 是几乎是当前Java开发的最好用的编辑器,尽管Idea 本就提供了不错的功能,但是不同的开发需求不一样,为了满足不同的需求,可以安装各种插件,非常好用...

    香菜聊游戏
  • 《保姆教程一》Idea 必装插件,墙裂推荐!!!

    idea 是几乎是当前Java开发的最好用的编辑器,尽管Idea 本就提供了不错的功能,但是不同的开发需求不一样,为了满足不同的需求,可以安装各种插件,非常好用...

    香菜聊游戏
  • 基于pygame实现童年掌机打砖块游戏

    本文为大家分享了童年掌机游戏,基于pygame实现打砖块的具体代码,供大家参考,具体内容如下

    砸漏
  • java SE学习之线程同步(详细介绍)

           java程序中可以允许存在多个线程,但在处理多线程问题时,必须注意这样一个问题:               当两个或多个线程同时访问同一个变...

    Gxjun
  • [视频] 砌墙神器速度比人快6倍,建筑工也要失业了?

    随着科技迅速发展,越来越多的工作被机器人所取代。据英国《每日邮报》3月27日报道,此前已在美国投入使用的砌墙机器人将在两年内“降临”英国工地。此类机器人一天能砌...

    机器人网

扫码关注云+社区

领取腾讯云代金券