一、数的计算递归背后的分形思维题目回顾给定自然数nnn可以在其左侧不断添加不超过前一个数一半的数字问能生成多少个数。初看简单的递归deff(n):ifn1:return1ans1# 不作任何处理算一个foriinrange(1,n//21):ansf(i)returnans深度思考这其实是记忆化搜索的裸题这道题的本质是什么每一个数nnn的生成方案完全依赖于所有小于等于n/2n/2n/2的数的方案之和。这形成了一棵天然的递归树f(6) 1 f(1) f(2) f(3) 1 1 (1f(1)) (1f(1)) 6但等等——如果n≤1000n \leq 1000n≤1000纯递归会不会超时答案是不会。因为递归深度最多log2n\log_2 nlog2n且每个f(i)f(i)f(i)被重复计算的次数有限。但如果nnn扩大到10510^5105呢这就引出了动态规划的思想dp[0]*(n1)dp[1]1foriinrange(2,n1):dp[i]1sum(dp[1:i//21])更进一步利用前缀和优化可以将O(n2)O(n^2)O(n2)降到O(n)O(n)O(n)dp[1]prefix[1]1foriinrange(2,n1):dp[i]1prefix[i//2]prefix[i]prefix[i-1]dp[i]感悟递归是自顶向下的诗意DP是自底向上的务实。好的算法工程师能在两者之间自由穿梭。二、时间加法不要过度工程化题目给定aaa点bbb分求ttt分钟后的时间。我的解法利用 Python 的datetimefromdatetimeimportdatetime,timedelta aint(input())bint(input())tint(input())time1datetime(2000,1,1,a,b)deltatimedelta(minutest)time1deltaprint(time1.hour)print(time1.minute)反思这是优雅还是过度设计用datetime确实简洁但它背后创建了整个日期对象调用了 C 扩展对于这么简单的问题是否杀鸡用牛刀更底层的思考# 纯数学解法totala*60btprint(total//60%24)print(total%60)方案时间复杂度空间复杂度可读性适用场景datetimeO(1)O(1)O(1)较高极高复杂日期计算纯数学O(1)O(1)O(1)O(1)O(1)O(1)高简单时间运算感悟工程中没有绝对的最好只有最合适。datetime胜在语义清晰数学法胜在零依赖。面试时先写数学法展示基本功再提datetime展示工程意识——双保险。三、人物相关性分析双指针的华尔兹题目统计文本中Alice和Bob作为独立单词出现且相距不超过KKK个字符的次数。核心难点单词边界Bobbi不算Bob需要\b词边界字符距离不是单词距离是字符位置距离效率字符串长度可达10610^6106暴力O(n2)O(n^2)O(n2)会 TLE我的解法预处理 滑动窗口importre kint(input())sinput()# 预处理找出所有 Alice 和 Bob 的起始位置A[m.start()forminre.finditer(r\bAlice\b,s)]# Alice 起始位置B[m.start()forminre.finditer(r\bBob\b,s)]# Bob 起始位置count0left0right0lenBlen(B)forainA:# Alice 占据 [a, a5)Bob 占据 [b, b3)# 两者距离 max(起点差) - min(终点差) 的某种形式...# 实际上题目定义的之间字符数需要仔细处理La-k-3# Bob 最早可以出现的位置Rak5# Bob 最晚可以出现的位置# 移动左指针找到第一个 L 的 BobwhileleftlenBandB[left]L:left1# 移动右指针找到第一个 R 的 BobwhilerightlenBandB[right]R:right1# [left, right) 内的 Bob 都满足条件countright-leftprint(count)算法剖析为什么这是O(n)O(n)O(n)关键在于两个指针都只向右移动left指针一旦越过某个 Bob再也不会回头right指针随着 Alice 位置右移R增大right也只会右移这形成了经典的滑动窗口模式总时间复杂度O(∣A∣∣B∣)O(|A| |B|)O(∣A∣∣B∣)即线性。边界条件的艺术这里的L和R计算需要极其小心Alice长度为 5Bob长度为 3如果 Alice 在 Bob 前面距离 B - (A 5)如果 Bob 在 Alice 前面距离 A - (B 3)统一处理有效区间 [A - K - 3, A K 5]感悟双指针算法的精髓在于单调性。当一个问题具有如果iii满足条件则i1i1i1也可能满足的单调特征时双指针就是你的华尔兹舞伴。四、最大距离暴力中的数学直觉题目数列中两元素距离定义为∣i−j∣∣ai−aj∣|i-j| |a_i - a_j|∣i−j∣∣ai−aj∣求最大值。数据范围n≤1000n \leq 1000n≤1000允许O(n2)O(n^2)O(n2)暴力。nint(input())lslist(map(int,input().split()))num-1foriinrange(n):forjinrange(i1,n):curj-iabs(ls[j]-ls[i])nummax(num,cur)print(num)但如果n≤105n \leq 10^5n≤105呢绝对值展开后∣i−j∣∣ai−aj∣max{(iai)−(jaj)(i−ai)−(j−aj)(jaj)−(iai)(j−aj)−(i−ai)|i-j| |a_i - a_j| \max\begin{cases} (i a_i) - (j a_j) \\ (i - a_i) - (j - a_j) \\ (j a_j) - (i a_i) \\ (j - a_j) - (i - a_i) \end{cases}∣i−j∣∣ai−aj∣max⎩⎨⎧(iai)−(jaj)(i−ai)−(j−aj)(jaj)−(iai)(j−aj)−(i−ai)即max(∣(iai)−(jaj)∣,∣(i−ai)−(j−aj)∣)\max(|(ia_i) - (ja_j)|, |(i-a_i) - (j-a_j)|)max(∣(iai)−(jaj)∣,∣(i−ai)−(j−aj)∣)所以只需维护(iai)(ia_i)(iai)和(i−ai)(i-a_i)(i−ai)的最大最小值O(n)O(n)O(n)搞定# 进阶版 O(n) 解法max1max2-float(inf)min1min2float(inf)fori,xinenumerate(ls):max1max(max1,ix)min1min(min1,ix)max2max(max2,i-x)min2min(min2,i-x)print(max(max1-min1,max2-min2))感悟绝对值问题第一反应永远是去绝对值分类讨论。这不仅是技巧更是一种代数直觉——把几何问题转化为线性问题。五、进制转换计算机世界的翻译官题目实现任意进制2-16之间的转换。核心代码int_to_char0123456789ABCDEFchar_to_int{ch:ifori,chinenumerate(int_to_char)}deftrans(s,n,m):# Step 1: N进制 - 十进制num0forchins:numnum*nchar_to_int[ch]# Step 2: 十进制 - M进制ifnum0:return0answhilenum!0:ansint_to_char[num%m]num//mreturnans[::-1]进制转换的数学本质任意进制转十进制(2022)92×930×922×912×901472(2022)_9 2 \times 9^3 0 \times 9^2 2 \times 9^1 2 \times 9^0 1472(2022)92×930×922×912×901472代码中的num num * n char_to_int[ch]正是霍纳法则Horner’s Method将O(n)O(n)O(n)次乘法优化到最优。十进制转任意进制本质是不断取模相当于xdk⋅mkdk−1⋅mk−1⋯d0x d_k \cdot m^k d_{k-1} \cdot m^{k-1} \cdots d_0xdk⋅mkdk−1⋅mk−1⋯d0每次num % m得到最低位d0d_0d0然后num // m去掉最低位。感悟进制转换教会我们——所有进制都是十进制的投影。十进制是人类的直觉二进制是计算机的母语而算法是它们之间的翻译官。六、今日心法总结┌─────────────────────────────────────────┐ │ 1. 递归 → 找重叠子问题 → 考虑记忆化/DP │ │ 2. 字符串匹配 → 预处理 双指针/滑动窗口 │ │ 3. 绝对值最值 → 拆四种情况 → 维护极值 │ │ 4. 进制转换 → 霍纳法则 取模迭代 │ │ 5. 工程思维 → 没有最好只有最合适 │ └─────────────────────────────────────────┘写在最后刷题不是为了背诵模板而是为了训练思维的模式识别。当你看到左边添加不超过一半时能否想到递归树当你看到两个元素距离限制时能否想到滑动窗口当你看到绝对值求最值时能否想到分类讨论这些直觉才是算法竞赛给予我们最宝贵的财富。“代码会过时思维永流传。”如果你也在刷题路上欢迎留言交流。算法的世界一个人走很快一群人走很远。
