Fork me on GitHub

算法进阶心法

0 - 算法, 0.0 - 学习规划

算法高手养成体系

一、筑基阶段（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. 双指针-有两个输入, 两个都需要遍历完

0 - 算法, 0.1 - 算法模版

正文

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. 滑动窗口

0 - 算法, 0.1 - 算法模版

正文

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. 构建前缀和

0 - 算法, 0.1 - 算法模版

正文

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

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. 高效的字符串构建

0 - 算法, 0.1 - 算法模版

正文

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

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. 链表-快慢指针

0 - 算法, 0.1 - 算法模版

正文

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

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. 找到符合确切条件的子数组数

0 - 算法, 0.1 - 算法模版

正文

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. 单调递增栈

0 - 算法, 0.1 - 算法模版

正文

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
}