DSA 清单

[xxleyi]

DSA 困境分析：底子薄，训练量不达标，平时工作与算法毫不沾边

DSA 破局之道：盯基础，抓训练量，工作之余，周期性重复练习

DSA 锦上添花：借机略通 C++、Java

DSA 刷题指北：

1. azl LeetCode Solutions' Record
2. Cracking the coding interview

---

• 二分查找：三种类型
• 括号匹配：从简单到复杂
• 表达式解析：从简单到复杂
• 排序（一）：冒泡、选择、插入、希尔
• 排序（二）：归并、快排、基数、桶
• 极值：优先级队列，完全二叉堆
• 二叉树：四种遍历以及相关操作
• 链表：遍历、排序、归并等操作

绪论

算法

ADT

复杂度度量与分析

递归

---

向量

二分查找的三个版本

起泡排序与归并排序

---

列表

插入、选择、归并排序

---

栈与队列

栈与递归

逆序输出、递归嵌套、延迟缓冲、逆波兰表达式

循环分配器、银行服务

---

二叉树

四种遍历

---

图

遍历

搜索

拓扑排序

---

搜索树

二叉搜索树

平衡二叉搜索树

AVL 树

---

高级搜索树

伸展树

B-树

红黑树

kd-树

---

词典

跳转表

散列表

散列应用

---

优先级队列

完全二叉堆

---

串

串匹配蛮力算法

KMP 算法

BM 算法

Karp-Rabin 算法

---

排序

快速排序

选取中位数

希尔排序

---

算法类别

分而治之

减而治之

貌似简明的递归

至拙至巧的迭代

二分

滑动窗口

动态规划

贪婪

回溯

位运算

[xxleyi]

二分查找：三种类型
#166 #1

[xxleyi]

括号匹配：从简单到复杂

# only '(' and ')'
def match(s):
    l_size = 0
    for i in s:
        if i == '(': l_size += 1
        else: l_size -= 1
        if l_size < 0:
            return False
    return l_size == 0

# or
def match(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        elif stack:
            stack.pop()
        else:
            return False
    return not stack

# when many kinds of brackets, stack is the only good way
def match(s):
    mapping = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for i in s:
        if i in mapping:
            stack.append(i)
        elif stack:
            if mapping[stack.pop()] != i:
                return False
        else:
            return False
    return not stack