V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
letianqiu
V2EX  ›  程序员

求助一道算法题。求思路。由一个 0 和 1 组成的矩阵,求出所有 1 构成的阶梯。

  •  
  •   letianqiu · 2017-08-18 20:08:44 +08:00 · 4275 次点击
    这是一个创建于 2414 天前的主题,其中的信息可能已经有所发展或是发生改变。

    初步发现 size * (steps + 1) - steps = n,如果对于每一个元素都枚举一遍,感觉复杂度非常高,而且会重复,比如 size 为 2 的可能是 size 为 3 的其中一部分。求指导

    tmp.PNG

    33 条回复    2017-08-19 21:07:36 +08:00
    shard
        1
    shard  
       2017-08-18 20:25:56 +08:00
    动态规划
    menc
        2
    menc  
       2017-08-18 20:29:51 +08:00
    这是一道回溯法的题啊,
    只不过加了一个向右和向下的 step 必须一致的约束不是么
    letianqiu
        3
    letianqiu  
    OP
       2017-08-18 20:33:58 +08:00
    @menc 能否更加详细一点。要把所有的阶梯都找到, 感觉回溯只能找到一条最长的,而且如何避免重复呢。
    letianqiu
        4
    letianqiu  
    OP
       2017-08-18 20:37:21 +08:00
    @shard 能否具体一点。
    Magentaize
        5
    Magentaize  
       2017-08-18 20:40:58 +08:00
    行最简形矩阵
    shard
        6
    shard  
       2017-08-18 20:44:37 +08:00 via iPhone
    没审题,我沙壁。请无视
    bjrjk
        7
    bjrjk  
       2017-08-18 22:31:06 +08:00 via Android
    @shard 一楼说的就很对很好,就是动态规划
    geelaw
        8
    geelaw  
       2017-08-18 22:44:16 +08:00 via iPhone
    预处理每个位置开始往右往下可以有多少个 1,然后递推找出每个位置是否是某个阶梯的结束位置
    hezhe
        9
    hezhe  
       2017-08-19 00:54:45 +08:00 via Android
    能否使用 dfs?找到的点标记下,但有的点有又可能会出现新的阶梯中,要分类判断下。
    hxndg
        10
    hxndg  
       2017-08-19 02:49:43 +08:00
    好久没做题了。。。总感觉回溯或者搜索都必须注意时间复杂度啊,总感觉会爆栈
    Xs0ul
        11
    Xs0ul  
       2017-08-19 03:42:38 +08:00 via Android
    我想的居然是卷积,怕不是学傻了(
    victor97
        12
    victor97  
       2017-08-19 09:42:38 +08:00 via Android
    首先,每行每列求前缀和,可以快速判断某条线段是否全为 1。
    枚举所有位置,再枚举长度,向左上方找。
    因为不考虑重复,所以要找仅 1 step 的阶梯即可。
    总复杂度 O(n³)
    letianqiu
        13
    letianqiu  
    OP
       2017-08-19 09:50:07 +08:00
    @victor97 需要考虑重复。当前我能想到的就是对每一个元素枚举,从 size 和 step 分别增长,找到存在的阶梯之后,比较是不是 map 里已有的 path 的其中一部分,如果是,就说明是重复的,放弃这条 path, 否则记录下 path,扔到 map 里。感觉复杂度至少 O(n^4)
    victor97
        14
    victor97  
       2017-08-19 09:56:22 +08:00 via Android
    是 起点相同,size 相同,step 不同 算重复吗,
    还是我理解错了重复的意思?
    letianqiu
        15
    letianqiu  
    OP
       2017-08-19 10:36:36 +08:00
    @victor97 算重复。这种情况下,只需要保留 steps 最大的。
    victor97
        16
    victor97  
       2017-08-19 10:57:42 +08:00 via Android
    我的意思其实也是重复的只算一次。
    从左至右,从上到下,枚举位置,那么只要判断左上方一个台阶就够了。
    如果要记录位置长度,再找到满足要求的更新坐标;如果不记录位置长度,只找一阶的数量就是答案。
    letianqiu
        17
    letianqiu  
    OP
       2017-08-19 11:16:18 +08:00
    @victor97 不是很明白你的意思诶。我算法水平太弱了。为什么只判断左上方一个台阶就可以。我的想法很初级,就是枚举每一个位置,往右下方走,size 从最小的 2 开始,step 从 1 开始,所有 step 找遍之后。size 增加。但是觉得这样有很多重复的。比如一个全都是 1 的 matrix,从( 0,0 )开始可以走到底,当从( 1,1 )开始走时,很多路径其实在( 0,0 )的时候都走过了, 属于无效的。
    victor97
        18
    victor97  
       2017-08-19 11:26:47 +08:00 via Android   ❤️ 1
    因为左上方的所有位置都是统计过的,如果发现能组成一阶台阶,要么是新出现的台阶,要么之前就已经是台阶了,只是长度 + 1,算重复。
    letianqiu
        19
    letianqiu  
    OP
       2017-08-19 11:33:46 +08:00
    @victor97 明白了。不过你说的求前缀和有什么用,就算知道了某列或者某行全为 1,并不能说明什么啊。还是需要枚举每一个位置。
    letianqiu
        20
    letianqiu  
    OP
       2017-08-19 11:50:37 +08:00
    @victor97 还有个问题,怎么区分是新台阶还是长度+1 的旧台阶。是不是和我原始的想法类似,开 map 保留所有已知的台阶构造,如果不是新台阶,那么当前位置(x, y)的上方(x-1, y)和左上方(x-1, y-1)是属于已经存在的台阶的构造的一部分,此时将原始台阶的长度+1,否则就是新台阶,加入 map
    imn1
        21
    imn1  
       2017-08-19 12:13:56 +08:00
    原矩阵把 行 中连续的 1 保留,其他置为 0,得到新矩阵 A
    原矩阵把 列 中连续的 1 保留,其他置为 0,得到新矩阵 B
    AB 的交集(逻辑与)就是阶梯的角

    后面自己推吧
    imn1
        22
    imn1  
       2017-08-19 12:18:22 +08:00
    楼上#21 说的不严谨,但原题也没有说清楚

    #21 说的是 转角
    还需要排除“断层”
    letianqiu
        23
    letianqiu  
    OP
       2017-08-19 12:23:24 +08:00
    @imn1 如果全都是 1 的矩阵,这么操作之后,并没有任何变化啊。要求就是 i 找出所有的形如图片中的台阶。觉得#18 说得有道理啊
    imn1
        24
    imn1  
       2017-08-19 12:43:24 +08:00
    @letianqiu
    实际上我就是搞不清楚你原题中阶梯的定义
    例如
    11000
    01000
    01000
    011111
    这种是否也算阶梯

    其实最简单的方法就是
    把所有符合阶梯定义的图形都写出来,然后去矩阵中找交集(平移和竖移)
    这里问题就是矩阵越大,那阶梯图形就越多,而且阶梯不明确定义横向最大连续和纵向最大连续的话,阶梯的变化很多

    反正思路不应该是在矩阵中逐点“画”阶梯,而是把已知定义的阶梯整体在矩阵中匹配
    mrcn
        25
    mrcn  
       2017-08-19 12:47:05 +08:00 via Android
    @shard 二维 dp 感觉可以做吧
    只是想不出转移方程
    letianqiu
        26
    letianqiu  
    OP
       2017-08-19 12:53:05 +08:00
    @imn1 你给的这个例子不属于阶梯。阶梯必须是横向和纵向的长度相等。你的方法好高深。
    letianqiu
        27
    letianqiu  
    OP
       2017-08-19 12:54:53 +08:00
    @mrcn 对啊。对于状态转移方程这题完全没有思路。目前觉得#18 楼的方法比较可行。#21 的方法对我来说太过于高深了。大致能理解他的意思,但是完全驾驭不了
    victor97
        28
    victor97  
       2017-08-19 13:24:37 +08:00   ❤️ 1
    @letianqiu #20
    满足一阶台阶且不满足二阶台阶的就是新台阶。
    另外,不需要用 map,每个位置记录以它为结尾的所有阶梯就行。
    victor97
        29
    victor97  
       2017-08-19 13:28:50 +08:00
    @letianqiu #19
    前缀和是快速判断某个区间全为 1 用的。
    如果不用前缀和,每次判台阶的复杂度和是 size*step ;使用前缀和优化为 step。
    victor97
        30
    victor97  
       2017-08-19 13:32:59 +08:00
    @letianqiu
    使用前缀和判断是否是新台阶的复杂度是常数级别的。
    letianqiu
        31
    letianqiu  
    OP
       2017-08-19 14:16:46 +08:00
    @victor97 大致明白了。受益匪浅啊。非常感谢啊。只是对于“另外,不需要用 map,每个位置记录以它为结尾的所有阶梯就行。”还有点点疑问。每个位置可能是不同 size 的阶梯的结尾,如果不开个 map 保存,如何能够记录。也许我没表达清楚题目要求,题目需要记录所有 size (宽度)下所有不同 steps (高度)的阶梯。所以我就想保存一个 map,key 是 size,value 还是一个 map,这个 map 的 key 是 steps,value 是阶梯的结尾位置的坐标。一个位置不可以出现在同一个 size 下,不同的高度的阶梯里。但是可以出现在不同的 size 的阶梯中。
    letianqiu
        32
    letianqiu  
    OP
       2017-08-19 19:44:45 +08:00
    @victor97 再次感谢你啊。按照你的思路,我基本上实现了。就是关于前缀和那一块没懂,我是用了五个 for 循环判断台阶的。比较傻
    Xs0ul
        33
    Xs0ul  
       2017-08-19 21:07:36 +08:00
    @imn1 #23 拿已知定义匹配倒是和我想到一块儿去了,用卷积就行(
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5411 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 06:46 · PVG 14:46 · LAX 23:46 · JFK 02:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.