Posted on | Edited on | In |

定义

AVL tree是一个BST对于每一个节点，左子树和右子树的高度差不超过1（空树高度为-1）

这里需要明确，高度的定义：

维基百科：
Height of node
The height of a node is the number of edges on the longest path between that node and a leaf.
Height of tree
The height of a tree is the height of its root node.

树的平衡维护

对一棵平衡的树，进行插入或删除可能改变树的平衡性，这里只考虑插入，删除类似（虽然稍微麻烦一点）。

对于节点X，插入一个节点导致其不平衡，会有四种情况：

  • 新增加的节点是其左结点的左子树
  • 新增加的节点是其左结点的右子树
  • 新增加的节点是其右结点的右子树
  • 新增加的节点是其右结点的左子树

后两种情况与前两种镜像，不作考虑，所以是由两种情况，称之为LL(Left-Left)问题和LR(Left-Right)问题

LL

-w635

当插入到X，导致$k_1$的的高度 > Z的高度+2的时候，树不平衡！

这时候要做的是想办法，把X提上去，把Z压下来，这里需要做的是从左图到右图的变形，这样的形变也叫做一次旋转。

这里有一个动态演示的网站：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html 显示了旋转的动画效果，非常直观

初始：

-w599

插入2之后：

-w599

再次插入1之后：

-w602

这里树的结构变动比较大，因为不是3结点不平衡，而是根节点5不平衡，所以是5和3旋转，根节点发生改变。

LR

-w656

很巧妙的一个变形！

在$k_1$的右子树中插入了东西，导致$k_3$不平衡，现在是要把$k_1$的右子树也就是$k_2$提上去，把D压下去，需要通过两次旋转，就是先$k_1$-$k_2$的一次RR旋转，再$k_2$-$k_3$的一次LL旋转，但是我通常都不想这样记，直接记住这个形式，下边那个从中间“穿过去”，然后原来的左右子树变为新的子树的右左子树。

例子就不举了。

树的平衡化

上述的两个旋转，是平衡化的两个基本操作，平衡化的变形肯定属于这两者。

如果是新的节点插入一棵已经平衡的树的话，用递归的方式非常直观，大概：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def insert(X, T):
    if T == null:
        place here
    else:
        if X < T.val:
            insert(X, T.left)
            if not balence:
                if is LL:
                    LLrotate
                else:
                    LRrotate
        else:
            insert(X, T.right)
            if not balence:
                if is RR:
                    RRrotate
                else:
                    RLrotate
    update height # don't forget, we use height to check balence

插入操作的实现

PAT-A 1066 Root of AVL Tree

https://pintia.cn/problem-sets/994805342720868352/problems/994805404939173888

-w975

-w990

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//
// Created by Zhao Xiaodong on 2018/8/22.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Node {
    int val;
    Node *left;
    Node *right;
    int height;
    Node(int val) : val(val), left(nullptr), right(nullptr) {}
};
int getHeight(Node *root) {
    if (!root)
        return -1;
    return root->height;
}
Node *llRotate(Node *root) {
    Node *newRoot = root->left;
    root->left = newRoot->right;
    newRoot->right = root;
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;
    return newRoot;
}
Node *rrRotate(Node *root) {
    Node *newRoot = root->right;
    root->right = newRoot->left;
    newRoot->left = root;
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;
    return newRoot;
}
Node *lrRotate(Node *root) {
    Node *newRoot = root->left->right;
    root->left->right = newRoot->left;
    newRoot->left = root->left;
    root->left = newRoot->right;
    newRoot->right = root;
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    newRoot->left->height = max(getHeight(newRoot->left->left), getHeight(newRoot->left->right)) + 1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;
    return newRoot;
}
Node *rlRotate(Node *root) {
    Node *newRoot = root->right->left;
    root->right->left = newRoot->right;
    newRoot->right = root->right;
    root->right = newRoot->left;
    newRoot->left = root;
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    newRoot->right->height = max(getHeight(newRoot->right->left), getHeight(newRoot->right->right)) + 1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;
    return newRoot;
}
Node *insert(Node *root, int k) {
    if (!root) {
        Node *node = new Node(k);
        node->height = 0;
        return node;
    }
    if (k < root->val) {
        root->left = insert(root->left, k);
        if (getHeight(root->left) - getHeight(root->right) == 2) {
            if (k < root->left->val)
                root = llRotate(root);
            else
                root = lrRotate(root);
        }
    } else {
        root->right = insert(root->right, k);
        if (getHeight(root->right) - getHeight(root->left) == 2) {
            if (k < root->right->val)
                root = rlRotate(root);
            else
                root = rrRotate(root);
        }
    }
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    return root;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    Node *root = nullptr;
    for (int i = 0; i < N; i++) {
        int k;
        cin >> k;
        root = insert(root, k);
    }
    cout << root->val;
    return 0;
}

不要眼高手低啊！！！算法思想，和实现出来，中间的差距，就是你想要提高的所谓的编程能力，或者码力！如果眼高手低，总觉得自己肯定能实现出来，一定会吃亏的！！！

Posted on | In , |

题目

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

-w958

想法

感觉是一道很经典的题目..

生成一棵不平衡的，单侧的树，然后旋转嘛？有点傻，不过这也是一个问题，把单侧树转变为平衡树

渐进式的，跟那个随即抽取的有点像，不知道总共有多长

AVL tree和splay tree都忘了，尴尬，不行，复习平衡树，然后再做这道题，同时写一篇博客

这道题，题目的数据结构没有高度，所以判断是否平衡还是个麻烦，而且全部是RR的不平衡，应该有更专属的方式来解决

哎呀，看了别人的答案，无非就是二分、递归建树，自己想的可能有点偏orz

解答

参考了:

JosephTao: Share my JAVA solution, 1ms, very short and concise.
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
    TreeNode* helper(ListNode* l, ListNode* r) {
        if (l == r)
            return NULL;
        ListNode* slow = l;
        ListNode* fast = l;
        while (fast != r && fast->next != r) {
            fast = fast->next->next;
            slow = slow->next;
        }
        TreeNode* node = new TreeNode(slow->val);
        node->left = helper(l, slow);
        node->right = helper(slow->next, r);
        return node;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head)
            return NULL;
        return helper(head, NULL);
    }
};

回顾

分治的策略，在这种情况下还是很适用的，一开始觉得链表的话，不好进行分治，但是没想到这个答案竟然是beat 100%，有些吃惊。

学习到了一个二分链表的小trick:

1
2
3
4
while (fast != r && fast->next != r) {
    fast = fast->next->next;
    slow = slow->next;
}

还是蛮有趣的，如果是自己做的话，肯定是先数一遍size，然后定位到size/2，这样应该会快一点。

Posted on | Edited on | In |

软件工程课程，24个人合作开发一个网站，虽然功能并不是特别的复杂，但是，多人的开发，增添了许多奇奇怪怪的问题，不管怎么说，这门课算是相对圆满的结束了，而作为这24人组织领导者的我也从其中学到了一些项目管理的经验，记下，一来可以回忆，二来可用于今后参考。

开始一个项目

其实，所谓的分模块各自独立开发，完全分离是不可能的。每个人都build from scratch，最后肯定是各自有各自奇怪的接口、结构等等。

所以，要做的第一件事，正确的事，就是建立一个repo，写清楚开发指导，让大家知道如何开始写，这一部分，需要注意，或者说必须要做到的几点：

1. 一个工程

说起来是一句废话，既然最终是完成一个项目，当然是在一个工程里边写了。可是我有点太想当然了，于是还是有因为有的模块用了其它的脚手架，有着差异很大的代码结构，导致了整合时花费了些力气的不愉快经历。

如果是最终是一个整体的项目，一定要在一个工程里写，不要想着先各自写自己的子模块，最后写一个顶层的模块将他们捏合在一起，会很痛苦。

当然，比如像一个网站采取前后端分离的架构，那么前后端两个工程，这是没有关系的。

2. 模块之间的独立性

所有人在一个工程里开发，如果不能有很好的独立性，每个人的开发或多或少都会受到拘束，这是我们不愿意看到的。所以在本次开发过程中，建立工程的同事，就需要规定好每个模块如何相互独立的开发。

以本次工程为例，初始项目中，为6个模块分别在合适的地方建立6个目录，有一个必要的入口文件。比如：

后端：用了Django，那么urls.py里写好路由映射，路由到对应目录下的urls.py即可。

前端：用了React生态，需要处理的事情多一些。首先是前端路由，给每个模块的入口component创建路由；其次还有redux的配置，创建根store，让每个子模块创建自己的store并注册到根store中。

这样，初期的开发，每个人在前端直接进入自己的路由，请求后端也全部请求自己子路由下的内容，可以做到相互独立的开发。

3. 示例参考

成员在开发完项目之后，肯定都对所用到的技术栈，一些best practice有或多或少的理解，但是在项目的开始并不是这样的，有许多成员不了解相关的库，框架，语言等。

此时，光给tutorial，documentation等是不够的，成员去学这些东西刚开始需要一段上手时间，而这并不是一个短期一次性项目高效的做法。最直接的就是，写个参考的示例，让不熟悉的成员能够模仿着去写，这样在模仿中学习，能够比较快的掌握所用的知识，同时，也可以学到一些在文档中并不会出现的best practice。

在本次项目的开发中，可以首先写个最简单的前后端交互的示例，有如下的功能：

  • 前端发送GET请求
  • 后端返回数据，比如Hello World
  • 前端redux相关的操作：触发action、reducer的行为、store的改动与视图的更新
  • react组件书写的示例

经过以上的几步，基本做好了项目起始的准备，每个人应该知道了在哪里开始写，怎么开始写这最基本的问题。

Git&GitHub使用

本项目的组织方式大致是这样的：

  • 所有代码放在一个repo中
  • master放整合的代码，受保护
  • 每个子模块有自己的分支，该模块的小组成员在此单分支上工作
  • 子模块完成某个功能之后，提交PR，将子分支merge到master中

就我个人理解，多人的开发，一般有两种模式，一种是多分支，分支之间PR；另一种是fork-PR。我在这次选择了前者，有几个考虑因素：

  1. 我可以看到各个子模块的进度，不至于不提交PR我什么都不知道
  2. 如果必要，我可以直接在某个分支上提交来修改一些代码
  3. 子模块一个分支上操作足够了，一个子模块有四个人参与，单分支基本满足了要求

单分支多人开发

对于多人在单分支上开发，还是需要遵从一定的workflow才能保证不会出现一些不愉快的事情。比如现在多人开发的单分支为common，可以遵从一下的流程：

  1. git checkout -b local 建立自己的本地分支
  2. coding..coding..
  3. git commit -a -m 'blabla' 在自己的分支上提交
  4. git checkout common 切换到common分支
  5. git pull 看看别人在这段时间有没有提交
  6. git checkout local
  7. git merge common 在自己的分支上merge别人的提交，如果有冲突，解决
  8. git checkout common
  9. git merge local 此时，merge 自己分支上的东西，是不会发生冲突的
  10. git push
  11. git checkout local 切回自己的分支，保持idle状态在自己本地分支这个习惯

Pull Request的使用

第一次使用Pull Request这个功能，有一些经验不足，导致自己的使用并不是很愉快。

Review这个设计方式很好，在接受更改的时候，可以审核代码，防止不合理的代码污染共有的分支。以下是自己经过尝试之后的一些心得：

  1. 提交PR之后，只是声明了一个分支到另一个分支的合并，并不是当前提交的状态到另一个分支的合并，所以，提交PR之后的commit，仍然会更新。所以，request change的时候，直接修改就好，不用关掉这个PR再开一个新的PR。
  2. 提交PR的频率尽可能高，不要憋着一个很大的功能再提交，我的建议是，只要写完了一小块内容，而这块内容不至于编译不通过，运行不起来，就可以提交PR，这样逐渐增加master上的功能，不至于一次提交PR，需要审核好多代码。

blame

之前只是注意到这个按钮，但是并没有细究过它的用处，不过，这次可真的是发现了它的用处哈哈。多人开发里边，真的是神器呀。

blame的功能是可以显示文件中对应行是由谁改动的，并且可以查看历史记录，看起来跟blame没有直接的关系，但其实我用到的时候，恰恰就是blame的时候。

-“这谁把我的代码改掉了？？？是你吗？”
-“不是我，我怎么可能去动你这部分的代码？？”
-“哦，是吗？我们来blame一下”
-“我错了orzorz”

今后多人开发的时候可要善用这个功能。

Posted on | Edited on | In |

vscode，一个出色的编辑器，现代，跨平台，高性能，配合Vim插件，自己的主力编辑器。

CMD+.

quick fix，相当于JB家的Alt+Enter

CMD+k,i

show hover message，很有用，键盘肯定会比鼠标块

Posted on | Edited on | In |

作为接触vim已经有两年的人来说，自己对vim的使用还是属于比较肤浅的状态，虽然本着这类工具，够用就行，不要花过多时间，喧宾夺主，但是还是记一些自己用的不太多但是很有用的命令吧。

c

删除并编辑，d用的很多，但是c却很少用，大多数都是d然后i，但这在运用.的时候，就会很低效

:<NUM> <NUM>G

跳转到指定行，这个是一个比较基本的功能，可是之前都没怎么用过

H M L

光标跳转到屏幕顶、中、底
用到的比较少，但是想想也是很有用的

< >

shift left/right 也就是可以调整代码缩进，这个以前都没发现啊

以前自己加缩进：<C-Q>jjjI<Tab><Esc> 现在看起来好傻

需要制定区域，像c,d一样
<< >> 对一行操作

Posted on | Edited on | In |

有些算法，自己觉得也就是那么回事，特别简单，但是想清楚每个细节怎么做，有什么小技巧，把它快速的实现出来，并不是那么容易。从想法到实现，总是有差距的。

经典问题：Course Schedule

LeetCode 207. Course Schedule
https://leetcode.com/problems/course-schedule/description/

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

1
2
3
4
Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

1
2
3
4
5
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
calculate inDegree # 入度，有多少边到当前结点
queue q
counter = 0 # 用于最后检查是不是所有的点都visited
for each v with inDegree[v] == 0:
    q.push(v)
while !q.empty():
    v = q.pop()
    counter++
    for each w adjacent v:
        inDegree[v]-- # 关键！当一个点visit之后，减小所有其指向点的入度
        if inDegree[v] == 0:
            q.push(v)
check counter == vertexNum

C++实现

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
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool canFinish(int N, vector<pair<int, int>>& P) {
        vector<vector<bool>> g(N, vector<bool>(N, false));
        for (auto p : P) {
            g[p.first][p.second] = true;
        }
        queue<int> q;
        vector<int> inDegree(N, 0);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (g[j][i] == true) {
                    inDegree[i]++;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            if (inDegree[i] == 0)
                q.push(i);
        }
        int num = 0;
        while (!q.empty()) {
            int t = q.front();
            q.pop();
            num++;
            for (int i = 0; i < N; i++) {
                if (g[t][i]) {
                    inDegree[i]--;
                    if (inDegree[i] == 0)
                        q.push(i);
                }
            }
        }
        return num == N;
    }
};

DFS

TODO..

Posted on | Edited on | In |

Ford-Fulkerson Algorithm

算法

1
2
3
4
5
6
# Gr: residual graph; G: original graph
Gr = G
flow = 0
while find a path in Gr:
    augment = min(segments in path)
    flow += augment

复杂度

$O(FE)$
F: 最大流
E: 边数

实现

参考：https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

示例图：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool findPath(vector<vector<int>> &G, int src, int dst, vector<int> &parent) {
    vector<bool> visited(G.size(), false);
    queue<int> q;
    q.push(src);
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        visited[curr] = true;
        for (int i = 0; i < G.size(); ++i) {
            if (G[curr][i] > 0 && !visited[i]) {
                q.push(i);
                parent[i] = curr;
                visited[i] = true;
            }
        }
    }
    return visited[dst];
}
int main() {
    vector<vector<int>> G = {
            {0, 16, 13, 0,  0,  0},
            {0, 0,  10, 12, 0,  0},
            {0, 4,  0,  0,  14, 0},
            {0, 0,  9,  0,  0,  20},
            {0, 0,  0,  7,  0,  4},
            {0, 0,  0,  0,  0,  0}
    };
    int res = 0;
    vector<int> parent(G.size());
    int start = 0, end = 5;
    while (findPath(G, start, end, parent)) {
        int minFlow = INT_MAX;
        for (int i = end; i != start; i = parent[i]) {
            minFlow = min(G[parent[i]][i], minFlow);
        }
        for (int i = end; i != start; i = parent[i]) {
            G[parent[i]][i] -= minFlow;
            G[i][parent[i]] += minFlow;
        }
        res += minFlow;
    }
    cout << res << endl;
    return 0;
}

注意点：

parent数组的使用！BFS不像DFS可以记录一条路径，回退重新延伸，不过可以逆向思维，记录parent，这样倒着推也可以得到整条路径！！！

Posted on | Edited on | In |

unweighted graph - BFS

BFS即可

1
2
3
4
5
6
7
startNode.dist = 0
enqueue(startNode)
while queue is not empty:
    N = dequeue()
    for each A adjacent N:
        A.dist = N.dist + 1
        enqueue(A)

如书上例图：

从v3出发的BFS最短路径表：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    size_t V = 7;
    vector<vector<int>> graph(V + 1, vector<int>(V + 1, 0));
    graph[1][2] = 1;
    graph[1][4] = 1;
    graph[2][4] = 1;
    graph[2][5] = 1;
    graph[3][1] = 1;
    graph[3][6] = 1;
    graph[4][3] = 1;
    graph[4][5] = 1;
    graph[4][6] = 1;
    graph[4][7] = 1;
    graph[5][7] = 1;
    graph[7][6] = 1;
    vector<int> dist(V + 1, INT_MAX);
    dist[3] = 0;
    queue<int> q;
    q.push(3);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int i = 1; i < graph[v].size(); i++) {
            if (graph[v][i] > 0 && dist[i] == INT_MAX) {
                dist[i] = dist[v] + 1;
                q.push(i);
            }
        }
    }
    for (int i = 1; i <= V; i++) {
        cout << dist[i] << " ";
    }
    return 0;
}

输出：

1
1 2 0 2 3 1 3

Dijkstra Shortest Path Algorithm

Greedy Algorithm

始终找最小的，这样保证不用look back:

1
2
3
4
5
6
for i from 1 to n:
    V = min dist unknown vertex
    V.known = true
    for each W adjacent V:
        if W.known == false and W.dist > V.dist + weight(V,W):
            W.dist = V.dist + weight(V,W)

复杂度：

对于基于顶点集 $Q$的实现，算法的运行时间是 $O(|E|\cdot dk{Q}+|V|\cdot em{Q})$，其中 $dk{Q}$和 $em{Q}$分别表示完成键的降序排列时间和从$Q$中提取最小键值的时间。

Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合$Q$，所以搜索$Q$中最小元素的运算Extract-Min($Q$)只需要线性搜索$Q$中的所有元素。这样的话算法的运行时间是$O(n^{2})$。

对于边数少于$n^{2}$的稀疏图来说，我们可以用邻接表来更有效的实现该算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点（Extract-Min）。当用到二叉堆的时候，算法所需的时间为 $ {\displaystyle O((m+n)logn)}$，斐波纳契堆能稍微提高一些性能，让算法运行时间达到 ${\displaystyle O(m+nlogn)}$ 。然而，使用斐波纳契堆进行编程，常常会由于算法常数过大而导致速度没有显著提高。

  • 遍历：$O(V^2)$
  • 二叉堆：$O((E + V)logV)$
  • 斐波那契堆：$O(E + VlogV)$

但是，不适用于有负边的：

这种情况下，从A出发Dijstra会认为A->C最短为2而不是-5.

实现

书上的示例：

从v1出发：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//
// Created by Zhao Xiaodong on 2018/4/17.
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    size_t V = 7;
    vector<vector<int>> graph(V + 1, vector<int>(V + 1, 0));
    graph[1][2] = 2;
    graph[1][4] = 1;
    graph[2][4] = 3;
    graph[2][5] = 10;
    graph[3][1] = 4;
    graph[3][6] = 5;
    graph[4][3] = 2;
    graph[4][5] = 2;
    graph[4][6] = 8;
    graph[4][7] = 4;
    graph[5][7] = 6;
    graph[7][6] = 1;
    vector<int> dist(V + 1, INT_MAX);
    vector<bool> known(V + 1, false);
    vector<int> prev(V + 1, 0);
    dist[1] = 0;
    for (int i = 0; i < V; i++) {
        int minD = INT_MAX;
        int minV = -1;
        for (int j = 1; j <= V; j++) {
            if (!known[j] && minD > dist[j])
                minD = dist[j];
                minV = j;
        }
        known[minV] = true;
        for (int k = 1; k <= graph[minV].size(); ++k) {
            if (graph[minV][k] > 0 && !known[k] && dist[k] > dist[minV] + graph[minV][k]) {
                dist[k] = dist[minV] + graph[minV][k];
                prev[k] = minV;
            }
        }
    }
    for (int i = 1; i <= V; i++) {
        cout << dist[i] << " ";
    }
    return 0;
}

输出:

1
0 2 3 1 3 6 5

Bellman–Ford algorithm

适用于有负边的，但较慢

1
2
3
4
5
6
7
8
9
queue q
while q is not empty:
    v = dequeue(q)
    for each w adjacent v:
        if w.dist > v.dist + cost(v,w):
            w.dist = v.dist + cost(v,w)
            w.path = v
            if w is not in q:
                enqueue(w, q)

复杂度：

时间复杂度：$O(VE)$

实现：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    size_t V = 7;
    vector<vector<int>> graph(V + 1, vector<int>(V + 1, 0));
    graph[1][2] = 2;
    graph[1][4] = 1;
    graph[2][4] = 3;
    graph[2][5] = 10;
    graph[3][1] = 4;
    graph[3][6] = 5;
    graph[4][3] = 2;
    graph[4][5] = 2;
    graph[4][6] = 8;
    graph[4][7] = 4;
    graph[5][7] = 6;
    graph[7][6] = 1;
    vector<int> dist(V + 1, INT_MAX);
    vector<int> prev(V + 1, 0);
    dist[1] = 0;
    vector<bool> isInque(V + 1, false);
    queue<int> q;
    q.push(1);
    isInque[1] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        isInque[v] = false;
        for (int i = 1; i <= V; i++) {
            if (graph[v][i] > 0 && dist[i] > dist[v] + graph[v][i]) {
                dist[i] = dist[v] + graph[v][i];
                prev[i] = v;
                if (!isInque[i])
                    q.push(i);
            }
        }
    }
    for (int i = 1; i <= V; i++) {
        cout << dist[i] << " ";
    }
    return 0;
}

输出：

1
0 2 3 1 3 6 5

All-pair Shortest Path

基本思想

动态规划。

D_k,i,j: 从i到j，只用v_1到v_k做中继节点

意思就是说：从i到j，加入一个中间节点v_k，如果路径里加了这个节点之后，使路径变短，那就更新路径！

pseudocode：

1
2
3
4
5
6
7
8
for i, j:
    D[i][j] = hasEdge(i, j) ? weight[i][j] : inf
for k 1..N:
    for i 1..N:
        for j 1..N:
            if D[i][k] + D[k][j] < D[i][j]:
                D[i][j] = D[i][k] + D[k][j]

伪代码很清楚，中间也没有什么trick，就不实现了

复杂度

复杂度伪代码也表现的很清楚，三层循环，O( N^3 )

Posted on | Edited on | In |

在一些OJ中，经常会需要调用一些语言的库函数，但是大多数情况下，自己需要查各种文档，这如果是考试或者是在平时些程序的过程中，是很不流畅的。

这里记下自己每次遇到过需要查文档的相关使用，以便日后复习回顾。

IO

1. getline 读入一行到string

1
2
string s;
getline(cin, s);

针对STDIO的优化

1
2
3
4
5
static int ____ = []() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();

stringstream

1
2
3
4
std::string input = "41 3.14 false hello world";
std::istringstream stream(input);
int n;
stream >> n;

Data Structure

set

1
2
3
4
5
6
set<int> s;
s.insert(3);
s.erase(itrator);
s.find(5) != s.end();
s.count(5) == 1;
vector<T>(s.begin(), s.end()); // set to vector

Algorithms

remove_if

1
2
3
4
str2.erase(std::remove_if(str2.begin(), 
                          str2.end(),
                          [](unsigned char x){return std::isspace(x);}),
            str2.end());

Posted on | Edited on | In |

又一基础数据结构的整理，知识需要不停的回顾与学习。

（此处的heap指binary heap, 且是最小堆）

性质

structure

complete binary tree

order

根节点的值 <= 叶节点的值

实现

数组实现（完全二叉树的表示方式）

  • 根节点放在A[1] (A[0]不使用)
  • A[x]的子节点为A[2x]以及A[2x + 1]

操作

Insert O(logN)

从最后向上找，找到适合放入插入值的位置放入。

1
2
3
4
5
6
7
8
9
void insert(vector<int> &heap, int val) {
    heap.push_back(val);
    int idx = heap.size() - 1;
    while (idx > 1 && heap[idx / 2] > val) {
        heap[idx] = heap[idx / 2]; // percolate up
        idx /= 2;
    }
    heap[idx] = val;
}

DeleteMin O(logN)

从根节点出发，找到适合放入最后一个元素的位置放入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int delete_min(vector<int> &heap) {
    int idx = 1;
    int ret = heap[idx];
    int last = heap.back();
    while (2 * idx < heap.size()) {
        int child = 2 * idx;
        if (child < heap.size() - 1 && heap[child + 1] < heap[child])
            child++; // 找到更小的child
        if (last > heap[child])
            heap[idx] = heap[child]; // percolate down
        else
            break; // 找到最后一个元素插入的合适位置！！！
        idx = child;
    }
    heap[idx] = last;
    heap.pop_back();
    return ret;
}

Build

Naive O(NlogN)

做n次插入操作

1
2
for x in arr:
    insert(heap, x)

O(N)

由下向上，依次进行heapify操作。

时间复杂度分析：

  • 对于高度为h的heapify操作：O(h)
  • 每一层高度为h的最多的节点：$\lceil\frac{n}{2^{h + 1}}\rceil$
  • 两者相乘累加
1
2
3
build_heap(heap):
    for i from heap_size / 2 to 1:
        heapify(heap, i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void percolate_down(vector<int> &heap, int idx) {
    int val = heap[idx];
    while (2 * idx < heap.size()) {
        int child = 2 * idx;
        if (child < heap.size() - 1 && heap[child + 1] < heap[child])
            child++;
        if (val > heap[child])
            heap[idx] = heap[child];
        else
            break;
        idx = child;
    }
    heap[idx] = val;
}
void build_min_heap(vector<int> &heap) {
    for (int i = heap.size() / 2; i > 0; --i) {
        percolate_down(heap, i);
    }
}

Merge

放到一起，build heap…

相关题目

K-th largest element problem

LeetCode 215. Kth Largest Element in an Array

很经典的题目，用heap可以做，也可以用类似快排那样划分的方式做，似乎有更好的表现，因为每次只用考虑一般，是O(N)的时间复杂度。
Heap Method:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
private:
    void makeHeap(vector<int>& heap) {
        for (int i = heap.size() / 2; i > 0; i--) {
            int idx = i;
            int val = heap[idx];
            while (2 * idx < heap.size()) {
                int child = 2 * idx;
                if (child + 1 < heap.size() && heap[child + 1] > heap[child])
                    child++;
                if (val < heap[child])
                    heap[idx] = heap[child];
                else
                    break;
                idx = child;
            }
            heap[idx] = val;
        }
    }
    int deleteMax(vector<int>& heap) {
        int ret = heap[1];
        int idx = 1;
        int last = heap.back();
        while (2 * idx < heap.size()) {
            int child = 2 * idx;
            if (2 * idx + 1 < heap.size() && heap[2 * idx + 1] > heap[2 * idx])
                child++;
            if (last < heap[child])
                heap[idx] = heap[child];
            else break;
            idx = child;
        }
        heap[idx] = last;
        heap.pop_back();
        return ret;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        nums.insert(nums.begin(), 0);
        makeHeap(nums);
        int res = 0;
        for (int i = 0; i < k - 1; i++)
            deleteMax(nums);
        return deleteMax(nums);
    }
};

Partition Method:

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
28
29
30
class Solution {
private:
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left];
        int l = left + 1, r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot)
                swap(nums[l++], nums[r--]);
            if (nums[l] >= pivot)
                l++;
            if (nums[r] <= pivot)
                r--;
        }
        swap(nums[left], nums[r]); // 注意与nums[r]交换
        return r;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (true) {
            int mid = partition(nums, left, right);
            if (mid == k - 1)
                return nums[mid];
            if (mid < k - 1)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
};

Top K Frequent

LeetCode 692. Top K Frequent Words

这个题，题目一般，不够经典，但是记下来用于回顾cpp标准库中的priority_queue的使用，包括自己写comparator等。

注意些comparator时判断的符号！！！
记住，默认排序的时候，排升序，默认用小于号比较，其它的基于这个可以推出。
比如这道题，是最大堆，所以应该是”排降序“，用大于号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for (string word : words)
            m[word]++;
        auto comp = [](const pair<string, int>& p1, const pair<string, int>& p2) {
            if (p1.second == p2.second)
                return p1.first > p2.first;
            return p1.second < p2.second;
        };
        vector<string> res;
        priority_queue< pair<string, int>, vector<pair<string, int>>, decltype(comp) > q(comp);
        for (pair<string, int> p : m) {
            q.push(p);
        }
        for (int i = 0; i < k; i++) {
            res.push_back(q.top().first);
            q.pop();
        }
        return res;
    }
};