NG找工投简历记录贴

那只有为xinyi祈祷了。

很感谢你写这么多可是并没有回答我的问题……

DFS里记visited不算memo的话你们说的DFS+memo到底是在memo啥?

你举例的斐波那契并不是一个DFS问题。虽然可以构造出图但是永远需要全图遍历,而DFS并不需要

nb, lu 老师这代码强啊,就是面试最好换一门语言

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        memo = {}
        m,n = len(matrix), len(matrix[0])
        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        def dfs(i,j):
            if (i,j) in memo:
                return memo[(i,j)]

            temp = 1
            for dx, dy in dirs:
                nx, ny = i+dx, j+dy
                if 0<=nx<m and 0<=ny<n and matrix[nx][ny]>matrix[i][j]:
                    temp = max(temp, 1+dfs(nx,ny))

            memo[(i,j)] = temp
            return temp

        res = 0
        for i in range(m):
            for j in range(n):
                res = max(res, dfs(i,j))
        return res

还是看代码吧

当然在python里稍微优雅一点的写法是@lru_cache

为啥

艹,这是个图遍历问题吧…那肯定什么顺序遍历都等价啊……

所以请问这个写法到底是dfs+memo还是dfs+dp啊,我只会这么一种按照high bar要求能过吗哈哈


把楼爬完明白了,这应该是就是dfs+dp吧,看楼里的memo应该是cache的意思

你们都好强,我已经躺平了也懒得做题,给offer就给不给就算了
多的那点工资交完税也没差多少,躺平等退休比较实在
好想退休好想拿退休金,什么OKR KPI RSU 都不如PTO

1 个赞

找我有事?

性感泥潭,在线刷题

我觉得这个lru_cache有可能是大知识 @HenYouFenLiangDeRen
大知识憋了这么久也该跟老坛友们产生一些互动了……

翻了翻 submission

around = ((0, 1), (0, -1), (1, 0), (-1, 0))

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        
        def get_around(x, y):
            for dx, dy in around:
                nx, ny = x+dx, y+dy
                if 0 <= nx < m and 0 <= ny < n:
                    yield (nx, ny)
         
        @cache
        def dp(x, y):
            res = 1
            for nx, ny in get_around(x, y):
                if matrix[nx][ny] > matrix[x][y]:
                    res = max(res, 1 + dp(nx, ny))
            return res
        
        return max(dp(x, y) for x in range(m) for y in range(n))
        
1 个赞

请换成 \color{red}{就} \color{red}{是} :yanjing:

那我倒是没那么确定 但这个接话的时机和语气太大知识了 很难想象有其他坛友cosplay 大知识

老师请相信自觉

刚去翻了下发现我居然也写过这道题 好久没看过leetcode了
想当初还在说每周打周赛 结果只正经打了三次(第一次快结束了才进去,只做了两道题,1500->1520+ :clown_face:)然后因为感恩节出去玩缺勤了就再也没打开过leetcode了 分数停留在1900多 :yaoming:

笑死我了,我上回发帖的时候就在想要是有人叫 @lru_cache 就好玩了……
不过怎么冒了个泡就不见了……

话说 @Ryan2022 倒是还经常冒泡……

1 个赞

那你应该再重新爬爬楼……
@Lunasol 的意思是这个写法过不了面试……

所谓的 high bar 我前面已经说了,需要

看起来很多人都没听懂,我来具体解释一下什么叫“从小到大填表”吧……

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{red}\,水老师小课堂\,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

在讲这道题之前,咱们先考虑简单一点的问题,假如不是找 longest increasing path in a matrix,而是找一维数组里的 longest increasing subarray,那应该怎么做?

所谓 DP 其实就像数学归纳法,刚开始只知道最小号问题的答案,之后不断地利用已经得到的答案来解决更大一号的问题。我们可以一边解决问题一边把答案填在一个表格里。

举个例子,假如数组是 2, 3, 1, 4, 6, 5,怎么填表来找到 longest increasing subarray 呢?

array 2 3 1 4 6 5
dp ? ? ? ? ? ?

我们从左往右来填表,表格里的答案表示我们沿着数组从左往右走到当前位置时,包含当前元素在内的 longest increasing subarray (so far) 到底有多长。

刚一开始,我们只走到数组的第一个元素 2,那么包含当前元素在内的 longest increasing subarray so far 是什么呢?其实想都不用想,就是这个元素自己呗!这其实就是所谓的“最小号问题”,也就是说对于只有一个元素的数组,longest increasing subarray so far 的长度就是 1:

array 2 3 1 4 6 5
dp 1 ? ? ? ? ?

接下来我们要干的事情就是不断地利用这个小号问题的答案来推导出更大一号问题的答案。怎么推呢?我们走到下一个元素 3,发现 3 比 2 大,这说明什么?说明 longest increasing subarray 又变长了!那我们填表的时候就在小一号问题的答案基础之上加一:

array 2 3 1 4 6 5
dp 1 2 ? ? ? ?

接下来我们走到下一个元素 1。很不幸,1 比 3 小,说明我们的 streak 断掉了,只能重新再来。[1] 这时候 longest increasing subarray so far 就是 1 自己了(因为要包含当前元素),长度为 1:

array 2 3 1 4 6 5
dp 1 2 1 ? ? ?

继续往右走,4 比 1 大,答案喜加一:

array 2 3 1 4 6 5
dp 1 2 1 2 ? ?

继续往右走,6 比 4 大,答案再加一:

array 2 3 1 4 6 5
dp 1 2 1 2 3 ?

最后一个元素 5 比 6 小,怎么办?断掉了就重来呗……

array 2 3 1 4 6 5
dp 1 2 1 2 3 1

于是整个表格就填完了。那么整个数组的 longest increasing subarray 长度是多少呢?其实就是表格里所有答案的最大值,也就是 3。

总结一下,我们所干的事情就是从左往右不断填表。这里面最小号问题的答案就是 dp[0] = 1,每次递推的逻辑是:

  • 如果数组当前元素比上一个元素更大,那么 dp[i] = dp[i-1] + 1
  • 否则,dp[i] = 1

当然这里面填表的顺序是很重要的,你不能先填了大号问题的答案再回来填小号问题的,毕竟咱们不是在演穿越剧……一维问题的表格是相对容易理解的,一眼就能看出来什么是小号问题、什么是大号问题。然而二维的问题就没那么容易了……

现在回到 Longest Increasing Path in a Matrix 这道题。这是一个二维的问题了,我们要填的表格到底是个什么东西呢?其实和上一道题是完全一样的,就是走到图里每一个位置的时候包含当前位置在内的 longest increasing path so far 到底有多长。什么意思呢?就拿原题里面的图来举例子吧……

image

比如说,当我们走到左下角的 2 的时候,longest increasing path so far 的长度就是 2,因为你可以通过 1→2 这样走过来。我们的目标就是要填满这样一个 3×3 的表格,填完之后表格里的最大值就是我们最终要的结果了。

可是这个表格应该按照什么顺序填呢?现在不再是一位数组了,没法直接从左往右填。这里面究竟什么是小号问题,什么是大号问题,怎样才能做到不“穿越”呢?

那就让我们先来想想最开始的情况。刚开始的时候,哪些位置的答案我们已经可以确定了?

请先思考一下,然后再继续看

没错,如果某一个位置 (i, j) 四周的邻居都比我大(或者和我一样),那我就能确定一定以及肯定地说,我的 longest increasing path so far 就是我自己,长度为 1,也就是 dp[i][j] = 1。这就是这道题里面的“最小号问题”。请注意,这里面的“最小号问题”可能不止一个位置。对于上图来说,在初始此刻我们已经可以填好如下表格了:

? ? 1
? ? ?
? 1 1

那接下来如何利用小号问题的答案来推导出更大一号问题的答案呢?

又到了思考时间

其实道理和最小号问题类似,如果某一个位置 (i,j) 四周还没有填表的邻居都比我大(或者和我一样),也就是说四周比我小的邻居都已经填好表了,那么我也可以确定一定以及肯定地说 dp[i][j] = max{四周所有比我小的邻居们的答案} + 1。

于是现在我们又可以多填一些答案了:

? ? 1
? 2 ?
2 1 1

有了这些答案,我们可以继续填更多的答案:

? 3 1
3 2 3
2 1 1

再来一轮:

4 3 1
3 2 3
2 1 1

这样整个表格就都填完了。如果你仔细观察的话,这个过程是不是很眼熟?

眼熟么?熟么?么??

如果你说拓扑排序确实没错,但哪怕你从没听说过拓扑排序,应该也能发现这其实就是个 BFS,每次填表的答案其实就是此时此刻 BFS 的层数。所以其实我们并不需要记录 dp[i][j],只需要一层一层地做 BFS,等最后结束时的层数就是最终结果了。

当然这里面还有一些技术细节,比如我们怎么知道什么时候轮到我可以填表了?我们可以记录一下每个位置四周有几个比我小的邻居还没填表,一边做 BFS 一边更新,当这个值为 0 的时候就表示我可以填表了。

最后放上代码吧,我在 @Lunasol 代码的基础上修改了一下,变量名就沿用鹿老师起的吧……

慎入
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
        out = [[0] * n for _ in range(m)]  # 有几个比我小的邻居还没填表
        queue = deque()

        for i in range(m):
            for j in range(n):
                for dx, dy in dirs:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] < matrix[i][j]:
                        out[i][j] += 1
                if out[i][j] == 0:
                    queue.append((i, j))

        res = 0
        while queue:
            res += 1
            for _ in range(len(queue)):
                i, j = queue.popleft()
                for dx, dy in dirs:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[i][j]:
                        out[nx][ny] -= 1
                        if out[nx][ny] == 0:
                            queue.append((nx, ny))
        return res

瞎折腾半天,时间空间复杂度和 @Lunasol 的记忆化搜索一样……

我真是闲得慌写了这么多,快赶上写篇游记花的时间了……


  1. @Lunasol 你刷题的 streak 断了么? ↩︎

25 个赞

支持水老师去出leetcode讲解!

1 个赞

我可没那闲心啊 :wulian:
我这是看到楼上的讨论实在有些捉急,就再来“因材施教”一把……

1 个赞

水老师的姿势水平很高啊。

1 个赞