图:并查集

并查集是一种树型的数据结构,其保持着用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。

并查集一般支持两种操作:

  1. 查找 查询两个元素a和b是否在同一个集合
  2. 合并 合并a和b所在的两个集合

阅读全文

图:最小生成树之Prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
贪心算法之最小生成树
伪代码:
MST-PRIM(G, w, r)
for each u in V[G]
do key[u] <- INF
pi[u] <- NIL
key[r] <- 0
Q <- V[G]
while Q != EMPTY
do u <- EXTRACT-MIN(Q)
for each v in Adj[u]
do if v in Q and w(u, v) < key[v]
then pi[v] <- u
key[v] = w(u,v)

阅读全文

二叉树的非递归遍历

这里给出二叉树的普通非递归遍历, 主要使用方法二就好了:

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
//二叉树的节点
struct Node {
int val;
Node *lch, *rch;
Node(int x):val(x), lch(NULL), rch(NULL) {}
};
//前序遍历
/*
方法一:
前序遍历就是先访问当前节点,然后依次访问左子结点,右子节点
所以很简单,我们就直接用一个栈先压入右子节点,然后压入左子结点就可以了
*/
void preOrderTraversal(Node *root) {
stack<Node *> s;
Node *cur; //当前访问节点
if (root != NULL) //如果根节点不为空,压栈
s.push(root);
while (!s.empty()) { //如果栈不为空
cur = s.top(); //输出当前访问节点
s.pop();
cout<<cur->val;
//依次将右子节点,左子结点压栈
if (cur->rch != NULL)
s.push(cur->rch);
if (cur->lch != NULL)
s.push(cur->lch);
}
}
/**
方法二
*/
void preOrderTraversal1(Node *root) {
if (root == NULL) return;
Node *cur = root;
stack<Node *> st;
while (!st.empty() || cur) {
while (cur) {
cout<<cur->val;
st.push(cur);
cur = cur->lch;
}
cur = st.top();
st.pop();
cur = cur->rch;
}
}
//中序遍历
/*
中序遍历不能像后序遍历一样记录前一个访问的节点,因为前一个访问的节点并不是要访问的节点的
直接子节点,所以又得换种方法:
我们用一个节点记录当前访问的节点,然后用一个栈记录上一个访问过的节点。如果当前的节点不为空,
那么向下访问左子结点。
如果当前访问的节点为空,说明上一个访问的节点已经没有左子结点了,那么输出上一个节点,
然后访问上一个节点的右子节点。
*/
void inorderTraversal(Node *root) {
stack<Node *> s;
Node *cur = root; //当前访问节点
while (!s.empty() || cur != NULL) { //如果当前访问节点与栈都不为空
if (cur != NULL) {
//如果当前节点不为空,那么继续往下访问左子结点,并将当前节点压栈
s.push(cur);
cur = cur->lch;
} else {
//如果当前节点为空,那么从栈顶弹出节点,并输出该节点,然后继续往下访问
//右子节点
cur = s.top();
s.pop();
cout<<cur->val;
cur = cur->rch;
}
}
}
/**
方法二
*/
void inOrderTraversal1(Node *root) {
if (root == NULL) return ;
Node *cur = root;
stack<Node *> st;
while (!st.empty() || cur) {
while (cur) {
st.push(cur);
cur = cur->lch;
}
cur = st.top();
cout<<cur->val;
cur = cur->rch;
}
}
//后序遍历的非递归实现
/*
后序遍历就是先访问节点的左子结点和右子节点,再访问当前节点
如果不用递归,我们就可以用栈,我们可以依次将当前节点、右子节点和左子结点入栈,
然后再弹栈
但是这里又有另一个问题,如果我们访问到了一个节点,可是我们不知道到底是应该将它的两个子节点
压栈还是该将它弹出。因此就需要一个辅助的节点来记录上一个弹出的节点,如果被弹出的上一个节点
是它的一个子节点,那么说明前面已经将该节点的子节点压栈了,现在该将它弹出。问题就解决了。
*/
void postorderTraversal(Node *root) {
stack<Node *> s;
Node *pre = NULL; //已经输出过的前一个节点
Node *cur = NULL; //当前访问的节点
if (root != NULL)
s.push(root); //首先将根节点压栈
while (!s.empty()) {
cur = s.top(); //获取栈顶的节点
if ((cur->lch == NULL && cur->rch == NULL) ||
(pre != NULL && (cur->lch == pre || cur->rch == pre))) {
//如果当前的节点既没有左子结点又没有右子节点
//或者当前节点的子节点已经被输出过,即已经是第二次经过该节点了
//输出当前节点,并且将当前节点赋给pre
cout<<cur->val;
s.pop();
pre = cur;
} else {
//依次将右子节点和左子结点入栈
if (cur->rch != NULL)
s.push(cur->rch);
if (cur->lch != NULL)
s.push(cur->lch);
}
}
}
/**
方法二
后序遍历和中序遍历和前序遍历不同,需要保存上一个访问过的节点,
然后根据这个节点来决定是否访问当前点
思路就是使用两个指针,一个用来遍历,另一个用来保存前一个访问的节点
遍历的节点先往左走到头,然后根据当前节点是否有右子节点或者右子节点是否访问过来判断是否要访问当前节点。
否则访问右子节点
*/
void postOrderTraversal1(Node *root) {
if (root == NULL) return ;
Node *cur = root, *pre = NULL;
stack<Node *> st;
while (!st.empty() && cur) {
while (cur) {
st.push(cur);
cur = cur->lch;
}
cur = st.top();
if (cur->rch == NULL || cur->rch == pre) {
cout<<cur->val;
pre = cur;
cur = NULL;
} else {
cur = cur->rch;
}
}
}
//层序遍历
//层序遍历跟前序遍历差不多,就是把栈换成了队列,然后左右子节点入队的顺序交换了一下
void levelorderTraversal(Node *root) {
queue<Node *> que;
Node *cur;
if (root != NULL)
que.push(root);
while (!que.empty()) {
cur = que.front();
cout<<cur->val;
que.pop();
if (cur->lch != NULL)
que.push(cur->lch);
if (cur->rch != NULL)
que.push(cur->rch);
}
}
int main() {
Node root(1);
Node c1(2);
Node c2(3);
Node c3(4);
Node c4(5);
Node c5(6);
root.lch = &c1;
root.rch = &c2;
c1.lch = &c3;
c1.rch = &c4;
c2.lch = &c5;
preOrderTraversal(&root);
cout<<endl;
preOrderTraversal1(&root);
postorderTraversal(&root);
inorderTraversal(&root);
levelorderTraversal(&root);
}

阅读全文

图:拓扑排序(Topological sort)

由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序。

  • 每个顶点出现且只出现一次;
  • 若A在序列中排在B的前面,则在图中不存在从B到A的路径。

阅读全文

堆排序: Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

这个题如果按照常规思路来做得话,就是将k个链表两两合并,但是这样做的时间复杂度高.

阅读全文

c语言的一些需要注意的小问题

#define square(x) x * x

如果执行的是square(z + 1),那么替换后的结果为z + 1*z + 1,结果是不对的,所以使用宏的时候还是得非常小心。

阅读全文

四则运算计算器实现

##波兰表示法与逆波兰表示法

波兰表示法(Polish notation,或波兰记法),是一种逻辑、算术和代数表示方法,其特点是操作符置于操作数的前面,因此也称做前缀表示法。与逆波兰表示法不同,前缀表达式基本没有在商业计算器中使用过,但是其体系经常在编译器构造的概念教学中首先使用。

阅读全文

二叉搜索树(binary search tree)

##二叉搜索树

二叉搜索树又叫二叉查找树,是指一棵空树或者具有下列性质的二叉树:

  • 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

阅读全文

iterator和指针

##Iterator

iterator一般用在容器中,下面是所有容器都支持的一些运算:

1
2
3
4
5
6
7
8
9
10
*iter 返回迭代器 iter 所指向的元素的引用
iter->mem 对 iter 进行解引用,获取指定元素中名为 mem 的成员。等效于 (*iter).mem
++iter iter++ 给 iter 加 1,使其指向容器里的下一个元素
--iter iter-- 给 iter 减 1,使其指向容器里的前一个元素
iter1 == iter2
iter1 != iter2 比较两个迭代器是否相等(或不等)。当两个迭代器指向同一个容器中的同一个元素,或者当它们都指向同一个容器的超出末端的下一位置时,两个迭代器相等

阅读全文

图: 二分图(用邻接表实现)

给定一个具有n个顶点的图。要给图上每个顶点染色,并且要使相邻的顶点颜色不同。问是否能最多使用2种颜色进行染色?题目保证没有重边和自环。

这个题可以使用dfs来实现,思路还是挺简单的。

假设有一个简单图,随意从一个顶点开始染色,然后给相邻的顶点染上相反的色,如果相邻顶点和自己的色相同,那么说明不是二分图。

阅读全文