Fork me on GitHub

算法进阶心法

算法高手养成体系

一、筑基阶段(1-3个月)

武器库建设

数据结构:

  • 数组
    前缀和、差分数组、双指针技巧(快慢指针/对撞指针)
  • 链表
    环形检测(Floyd龟兔算法)、LRU缓存实现

  • 红黑树旋转规则、B+树在数据库索引的应用

  • 邻接表与邻接矩阵的存储差异,Dijkstra堆优化版时间复杂度推导

算法范式:

  • 分治
    Karatsuba大数乘法(时间复杂度$O(n^{\log 3})$)
  • 贪心
    Huffman编码的熵最优性证明
  • DP
    背包问题状态压缩技巧(滚动数组)

每日训练

  1. 完成《算法导论》第1-15章课后习题(重点:递归式求解主方法)
  2. 在LeetCode按类型刷题,每日3道(Easy 1, Medium 2)

二、思维强化阶段(3-6个月)

高阶算法模式

位运算魔法:

  • 用XOR找缺失数(LC268)
  • 快速幂算法(矩阵快速幂解斐波那契)

空间换时间:

  • 单调栈解决Next Greater Element(LC496)
  • 跳表(SkipList)实现$O(\log N)$查询

数学建模:

  • 约瑟夫环递推公式推导
  • 用中国剩余定理解决周期问题(LC1250)

实战突破:

  1. 参加每周LeetCode周赛,目标进入前10%
  2. 实现《算法竞赛入门经典》中的STL轮子(手写红黑树)

三、领域专精阶段(6-12个月)

分支选择与深化

机器学习算法:

  • 推导XGBoost损失函数泰勒展开过程
  • 手写SVM对偶问题求解器(SMO算法)

分布式算法:

  • Raft协议Leader选举的随机超时机制
  • Gossip协议在Cassandra中的应用

几何计算:

  • 凸包Graham扫描法实现
  • 使用扫描线算法求矩形并集面积(LC850)

专项训练:

  1. 在Codeforces刷2200+分的计算几何题目
  2. 复现Google Spanner的TrueTime API设计

四、思维跃迁训练法

降维打击法

  • 将字符串匹配问题转化为自动机(AC自动机实现)
  • 用FFT加速多项式乘法(大数乘法优化)

极限压榨法

  • 在内存限制1MB下实现外排序(多路归并)
  • 用位图处理40亿整数去重(LC原题变形)

五、工具链配置

调试神器

# 重定向调试工具
import pdb
pdb.set_trace()

02. 双指针-有两个输入, 两个都需要遍历完

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
fun twoPointers(nums1: IntArray, nums2: IntArray) {
var pointer1 = 0
var pointer2 = 0

while (pointer1 < nums1.size && pointer2 < nums2.size) {
// 处理指针1和指针2对应位置的元素
// ...

// 移动指针
pointer1++
pointer2++
}

// 处理剩余未遍历完的元素
while (pointer1 < nums1.size) {
// 处理指针1对应位置的元素
// ...
pointer1++
}

while (pointer2 < nums2.size) {
// 处理指针2对应位置的元素
// ...
pointer2++
}
}

03. 滑动窗口

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fun slidingWindow(nums: IntArray, k: Int): Int {
val n = nums.size
var sum = 0
var maxSum = 0

// 计算第一个窗口的和
for (i in 0 until k) {
sum += nums[i]
}

maxSum = sum

// 滑动窗口
for (i in k until n) {
// 新窗口的和等于之前窗口的和加上新进入窗口的元素,减去滑出窗口的元素
sum += nums[i] - nums[i - k]
// 更新最大和
maxSum = maxOf(maxSum, sum)
}

return maxSum
}

04. 构建前缀和

正文

以下是一个前缀和算法的常见模板:

1
2
3
4
5
6
7
8
9
10
fun prefixSum(nums: IntArray): IntArray {
val prefixSum = IntArray(nums.size + 1)

// 计算前缀和数组
for (i in 1..nums.size) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1]
}

return prefixSum
}

在这个模板中,我们使用一个额外的数组 prefixSum 来存储原始数组 nums 的前缀和。通过遍历原始数组,我们可以计算每个位置的前缀和并存储在 prefixSum 中。

使用前缀和数组 prefixSum,我们可以高效地回答多个查询,例如计算某个区间的和。假设我们需要计算区间 [left, right] 的和,我们可以使用如下方式获取结果:

1
val sum = prefixSum[right + 1] - prefixSum[left

这个计算结果即为原始数组中从位置 left 到位置 right 的元素之和。
请注意,在模板中,前缀和数组 prefixSum 的长度比原始数组 nums 的长度多了一个元素。这是为了方便计算区间和时的边界情况。

05. 高效的字符串构建

正文

以下是一个高效的字符串构建算法模板:

1
2
3
4
5
6
7
8
9
fun buildString(chars: List<Char>): String {
val sb = StringBuilder()

for (ch in chars) {
sb.append(ch)
}

return sb.toString()
}

在这个模板中,我们使用 StringBuilder 来构建字符串。StringBuilder 是可变的字符串类,可以高效地进行字符串的拼接操作。

我们通过遍历字符列表 chars,逐个将字符添加到 StringBuilder 中。最后,通过调用 toString() 方法,将 StringBuilder 转换为最终的字符串结果并返回。

使用 StringBuilder 的好处是它避免了在每次拼接字符串时创建新的字符串对象,从而提高了性能和效率。特别是在需要频繁拼接大量字符串的情况下,使用 StringBuilder 可以避免不必要的性能损耗。

使用这个模板,你可以根据具体需求构建字符串。可以根据问题的要求在遍历过程中进行一些字符处理、条件判断等操作。

06. 链表-快慢指针

正文

在模板中,我们使用两个指针,一个指针每次向后移动一个节点,另一个指针每次向后移动两个节点。如果链表中存在循环,快指针最终会追上慢指针,这样我们就可以判断出链表有循环。如果链表没有循环,快指针会先到达链表的末尾,此时我们就可以判断链表没有循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fun hasCycle(head: ListNode?): Boolean {
var slow = head
var fast = head

while (fast?.next != null && fast.next?.next != null) {
slow = slow?.next
fast = fast.next?.next

if (slow == fast) {
return true
}
}

return false
}

08. 找到符合确切条件的子数组数

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
var count = 0
var total = 0
var left = 0

for (right in nums.indices) {
total += nums[right]

while (left <= right && total > goal) {
total -= nums[left]
left++
}

if (total == goal) {
count++

// 统计连续的0
var temp = left
while (temp <= right && nums[temp] == 0) {
count++
temp++
}
}
}

return count
}

09. 单调递增栈

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
fun monotonicStack(nums: IntArray): IntArray {
val stack = mutableListOf<Int>()
val result = IntArray(nums.size) { -1 }

for (i in nums.indices) {
while (stack.isNotEmpty() && stack.last() < nums[i]) {
stack.removeAt(stack.size - 1)
}

// 在这里可以根据题目需求进行处理
// 例如:找到栈中元素的下一个更大元素
if (stack.isNotEmpty()) {
result[i] = stack.last()
}

stack.add(nums[i])
}

return result
}