Python技术迷

一句话一年多 12k,很多人在薪资谈判上吃亏,不是因为能力不够,是因为不敢开口。

候选人面试谈薪,HR问期望,他没缩着,直接报了28k。HR一听,低头看简历,憋了几秒,说他们这边最多只能给25k。

很多人到这一步就怂了,心里想着算了算了,有工作就行。但他没急着点头,只是补了一句:我手里还有差不多价位的机会,不过更想来你们这边,能不能再帮我确认下空间?

Image

结果HR去找领导聊了一圈,回来一句:28k可以。

就这么几句话,一个月差3k,一年就是三万多。你说这钱是能力涨出来的吗?不完全是,更多是敢不敢开口。

职场里很多报价,第一口真不一定是底线。你别一听“最多”就当圣旨。语气稳一点,别跪着谈,也别上来就硬刚,问一句有没有空间,可能真就不一样了。

今日算法题

松鼠一开始不在树上,这个条件很容易被写废。

我见过有人上来就 DFS,状态里放松鼠位置、坚果集合、当前步数。代码能跑,样例也能过,一提交就被数据教做人。这个题不是搜索题,真按“松鼠搬坚果”的过程模拟,方向就歪了。

题目大概是这样:有一棵树,一个松鼠位置,一堆坚果。松鼠每次只能拿一个坚果,拿到以后必须送回树下,最后要求总路程最短。

这里我第一眼看的不是网格大小,也不是坚果数量,而是这句话:

松鼠一开始在 squirrel,不在 tree。

如果松鼠一开始就在树上,那每个坚果的代价很死:

tree -> nut -> tree

也就是每个坚果都走两遍。

所以可以先把所有坚果都当成“从树出发再回树”来算:

base = 所有坚果到树距离 * 2

麻烦只出在第一个坚果。

因为第一个坚果不是从树出发,而是从松鼠当前位置出发。后面送回树之后,松鼠就在树下了,剩下的坚果都跟普通情况一样。

也就是说,只需要挑一个“第一个捡的坚果”。

原本这个坚果的代价是:

tree -> nut -> tree

现在变成:

squirrel -> nut -> tree

后面的 nut -> tree 没变,变的只有前半段:

tree -> nut

被替换成:

squirrel -> nut

所以哪个坚果适合第一个捡?就看它能省多少。

省下来的距离是:

dist(tree, nut) - dist(squirrel, nut)

这个值越大越好。

这里不要想复杂。不是离松鼠最近的坚果一定最好,也不是离树最远的一定最好。它看的是差值。

比如一个坚果离松鼠很近,但离树也很近,那省不了多少。另一个坚果离树很远,松鼠过去又刚好近,这种才赚。

代码我一般就这么写,不绕:

from typing import List


classSolution:
defminDistance(
        self,
        height: int,
        width: int,
        tree: List[int],
        squirrel: List[int],
        nuts: List[List[int]]
    )
 -> int:

defmanhattan(a: List[int], b: List[int]) -> int:
return abs(a[0] - b[0]) + abs(a[1] - b[1])

        total = 0
        best_gain = -10**9

for nut in nuts:
            tree_cost = manhattan(tree, nut)
            squirrel_cost = manhattan(squirrel, nut)

            total += tree_cost * 2

            gain = tree_cost - squirrel_cost
if gain > best_gain:
                best_gain = gain

return total - best_gain

这里的 height 和 width 没用上,不是漏了。

这题走的是曼哈顿距离,只要坐标合法,网格边界对最短路没有影响。上下左右走,两个点之间最短就是行差加列差。

再拿一组小数据过一下:

tree = [2, 2]
squirrel = [4, 4]
nuts = [[3, 0], [2, 5]]

到树的距离:

[3,0] -> 3
[2,5] -> 3
base = 3*2 + 3*2 = 12

松鼠到坚果:

[4,4] -> [3,0] = 5,gain = 3 - 5 = -2
[4,4] -> [2,5] = 3,gain = 3 - 3 = 0

选第二个坚果先捡,不亏也不赚,答案还是 12。

如果你写出来的逻辑在反复考虑“下一颗坚果去哪捡”,基本可以停一下了。松鼠每次送完坚果都会回到树下,后面的起点都一样,只有第一次特殊。

这题卡的不是代码量,是别把“模拟”两个字当真。真正要模拟的只有第一次出发。其余全是固定账。