滑动窗口

可变滑动窗口

Input: array, target
Output: window
n = Length(array)
left = 0, right = 0
window = []
while(right < n)
    window.add(array[right++])
    while(window meets the conditions)
        do something
        window.remove(array[left++])      
    //res += left 越长越合法，即当窗口的conditions是'不满足某某条件'那么[0...left-1, right]都是满足条件的结果，个数为left-1-0+1=left个
return window

固定滑动窗口

Input: array, windowSize
Output: window
n = Length(array)
left = 0, right = 0
window = []
while(right < n)
    window.add(array[right++])
    if(Length(window) >= windowSize)
        do something
        window.remove(array[left++])      
return window

注意：固定滑动窗口condition判定用的if， 可变滑动窗口用的while

二叉树的遍历

三种方法

递归

//前序遍历
void traversal(TreeNode* root,vector<int>& result)
{
    if(root == nullptr) return;
    result.push_back(root->val); //中
    traversal(root->left, result); //左
    traversal(root->right, result); //右
}

//中序遍历
void traversal(TreeNode* root,vector<int>& result)
{
    if(root == nullptr) return;
    traversal(root->left, result); //左
    result.push_back(root->val); //中
    traversal(root->right, result); //右
}

//后序遍历
void traversal(TreeNode* root,vector<int>& result)
{
    if(root == nullptr) return;
    traversal(root->left, result); //左
    traversal(root->right, result); //右
    result.push_back(root->val); //中
}

布尔标记的迭代法

使用bool标记是否为当前节点的左右节点安排过入栈，如有，则处理该节点，如无，则安排其左右节点，并将标记置为true

stack<pair<TreeNode*, bool>> s;
if(root) s.push({root, false});
while (!s.empty()) 
{
    auto [current, visited] = s.top();
    s.pop();
    if(visited)
    {
        //左右和自己已经安排过入栈，处理节点
        do something
    }
    else
    {
        //安排左右和自己入栈的顺序
        //前序顺序为中左右，那么入栈就要右左中
        //中序顺序左中右，那么入栈就要右中左
        //后序顺序左右中，那么入栈就要中右左
        s.push({current, true}); //中
        if(current->right) s.push({current->right, false}); //右
        if(current->left) s.push({current->left,false}); //左
    }
}

注意这种方法的入栈顺序与遍历顺序的关系

层序遍历

queue<Node*> q;
if(root) q.push(root);
while (!q.empty()) 
{
    int size = q.size(); 
    for(int i = 0; i < size; i++) //注意：这里一定要用固定大小的size。不能用vector的size()
    {
        auto current = q.front();
        q.pop();
        do something
        for(auto x : current->children)
        {
            if(current->left) q.push(current->left);
            if(current->right) q.push(current->right);
        }
    }
}

回溯法

void backTracking(参数)
{
    if(终止条件)
    {
        do something
        return;
    }
    for(本层元素)
    {
        处理节点 //例如: push_back(current)
        backTracking(参数) //例如: backTracking(i+1)
        回溯 //例如: pop_back()
    }
}

动态规划

背包问题

均使用状态压缩，初始化简单。

01背包

for(int i = 0; i < items.size(); i++) //物品
{
    for(int j = bagCapacity; j >= weights[i]; j--) //背包
    {
        dp[j] = max(dp[j], dp[j - weights[i]] + value[i]);
    }
}

二维DP物品和背包的顺序无所谓，但是状态压缩后的DP顺序很重要

完全背包

for(int i = 0; i < items.size(); i++) //物品
{
    for(int j = weights[i]; j <= bagCapacity ; j++) //背包
    {
        dp[j] = max(dp[j], dp[j - weights[i]] + value[i]);
    }
}

注意：01背包和完全背包中背包的遍历顺序

完全背包的顺序 组合数：先物品后背包 排列数：先背包后物品

多重背包

将多重背包展开即可转换为01背包问题

for(int i = 0; i < items.size(); i++) //物品
{
    for(int j = bagCapacity; j >= weights[i]; j--) //背包
    {
        for (int k = 1; k <= itemNums[i] && (j - k * weight[i]) >= 0; k++) 
        { 
            dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
        }
    }
}

单调栈

注意栈的顺序是递增还是递减，栈里面存储的是索引。

作用是找到最近的比自己大/小的元素

stack<int> s;
vector<int> result(nums.size(),0);
for(int i = 0; i < nums.size(); i++)
{
    while(!s.empty() && nums[i] > nums[s.top()])
    {
        result[s.top()] = i - s.top();
        s.pop();
    }
    s.push(i);
}

图论

主意DFS BFS算法， 最短距离的算法

DFS

void dfs(int start, vector<vector<int>>& adjs, vector<bool>& visited)
{
    //Optional
    //if(condition) return;
    visited[start] = true;
    do something;
    for(int next : adjs[start])
    {
        if(!visited[next])
        {
            dfs(next, adjs, visited);
        }
    }
}

BFS

int bfs(vector<vector<int>>& adjs, vector<bool>& visited, int n) {
        queue<int> q;
        q.push(0);
        visited[0] = true;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int current = q.front();
                q.pop();
                do something;
                for (int neighbor : adjs[current]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
        }
    }

并查集

1. 并
2. 查

class DisjointSet
{
  private:
    std::vector<int> parents;
  public:
    DisjointSet(int size) 
    {
        parents.resize(size);
        for (int i = 0; i < size; ++i) {
            parents[i] = i; // 初始时每个元素的父节点是自身
        }
    }
    int Find(int x) //  0 =< x < size
    {
        if(parents[x] == x) //需要寻找的元素的父节点是自身
        {
            return x; //直接返回自身也就是根节点
        }
        parents[x] = Find(parents[x]); // 如果x有父节点，一直向上查找，同时路径压缩，直接将x的父节点设置为根节点
        return parents[x];
    }
    void Unite(int x, int y)
    {
        // 寻找x，y的根节点
        // 将某一个根节点连接到另一个树的根节点
        parents[Find(x)] = Find(y); // 将x的父节点设置为y的根节点
        //TODO: 启发式合并
    }
    bool IsConnected(int x, int y)
    {
        return Find(x) == Find(y);
    }

};

迪杰斯特拉算法

适用于没有负权的图（有向图or无向图）

vector<int> distances(n, INT_MAX);
set<int> visited; //or vector<bool> visited(n, false);
//{distance, node} 维护distances中距离最小的节点，小根堆，将distance放在第一位，这样可以保证小根堆按照distance排序
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// initial distance
distances[0] = 0;
pq.push({0, 0});
while (!pq.empty())
{
    int node = pq.top().second;
    pq.pop();
    if (visited.count(node)) // or if(visited[node]) continue;
        continue;
    visited.insert(node); // or visited[node] = true;
    for (auto &edge : adjs[node])
    {
        int weight = edge.first;
        int next = edge.second;
        if (distances[next] > distances[node] + weight)
        {
            distances[next] = distances[node] + weight;
            pq.push({distances[next], next});
        }
    }
}

Floyd算法

// D P
// P矩阵存储的是前驱节点
vector<vector<int>> D(n, vector<int>(n, INT_MAX)); // 距离矩阵
vector<vector<int>> P(n, vector<int>(n, -1));      // 路径矩阵

for (int k = 0; k < n; k++) // n次迭代，每次以k为中间节点更新矩阵
{
    // 以k为中间节点，更新矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (D[i][k] != INT_MAX && D[k][j] != INT_MAX && D[i][k] + D[k][j] < D[i][j])
            {
                D[i][j] = D[i][k] + D[k][j];
                P[i][j] = P[k][j];
            }
        }
    }
}

最小生成树

稀疏图使用kruskal算法，稠密图使用prime算法

Prime算法

vector<vector<int>> grid;

vector<bool> isInTree(n, false);
// 记录当前离最小生成树最近的节点,{distance, node}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minDistance;
minDistance.push({0, 0});
while (!minDistance.empty()) // n-1次即可构成连通分量
{
    // 取出离最小生成树最近的节点
    auto [distance, node] = minDistance.top();
    minDistance.pop();
    if (isInTree[node])
        continue;
    // 加入最小生成树
    isInTree[node] = true;
    // 更新其他非最小生成树的节点到最小生成树的距离
    for (int next = 0; next < grid[node].size(); next++)
    {
        if (!isInTree[next] && grid[node][next] != INT_MAX)
        {
            minDistance.push({grid[node][next], next});
        }
    }
}

Kruskal算法

vector<vector<int>> edges;
DisjointSet disjointSet; // 并查集
// 按权值从小到大
sort(edges.begin(), edges.end(), [](auto &a, auto &b) { return a[2] < b[2]; });
for (auto edge : edges)
{
    // 判断边的两个顶点是否是与一个集合
    if (!disjointSet.IsConnected(edge[0], edge[1]))
    {
        // 不属于则加入最小生成树
        disjointSet.Unite(edge[0], edge[1]);
    }
}

欧拉路径

欧拉路径：通过图中所有边恰好一次且行遍所有顶点的通路

欧拉回路：通过图中所有边恰好一次且行遍所有顶点的回路（回到起点）

欧拉图：具有欧拉回路的无向图或有向图

半欧拉图：具有欧拉路径但不具有欧拉回路的无向图或有向图

对于无向图，欧拉图中所有顶点的度数都是偶数，因为每个点的入度和出度成对出现

对于有向图，欧拉图中所有节点的入度和出度都相等

判断是否为欧拉图

对于无向图， 当且仅当是连通图且没有奇度顶点时，为欧拉图

对于无向图 ，当且仅当是连通图且图中恰有0个或2个奇度顶点时，为半欧拉图

对于有向图 ，当且仅当所有顶点属于同一个强连通分量且每个顶点的入度和出度相同时，为欧拉图

对于有向图 ， 当且仅当满足下面条件时，为半欧拉图

1. 如果将所有的有向边退化为无向边时，那么所有顶点属于同一个连通分量。
2. 最多只有一个顶点的出度与入度差为 1。
3. 最多只有一个顶点的入度与出度差为 1。
4. 所有其他顶点的入度和出度相同。

欧拉路径/回路流程

1. 建邻接表、入度表、出度表
2. 根据是通路还是回路判断是否要找起点start
3. Hierholzer 算法找路
4. 最后将上一步找的路再逆回来

Hierholzer算法

1. 从起点出发，进行深度优先搜索。
2. 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边（灵魂）。
3. 如果没有可移动的路径，则将所在节点加入到结果中，并返回。

void dfs(int node, vector<vector<int>>& adjs)
{
    while(!adjs[node].empty())
    {
        int next = adjs[node].back();
        adjs[node].pop_back();
        dfs(node,adjs);
    }
    //do something
    //eg. result.push_back(node)
}


//已知
vector<vector<int>> adjs;//邻接表
vector<int> inDegree, outDegree;
int start

//only for 欧拉路径 需要找起点 欧拉回路任意一个点都可以为起点
for(auto x : outDegree)
{
    if(outDegree[x] == inDegree[x] + 1)
    {
        start =x;
        break;
    }
}

// eg.reverse(result.begin, result.end())

数论

欧拉筛（线性筛）

欧拉筛的时间复杂度O(logn)因此不介绍其他算法（埃氏筛O(nloglogn)）

目的是筛去合数

核心思想：让每个合数被他最小质因子筛去

vector<bool> isNotPrime(n, false);
vector<int> primes; //质数表
for(int i = 2; i <=n; i++)
{
    if(!isNotPrime[i])
    {
        primes.push_back(i); //将质数放入质数表
    }
    for(int p : primes)
    {
        isNotPrime[p * i] = true; //由最小质因子筛去的合数
        if(i % p == 0) // p 为 i 的最小质因子
        {
            break;
        }
    }

}

i%p==0 break的原因： 欧拉筛的核心思想是让合数被他最小的质因子筛去，那么对于任何一个i来说， 他的最小质因子一定是 $p_i, i mod p_i = 0$ 那么对于 $p_j > p_i$ 来说 $p_j * i$ 中最小质因子不是 $p_j$ 而是 $p_i$ 因为 $p_j * i$ 能被 $p_i$ 整除。 那么对于 $p_k < p_i$ 来说 $k = p_k * i$ k是合数且最小质因子一定是 $p_k$ 故筛去。