(P0) leetcode 基础速通

动机、参考资料、涉及内容

leetcode 算法题一些基础数据结构, 标准库的使用

C++ STL 容器相关方法

这个链接底部有一张表梳理容器的全部方法: https://en.cppreference.com/w/cpp/container

通用成员函数, 迭代器, range based for

通用的成员函数名有:

• push_back, pop_back
• begin, end, rbegin, rend: 返回迭代器
• front, back: 返回首/尾元素

#include<vector>
#include<iostream>
using namespace std;

int main(){
    int n = 5;
    vector<int> vec(n, 0);

    for (size_t i=0; i<5; i++){
        vec[i] = i;
    }

    for (auto const &item: vec){
        cout << item << " ";  // item 分别是 vec[0], vec[1], ... 的常引用
    }
    cout << "\n";
    auto it = vec.begin();  // 这里的 auto 实际上是 vector<int>::iterator
    auto const cit = vec.begin();  // 这里的 auto 是 vector<int>::const_iterator
    cout << *cit << endl;

    // 反向迭代器: rbegin 是第 n - 1 个元素对应的迭代器, rend 是第 -1 个元素对应的迭代器
    for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " ";
    }
    cout << "\n";
}

vector

vector 的 push_back, emplace_back

unordered_map, unordered_set

map, set

multiset, multimap, unorderd_multiset, unordered_multimap

不带 multi 的表示键不允许重复, 带 unordered 采用哈希表实现, 不带 unordered 采用红黑树实现(因此支持范围查找). 头文件不区分 multi, 也就是:

• #include<map>: 包含 map 与 multimap
• #include<set>: 包含 set 与 multiset
• #include<unordered_map>: 包含 unordered_map 与 unordered_multimap
• #include<unordered_set>: 包含 unordered_set 与 unordered_multiset

deque(不常用)

stack, queue, priority_queue

stack, queue, priority_queue 均属于容器适配器

heap

堆相关的操作有些是通过算法来实现的, 基本模式是:

vector<int> vec{1, 4, 6, 0, 10};

// 插入需要两个步骤
vec.push_back(0);
push_heap(vec.begin(), vec.end());  // push_heap 是上浮

// 删除也需要两个步骤
vec.pop_heap(vec.begin(), vec.end());
vec.pop_back()

具体例子, 注意默认是大根堆, 如果需要使用小根堆, 那么 make_heap, pop_heap, push_heap 每次都要传入 greater<int>()

#include<vector>
#include<iostream>
#include<algorithm>   // for make_heap, pop_heap, push_heap
#include<functional>  // for std::greater
#include<cassert>     // assert 宏
using namespace std;

void print(vector<int> arr){
    for (auto x: arr)
        cout << x << " ";
    cout << "\n";
}

int main(){
    vector<int> arr{1, 3, 7, 2, 6};
    arr.pop_back();
    // 1 3 7 2
    print(arr);

    make_heap(arr.begin(), arr.end(), greater<int>());  // make_heap 用于建立堆, 默认是大顶堆, 传入第三个参数可以改为小顶堆
    // 1 2 7 3
    print(arr);
    assert(is_heap(arr.begin(), arr.end(), greater<int>()));

    arr.push_back(0);
    // 1 2 7 3 0
    print(arr);
    push_heap(arr.begin(), arr.end(), greater<int>());  // push_heap 的语义是将最后一个元素上浮至合适的位置
    // 0 1 7 3 2
    print(arr);

    pop_heap(arr.begin(), arr.end(), greater<int>());  // pop_heap 的语义是先交换 arr[0] 和 arr[n-1], 然后再让 arr[0] 下浮至合适的位置
    // 1 2 7 3 0
    print(arr);
    arr.pop_back();  // 手工调用成员函数 pop_back 删除原先的堆顶元素
    // 1 2 7 3
    print(arr);
    pop_heap(arr.begin(), arr.end(), greater<int>());
    // 2 3 7 1
    print(arr);
    // 2 3 7
    arr.pop_back();
    print(arr);
    
    return 0;
}

C++ STL algorithm

完整列表参考 https://en.cppreference.com/w/cpp/algorithm

sort, 仿函数, lambda 函数

// 此例为完整可运行的例子
#include<vector>
#include<algorithm>   // for std::sort
#include<functional>  // for std::greater, std::less
#include<iostream>    // for std::cout, std::endl

struct Compare {
    // 仿函数就是重载了 operator() 的雷
    bool operator()(int a, int b) {
        return a > b; // 降序
    }
};

int main(){
    std::vector<int> v1{1, 3, 2, 4, 6};  // C++11 一致性初始化的写法
    // sort 函数的第三个参数的语义是 func(a, b) -> a 是否小于 b
    std::sort(v1.begin(), v1.end(), Compare());  // 算法: 排序, 传入的参数是一个仿函数实例

    // lambda 函数的高级用法, 方括号内的内容是闭包
    auto print = [&v1](std::string const &rem)
    {
        for (auto const &a : v1)
            std::cout << a << ' ';
        std::cout << ": " << rem << '\n';
    };
    print("using function object");  // rem="using function object"

    std::vector<int> v2 = {1, 3, 2, 4, 6};
    // lambda 函数
    auto compare_lambda = [](int a, int b){return a > b;};
    std::sort(v2.begin(), v2.end(), compare_lambda);
    // 由于 v2 是 vector<int> 实际上传值效率也很快
    for (auto a: v2){
        std::cout << a << " ";
    }
    std::cout << ": " << "using lambda" << "\n";


    std::vector<int> v3 = {1, 3, 2, 4, 6};
    std::sort(v3.begin(), v3.end(), std::greater<int>());
    for (int i = 0; i < v3.size(); i++){
        std::cout << v3[i] << " ";
    }
    std::cout << ": " << "using standard library greater<T>()" << "\n";

    return 0;
}

lambda 函数的类型是无法显式写出, 但它确实有类型, 由编译器来生成. 在上面的例子里, 传入 lambda 函数或者仿函数时, 都会进行相应的模板实例化. 如果要强行写 lambda 函数的变量类型, 有两种方案:

auto cmp = [](int a, int b) { return a > b; };
decltype(cmp) another_cmp = cmp; // 使用 decltype 推导类型, C++11 特性

#include <functional>
// 所谓的类型擦除, 会影响性能. TODO
// 这里涉及到的 std::function, 与传统的函数指针的区别, 暂不深究: TODO
std::function<bool(int, int)> cmp = [](int a, int b) { return a > b; };
std::sort(v.begin(), v.end(), cmp);

Python 内置数据结构 (已基本完成)

Python 中关于数据结构的实现比较有限

列表, 字典, 集合, 元组

略

数据结构(collections): Counter, DefaultDict, deque

略

排序, 二分插入/查找

排序

x = [1, 3, 2, 4, 8, 7, 6, 5]
y = sorted(x)  # 排序结果放在另一个数组里
print("x", x)  # x = [1, 3, 2, 4, 8, 7, 6, 5]
print("y", y)  # y = [1, 2, 3, 4, 5, 6, 7, 8]
x.sort(key=lambda x: x, reverse=False)  # 可以指定 key, 以及是否倒序
print(x)       # x = [1, 2, 3, 4, 5, 6, 7, 8]

针对有序列表, bisect 提供了如下函数进行二分插入 (可以在此基础上进行二分查找)

import bisect
x = [1, 3, 4, 4, 5, 6, 6]
# 寻找插入位置的最左端点
idx = bisect.bisect_left(x, 4)
print(idx)
# 寻找插入位置的最右端点, bisect 是 bisect_right 的别名
idx = bisect.bisect_right(x, 4)  # bisect.bisect(x, 4)
print(idx)

# 进行插入, 类似的, 还有 insort_right(insort)
bisect.insort_left(x, 2)
print(x)

队列, 栈, 优先队列

queue.SimpleQueue (队列), queue.LifoQueue (栈), queue.PriorityQueue (优先队列) 只提供了如下方法:

• 取出队列里的第一个元素: get
• 放入一个元素: put
• 当前队列长度: qsize
• 获取队列里的第一个元素但不取出: 不提供

from queue import SimpleQueue, LifoQueue, PriorityQueue

q1 = SimpleQueue()
q1.put(1)
q1.put(2)
q1.put(3)
print(f"q1.qsize()={q1.qsize()}")  # 3
print(q1.get())                    # 1
print(q1.get())                    # 1

q2 = LifoQueue()
q2.put(1)
q2.put(2)
q2.put(3)
print(f"q2.qsize()={q2.qsize()}")  # 3
print(q2.get())                    # 3
print(q2.get())                    # 2

# 越小的越先出
q3 = PriorityQueue()
q3.put((1, "xxx"))  # 第一项是优限级
q3.put((3, "data"))
q3.put((2, "other data"))
print(f"q3.qsize()={q3.qsize()}")  # 3
print(q3.get())                    # (1, "xxx")
print(q3.get())                    # (2, "data")

堆: 含 top-k 算法

与优先队列一样, 堆的实现也是默认用了小根堆. 实现在 heapq 这个内置库中, 特点是直接给了一些函数对列表进行操作, 函数名也稍显奇怪:

heapify: 构建堆, heappop: 弹出, heappush: 压入, arr[0]: 取堆顶元素

高级特性:

heappushpop: 先 push 一个元素再 pop; heapreplace: 先 pop 再 push 一个元素; nlargest: 最大的 n 的元素(按降序给出); nsmallest: 最小的 n 个元素, 按升序给出. 备注: nlargest 和 nsmallest 不会修改原列表

ps: 堆和优先队列的区别, 堆是具体是数据结构, 一个满足特定条件的二叉树, 由于他是完全二叉树, 所以可以用数组实现. 而优先队列是抽象数据结构, 通常用堆来实现优先队列

import heapq

arr = [2, 1, 9, 10, 5, 6, 7]
heapq.heapify(arr)  # 原地转化为小根堆, O(n) 复杂度
print(arr)
print(arr[0])       # 堆顶元素, 相当于 top, 这是符合规范的做法
print(heapq.heappop(arr))  # 弹出堆顶元素
heapq.heappush(arr, 0)
print(arr)
print(heapq.heapreplace(arr, 1))  # 先pop再push
print(arr)
print(heapq.heappushpop(arr, 3))  # 先push再pop
print(arr)

# 目前为止, arr 是
# [2, 5, 3, 10, 7, 9, 6]

print(heapq.nlargest(2, arr, key=lambda x: x))  # 前 2 大的数 [10, 9], 原数组不动
print(arr)

print(heapq.nsmallest(3, arr))  # 最小的 3 个数, [2, 3, 5], 原数组不动
print(arr)

图: 拓扑排序

graphlib 标准库实际上只提供了拓扑排序功能: TopologicalSorter, 最重要的是 add (加入依赖关系) 和 static_order (获取拓扑排序结果) 方法

import graphlib

# key: 前驱节点集合
graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}

# B -> D, C -> D, A -> C, A -> B
ts = graphlib.TopologicalSorter(graph)
try:
    print(tuple(ts.static_order()))  # A -> B -> C -> D
except graphlib.CycleError:
    print("Error")

如果希望追加点和前驱关系, 可以使用 add

import graphlib
ts = graphlib.TopologicalSorter()
ts.add("A")
ts.add("B", "C", "D")  # C 和 D 需要在 B 之前完成
ts.add("A", "B")       # B 需要在 A 之前完成
ts.add("E")
print(list(ts.static_order()))  # ['C', 'D', 'E', 'B', 'A']

C++ 高级

本节只做记录, 不做展开

480-滑动窗口中位数, 官方题解实现里使用了函数模板, 来避免为 std::priority_queue<int> (大根堆), std::priority_queue<int, std::vector<int>, std::greater<int>> (小根堆) 写重复代码. 可以替代大做法是使用 C++17 引入的 std::variant 搭配 std::visit 来实现