Python技术迷

拒绝月薪25000的大厂offer,去了月薪5k的体制内,发现当初劝我的同学进了大厂。。

听人劝,吃大亏。

这位网友听信同学的建议,放弃了月薪 2.5W 的大厂,毅然决然地奔向了 5K 的体制内,结果回头一看,那个劝他去体制内的同学,却已经在大厂里快乐摸鱼,年终分红,甚至可能在晒着股权激励了……这不就是劝人考公,自己进大厂的现实版吗?

Image

程序员选择真的很重要。大厂虽卷,但至少钱多;体制内虽稳,但成长速度会大打折扣。

当然,每个人追求不同,不能简单说哪个更好,但这个事最扎心的地方是——劝你“躺平”的人,自己却在拼命往上爬!

所以,选择之前一定要问问自己:你图什么?是钱?是安稳?还是只是听了别人的忽悠? 毕竟,别人给的建议,可能只是他们嘴上的“理想”,而他们实际的人生轨迹,完全是另一回事啊!【备注:文末可领最新资料】。

算法题:消除游戏

当然,作为一个爱折腾算法的程序员,我最近又刷到了一道挺有意思的题——消除游戏。这题的设定挺简单,给你一个从 1 到 ( n ) 的数字列表,每次删除列表中的偶数,重复这个操作,直到只剩一个数字为止,问你最后剩下的数字是多少。

这个题一看就让人想起经典的约瑟夫环或者丢手绢游戏,不过它的规则是固定的,每轮都从左往右删掉偶数,再从剩下的数字中重复这个过程。

看着这个游戏规则,我脑子里先蹦出来的就是模拟,毕竟最直接的方法就是按照规则操作一遍:

def last_remaining(n):
    nums = list(range(1, n + 1))
    left_to_right = True

    while len(nums) > 1:
        if left_to_right:
            nums = nums[1::2]  # 从左到右,删掉偶数
        else:
            nums = nums[::-1][1::2][::-1]  # 反向删掉偶数
        left_to_right = not left_to_right  # 方向切换

        return nums[0]

print(last_remaining(9))  # 输出 6

这个方法很直观,但是效率感人,时间复杂度是 ( O(n) ),空间复杂度也要 ( O(n) )。要是 ( n ) 变大,这代码就跑得像🐢一样。

那有没有更聪明的方法呢?当然有!我们来分析一下这个消除规则的数学性质。

  • 第一轮 从 1, 2, 3, ..., n 里删掉所有偶数,剩下的是 ( 1, 3, 5, 7, ... ) 也就是等差数列。
  • 第二轮 从剩下的数里反方向再删一遍偶数,继续缩小范围。
  • 第三轮、第四轮…… 这个过程一直持续到最后只剩下一个数字。

聪明的人可能已经发现,这个过程可以反向推导回来,每次相当于把原来的数列缩小一半,并且始终是从 1 开始的等差数列。

公式解法

经过数学推导(省略一堆推导过程,否则你们要翻白眼了😂),最后剩下的数字遵循这样的递推公式:

Image

直接上代码:

def last_remaining_math(n):
    return 1 if n == 1 else 2 * (n // 2 - last_remaining_math(n // 2) + 1)

print(last_remaining_math(9))  # 输出 6

这个方法的时间复杂度降到了 **( O(\log n) )**,而且只用 ( O(1) ) 额外空间,完美优化 🎯!

更优雅的迭代解法

如果递归不太符合你的审美,那可以改成迭代的形式:

def last_remaining_iter(n):
    remaining = n
    step = 1
    head = 1
    left = True

    while remaining > 1:
        if left or remaining % 2 == 1:
            head += step  # 头部的数字变化
        step *= 2
        remaining //= 2
        left = not left  # 方向切换

    return head

print(last_remaining_iter(9))  # 输出 6

这段代码的逻辑也很好理解,每一轮步长翻倍,剩余数量减半,并且在从左向右或者从右向左消除的时候,有不同的更新方式。

总结

如果你是面试遇到这道题,记住三件事:

  1. 直接模拟的方法很直观,但性能很差,尽量不用。
  2. 递归方式是最简洁的公式解法,适合递归思维的人。
  3. 迭代方式是最稳定、最面向工程的解法,适合日常实战。

刷算法题就像写代码,理解本质比记住套路更重要,不然面试的时候一紧张,背的东西就全忘了。

最后,我为大家打造了一份deepseek的入门到精通教程,完全免费:https://www.songshuhezi.com/deepseek

也可以看我写的这篇文章《DeepSeek满血复活,直接起飞!》来进行本地搭建。

对编程、职场感兴趣的同学,大家可以联系我微信:golang404,拉你进入“程序员交流群”。
🔥虎哥私藏精品 热门推荐🔥

虎哥作为一名老码农,整理了全网最全《python高级架构师资料合集》。

资料包含了《IDEA视频教程》、《最全python面试题库》、《最全项目实战源码及视频》及《毕业设计系统源码》,总量高达650GB,全部免费领取