8000 spannig tree, unionfind · qinyafee/leetcode@44b3a7c · GitHub
[go: up one dir, main page]
Skip to content

Commit 44b3a7c

Browse files
qinyafeeqinyafee
committed
spannig tree, unionfind
Signed-off-by: Yafei <yafee.qin@gmail.com>
1 parent 82dec50 commit 44b3a7c

File tree

10 files changed

+570
-28
lines changed

10 files changed

+570
-28
lines changed

‎.clang-format

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
BasedOnStyle: Google
2+
---
3+
Language: Cpp
4+
Cpp11BracedListStyle: true
5+
Standard: Cpp11
6+
AllowShortFunctionsOnASingleLine: None
7+
DerivePointerAlignment: false
8+
PointerAlignment: Left
9+
CommentPragmas: '^ NOLINT'
10+
ColumnLimit: 100
11+
TabWidth: 2

‎.gitignore

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,6 @@
11
.idea
22
algorithms-java/out
33
*.class
4+
5+
6+
.vscode/

‎NoIncluded.md

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,16 @@ https://leetcode-cn.com/problems/map-of-highest-peak/
2323

2424
1254.统计封闭岛屿的数目
2525

26+
919.https://leetcode.cn/problems/complete-binary-tree-inserter
27+
28+
// 并查集 UnionFind
29+
1319.连通网络的操作次数 // https://leetcode.cn/problems/number-of-operations-to-make-network-connected
30+
684.https://leetcode.cn/problems/redundant-connection/
31+
959.由斜杠划分区域 https://leetcode.cn/problems/regions-cut-by-slashes/ [没刷]
32+
1579.保证图可完全遍历 https://leetcode.cn/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/ [没刷]
33+
34+
35+
785. 判断二分图 https://leetcode.cn/problems/is-graph-bipartite/
2636

2737
## 没刷的H
2838
Median of Two Sorted Arrays

‎algorithms/cpp/UnionFind/1319.number-of-operations-to-make-network-connected.cpp

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
// https://leetcode.cn/problems/number-of-operations-to-make-network-connected/solution/lian-tong-wang-luo-de-cao-zuo-ci-shu-by-leetcode-s/
2+
// 我们可以使用并查集来得到图中的连通分量数。
3+
// 并查集本身就是用来维护连通性的数据结构。
4+
// 如果其包含 n 个节点，那么初始时连通分量数为n;
5+
// 每成功进行一次合并操作，连通分量数就会减少1。
6+
// 最后要保证只有1个联通分量
7+
8+
// 并查集模板
9+
class UnionFind {
10+
public:
11+
vector<int> parent;
12+
vector<int> size;
13+
int n;
14+
// 当前连通分量数目
15+
int setCount;
16+
17+
public:
18+
UnionFind(int _n) : n(_n), setCount(_n), parent(_n), size(_n, 1) {
19+
std::iota(parent.begin(), parent.end(), 0); //! 用法
20+
}
21+
22+
int findset(int x) {
23+
return parent[x] == x ? x : parent[x] = findset(parent[x]);
24+
}
25+
26+
bool unite(int x, int y) {
27+
x = findset(x);
28+
y = findset(y);
29+
if (x == y) {
30+
return false;
31+
}
32+
if (size[x] < size[y]) { //保证短的挂到长的
33+
swap(x, y);
34+
}
35+
parent[y] = x;
36+
size[x] += size[y];
37+
--setCount; // 每次merge，联通分量-1
38+
return true;
39+
}
40+
41+
bool connected(int x, int y) {
42+
x = findset(x);
43+
y = findset(y);
44+
return x == y;
45+
}
46+
};
47+
48+
class Solution {
49+
public:
50+
int makeConnected(int n, vector<vector<int>>& connections) {
51+
if (connections.size() < n - 1) {
52+
return -1;
53+
}
54+
55+
UnionFind uf(n);
56+
for (const auto& conn : connections) {
57+
uf.unite(conn[0], conn[1]);
58+
}
59+
60+
return uf.setCount - 1;
61+
}
62+
};

‎algorithms/cpp/UnionFind/684.findRedundantConnection.cpp

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
// https://leetcode.cn/problems/redundant-connection/submissions/
2+
// 并查集
3+
4+
// 0.并查集, Disjoint
5+
// Set，即不相交集合。是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
6+
// 并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。
7+
// https://www.runoob.com/data-structures/union-find-quick-merge.html
8+
class UnionFind // 并查集，主要作用是检查两个顶点是不是在同一个连通分量[集合]
9+
{
10+
vector<int> parent; // parent[i]表示当前元素i指向的父节点
11+
int count;
12+
13+
public:
14+
UnionFind(int n) : count(n) {
15+
parent.resize(n);
16+
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
17+
for (int i = 0; i < n; ++i) {
18+
parent[i] = i;
19+
}
20+
}
21+
22+
// 查找元素 a 所对应的集合编号，不断去查询自己的父亲节点, 直到到达根节点，
23+
// O(h) 复杂度, h 为树的高度。
24+
int find(int a) {
25+
// assert( p >= 0 && p < count );
26+
while (a != parent[a]) { //根节点的特点 parent[a] == a
27+
a = parent[a];
28+
}
29+
return a;
30+
}
31+
32+
// 查看元素p和元素q是否所属一个集合
33+
// O(h)复杂度, h为树的高度
34+
bool isConnected(int p, int pq) {
35+
return find(p) == find(pq);
36+
}
37+
38+
// 合并元素 p 和元素 pq 所属的集合
39+
// 分别查询两个元素的根节点，使其中一个根节点指向另外一个根节点，两个集合就合并了。
40+
// O(h) 时间复杂度，h 为树的高度。
41+
void merge(int a, int b) {
42+
int pa = find(a);
43+
int pb = find(b);
44+
if (pa == pb) {
45+
return;
46+
}
47+
parent[pa] = pb;
48+
}
49+
};
50+
51+
class Solution {
52+
public:
53+
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
54+
set<int> vertexs;
55+
for(const auto& e : edges){
56+
vertexs.insert(e[0]);
57+
vertexs.insert(e[1]);
58+
}
59+
const int N = vertexs.size();
60+
UnionFind uf(N+1);
61+
for(auto it = edges.begin(); it != edges.end(); ++it){
62+
const int from = it->front();
63+
const int to = it->back();
64+
if(!uf.isConnected(from, to)){
65+
uf.merge(from, to);
66+
} else{
67+
return *it;
68+
}
69+
}
70+
return {};
71+
}
72+
};

‎algorithms/cpp/climbStairs/climbStairs.cpp

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,8 @@ class Solution {
5151
};
5252
// 爬楼梯变种总结
5353
// https://blog.csdn.net/wjhshuai/article/details/68952756
54+
// 上n个台阶，每次一步或两步，求走法数量，简单DP。
55+
// 上一题变形，最多只能连续走m次两步。依然DP，dp[i][j]表示到第i级台阶，前面连续走了j次两步的走法数量。写出转移方程，面试官没有让写代码。
5456

5557
// clang-format off
5658
class Solution {

‎algorithms/cpp/countCompleteTreeNodes/CompleteBinaryTreeInserter.cpp

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
// 222.
2+
// https://leetcode.cn/problems/count-complete-tree-nodes/solution/wan-quan-er-cha-shu-de-jie-dian-ge-shu-by-leetco-2/
3+
// 规定根节点位于第 0 层
4+
// 最大层数为 h 的完全二叉树，节点个数一定在 [2^h,2^(h+1)−1]的范围内,
5+
// 在该范围内通过二分查找,得到完全二叉树的节点个数
6+
7+
// 919.
8+
// https://leetcode.cn/problems/complete-binary-tree-inserter/solution/cshuang-100-shi-xian-o1kong-jian-olognsh-nwm4/
9+
10+
class CBTInserter {
11+
private:
12+
TreeNode* root_;
13+
int size_;
14+
15+
public:
16+
CBTInserter(TreeNode* root) : root_(root) {
17+
size_ = countNodes(root);
18+
}
19+
20+
int insert(int val) {
21+
TreeNode* node = root_;
22+
int idx = ++size_; // idx: 本次插入结点的编号
23+
int _idx = idx;
24+
int bits = 0; // bits: idx的位数
25+
while (_idx) {
26+
++bits;
27+
_idx >>= 1;
28+
}
29+
30+
--bits; // idx首位1不需要
31+
while (--bits > 0) { //! bits=1时，--bits=0, 最后一次不进入
32+
if (idx & (1 << bits)) {
33+
node = node->right;
34+
} else {
35+
node = node->left;
36+
}
37+
}
38+
if (idx & 1) {
39+
node->right = new TreeNode(val);
40+
} else {
41+
node->left = new TreeNode(val);
42+
}
43+
return node->val;
44+
}
45+
46+
TreeNode* get_root() {
47+
return root_;
48+
}
49+
50+
public:
51+
int countNodes(TreeNode* root) {
52+
if (root == nullptr) {
53+
return 0; //! corner case
54+
}
55+
int level = 0; //规定根节点位于第 0 层
56+
TreeNode* p = root;
57+
while (p->left != nullptr) { //求得最大层数h
58+
++level;
59+
p = p->left;
60+
}
61+
62+
// 节点序号：上界= 2^h，下界=2^(h+1)-1
63+
int low = 1 << level, high = (1 << (level + 1)) - 1;
64+
while (low < high) {
65+
int mid = (high - low + 1) / 2 + low;
66+
if (exists(root, level, mid)) {
67+
low = mid; // 如果第 k 个节点存在，则节点个数一定 >=k
68+
} else {
69+
high = mid - 1; // 如果第 k 个节点不存在，则节点个数一定 <k
70+
}
71+
}
72+
return low;
73+
}
74+
75+
// 判断最后一层第k个索引是否存在
76+
// 如果第 k 个节点位于第 l 层，则 k 的二进制表示包含 l+1 位
77+
// 其中最高位是 1，其余各位从高到低表示从根节点到第 k 个节点的路径，
78+
// 0 表示移动到左子节点，1表示移动到右子节点。
79+
bool exists(TreeNode* root, int level, int k) {
80+
int bits = 1 << (level - 1); // 从第l-1位开始找，对应第l=1层
81+
TreeNode* p = root;
82+
while (p != nullptr && bits > 0) {
83+
if (!(bits & k)) {
84+
p = p->left;
85+
} else {
86+
p = p->right;
87+
}
88+
bits >>= 1;
89+
}
90+
return p != nullptr;
91+
}
92+
};
93+
94+
// Source : https://leetcode.com/problems/count-complete-tree-nodes/
95+
96+

0 commit comments

Comments
 (0)
0