Python技术迷

刚入职没几个月,成为了一坨服务的owner,因巧合触发了陈年代码的bug,导致s0事故,这个锅要背吗

刚看到个贴子:新人入职没多久,被拍成一坨老系统的 owner,一次巧合触发了陈年 bug,搞成 S0 事故,正纠结这锅是不是自己背。

Image

网友们吵得挺热闹,有的说“谁是 owner 谁背锅”,有的说“这明明是历史债务,凭啥砸新人头上”。我觉得这事吧,得拆开看: 如果你按流程操作、没有越权乱改,那技术上这是系统和团队多年的欠账,新人只是最后那个“按开关”的人,责任不该一股脑往你身上压;但只要你是 owner,复盘、补齐文档、推动修 bug,这些责任肯定跑不掉。

换个角度想,背“全部责任”不公平,但躲得干干净净也不现实。说到底,这次事故是你职业生涯里一堂很贵的课:会写在简历背后,也会写进你以后说话做事的底气里。

面试题:完美数

咱先把话说明白哈,这篇就是那种你坐地铁刷手机也能看懂的算法小文,不整那些特别夸张的词儿,就是聊聊「完美数」和 Python 怎么写。

完美数是个啥

先说定义,不然没法写代码。

一个正整数,它所有「真因子」的和,刚好等于它自己,这货就叫完美数。 真因子就是:能整除它、但又比它小的那些数。

举个最经典的:6

  • 6 的因子有:1, 2, 3, 6
  • 真因子就是去掉自己:1, 2, 3
  • 1 + 2 + 3 = 6,刚好等于自己,所以 6 就是完美数

再来一个 28:

  • 因子:1, 2, 4, 7, 14, 28
  • 真因子:1 + 2 + 4 + 7 + 14 = 28
  • 也满足,OK,完美数一个

日常里常见的完美数其实就那几个:6、28、496、8128……再往后就非常大了,平时写代码一般用不上那种体型的。

最直接的暴力解法

先别想优化,咱就用最朴素的想法走一遍。

思路就一句话:把 1 到 n-1 全部试一遍,能整除就累加,最后看和是不是等于 n。

翻成 Python 差不多这样:

defis_perfect_naive(n: int) -> bool:
"""最朴素版本,直接从 1 遍历到 n-1"""
if n <= 1:
returnFalse# 1 不算完美数

    s = 0
for i in range(1, n):
if n % i == 0:
            s += i
return s == n

你可以随手测几下:

print(is_perfect_naive(6))    # True
print(is_perfect_naive(28))   # True
print(is_perfect_naive(10))   # False

这个代码好处是特别好懂,坏处也很明显:太慢。 你想啊,如果 n 是 10 万,你要循环 1 到 99999,一次判断一个,时间复杂度是 O(n)。

如果题目让你「找出 10 万以内所有完美数」,这么写是勉强还行;要是上到 10^9,那基本就告辞了。

简单但很管用的优化

其实我们找因子没必要从 1 找到 n-1,这有点太实在了。

有个常识: 如果 i 能整除 n,那 n // i 也一定是 n 的一个因子,而且它俩是成对出现的,比如:

  • n = 28
  • i = 2,可以整除
  • 另一个因子就是 28 // 2 = 14

而且**一对因子中至少有一个不大于 sqrt(n)**,所以咱只需要从 1 遍历到 sqrt(n) 就行了,后半段因子用「配对」的方式加进去。

注意两个小细节:

  1. 因为是「真因子」,所以如果某次配出了 n 自己,要把 n 排除掉;
  2. i * i == n 的时候,i 和 n//i 是同一个数,不能加两遍。

用 Python 写就是这样:

import math

defis_perfect(n: int) -> bool:
"""利用 sqrt(n) 优化的完美数判断"""
if n <= 1:
returnFalse

    s = 1# 1 一定是因子,先加上
# 从 2 到 sqrt(n)
    limit = int(math.sqrt(n))
for i in range(2, limit + 1):
if n % i == 0:
            other = n // i
            s += i
if other != i:      # 避免平方根重复加
                s += other

return s == n

再来测一把:

for x in [2, 3, 4, 5, 6, 28, 496, 8128]:
    print(x, is_perfect(x))

这次的复杂度就是 O(√n),差距非常大。 比如 n = 10^8:

  • 朴素版要循环一亿次;
  • 优化版只要循环一万次左右,差了一万倍。

扫一段区间里的完美数

算法题里还有一种问法:给你一个上界,比如 1e5,问你「找出所有不超过它的完美数」。

其实就是在一个区间里,对每个数调用一次 is_perfect,然后把结果收集起来:

defperfect_numbers_in_range(limit: int):
"""返回 [1, limit] 区间内所有的完美数"""
    res = []
for n in range(2, limit + 1):
if is_perfect(n):
            res.append(n)
return res

if __name__ == "__main__":
    nums = perfect_numbers_in_range(10000)
    print("10000 以内的完美数:", nums)

你跑一下就能看到结果:[6, 28, 496, 8128]

这个写法在面试里基本就够交差了,面试官要是追问,你再顺嘴说一句「整体复杂度大概是 O(N√N),在 N 不是特别大的时候够用」。

你真要刷题,就把上面那两个函数背一下,手熟了,后面做类似「因子求和」「质因数分解」的题都能顺着这个思路来。 行,我先去喝口水,有别的算法你再扔过来一起整。

-END-

我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html

🔥虎哥私藏精品🔥

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