Python技术迷

真的被大厂人的存款搞破防了 一个36岁手握230万,问够不够躺平养老;另一个存够250万,说完全不想上班了。

一个大厂人36岁,卡里两百多万,认真发问:这点钱能不能不上班了。另一个更直接,攒到二百五十万,整个人已经对工位失去兴趣。

这哪是焦虑啊,这简直是把普通打工人的梦拿出来当选择题做。

人家的问题是“我能不能提前退休”,我的问题是“这个月别出意外,撑到发薪日”。同样是坐办公室、开会、被需求追着跑,有的人是在算现金流够不够躺,有的人是在算花呗还完还能不能点外卖。

Image

最扎心的是,人家也觉得自己累,也觉得上班没意思。可他烦的是怎么退出游戏,我们烦的是别被游戏踢出去。

这差距,真不是一句“都是牛马”能糊弄过去的。牛马和牛马之间,也有草料等级的。

算法题:找到所有的农场组

这题别上来就 DFS。

题目叫“找到所有的农场组”,给你一个 m x n 的矩阵,1 表示农田,0 表示空地。要返回每一块农田的左上角和右下角坐标。

我第一眼看这题,先看约束:每块农田一定是一个矩形,而且不同农田之间不会相邻。

这句话很关键。

有了这个前提,就没必要一格一格 flood fill。DFS 能做,但有点重,像拿扳手拧瓶盖。这里直接扫矩阵,遇到一块农田的左上角,再往右、往下找到边界就行。

比如这个矩阵:

1 1 0
1 1 0
0 0 1

结果就是:

[0,0,1,1]
[2,2,2,2]

问题在于,怎么判断当前这个 1 是不是一块农田的起点?

我一般不会额外搞个 visited。因为矩形农田有个特征:如果一个格子是某块农田的左上角,那么它的上面不是 1,左边也不是 1。

判断条件就是这两个:

i == 0or land[i - 1][j] == 0
j == 0or land[i][j - 1] == 0

这样扫到农田内部的点时,直接跳过。

代码可以写得很短:

from typing import List


classSolution:
deffindFarmland(self, land: List[List[int]]) -> List[List[int]]:
        rows, cols = len(land), len(land[0])
        ans = []

for r in range(rows):
for c in range(cols):
if land[r][c] == 0:
continue

                has_up = r > 0and land[r - 1][c] == 1
                has_left = c > 0and land[r][c - 1] == 1

if has_up or has_left:
continue

                bottom = r
while bottom + 1 < rows and land[bottom + 1][c] == 1:
                    bottom += 1

                right = c
while right + 1 < cols and land[r][right + 1] == 1:
                    right += 1

                ans.append([r, c, bottom, right])

return ans

这里有个细节,找 bottom 的时候只沿着当前列往下找,找 right 的时候只沿着当前行往右找。

为什么不需要检查整个矩形?

因为题目已经保证每块农田是矩形。如果没有这个保证,那这段代码就不够,要换成 DFS 或 BFS,把连通块完整扫出来。

这题最容易写复杂的地方,就是把它当成普通岛屿题。

岛屿题一般长这样:

1 1 0
0 1 1

形状可能歪歪扭扭,所以要 DFS。

但农场组不一样,它是矩形:

1 1 1
1 1 1

矩形就别递归了,直接找边界。

复杂度也正常,外层把矩阵扫一遍,时间是 O(m * n)。虽然里面有两个 while,但只在每块农田的左上角触发,整体不会炸。

空间复杂度是 O(1),不算返回结果。

这题我更推荐这种写法。不是因为 DFS 不行,而是因为这题给了矩形条件,不用白不用。题目里给的条件,很多时候就是在暗示你别走重路。