leetcode 困难题 753. Cracking the Safe 破解保险箱

Problem: 753. Cracking the Safe 破解保险箱

解题过程

太难了，不会的，看了官方题解和另一个人的题解，总算稍稍理解了，dfs(0);，dfs从0开始，因n-1个0，实际数值还是0，所以的话就从0开始了实际是从”000…00“开始的，欧拉回路最后回到原点，所以答案还需要拼接上n-1个0，也就是ans += string(n-1, ‘0’)，欧拉图看了一会才明白怎么连接的，具体的就是pow(k, n-1)个节点，按照题目的意思，需要尽可能的短，每个节点有k个边，从0，1，2，。。。，k-1编号，某个节点n-1个字符，加上编号index，就形成了n位的password，然后去掉第一个数字，就得到后面的n-1个数字即边连接的下一个节点，所以若当前节点是123456，选择的边是9，那么形成了1234569这个数字，去掉第一个数字234569，所以123456和234569通过边9相连

int nei = node * 10 + x;将边的编号拼接上去，seen.count(nei)统计边是否访问过，插入这个边seen.insert(nei)，nei % highest去掉第一个数字

Code

class Solution { public: // vector<string> tg; // void dfs(int n, int k, string str) { // if(n==0) { // tg.push_back(str); // return; // } // for(int i = 0; i < k; i++) { // str += (i+'0'); // dfs(n-1, k, str); // str.pop_back(); // } // } int k, highest; unordered_set<int> seen; string ans; string crackSafe(int n, int k) { // dfs(n-1, k, ""); this->k = k; highest = pow(10, n-1); dfs(0); // start from 000...0, length is n-1 ans += string(n-1, '0'); // back to 000...0, length n - 1 return ans; } void dfs(int node) { for(int x = 0; x < k; ++x) { int nei = node * 10 + x; // concat [n-1, index], get n digits if(!seen.count(nei)) { // remember edge had seen, length = n seen.insert(nei); // insert edge dfs(nei % highest); // get n-1 digits in tail, the next node ans += (x + '0'); // get answer } } } };