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/_/article/details/?utm_medium=distribute.pc_relevant.none-task-blog-2_defaultbaidujs_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中恰有两个奇数度顶点。

class Solution { 
    public: int edgeNums = -1; int nodeNums = -1; unordered_map<string, int> nodes; unordered_map<int, string> toStr; vector<string> findItinerary(vector<vector<string>>& tickets) { 
    // map str to int according to dictionary order set<string, std::less<string>> airports; for(auto& vec : tickets) { 
    airports.insert(vec[0]); airports.insert(vec[1]); } int i = 0; for(auto& str : airports) { 
    toStr[i] = str; nodes[str] = i++; } // construct the adj table int nodeNums = airports.size(); int edgeNums = tickets.size(); // vector<vector<int>> table(nodeNums, vector<int>(0)); vector<priority_queue<int, vector<int>, greater<int>>> table(nodeNums, priority_queue<int, vector<int>, greater<int>>()); for(auto& vec : tickets) { 
    table[nodes[vec[0]]].push(nodes[vec[1]]); } vector<string> strRes; vector<priority_queue<int, vector<int>, greater<int>>> tableTmp(table); vector<int> res; dfs(nodes["JFK"], tableTmp, res); reverse(res.begin(), res.end()); for(auto& node : res) { 
    strRes.push_back(toStr[node]); } return strRes; } //  void dfs(int st, vector<priority_queue<int, vector<int>, greater<int>>>& map, vector<int>& res) { 
    while(!map[st].empty()) { 
    int nextSt = map[st].top(); map[st].pop(); // cout << "from to: " << toStr[st] << " -> " << toStr[nextSt] << endl; dfs(nextSt, map, res); } res.emplace_back(st); } };

讯享网

0753crackSafe 激活成功教程保险箱(变形欧拉路)

1 题目

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则为逆序栈

讯享网class 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函数，所以务必及时清理不需要的代码

class 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); } };

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子节点仔细说明：

讯享网 // 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) ) );

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次，于是需要记忆化搜索

/ * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { 
    public: int level = 0; unordered_map<TreeNode* , int> memo; int minCameraCover(TreeNode* root) { 
    ++level; if(nullptr == root) { 
    return 0; } if(nullptr == root->left && nullptr == root->right) { 
    return 1; } // dp: TreeNode* r_l = root->left; TreeNode* r_r = root->right; TreeNode* r_ll = getL(r_l); TreeNode* r_lr = getR(r_l); TreeNode* r_rl = getL(r_r); TreeNode* r_rr = getR(r_r); TreeNode* r_lll = getL(r_ll); TreeNode* r_llr = getR(r_ll); TreeNode* r_lrl = getL(r_lr); TreeNode* r_lrr = getR(r_lr); TreeNode* r_rll = getL(r_rl); TreeNode* r_rlr = getR(r_rl); TreeNode* r_rrl = getL(r_rr); TreeNode* r_rrr = getR(r_rr); int cover_r_lll = getFromMemo(r_lll); int cover_r_llr = getFromMemo(r_llr); int cover_r_lrl = getFromMemo(r_lrl); int cover_r_lrr = getFromMemo(r_lrr); int cover_r_rll = getFromMemo(r_rll); int cover_r_rlr = getFromMemo(r_rlr); int cover_r_rrl = getFromMemo(r_rrl); int cover_r_rrr = getFromMemo(r_rrr); int cover_r_ll = getFromMemo(r_ll); int cover_r_lr = getFromMemo(r_lr); int cover_r_rl = getFromMemo(r_rl); int cover_r_rr = getFromMemo(r_rr); int cover_r_l = getFromMemo(r_l); int cover_r_r = getFromMemo(r_r); // // choosing: root // int tmpRootCover = min( // // min( // // do not ignore // 1 + minCameraCover(r_ll) + minCameraCover(r_lr) + minCameraCover(r_rl) + minCameraCover(r_rr), // // 1 + minCameraCover(r_l) + minCameraCover(r_r) // // ), // // partly ignore root choosen // min( // 1 + minCameraCover(r_ll) + minCameraCover(r_lr) + minCameraCover(r_r),  // 1 + minCameraCover(r_rl) + minCameraCover(r_rr) + minCameraCover(r_l) // ) // ); int tmpRootCover = min( 1 + cover_r_ll + cover_r_lr + cover_r_rl + cover_r_rr, min( 1 + cover_r_ll + cover_r_lr + cover_r_r, 1 + cover_r_rl + cover_r_rr + cover_r_l ) ); // // choosing: right  // int tmpRightCover = min( // // don't ignore, will not put cam on r_rl, r_rr // 1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_l), // min( // // 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), // // 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) // ) // ); int tmpRightCover = min( 1 + cover_r_rll + cover_r_rlr + cover_r_rrl + cover_r_rrr + cover_r_l, min( 1 + cover_r_rrl + cover_r_rrr + cover_r_rl + cover_r_l, 1 + cover_r_rll + cover_r_rlr + cover_r_rr + cover_r_l ) ); // // choosing: left // int tmpLeftCover = min( // 1 + minCameraCover(r_lll) + minCameraCover(r_llr) + minCameraCover(r_lrl) + minCameraCover(r_lrr) + minCameraCover(r_r), // min( // 1 + minCameraCover(r_ll) + minCameraCover(r_lrl) + minCameraCover(r_lrr) + minCameraCover(r_r), // 1 + minCameraCover(r_lr) + minCameraCover(r_lll) + minCameraCover(r_llr) + minCameraCover(r_r) // ) // ); int tmpLeftCover = min( 1 + cover_r_lll + cover_r_llr + cover_r_lrl + cover_r_lrr + cover_r_r, min( 1 + cover_r_ll + cover_r_lrl + cover_r_lrr + cover_r_r, 1 + cover_r_lr + cover_r_lll + cover_r_llr + cover_r_r ) ); return min(tmpRootCover, min(tmpLeftCover, tmpRightCover)); } TreeNode* getR(TreeNode* root) { 
    if(nullptr == root) { 
    return nullptr; } else { 
    return root->right; } } TreeNode* getL(TreeNode* root) { 
    if(nullptr == root) { 
    return nullptr; } else { 
    return root->left; } } int getFromMemo(TreeNode* root) { 
    if(memo.end() == memo.find(root)) { 
    memo[root] = minCameraCover(root); } return memo[root]; } };

lcDFS1 深度优先遍历1[记忆化搜索]

1 深度优先遍历

2 例子

0332HierholzerToFindEulerPath 找欧拉路径

1 题目

2 解题思路

0753crackSafe 激活成功教程保险箱(变形欧拉路)

1 题目

2 解题思路

0514wayOfFreedom 自由之路

1 题目

2 解题思路

0968minCameraCover 监控二叉树

1 题目

2 解题思路

相关推荐