算法与数据结构¶

经典数据结构实现¶

平衡二叉树 + avl tree + red-black tree
嵌入式哈希表
二叉堆 (优先队列)

经典算法实现¶

排序¶

快速排序
归并排序

经典问题¶

数组¶

Two Sum 问题¶

分两种情况: 数组有序和数组无序

数组无序: (LC 1)

Brute force
Hash table

数组有序: (LC 167)

Two pointers
Binary search

一端步进, 另一端采用二分查找

Three Sum 问题¶

(LC 15)

Brute Froce (时间 O(n^3), 空间 O(1), TLE)

三个索引 i, j, k, i 从 0 开始, 止于 len - 3, j 从 i + 1 开始, 止于 len - 2, k 从 j + 1 开始, 止于 len - 1.
Brute Force + Set (时间 O(n^2), 空间 O(n), TLE)

所有元素入 set. 两个索引遍历, 检查两个索引的负数是否在 set 中, 是的话加入返回结果, 去重.

这个方法在元素最多的一个 case 上 TLE 了, LC 15 这题时间卡的比较细, 轻微优化就能 AC, 具体见方法 3.
先排序, 然后使用类似于 twoSum 的双指针法

这个方法一开始我也 TLE 了, 后来做了一点轻微的调整就 AC 了, 具体可见 git log 或者 leetcode 上的提交记录

延伸 (LC 16)

和 LC 15 的解法 3 类似, 同样也是先排序, 然后双指针. 可见 git 或者 leetcode 上的提交.

需要注意的是这里不需要处理左右指针重复元素的情况, 因为这里求得是差距最小. 像比如下面的情况, target 为 3, 起初 i, j, k 的位置是这样:

[1, 1, 1, 1, 2, 2, 3]

i j k

算得 1 + 1 + 3 = 4, 储存这个结果之后, 如果我们处理重复元素的话, 则 j, k 会移动到如下的位置 (注意和 LC 15 的处理重复元素还有轻微差别, LC 15 的话 j 会移动到 2 的位置. 这里我们不能移动到 2, 那样会漏掉一些结果):

[1, 1, 1, 1, 2, 2, 3]

i j k

这样继续算得 1 + 1 + 2 = 4, 然而我们错过了最佳答案: 1 + 1 + 1 = 3, 也就是如下的情况:

[1, 1, 1, 1, 2, 2, 3]

i j k

因此在这里我们不需要处理重复元素, 因为有可能这两个重复元素就会促成最佳答案.

选择问题 (最大第 k 个元素问题)¶

最小堆

字符串¶

trim (去掉头尾以及中间重复出现的空格):

for (i = 0, k = -1 ; s[i] != '\0' ; ) {
    if (s[i] == ' ' && (!i || s[i - 1] == ' ')) {
        while (s[++i] == ' ');
    } else {
        s[++k] = s[i++];
    }
}

if (s[k] == ' ') s[k] = '\0';
else s[k + 1] = '\0';