Python技术迷

这…以后谁还敢连公司WIFI

公司这波操作,真把打工人整清醒了:连个公司Wifi,最后能给你导出一份“摸鱼尸检报告”。63个人,平均工作占比42.5%,这数字一出来,办公室空气都得安静三秒。

Image

最狠的不是迟到,是细到离谱。谁10:55才上线,谁小红书刷了906条,谁BOSS直聘点了50次,谁一边挂着全程在线一边工作只占7.1%,全给你排得明明白白。网友都看乐了,有人说“以后流量当饭吃”,还有人说“HR看完估计先盯69号,再盯155号”。

但你别说,这玩意最吓人的不是抓摸鱼,是它真能把人一天活成后台数据。你以为自己在工位上演正常上班,其实系统那边已经给你打上“购物138条、建议介入”的标签了。以后谁还敢随手连公司Wifi,连摸鱼都得先开热点。

算法题:摘樱桃

这题一上来就别想着贪心。

你站在左上角,走到右下角摘樱桃,回来还得再走一遍。很多人第一反应是:去的时候尽量多摘,回来的时候再补漏。这个思路我第一眼就不太信,因为前一趟走法会直接影响后一趟,两个过程根本不是独立的。你以为自己在做两次路径搜索,实际上是在做一件事:两个人同时从左上角走到右下角,只不过步数同步。这个转法很关键,题一下就顺了。参考的行文气质我按你给的几篇技术文去校了下,但下面内容是我重新写的,不复述原文。

题目里有三种格子:

  • 1:有樱桃,能摘
  • 0:空地,能走
  • -1:刺,不能走

难点不在走路,在“同一个樱桃不能摘两次”。

所以我一般这么想:设两个人同时出发,都只能向右或者向下。走了 k 步之后,第一个人在 (x1, y1),第二个人在 (x2, y2),因为步数相同,所以有:

y1 = k - x1
y2 = k - x2

这样状态就能压成三个维度:dp[k][x1][x2],表示两个人都走了 k 步时,分别站在 (x1, k-x1) 和 (x2, k-x2),此时最多能摘多少樱桃。

这里有个细节很容易写脏:如果两个人站在同一个格子,这个格子的樱桃只能算一次。

状态转移也不复杂。两个人每一步都只有“向下”或“向右”两种选择,所以前一个状态一共就四种来源:

  • 上上
  • 上左
  • 左上
  • 左左

把无效坐标、荆棘格子过滤掉,再取最大值就行。

代码我给你一版能直接跑的,没搞那些花里胡哨的写法:

defcherryPickup(grid):
    n = len(grid)
    neg = float('-inf')

    dp = [[neg] * n for _ in range(n)]
    dp[0][0] = grid[0][0]

for k in range(1, 2 * n - 1):
        new_dp = [[neg] * n for _ in range(n)]

for x1 in range(max(0, k - n + 1), min(n, k + 1)):
            y1 = k - x1
if grid[x1][y1] == -1:
continue

for x2 in range(max(0, k - n + 1), min(n, k + 1)):
                y2 = k - x2
if grid[x2][y2] == -1:
continue

                best = dp[x1][x2]

if x1 > 0:
                    best = max(best, dp[x1 - 1][x2])
if x2 > 0:
                    best = max(best, dp[x1][x2 - 1])
if x1 > 0and x2 > 0:
                    best = max(best, dp[x1 - 1][x2 - 1])

if best == neg:
continue

                gain = grid[x1][y1]
if x1 != x2 or y1 != y2:
                    gain += grid[x2][y2]

                new_dp[x1][x2] = best + gain

        dp = new_dp

return max(0, dp[n - 1][n - 1])

这段代码的味道就在这:不是分别算“去”和“回”,而是一次性把冲突处理掉。两个路径同步推进,共享一个时间轴。这样“重复摘樱桃”的问题天然就没了,不需要后面再补丁式修修补补。

复杂度也比较稳,时间复杂度 O(n^3),空间复杂度 O(n^2)。LeetCode 这题这样写是够用的。