这…以后谁还敢连公司WIFI
公司这波操作,真把打工人整清醒了:连个公司Wifi,最后能给你导出一份“摸鱼尸检报告”。63个人,平均工作占比42.5%,这数字一出来,办公室空气都得安静三秒。
最狠的不是迟到,是细到离谱。谁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 这题这样写是够用的。