lcDFS1 - 深度优先遍历1
1 深度优先遍历
最常见的优化：
1 记忆化搜索： 使用hash记录遍历起点对应的值，然后直接从hash中获得，避免重复计算
2 常见算法：
对于欧拉图和半欧拉图算欧拉路径：hierholzer算法
2 例子
0332HierholzerToFindEulerPath 找欧拉路径
1 题目
https://leetcode-cn.com/problems/reconstruct-itinerary/
2 解题思路
hierholzer算法参考：https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
https://blog.csdn.net/qq_34292517/article/details/105463522?utm_medium=distribute.pc_relevant.none-task-blog-2defaultbaidujs_title~default-0.pc_relevant_default&spm=1001.2101.3001.4242.1&utm_relevant_index=3
- 1 自己的思路：
- 1.1 主要是使用hierholzer算法找到欧拉路径，由于需要字典序，那么我们邻接表则使用优先队列来存储
- 2 hierholzer算法
- 2.1 dfs，当一个节点没邻居了(因为每访问一条边就删除一条边)
- 2.2 将节点入栈reversePath
- 2.3 dfs完成，reversePath则为逆序栈
- 3 欧拉图等等理解：参考上述第二篇文章
基本概念
圈：任选图中一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径称为圈。
欧拉路径：通过图中所有边一次且仅一次遍历所有顶点的路径称为欧拉(Euler)路径；
欧拉回路：通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路；
欧拉图：具有欧拉回路的图称为欧拉图；
半欧拉图：有欧拉路径但没有欧拉回路的图称为半欧拉图。
欧拉图与半欧拉图的判定：
G是欧拉图 ⇔ G中所有顶点的度均为偶数 ⇔ G是若干个边不重的圈的并。
G是半欧拉图 ⇔ G中恰有两个奇数度顶点。
1 | class Solution { |
0753crackSafe 破解保险箱(变形欧拉路)
1 题目
https://leetcode-cn.com/problems/freedom-trail/
https://leetcode-cn.com/problems/reconstruct-itinerary/
2 解题思路
- 1 对于 n = 3, k = 3, 我们的图的节点为(k ^ (n-1)个)： 00, 01, …, 22, 然后每个节点都有k个边，这样一共是k^n个边
- 1.1 那么如何认为走过一条边就是尝试一次密码呢？
- 1.2 比如: 00的邻接顶点为0,1,2, 那么当dfs访问从00节点到其邻接点分别组成的边为000，001，002，则他们对应的下一跳就为: 00,01,02，也就是取当前dfs访问得到的边的后n-1位
- 2 hierholzer算法
- 2.0 选择一个节点开始dfs
- 2.1 当一个节点没邻居了
- 2.2 将节点入栈reversePath
- 2.3 dfs完成，reversePath则为逆序栈
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
79class Solution {
public:
int n = -1;
int k = -1;
vector<char> kVec;
string crackSafe(int n, int k) {
// since for each bit, there a k's possiblity
// so the final str's length = k^n
// consider a G, vertices are {0, 1, ..., k-1}
// for each edge: vi -> vj(vi could equal vj),
// there shall be n-1's such same edge
// we just need a way to walk through the G
// try hierholzer algo
if(1 == n) {
string tmpRes = "";
for(int i = 0; i < k; ++i) {
tmpRes.push_back(i + '0');
}
return tmpRes;
}
this->k = k;
this->n = n;
for(int i = 0; i < k; ++i) {
kVec.push_back(i + '0');
}
unordered_set<string> seen;
unordered_map<string, vector<char>> graph;
buildGraph("", n - 1, graph);
string stStr(n-1, '0');
string res = "";
hierholzer(stStr, graph, res, seen);
// when n=3, k=3, we start from "00" node, so we add reverse of "00" to the end of the res, cause hierholzer produce a reverse eular path (start from "00", end to "00")
res += stStr;
return res;
}
void buildGraph(string tmp, int leftBitNum, unordered_map<string, vector<char>>& graph) {
if(0 == leftBitNum) {
// cout << "len: " << leftBitNum << "finish node: " << tmp << endl;
graph[tmp] = kVec;
return;
}
for(int st = 0; st < k; ++st) {
buildGraph(tmp + kVec[st], leftBitNum-1, graph);
}
}
void hierholzer(
string st,
unordered_map<string, vector<char>>& graph,
string& res,
unordered_set<string>& seen) {
// cout << "doing : " << st << endl;
bool hasOut = false;
for(int edIdx = 0; edIdx < k; ++edIdx) {
string curEdge(st);
curEdge.push_back(graph[st][edIdx]);
if(seen.count(curEdge)) {
continue;
}
hasOut = true;
string nextSt = curEdge.substr(1);
// cout << "st -> nextSt: " << st << " -> " << nextSt << endl;
seen.insert(curEdge);
// cout << "see edge: " << curEdge << endl;
hierholzer(nextSt, graph, res, seen); // post order
res.push_back(graph[st][edIdx]); // hierholzer
}
}
};
0514wayOfFreedom 自由之路
1 题目
https://leetcode-cn.com/problems/freedom-trail/
2 解题思路
- 1 首先考虑到，key中的每一个字符，环的所有同种字符的所有位置都是遍历的可能
- 1.1 于是使用dfs去尝试对于key的一个字符的每个位置即可，然后讲每个位置得到的结果比较取一个最小值
- 1.2 1.1中提到的算法肯定是有问题的，比如key： abc， 然后ring: aaabbbccc
- 会出现哪种情况呢？ ring中a的三个位置都会搜索，然后对于剩下的key和ring bc以及bbbccc会由于a有三个位置而搜索了三遍，所以需要记忆化搜索
- 1.3 使用memo[i][j]记录： key[i:]和ring[j:]对应的最小步数即可
- 2 经过1的思考，也较为容易知道，本题目，动态规划也能做
- 3 写代码的教训，由于我将dfsmemo写好，然后调用dfs的地方也改了，但是依然超时？
- 3.1 因为dfsmemo递归调用不是自身，而是dfs函数，所以务必及时清理不需要的代码
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
73class Solution {
public:
int ringLen = -1;
int keyLen = -1;
int findRotateSteps(string ring, string key) {
unordered_map<char, vector<int>> ringMap;
ringLen = ring.length();
keyLen = key.length();
int pos = 0;
for(auto& c : ring) {
if(0 == ringMap.count(c)) {
vector<int> tmp = {pos};
ringMap[c] = tmp;
} else {
ringMap[c].push_back(pos);
}
++pos;
}
vector<vector<int>> memo(keyLen, vector<int>(ringLen, INT_MAX));
return dfsMemo(0, 0, ringMap, key, memo);
}
// no memo dfs, too slow
int dfs(int tar, int markPos, unordered_map<char, vector<int>>& ringMap, string& key) {
if(tar == key.length()) {
return 0;
}
int minStep = INT_MAX;
// for cur key char, try ervery possible way on the ring
for(auto tarPos : ringMap[key[tar]]) {
int curStep = minDis(tarPos, markPos); // rotate
curStep += 1; // write
minStep = min(
minStep,
dfs(tar + 1, tarPos, ringMap, key) + curStep
);
}
return minStep;
}
// memo version
int dfsMemo(int tar, int markPos, unordered_map<char, vector<int>>& ringMap, string& key,
vector<vector<int>>& memo) {
if(tar == key.length()) {
return 0;
}
if(INT_MAX != memo[tar][markPos]) {
return memo[tar][markPos];
}
// for cur key char, try ervery possible way on the ring
for(auto tarPos : ringMap[key[tar]]) {
int curStep = minDis(tarPos, markPos); // rotate
curStep += 1; // write
memo[tar][markPos] = min(
memo[tar][markPos],
dfsMemo(tar + 1, tarPos, ringMap, key, memo) + curStep
);
}
// cout << "memo ing: " << tar << ", " << markPos << ": " << memo[tar][markPos] << endl;
return memo[tar][markPos];
}
int minDis(int tarPos, int markPos) {
int gt = max(tarPos, markPos);
int lt = min(tarPos, markPos);
return min(gt - lt, lt + ringLen - gt);
}
};
- 3.1 因为dfsmemo递归调用不是自身，而是dfs函数，所以务必及时清理不需要的代码
0968minCameraCover 监控二叉树
1 题目
https://leetcode-cn.com/problems/binary-tree-cameras/submissions/
2 解题思路
- 1 首先得在思考的过程中，理解改题目的本质就是，
- 1.1 在dfs的过程中，在每个节点可以放置或者不放置相机，重要的是，如何去体现放置还是不放置相机
- 1.2 如何提现呢？很简单，比如root放置，然后你想让它的两个子节点都不放置，那么直接递归调用两个子节点的后代即可，具体看代码即可
- 1.3 那么对于每个节点，有几种放置相机的可能呢？
- 一共三种，要么root，要么left，要么right，然后取最小代价即可，这里以选择left子节点仔细说明：
1
2
3
4
5
6
7
8
9
10
11
12
13// choosing: right
int tmpRightCover = min(
// r的监控器对r的两个子节点都有监控作用，于是直接去计算两个子节点的子节点
1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_l),
min(
// r的监控器对r的两个子节点中的右孩子有监控作用，于是计算方式变为算右孩子两个子节点加上左侧节点
// partly ignore, will not put cam on r_rr, may on r_r
1 + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_rl) + minCameraCover(r_l),
// r的监控器对r的两个子节点中的左孩子有监控作用，于是计算方式变为算左孩子两个子节点加上右侧节点
// partly ignore, will not put cam on r_rl, may on r_l
1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rr) + minCameraCover(r_l)
)
);
- 一共三种，要么root，要么left，要么right，然后取最小代价即可，这里以选择left子节点仔细说明：
- 2 优化思路：
- 2.1 同一层递归里面，相同函数名不要反复出现，用临时变量存储以加速
- 2.2 使用hash存储对应的节点的最小监控值，如果能在hash命中就不用反复计算
- 2.3 优先计算小规模，然后计算大规模
- 3 关于为什么需要hash来避免反复计算：
- 3.1 看例子：
[0,null,0,null,0,null,0,null,0,null,0,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,0,null,null,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null] - 3.2 也就是单链表，你会发现，到达第4个节点，可以有两种监控方式，那么说明第4个节点的计算会重复2次，于是需要记忆化搜索
- 3.1 看例子：
1 | /** |