devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode专题：回溯与图论（完结，已更30题）_f_path.clear();

作者：AllinToyou | 2024-04-16 11:51:33

赞

踩

f_path.clear();

目录

LeetCode39/40.组合总和I/II（组合）：

问题描述：

39:

40:

代码分析：

39：

40：

LeetCode131/93.分割回文串/复原IP地址（分割）：

问题描述：

131：

93：

代码分析：

131：

93：

LeetCode46/47：全排列I/II（排列）：

问题描述：

46：

47：

代码分析：

46:

47：

LeetCode51/37.N皇后/解数独（棋盘）：

问题描述：

51：

37：

代码分析：

51：

37：

回溯+状压优化

LeetCode491/332/753.递增子序列/重新安排行程/破解保险箱：

问题描述：

491：

332：

753：

代码分析：

491：

332：

 方法一：Hicrholzer算法

753：

 法一：Hicrholzer

LeetCode127.单词接龙（双端BFS，难）：

问题描述：

代码分析：

法一：广度优先搜索+优化建图

法二：双向BFS

LeetCode403.青蛙过河：

问题描述：

代码分析：

DFS：

记忆化搜索：

动态规划：

BFS：

LeetCode417.太平洋大西洋水流问题：

问题描述：

代码分析：

法一：多源BFS

法二：DFS

法三：并查集

LeetCode433.最小基因变化：

问题描述：

代码分析：

法一：BFS

法二：双向BFS

法三：A* 算法

法三：建图 + DFS

LeetCode675.为高尔夫比赛砍树：

问题描述：

代码分析：

BFS：

A*算法：

A*算法 + 并查集预处理无解：

LeetCode752.打开转盘锁（类似127）：

问题描述：

代码分析：

双向BFS：

AStar 算法：

IDA* 算法：

LeetCode773.滑动谜题：

问题描述：

代码分析：

BFS：

A* 算法：

LeetCode815.公交路线：

问题描述：

代码分析：

朴素BFS：

双向BFS：

LeetCode847.访问所有节点的最短路径：

问题描述：

代码分析：

状态压缩+BFS：

Floyd+状压DP：

A* ：

LeetCode863.二叉树中所有距离为K的结点：

问题描述：

代码分析：

建图+BFS：

建图+迭代加深：

Map存储邻接节点（省去存图操作）：

LeetCode864.获取所有钥匙的最短路径：

问题描述：

代码分析：

LeetCode1036.逃离大迷宫：

问题描述：

代码分析：

BFS+给定障碍物所能围成的最大面积：

离散化+BFS（难）：

LeetCode1345.跳跃游戏IV：

问题描述：

代码分析：

单向BFS：

双向BFS：

LeetCode.跳跃游戏专栏：

LeetCode55.I：

LeetCode45.II：

 LeetCode1306.III：

广搜：

DFS转换为二叉树：

LeetCode1340.V：

递归：

记忆化搜索：

LeetCode1696.VI：

动态规划+优先队列优化：

动态规划+单调队列：

LeetCode1871.VII：

方法一：BFS+剪枝

方法二：动态规划+前缀和优化

完结......（90000字）

LeetCode39/40.组合总和I/II（组合）：

问题描述：

39:

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

40:

给定一个候选人编号的（有重复元素）集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次 。

注意：解集不能包含重复的组合（两题都是解集不重复）（注意区别！！！）

示例 1：

输入：candidates = [2, 3, 6, 7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

代码分析：

39：

        中规中矩。虽然组合中可以有重复元素，但为了使得解集不包含重复的组合，我们在for循环的时候就需要适当的逻辑。比如说有了 [2, 2, 3] 就不能有 [2, 3, 2] ，我们很容易想到严格限制下一层dfs所能够取得的值在当前层dfs所取值的之后位置！（即在startIndex之后）这样就能做到不重不漏（无需对candidates进行排序）。

        本题还需要startIndex来控制for循环的起始位置，我们已经见过多次。但是对于组合问题，什么时候需要startIndex呢？

        代码随想录 举过例子，如果是一个集合来求组合的话，就需要startIndex，例如：77. 组合，216. 组合总和 III；

        如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17. 电话号码的字母组合。

        注意以上 Carl哥 只是说求组合的情况，如果是排列问题，又是另一套分析的套路，后面再讲解排列的时候就重点介绍。

        直接上代码，我们重点讲第二题。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> res;
  4.     vector<int> path;
  5.     void dfs(vector<int> &candidates, int target, int sum, int startIndex) {
  6.         if(sum == target) {
  7.             res.emplace_back(path);
  8.             return;
  9.         }
  10.         //为了使得上一层的值不可能在本轮大于target，我们最好还需要将candidates数组进行排序，使得若当前元素不符合则之后元素一定不符合
  11.         for(int i = startIndex; i <= candidates.size() - 1; ++i) {
  12.             if(sum + candidates[i] <= target) {
  13.                 sum += candidates[i];
  14.                 path.emplace_back(candidates[i]);
  15.                 dfs(candidates, target, sum, i);
  16.                 sum -= candidates[i];
  17.                 path.pop_back();
  18.             }
  19.             //剪枝
  20.             else break;
  21.         }
  22.     }
  23.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  24.         res.clear();
  25.         path.clear();
  26.         sort(candidates.begin(), candidates.end());
  27.         dfs(candidates, target, 0, 0);
  28.         return res;
  29.     }
  30. };

——by 代码随想录

40：

        本题的难点在于：集合（数组candidates）有重复元素，但还不能有重复的组合。

        一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！所以要在搜索的过程中就去掉重复组合。

        都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

        那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

        回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

        所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

        不同树层相当于不同的元素子集，是不能有重复子集（注意子集的定义）的；而不同树枝上的相当于同一组合内的不同元素，是可以重复的。

        到这，我们已经不是很陌生了，在LeetCode专题：树与回溯 78.90.两题中已经预先探讨过此种做法，我们来复习一下。

        为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）再次强调一下，树层去重的话，需要对数组排序！

选择过程树形结构如图所示：

        先放used数组做法，再放直接用candidates进行去重的做法。

        前面我们提到：要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过了呢。

        由于树层和树枝都包含“使用过”的情况，所以判断条件中 candidates[i] == candidates[i - 1]肯定少不了。但是如何判断当前是在树层还是树枝？需要加上used[i - 1] == false（看代码可能会更清晰一点，这表明当前candidates[i]是从candidates[i - 1]回溯回来的，将used释放了；而将used置为true通过程序则表明进入了下一层递归）。

  1. /*使用used去重*/
  2. class Solution {
  3. private:
  4.     vector<vector<int>> result;
  5.     vector<int> path;
  6.     void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
  7.         if (sum == target) {
  8.             result.push_back(path);
  9.             return;
  10.         }
  11.         //&&后为剪枝逻辑，在第39题中提到
  12.         for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
  13.             // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  14.             // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
  15.             // 要对同一树层使用过的元素进行跳过
  16.             if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
  17.                 continue;
  18.             }
  19.             sum += candidates[i];
  20.             //注意，path和used都需要回溯
  21.             path.push_back(candidates[i]);
  22.             used[i] = true;
  23.             backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
  24.             used[i] = false;
  25.             sum -= candidates[i];
  26.             path.pop_back();
  27.         }
  28.     }
  29.  
  30. public:
  31.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  32.         //别忘全用false来初始化
  33.         vector<bool> used(candidates.size(), false);
  34.         path.clear();
  35.         result.clear();
  36.         // 首先把给candidates排序，让其相同的元素都挨在一起。
  37.         sort(candidates.begin(), candidates.end());
  38.         backtracking(candidates, target, 0, 0, used);
  39.         return result;
  40.     }
  41. };
  42. 作者：代码随想录
  1. /*candidates自身去重逻辑*/
  2. class Solution {
  3. public:
  4.     vector<vector<int>> res;
  5.     vector<int> path;
  6.     void dfs(vector<int> &candidates, int target, int sum, int startIndex) {
  7.         if(sum == target) {
  8.             res.emplace_back(path);
  9.             return;
  10.         }
  11.         //剪枝同理
  12.         for(int i = startIndex; i <= candidates.size() - 1; ++i) {
  13.             //
  14.             if(i > startIndex && candidates[i] == candidates[i - 1]) {
  15.                 continue;
  16.             }
  17.             if(sum + candidates[i] <= target) {
  18.                 sum += candidates[i];
  19.                 path.emplace_back(candidates[i]);
  20.                 dfs(candidates, target, sum, i+1);
  21.                 sum -= candidates[i];
  22.                 path.pop_back();
  23.             }
  24.             else break;
  25.         }
  26.     }
  27.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  28.         res.clear();
  29.         path.clear();
  30.         sort(candidates.begin(), candidates.end());
  31.         dfs(candidates, target, 0, 0);
  32.         return res;
  33.     }
  34. };

LeetCode131/93.分割回文串/复原IP地址（分割）：

问题描述：

131：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

93：

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

代码分析：

131：

        直接上代码：

  1. class Solution {
  2. public:
  3.     vector<vector<string>> res;
  4.     vector<string> path;
  5.     //需要记下当前层dfs截取到的字符串的末位的下标
  6.     void dfs(string s, int startIndex) {
  7.         if(startIndex == s.size()) {
  8.             res.emplace_back(path);
  9.             return;
  10.         }
  11.         for(int len = 1; len <=s.size() - startIndex; ++len) {
  12.             string sub = s.substr(startIndex, len);
  13.             if(check(sub)) {
  14.                 path.emplace_back(sub);
  15.                 dfs(s, startIndex + len);
  16.                 path.pop_back();
  17.             }
  18.         }
  19.     }
  20.     bool check(string s) {
  21.         string t = s;
  22.         reverse(t.begin(), t.end());
  23.         if(t == s)
  24.             return true;
  25.         else return false;    
  26.     }
  27.     vector<vector<string>> partition(string s) {
  28.         res.clear();
  29.         path.clear();
  30.         dfs(s, 0);
  31.         return res;
  32.     }
  33. };

93：

        也没有什么好说的，切割类的问题也是模板题：

  1. class Solution {
  2. public:
  3.     vector<string> res;
  4.     string path;
  5.     void dfs(string s, int startIndex, int count) {
  6.         /* 不能少判断了> s.size()的情况，因为startIndex可能超出s.size()*/
  7.         if(startIndex > s.size()) return;
  8.         if(startIndex == s.size() && count == 4) {
  9.             res.emplace_back(path);
  10.             return;
  11.         }
  12.         for(int len = 1; len <= s.size() - startIndex; ++len) {
  13.             string sub = s.substr(startIndex, len);
  14.             if(sub.size() > 1 && sub[0] == '0') continue;
  15.             //注意此处若不加sub.size()，由于题目的数据范围会使得stoi超出int报错
  16.             if(sub.size() > 3 || stoi(sub) > 255) continue;
  17.             path.append(sub);
  18.             if(startIndex + len != s.size()) {
  19.                 path.push_back('.');
  20.             }
  21.             //注意此处len > 1
  22.             dfs(s, startIndex + len, count + 1);
  23.             if(startIndex + len != s.size()) {
  24.                 path.pop_back();
  25.             }
  26.             path.erase(path.size() - len, len);
  27.         }    
  28.     }
  29.  
  30.     vector<string> restoreIpAddresses(string s) {
  31.         res.clear();
  32.         dfs(s, 0, 0);
  33.         return res;
  34.     }
  35. };

LeetCode46/47：全排列I/II（排列）：

问题描述：

46：

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列（区别于子集的概念） 。你可以 按任意顺序 返回答案。

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

47：

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

代码分析：

46:

        就是我们在《啊哈算法》中很熟悉的全排列问题，直接用vector数组去重即可：

  1. class Solution {
  2. public:
  3.     vector<vector<int>> res;
  4.     vector<int> path;
  5.     void dfs(vector<int> & nums, int step, vector<bool> &used) {
  6.         if(step == nums.size() + 1) {
  7.             res.emplace_back(path);
  8.             return;
  9.         }
  10.         for(int i = 0; i <= nums.size() - 1; ++i) {
  11.             if(used[i] == true) {
  12.                 used[i] = false;
  13.                 path.emplace_back(nums[i]);
  14.                 dfs(nums, step + 1, used);
  15.                 path.pop_back();
  16.                 used[i] = true;
  17.             }
  18.         }
  19.     }
  20.     vector<vector<int>> permute(vector<int>& nums) {
  21.         res.clear();
  22.         path.clear();
  23.         //可用状态
  24.         vector<bool> used(nums.size(), true);
  25.         dfs(nums, 1, used);
  26.         return res;
  27.     }    
  28. };

47：

        虽然有重复数字，但是重复的数字之间可没有排队顺序的区别！也就是说[1, 1, 2]与[1, 1, 2]之间没有区别！一个比较好想的办法就是树枝（还是前面提到的概念）中确保每个元素都使用到（从0开始而非startIndex），树层间跳过相同的元素即可（前提是将nums排好序，使得相同元素贴在一起）。另外注意本题和90.子集II的区别：在树层之间是否需要使用startIndex！（归根结底还是子集与排列的区别）

  1. class Solution {
  2. public:
  3.     vector<vector<int>> res;
  4.     vector<int> path;
  5.     void dfs(vector<int> & nums, int step, vector<bool> &used) {
  6.         if(step == nums.size() + 1) {
  7.             res.emplace_back(path);
  8.             return;
  9.         }
  10.         //注意下标并非从startIndex开始
  11.         for(int i = 0; i <= nums.size() - 1; ++i) {
  12.             if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
  13.                 continue;
  14.             if(used[i] == false) {
  15.                 used[i] = true;
  16.                 path.emplace_back(nums[i]);
  17.                 dfs(nums, step + 1, used);
  18.                 path.pop_back();
  19.                 used[i] = false;
  20.             }
  21.         }
  22.     }
  23.     vector<vector<int>> permuteUnique(vector<int>& nums) {
  24.         res.clear();
  25.         path.clear();
  26.         //未使用即0 false, 使用过即1 true
  27.         sort(nums.begin(), nums.end());
  28.         vector<bool> used(nums.size(), false);
  29.         dfs(nums, 1, used);
  30.         return res;
  31.     }    
  32. };

        这里透露一下。去重部分的 used[]i - 1] == false 如果改成 used[i - 1] == true， 也是正确的!

        这是为什么呢？如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

        对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

        我们举[1, 1, 1]这个极为特殊的例子来分别理解一下树层去重和树枝去重的过程。

        树层上去重(used[i - 1] == false)，的树形结构如下：

        树枝上去重（used[i - 1] == true）的树型结构如下：

        大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

——by 代码随想录

LeetCode51/37.N皇后/解数独（棋盘）：

问题描述：

51：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

37：

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

 

代码分析：

51：

        常规经典的回溯题，可能难在条件的判断上，我们直接贴代码，插一嘴，这一题也适合2023/3/5米哈游的笔试题原型，并非老掉牙不会再考了。

  1. class Solution {
  2. public:
  3.     vector<vector<string>> res;
  4.     //n为输入棋盘的大小
  5.     //棋盘为实例传参
  6.     //row为当前行
  7.     void dfs(int n, int row, vector<string> &chessbord) {
  8.         if(row == n) {
  9.             res.emplace_back(chessbord);
  10.             return;
  11.         }
  12.         for(int col = 0; col <= n - 1; ++col) {
  13.             if(isValid(row, col, chessbord, n)) {
  14.                 chessbord[row][col] = 'Q';
  15.                 dfs(n, row + 1, chessbord);
  16.                 chessbord[row][col] = '.';
  17.             }
  18.         }
  19.     }
  20.     bool isValid(int row, int col, vector<string> &chessbord, int n) {
  21.         //先检查列
  22.         for(int i = 0; i <= row - 1; ++i) {
  23.             if(chessbord[i][col] == 'Q') 
  24.                 return false;
  25.         }
  26.         //再检检查对角线
  27.         for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
  28.             if(chessbord[i][j] == 'Q') 
  29.                 return false;
  30.         }
  31.         for(int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; --i, ++j) {
  32.             if(chessbord[i][j] == 'Q') 
  33.                 return false;
  34.         }
  35.         return true;        
  36.     }
  37.     vector<vector<string>> solveNQueens(int n) {
  38.         res.clear();
  39.         vector<string> chessbord(n, string(n, '.'));
  40.         dfs(n, 0, chessbord);
  41.         return res; 
  42.     }
  43. };

37：

        本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。因为这个树形结构太大了，抽取一部分，如图所示：

  • 递归函数的返回值需要是bool类型，为什么呢？

        因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。

  • 不用终止条件会不会死循环？

        递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！

  • 注意代码中 return false的地方，这里放return false 是有讲究的。

        因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！

  1. class Solution {
  2. public:
  3.     bool dfs(vector<vector<char>> &board) {
  4.         //逐行逐层扫描
  5.         for(int i = 0; i < board.size(); ++i) {
  6.             for(int j = 0; j < board[0].size(); ++j) {
  7.                 if(board[i][j] == '.') {
  8.                     for(char k = '1'; k <= '9'; ++k) {
  9.                         if(isValid(i, j, k, board)) {
  10.                             board[i][j] = k;
  11.                             //注意此处既是递归调用，又是判断是否终止的剪枝（如果基于当前摆放的最终棋盘满足要求，就没必要继续寻找别的可能）
  12.                             if(dfs(board)) 
  13.                                 //注意所有的return都是返回到上一级调用处，所以只要有true，就一直退出dfs
  14.                                 return true;
  15.                             board[i][j] = '.';    
  16.                         }
  17.                     }
  18.                     return false;
  19.                 }
  20.             }
  21.         }
  22.         return true;
  23.     }
  24.  
  25.     bool isValid(int row, int col, char val, vector<vector<char>> &board) {
  26.         for (int i = 0; i < 9; i++) { // 判断行里是否重复
  27.             if (board[row][i] == val) {
  28.                 return false;
  29.             }
  30.         }
  31.         for (int j = 0; j < 9; j++) { // 判断列里是否重复
  32.             if (board[j][col] == val) {
  33.                 return false;
  34.             }
  35.         }
  36.         int startRow = (row / 3) * 3; 
  37.         int startCol = (col / 3) * 3;
  38.         for (int i = startRow; i < startRow + 3; ++i) { // 判断九宫格里是否重复
  39.             for (int j = startCol; j < startCol + 3; ++j) {
  40.                 if(board[i][j] == val) {
  41.                     return false;
  42.                 }
  43.             }
  44.         }
  45.         return true;
  46.     }
  47.  
  48.     void solveSudoku(vector<vector<char>>& board) {
  49.         //实际内部修改的是传参本身，返回值对外部无影响，只作用于递归函数判断条件
  50.         dfs(board);
  51.     }
  52. };

回溯+状压优化

        上述做法是朴素的回溯，我们要看的是 Ikaruga 的使用Bitset的做法：

        状态压缩使用 bitset<9> 来压缩存储每一行、每一列、每一个 3x3 宫格中 1-9 是否出现，这样每一个格子就可以计算出所有不能填的数字，然后得到所有能填的数字getPossibleStatus()。填入数字和回溯时，只需要更新存储信息，每个格子在使用时，会根据存储信息重新计算能填的数字。

        每次回溯都使用 getNext() 选择能填的数字最少的格子开始填，这样填错的概率最小，回溯次数也会变少，使用 fillNum() 在填入和回溯时负责更新存储信息一旦全部填写成功，一路返回 true ，结束递归。

  1. class Solution {
  2.  
  3. public:
  4.     //从存储信息中获得board[i][j]上可以填的候选数字
  5.     bitset<9> getPossibleStatus(int x, int y)
  6.     {
  7.         //按位取反
  8.         return ~(rows[x] | cols[y] | cells[x / 3][y / 3]); //rows、cols、cells是主函数中预处理的board各点的二进制信息（二维数组），可以用bitset运算并存储
  9.     }
  10.     //从存储信息中获取当前board中候选数字最少的空白格
  11.     vector<int> getNext(vector<vector<char>>& board)
  12.     {
  13.         //这里用vector来存储选中的格子的行列二元组
  14.         vector<int> ret;
  15.         int minCnt = 10;
  16.         for (int i = 0; i < board.size(); i++)
  17.         {
  18.             for (int j = 0; j < board[i].size(); j++)
  19.             {
  20.                 if (board[i][j] != '.') continue;
  21.                 auto cur = getPossibleStatus(i, j);
  22.                 //count()用于计算bitset中1的个数
  23.                 if (cur.count() >= minCnt) continue;
  24.                 ret = { i, j };
  25.                 minCnt = cur.count();
  26.             }
  27.         }
  28.         return ret;
  29.     }
  30.     //在填入和回溯时更新borad[x][y]的存储信息（所在的行、列、3*3 宫格 都已经有了哪些数字）。
  31.     //fillFlag = true : 填入; false : 回溯
  32.     void fillNum(int x, int y, int n, bool fillFlag)
  33.     {
  34.         rows[x][n] = (fillFlag) ? 1 : 0;
  35.         cols[y][n] = (fillFlag) ? 1 : 0;
  36.         cells[x/3][y/3][n] = (fillFlag) ? 1: 0;
  37.     }
  38.     
  39.     bool dfs(vector<vector<char>>& board, int cnt)
  40.     {
  41.         if (cnt == 0) return true; //所有空白格都填完，递归结束
  42.         auto next = getNext(board); //board中候选数字最少的空白格（二元组[x, y]）
  43.         auto bits = getPossibleStatus(next[0], next[1]); //该格子可填的候选数字
  44.         for (int n = 0; n < bits.size(); n++) // 1~9 -> 0~8
  45.         {
  46.             //test用于检查bits[n]是为0/1并返回0/1
  47.             if (!bits.test(n)) continue; //数字 n + 1 不是能填入的数字，直接跳过
  48.             fillNum(next[0], next[1], n, true); //填入时更新bitset的存储信息
  49.             board[next[0]][next[1]] = n + '1'; //填入
  50.             if (dfs(board, cnt - 1)) return true; //同上一种做法理
  51.             board[next[0]][next[1]] = '.'; //擦除
  52.             fillNum(next[0], next[1], n, false); 回溯时还原bitset的存储信息
  53.         }
  54.         return false;
  55.     }
  56.  
  57.     void solveSudoku(vector<vector<char>>& board) 
  58.     {
  59.         rows = vector<bitset<9>>(9, bitset<9>());
  60.         cols = vector<bitset<9>>(9, bitset<9>());
  61.         cells = vector<vector<bitset<9>>>(3, vector<bitset<9>>(3, bitset<9>()));
  62.  
  63.         int cnt = 0; //数独board中需要填的空白格个数
  64.         //压缩存储每一行、每一列、每一个3*3宫格中都出现了哪些数字
  65.         for (int i = 0; i < board.size(); i++)
  66.         {
  67.             for (int j = 0; j < board[i].size(); j++)
  68.             {
  69.                 if (board[i][j] == '.') {
  70.                     cnt++;
  71.                     continue;
  72.                 }
  73.                 int n = board[i][j] - '1';
  74.                 rows[i] |= (1 << n);
  75.                 cols[j] |= (1 << n);
  76.                 cells[i / 3][j / 3] |= (1 << n);
  77.             }
  78.         }
  79.         dfs(board, cnt);
  80.     }
  81.  
  82. private:
  83.  
  84.     vector<bitset<9>> rows;
  85.     vector<bitset<9>> cols;
  86.     vector<vector<bitset<9>>> cells;
  87.  
  88. };
  89. 作者：Ikaruga

 

        复习一下位运算：

LeetCode491/332/753.递增子序列/重新安排行程/破解保险箱：

问题描述：

491：

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]

332：

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

  • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

753：

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位都是范围 [0, k - 1] 中的一个数字。

保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 最后 n 位输入 ，如果匹配，则能够打开保险箱。

在只知道密码位数 n 和范围边界 k 的前提下，请你找出并返回确保在输入的 某个时刻 能够打开保险箱的任一 最短 密码序列 。

输入：n = 2, k = 2
输出："01100"
解释：对于每种可能的密码：
- "00" 从第 4 位开始输入。
- "01" 从第 1 位开始输入。
- "10" 从第 3 位开始输入。
- "11" 从第 2 位开始输入。
因此 "01100" 可以确保打开保险

代码分析：

491：

        经过前面题目的洗礼，我们很快写出以下框架：

  1. class Solution {
  2. public:
  3.     //unordered_map<...> map;
  4.     vector<vector<int>> res;
  5.     vector<int> path;
  6.     int top = -101;
  7.     void dfs(vector<int> &nums, int startIndex) {
  8.         if(startIndex == nums.size() && 去重逻辑) {
  9.             res.emplace_back(path);
  10.             return;
  11.         }
  12.         for(int i = startIndex; i <= nums.size() - 1; ++i) {
  13.             if(nums[i] >= top) {
  14.                 //可以选择
  15.                 path.emplace_back(nums[i]);
  16.                 dfs(nums, i + 1);
  17.                 path.pop_back();
  18.                 //也可以不选择
  19.                 dfs(nums, i + 1);
  20.             }
  21.         }
  22.     }
  23.     vector<vector<int>> findSubsequences(vector<int>& nums) {
  24.         res.clear();
  25.         path.clear();
  26.         dfs(nums, 0);
  27.         return res;
  28.     }
  29. };

        我们发现，只要妥善处理好去重的逻辑即可。一种最朴素的方式是使用unordered_map进行去重，当然，如果我们简单地这样枚举，对于每一个子序列，我们还需要做一次 O(n) 的合法性检查和哈希判重复，在执行整个程序的过程中，我们还需要使用一个空间代价 O(2^n) 的哈希表来维护已经出现的子序列的哈希值。

        在上面的个人解法中，除了没写出来的哈希表逻辑以外，我们的去重保障是：只有当前元素大于等于上一个选择的元素的时候才能选择这个元素，并且我们要使用startIndex逻辑，这样枚举出来的所有元素都是合法的。但这种“明智的做法”并不适用本题，别忘了，本题中的元素可以选择也可以不选择，结束dfs的时机也是选择性的！

        正确的做法？

        我们需要给「不选择」做一个限定条件，只有当前的元素不等于上一个选择的元素的时候，才考虑不选择当前元素，直接递归后面的元素。因为如果有两个相同的元素，我们会考虑这样四种情况：

  1. 前者被选择，后者被选择
  2. 前者被选择，后者不被选择
  3. 前者不被选择，后者被选择
  4. 前者不被选择，后者不被选择

        其中第二种情况和第三种情况其实是等价的，我们这样限制之后，舍弃了第二种，保留了第三种，于是达到了去重的目的。

  1. class Solution {
  2. public: 
  3.     vector<vector<int>> ans;
  4.     vector<int> temp;
  5.  
  6.     void dfs(int cur, int last, vector<int>& nums) {
  7.         //注意cur即为当前元素的下标，递归函数此时仅有两种情况：选择与不选择。
  8.         //考虑到temp数组中只要有两个以上符合条件的元素即可加入ans结果集，若终止的时机不固定，则此题没法解决。所以我们要让时机强制固定下来（必须等到dfs访问到数组末的元素才可以把temp加入结果集）。可以理解成：长度为小于等于nums.size()的数组（排除非递增部分）中，每个元素都可以加入或不加，一共有多少种temp方案。
  9.         //我们抛弃了for循环枚举所有元素的做法，步步为营，把每次选取一元素下发给每一层dfs，而此时枚举的是元素是否被选取。
  10.         if (cur == nums.size()) {
  11.             if (temp.size() >= 2) {
  12.                 ans.push_back(temp);
  13.             }
  14.             return;
  15.         }
  16.         if (nums[cur] >= last) {
  17.             temp.push_back(nums[cur]);
  18.             dfs(cur + 1, nums[cur], nums);
  19.             temp.pop_back();
  20.         }
  21.         if (nums[cur] != last) {
  22.             dfs(cur + 1, last, nums);
  23.         }
  24.     }
  25.  
  26.     vector<vector<int>> findSubsequences(vector<int>& nums) {
  27.         dfs(0, INT_MIN, nums);
  28.         return ans;
  29.     }
  30. };
  31. 作者：力扣官方题解

332：

        比较难，无论是回溯终止条件的选取，还是排序的规则，或是元素的表示方法。

        本题与 753. 破解保险箱 类似，均为求解欧拉回路/欧拉通路的问题。

        我们化简本题题意：给定一个 n 个点 m 条边的图，要求从指定的顶点出发，经过所有的边恰好一次（可以理解为给定起点的「一笔画」问题），使得路径的字典序最小。

        这种「一笔画」问题与欧拉图或者半欧拉图有着紧密的联系，下面给出定义：

  • 通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路；
  • 通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路；
  • 具有欧拉回路的无向图称为欧拉图；
  • 具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。

        因为本题保证至少存在一种合理的路径，也就告诉了我们，这张图是一个欧拉图或者半欧拉图。我们只需要输出这条欧拉通路的路径即可。

        我们插一嘴，如果没有保证至少存在一条合理的路径，则需要判别这张图是否是欧拉图或者半欧拉图，具体地：

  • 对于无向图 G，G 是欧拉图当且仅当 G 是连通的且没有奇度顶点。
  • 对于无向图 G，G 是半欧拉图当且仅当 G 是连通的且 G 中恰有 0 个或 2 个奇度顶点。
  • 对于有向图 G，G 是欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
  • 对于有向图 G，G 是半欧拉图当且仅当：

        1.如果将 G 中的所有有向边退化为无向边时，那么 G 的所有顶点属于同一个强连通分量；

        2.最多只有一个顶点的出度与入度差为 1；

        3.最多只有一个顶点的入度与出度差为 1；

        4.所有其他顶点的入度和出度相同。

考虑如下的图：

         从起点JFK出发，合法的路径有两条：

  • JFK→AAA→JFK→BBB→JFK
  • JFK→BBB→JFK→AAA→JFK

        既然要求字典序最小，那么每次应该贪心地选择当前节点所连节点中字典序最小的那个，并将其入栈。最后栈中就保存了我们遍历的顺序。

        如何快速找到字典序最小的呢？可以使用优先队列存储当前节点所连到的点。每次我们 O(1) 地找到最小字典序的节点，并 O(log⁡m)地删除它。

        接下来我们考虑一种特殊情况：

        当我们先访问AAA时，无法回到JFK，这样就无法访问剩余的边。

        也就是说，当我们贪心地选择字典序最小的节点前进时，我们可能先走入「死胡同」，从而导致无法遍历到其他还未访问的边。于是我们希望能够遍历完当前节点所连接的其他节点后再进入「死胡同」。

        注意：对于每一个节点，它只有最多一个「死胡同」分支。依据前言中对于半欧拉图的描述，只有那个入度与出度差为 1 的节点会导致「死胡同」。

 方法一：Hicrholzer算法

        该算法用于在连通图中寻找欧拉路径，其流程如下：

  1. 从起点出发，进行深度优先搜索。
  2. 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。
  3. 如果没有可移动的路径，则将所在节点加入到栈中，并返回。

  1. class Solution {
  2. public:
  3.     unordered_map<string（出发城市）, priority_queue<string（出发城市）, vector<string>（出发城市所连接的到达城市的集合）, std::greater<string>>（优先队列greater从小到大）> vec;
  4.  
  5.     vector<string> stk;
  6.  
  7.     void dfs(const string& curr) {
  8.         while (vec.count(curr) && vec[curr].size() > 0) {
  9.             //堆top为字典序最小的
  10.             string tmp = vec[curr].top();
  11.             vec[curr].pop();
  12.             //不可以把局部变量tmp传递给dfs值引用
  13.             dfs(move(tmp));
  14.         }
  15.         //最后才放入当前节点，使得stk为逆序
  16.         stk.emplace_back(curr);
  17.     }
  18.  
  19.     vector<string> findItinerary(vector<vector<string>>& tickets) {
  20.         //遍历每一个航班
  21.         for (auto& it : tickets) {
  22.             vec[it[0]].emplace(it[1]);
  23.         }
  24.         dfs("JFK");
  25.  
  26.         reverse(stk.begin(), stk.end());
  27.         return stk;
  28.     }
  29. };
  30. 作者：力扣官解

        看完代码，肯定有很多疑惑，我们引用 leodaddy ：

  1. 由于题目中说必然存在一条有效路径(至少是半欧拉图)，所以算法不需要回溯（加入到结果集里的元素不需要删除）
  2. 整个图最多只有一个死胡同（出入度相差为1），并且该死胡同一定是最后一个被访问到的，否则无法完成一笔画。
  3. DFS的调用其实是一个拆边的过程（既每次递归调用删除一条边，所有子递归都返回后，再将当前节点加入结果集保证了结果集的逆序输出），一定是递归到这个死胡同（没有子递归可以调用）后递归函数开始返回。所以死胡同是第一个加入结果集的元素。
  4. 最后逆序输出。

        我们再来看 代码随想录 的思路：

  • 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系？

        一个城市映射多个城市并且城市之间要用字母序排列。一映射多，可以使用unordered_map。而让城市之间有顺序就得用map/multimap/multiset。

        因此存放映射关系可以定义为 unordered_map<string（出发城市）, multiset<string>（到达城市的集合）>  或者 unordered_map<string（出发城市）, map<string（到达城市）, int（航班次数）>>。

        那么我们到底选择那一个呢？

        如果使用unordered_map<string, multiset<string>> 遍历multiset的时候，不能删除元素！一旦删除元素，迭代器就失效了。而本地在回溯的过程中就是要不断的增删 multiset里的元素，所以我们使用unordered_map<string, map<string, int>> targets。

        在遍历 unordered_map<出发城市, map<到达城市, 航班次数>> targets的过程中，可以使用航班次数这个字段的数字 --或者++，来标记到达城市是否使用过了，而不用对集合做删除元素或者增加元素的操作。

  • 这是一个图不是一棵树，使用深搜/回溯的终止条件是什么呢？

        以题中的示例，输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]。一共四个航班，只要找出一种行程路线。如果机场个数达到了航班数+1，那我们就成功找到了行程。

  • 回溯的过程中，如何遍历一个城市所对应的所有城市？

        我们刚刚说了，不能选用“一旦有元素增删，容器的迭代器就会失效”的multiset。此外有些题解使用了例如list的迭代器，使用splice来保证迭代器不失效。

  • 为什么一定要增删元素？

        出发城市和到达城市是会重复的，搜索的过程若没及时删除元素就会进入死循环，如图所示：

  1. class Solution {
  2. public:
  3.     unordered_map<string, map<string, int>> targets;
  4.     //ticketNum为当前航班数,result为结果集
  5.     bool dfs(int ticketNum, vector<string> &result) {
  6.         if(result.size() == ticketNum + 1) {
  7.             return true;
  8.         }
  9.         //以当前result顶部元素作为出发城市开始拓展,使用计数器代替了从容器中真正删除元素
  10.         for(pair<const string, int> &target : targets[result[result.size() - 1]]) {
  11.             //为0即使用过
  12.             if(target.second > 0) {
  13.                 result.emplace_back(target.first);
  14.                 --target.second;
  15.                 //为true则一直返回
  16.                 if(dfs(ticketNum, result)) 
  17.                     return true;
  18.                 result.pop_back();
  19.                 ++target.second;    
  20.             }
  21.         }
  22.         return false;
  23.     }
  24.     vector<string> findItinerary(vector<vector<string>>& tickets) {
  25.         targets.clear();
  26.         vector<string> result;
  27.         //预处理targets集合
  28.         for(const vector<string> &vec : tickets) {
  29.             targets[vec[0]][vec[1]]++;
  30.         }
  31.         //别忘记在result中先放入起点
  32.         result.emplace_back("JFK");
  33.         dfs(tickets.size(), result);
  34.         return result;
  35.     }
  36. };

753：

        本题和上一题类似，都是LeetCode平台为数不多的求解欧拉通路/欧拉回路的题目。

        由于翻译问题，本题文字信息不是很好能被接受，真实意图为：返回所有结果的最小综合子串。

        上一题是所有边一笔画，典型的欧拉问题，而本题严格来讲，当理解为n-1个节点和1个节点之间连线时是欧拉回路，而当理解为n个节点时所有节点一笔画，是哈密顿回路。

        下面引用 我爱志方小姐 ：

 法一：Hicrholzer

        具体地，我们将所有的 n−1 位数作为节点，共有 k^{n-1} 个节点，每个节点有 k 条入边和出边。如果当前节点对应的数为 a1a2⋯an−1，那么它的第 x 条出边就连向数 a2⋯an−1x 对应的节点。这样我们从一个节点顺着第 x 条边走到另一个节点，就相当于输入了数字 x。

        在某个节点对应的数的末尾放上它的某条出边的编号，就形成了一个 n 位数，并且每个节点都能用这样的方式形成 k 个 n 位数。

  • 例如 k=4，n=3 时，节点分别为 00,01,02,⋯ ,32,33，每个节点的出边的编号分别为 0,1,2,3，那么 00 和它的出边形成了 000,001,002,003 这 4 个 3 位数，32 和它的出边形成了 320,321,322,323 这 4 个 3 位数。

        这样共计有 k^{n−1}×k=k^{n}  个 n 位数，恰好就是所有可能的密码。

        由于这个图的每个节点都有 k 条入边和出边，因此它一定存在一个欧拉回路，即可以从任意一个节点开始，一次性不重复地走完所有的边且回到该节点。因此，我们可以用 Hierholzer 算法找出这条欧拉回路：

        设起始节点对应的数为 u，欧拉回路中每条边的编号为 x1,x2,x3,⋯，那么最终的字符串即为ux_{1} x_{2} x_{3}...

        Hierholzer 算法如下：

  • 我们从节点 u 开始，任意地经过还未经过的边，直到我们「无路可走」。此时我们一定回到了节点 u，这是因为所有节点的入度和出度都相等。
  • 回到节点 u 之后，我们得到了一条从 u 开始到 u 结束的回路，这条回路上仍然有些节点有未经过的出边。我么从某个这样的节点 v 开始，继续得到一条从 v 开始到 v 结束的回路，再嵌入之前的回路中，即从

u->...->v->...->u

变为

u->...->v->...->v->...->u

        以此类推，直到没有节点有未经过的出边，此时我们就找到了一条欧拉回路。

  1. class Solution {
  2. public:
  3.     unordered_set<int> seen;
  4.     string ans;
  5.     int heighest;
  6.     int k;
  7.     void dfs(int node) {
  8.         for(int x = 0 ; x < k; ++x) {
  9.             int nei = node *10 + x;
  10.             if(!seen.count(nei)) {
  11.                 seen.insert(nei);
  12.                 dfs(nei % height);
  13.                 ans += (x + '0');
  14.             }
  15.         }
  16.     }
  17.     string crackSafe(int n, int k) {
  18.         highest = pow(10, n - 1);
  19.         this->k = k;
  20.         dfs(0);
  21.         ans += string(n - 1, '0');
  22.         return ans;
  23.     }
  24. };

        时空复杂度均为O(n * k^n)。本题这种拓扑结构的类型比较难，优先级可以放后。

LeetCode127.单词接龙（双端BFS，难）：

问题描述：

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

  • 每一对相邻的单词只差一个字母。
  •  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

代码分析：

法一：广度优先搜索+优化建图

        题目要求最短转换序列长度，“最短”首先想到的是广搜。本题没有直接给出图的模型，所以我们要按照题目意思抽象建立图的模型。

        我们可以把每个单词都抽象为一个点，如果两个单词可以只改变一个字母进行转换，那么说明他们之间有一条双向边。因此我们只需要把满足转换条件的点相连，就形成了一张图。

        基于该图，我们以 beginWord 为图的起点，以 endWord 为终点进行广度优先搜索，寻找 beginWord 到 endWord 的最短路径。

        如图所示：

        基于上面的思路，我们思考如何编程实现：

        首先为了方便表示，我们先给每一个单词标号，即给每个单词分配一个 id。创建一个由单词 word 到 id 对应的映射 wordId，并将 beginWord 与 wordList 中所有的单词都加入这个映射中。之后我们检查 endWord 是否在该映射内，若不存在，则输入无解。我们可以使用哈希表实现上面的映射关系。

        然后我们需要建图，依据朴素的思路，我们可以尝试枚举每一对单词的组合，判断它们是否恰好相差一个字符，以判断这两个单词对应的节点是否能够相连。但是这样效率太低，我们可以优化建图。

  • 具体地，我们可以创建虚拟节点。对于单词 hit，我们创建三个虚拟节点 *it、h*t、hi*，并让 hit 向这三个虚拟节点分别连一条边即可。如果一个单词能够转化为 hit，那么该单词必然会连接到这三个虚拟节点之一。对于每一个单词，我们枚举它连接到的虚拟节点，把该单词对应的 id 与这些虚拟节点对应的 id 相连即可。

        最后我们将起点加入队列开始广度优先搜索，当搜索到终点时，我们就找到了最短路径的长度。注意因为添加了虚拟节点，所以我们得到的距离为实际最短路径长度的两倍。同时我们并未计算起点对答案的贡献，所以我们应当返回距离的一半再加一的结果。

  1. class Solution {
  2. public:
  3.     unordered_map<string, int> wordId;
  4.     vector<vector<int>> edge;
  5.     int nodeNum = 0;
  6.  
  7.     void addWord(string &word) {
  8.         if(!wordId.count(word)) {
  9.             wordId[word] = nodeNum++;
  10.             edge.emplace_back();
  11.         }
  12.     }
  13.         
  14.     void addEdge(string &word) {
  15.         addWord(word);
  16.         int id1 = wordId[word];
  17.         for(char &it : word) {
  18.             char tmp = it;
  19.             it = '*'; //注意是值引用传递，会修改Word原串
  20.             addWord(word);
  21.             int id2 = wordId[word];
  22.             //彼此建立连接
  23.             edge[id1].push_back(id2);
  24.             edge[id2] .push_back(id1);
  25.             it = tmp;
  26.         }
  27.     }
  28.  
  29.     int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
  30.         for(string &word : wordList) {
  31.             addEdge(word);
  32.         }
  33.         addEdge(beginWord);
  34.         if(!wordId.count(endWord)) 
  35.             return 0;
  36.         //计数器，nodeNum恰好为算上模糊态的所有词数    
  37.         vector<int> dis(nodeNum, INT_MAX);
  38.         int beginId = wordId[beginWord], endId =  wordId[endWord];
  39.         dis[beginId] = 0; 
  40.         //开始BFS
  41.         queue<int> que;
  42.         que.push(beginId);
  43.         while(!que.empty()) {
  44.             int x = que.front();
  45.             que.pop();
  46.             if(x == endId) {
  47.                 return dis[endId] / 2 + 1;
  48.             }
  49.             for(int &it : edge[x]) {
  50.                 if(dis[it] == INT_MAX) {
  51.                     dis[it] = dis[x] + 1;
  52.                     que.push(it);
  53.                 }
  54.             }
  55.         }
  56.         return 0;
  57.     }
  58. };

        时间复杂度：O(N * C^2)，N为wordList长度，C为列表中单词的长度。

        建图过程中，对于每一个单词，我们需要枚举它连接到的所有虚拟节点，时间复杂度为 O(C)，将这些单词加入到哈希表中，时间复杂度为 O(N×C)，因此总时间复杂度为 O(N×C)。

广度优先搜索的时间复杂度最坏情况下是 O(N×C)。每一个单词需要拓展出 O(C) 个虚拟节点，因此节点数 O(N×C)。

法二：双向BFS

        根据给定字典构造的图可能会很大，而广度优先搜索的搜索空间大小依赖于每层节点的分支数量。假如每个节点的分支数量相同，搜索空间会随着层数的增长指数级的增加。考虑一个简单的二叉树，每一层都是满二叉树的扩展，节点的数量会以 2 为底数呈指数增长。

        如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始，另一边从 endWord 开始。我们每次从两边各扩展一层节点，当发现某一时刻两边都访问过同一顶点时就停止搜索。这就是双向广度优先搜索，它可以可观地减少搜索空间大小，从而提高代码运行效率。如下图：

  1. class Solution {
  2. public:
  3.     unordered_map<string, int> wordId;
  4.     vector<vector<int>> edge;
  5.     int nodeNum = 0;
  6.  
  7.     void addWord(string& word) {
  8.         if (!wordId.count(word)) {
  9.             wordId[word] = nodeNum++;
  10.             edge.emplace_back();
  11.         }
  12.     }
  13.  
  14.     void addEdge(string& word) {
  15.         addWord(word);
  16.         int id1 = wordId[word];
  17.         for (char& it : word) {
  18.             char tmp = it;
  19.             it = '*';
  20.             addWord(word);
  21.             int id2 = wordId[word];
  22.             edge[id1].push_back(id2);
  23.             edge[id2].push_back(id1);
  24.             it = tmp;
  25.         }
  26.     }
  27.  
  28.     int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
  29.         for (string& word : wordList) {
  30.             addEdge(word);
  31.         }
  32.         addEdge(beginWord);
  33.         if (!wordId.count(endWord)) {
  34.             return 0;
  35.         }
  36.  
  37.         vector<int> disBegin(nodeNum, INT_MAX);
  38.         int beginId = wordId[beginWord];
  39.         disBegin[beginId] = 0;
  40.         queue<int> queBegin;
  41.         queBegin.push(beginId);
  42.  
  43.         vector<int> disEnd(nodeNum, INT_MAX);
  44.         int endId = wordId[endWord];
  45.         disEnd[endId] = 0;
  46.         queue<int> queEnd;
  47.         queEnd.push(endId);
  48.  
  49.         while (!queBegin.empty() && !queEnd.empty()) {
  50.             int queBeginSize = queBegin.size();
  51.             for (int i = 0; i < queBeginSize; ++i) {
  52.                 int nodeBegin = queBegin.front();
  53.                 queBegin.pop();
  54.                 if (disEnd[nodeBegin] != INT_MAX) {
  55.                     return (disBegin[nodeBegin] + disEnd[nodeBegin]) / 2 + 1;
  56.                 }
  57.                 for (int& it : edge[nodeBegin]) {
  58.                     if (disBegin[it] == INT_MAX) {
  59.                         disBegin[it] = disBegin[nodeBegin] + 1;
  60.                         queBegin.push(it);
  61.                     }
  62.                 }
  63.             }
  64.  
  65.             int queEndSize = queEnd.size();
  66.             for (int i = 0; i < queEndSize; ++i) {
  67.                 int nodeEnd = queEnd.front();
  68.                 queEnd.pop();
  69.                 if (disBegin[nodeEnd] != INT_MAX) {
  70.                     return (disBegin[nodeEnd] + disEnd[nodeEnd]) / 2 + 1;
  71.                 }
  72.                 for (int& it : edge[nodeEnd]) {
  73.                     if (disEnd[it] == INT_MAX) {
  74.                         disEnd[it] = disEnd[nodeEnd] + 1;
  75.                         queEnd.push(it);
  76.                     }
  77.                 }
  78.             }
  79.         }
  80.         return 0;
  81.     }
  82. };

        时间复杂度：O(N × C^2)。其中 N 为 wordList 的长度，C 为列表中单词的长度。

  • 建图过程中，对于每一个单词，我们需要枚举它连接到的所有虚拟节点，时间复杂度为 O(C)，将这些单词加入到哈希表中，时间复杂度为 O(N×C)，因此总时间复杂度为 O(N×C)。
  • 双向广度优先搜索的时间复杂度最坏情况下是 O(N×C)。每一个单词需要拓展出 O(C) 个虚拟节点，因此节点数 O(N×C)。

        空间复杂度：O(N × C^2)。其中 N 为 wordList 的长度，C 为列表中单词的长度。哈希表中包含 O(N×C) 个节点，每个节点占用空间 O(C)，因此总的空间复杂度为 O(N × C^2)。

LeetCode403.青蛙过河：

问题描述：

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

示例 1：

输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

代码分析：

DFS：

        最直接的想法是使用深度优先搜索的方式尝试所有跳跃方案，直到我们找到一组可行解为止。但是不加优化的该算法的时间复杂度在最坏情况下是指数级的，剧透一下，时间复杂度为O(3^n)，而本题的数据范围是10^3，肯定会TLE。

        通常设计 DFS 函数时，我们只需要不失一般性的考虑完成第 i 块石子的跳跃需要些什么信息即可：

  • 需要知道当前所在位置在哪，也就是需要知道当前石子所在列表中的下标 u。
  • 需要知道当前所在位置是经过多少步而来的，也就是需要知道上一步的跳跃步长 k。
  1. class Solution {
  2.     Map<Integer, Integer> map = new HashMap<>();
  3.     public boolean canCross(int[] ss) {
  4.         int n = ss.length;
  5.         // 将石子信息存入哈希表
  6.         // 为了快速判断是否存在某块石子，即快速查找某块石子的河中位置和所在的数组下标
  7.         for (int i = 0; i < n; i++) {
  8.             map.put(ss[i], i);
  9.         }
  10.         // check first step
  11.         // 根据题意，初始位置是ss[0]=0,第一步是固定经过步长 1 到达第一块石子（下标为 1）
  12.         if (!map.containsKey(1)) return false;
  13.         //如果存在第一块石头，那么递归应从第一块石头位置开始
  14.         return dfs(ss, ss.length, 1, 1);
  15.     }
  16.  
  17.     /**
  18.      * 判定是否能够跳到最后一块石子
  19.      * @param ss 石子列表【不变】
  20.      * @param n  石子列表长度【不变】
  21.      * @param u  当前所在的石子的下标
  22.      * @param k  上一次是经过多少步跳到当前位置的
  23.      * @return 是否能跳到最后一块石子
  24.      */
  25.     boolean dfs(int[] ss, int n, int u, int k) {
  26.         if (u == n - 1) return true;
  27.         for (int i = -1; i <= 1; i++) {
  28.             // k + i为本次的跳跃距离
  29.             // 如果是原地踏步的话，直接跳过
  30.             if (k + i == 0) continue;
  31.             // 下一步的石子理论河中位置
  32.             int next = ss[u] + k + i;
  33.             // 如果存在下一步的石子，则跳转到下一步石子，并 DFS 下去
  34.             if (map.containsKey(next)) {
  35.                 boolean cur = dfs(ss, n, map.get(next), k + i);
  36.                 // 执行到这可以认为cur已经得出结果，可以直接返回
  37.                 if (cur) return true;
  38.             }
  39.         }
  40.         return false;
  41.     }
  42. }
  43. 作者：宫水三叶

        既然超时，我们需要考虑加入「记忆化」功能，或者改为使用带标记的 BFS。

记忆化搜索：

        在考虑加入「记忆化」时，我们只需要将 DFS 方法签名中的【可变】参数作为维度，DFS 方法中的返回值作为存储值即可。

        通常我们会使用「数组」来作为我们缓存中间结果的容器，对应到本题，就是需要一个 boolean[石子列表下标][跳跃步数] 这样的数组，但使用布尔数组作为记忆化容器往往无法区分「状态尚未计算」和「状态已经计算，并且结果为 false」两种情况。

        因此我们需要转为使用 int[石子列表下标][跳跃步数]，默认值 0 代表状态尚未计算，−1 代表计算状态为 false，1 代表计算状态为 true。

        接下来需要估算数组的容量，可以从「数据范围」入手分析。

  • 根据 2 <= stones.length <= 2000，我们可以确定第一维（数组下标）的长度为 2009，而另外一维（跳跃步数）是与跳转过程相关的，无法直接确定一个精确边界，但是一个显而易见的事实是，跳到最后一块石子之后的位置是没有意义的，因此我们不会有「跳跃步长」大于「石子列表长度」的情况，因此也可以定为 2009（这里是利用了由下标为 i 的位置发起的跳跃不会超过 i+1 的性质）。至此，我们定下来了记忆化容器为 int[][] cache = new int[2009][2009]。

        可以看出，上述确定容器大小的过程还是需要一点点分析 & 经验的。

        或者直接使用「哈希表」作为记忆化容器来简化思维难度。「哈希表」本身属于非定长容器集合，我们不需要分析两个维度的上限到底是多少。

        另外，当容器维度较多且上界较大时（例如上述的 int[2009][2009]），直接使用「哈希表」可以有效降低「爆空间/时间」的风险（不需要每跑一个样例都创建一个百万级的数组）。

  1. class Solution {
  2.     Map<Integer, Integer> map = new HashMap<>();
  3.     /* int[][] cache = new int[2009][2009];*/
  4.     Map<String, Boolean> cache = new HashMap<>();
  5.     public boolean canCross(int[] ss) {
  6.         int n = ss.length;
  7.         // 将石子信息存入哈希表
  8.         // 为了快速判断是否存在某块石子，即快速查找某块石子的河中位置和所在的数组下标
  9.         for (int i = 0; i < n; i++) {
  10.             map.put(ss[i], i);
  11.         }
  12.         // check first step
  13.         // 根据题意，初始位置是ss[0]=0,第一步是固定经过步长 1 到达第一块石子（下标为 1）
  14.         if (!map.containsKey(1)) return false;
  15.         //如果存在第一块石头，那么递归应从第一块石头位置开始
  16.         return dfs(ss, ss.length, 1, 1);
  17.     }
  18.  
  19.     boolean dfs(int[] ss, int n, int u, int k) {
  20.         // 注意此处key值除了可以用字符串存储，还可以简单映射为auto key = u * 10000 + k
  21.         String key = u + "_" + k; 
  22.         // if(cache[u][k] != 0) return cache[u][k] == 1;该状态已经计算过，直接返回计算结果
  23.         if(cache.containsKey(key))
  24.             return cache.get(key);
  25.         if(u == n - 1) 
  26.             return true;    
  27.         for (int i = -1; i <= 1; i++) {
  28.             // k + i为本次的跳跃距离
  29.             // 如果是原地踏步的话，直接跳过
  30.             if (k + i == 0) continue;
  31.             // 下一步的石子理论河中位置
  32.             int next = ss[u] + k + i;
  33.             // 如果存在下一步的石子，则跳转到下一步石子，并 DFS 下去
  34.             if (map.containsKey(next)) {
  35.                 boolean cur = dfs(ss, n, map.get(next), k + i);
  36.                 // cache[u][k] = cur ? 1 : -1 
  37.                 cache.put(key, cur);  
  38.                 // 执行到这可以认为cur已经得出结果，可以直接返回
  39.                 if (cur) return true;
  40.             }
  41.         }
  42.         // cache[u][k] == -1;
  43.         cache.put(key, false);
  44.         return false;
  45.     }
  46. }
  47. 作者：宫水三叶

        时空复杂度为O(n^2)。

        下面我们给出C++版的代码，因为有值得学习参考的地方，尤其是function和lambda的相关知识，这样可以避免传参，[&]以引用的形式捕获参数，可以直接使用函数内部定义的map、f、stones数组。不需要重新再canCross外单独写一个dfs函数然后将参数全部传递进去。

  1. class Solution {
  2. public:
  3.     bool canCross(vector<int>& stones) {
  4.         int n = stones.size();
  5.         if(stones[1] != 1) return false;
  6.         map<int,int> mp;
  7.         map<int,bool> f; //记忆化cache
  8.         for(int i = 0; i < n; i++) mp[stones[i]] = i;
  9.  
  10.         //这样可以在函数里面嵌套定义“函数”，也能省去两个引用类型的变量传递
  11.         std::function<bool(int,int)> dfs = [&](int idx,int k){
  12.             auto key = idx * 10000 + k; //key值可以这样映射
  13.             if(f.count(key)) return f[key];
  14.             if(idx == n - 1) return true;
  15.             for(int i = -1; i <= 1; i++){
  16.                 if(k + i == 0) continue;
  17.                 int next = stones[idx] + k + i;
  18.                 if(mp.count(next)){
  19.                     bool cur = dfs(mp[next],k + i);
  20.                     f[key] = cur; 
  21.                     if(cur) return true;
  22.                 }
  23.             }
  24.             f[key] = false;
  25.             return false;
  26.         };
  27.         
  28.         return dfs(1,1);
  29.     }
  30. };
  31. 作者：宫水三叶

        时空复杂度为O(n^2)。

动态规划：

        有了「记忆化搜索」的基础，要写写出来动态规划就变得相对简单了。

        我们可以从 DFS 函数的可变参数出发作为状态定义，DFS返回值作为动归数组的值，写出「动态规划」解法。

        可以设定 f[][] 作为动归数组：

  • 第一维为可变参数 u，代表石子列表的下标，范围为数组 stones 长度；
  • 第二维为可变参数 k，代表上一步的的跳跃步长，前面也分析过了，最多不超过数组 stones 长度。

        这样的【状态定义】所表示的含义为：当前在第i个位置，并且是以步长k跳到位置 i 时，是否到达最后一块石子。

        对于 f[i][k]是否为真，则取决于上一步j的状态值，结合每次步长的变化为 [-1,0,1] 可知：

  • 可从 f[j][k−1] 状态而来：先是经过 k−1 的跳跃到达位置 j，再在原步长的基础上 +1，跳到了位置 i。
  • 可从 f[j][k] 状态而来：先是经过 k 的跳跃到达位置 j，维持原步长不变，跳到了位置 i。
  • 可从 f[j][k+1] 状态而来：先是经过 k+1 的跳跃到达位置 j，再在原步长的基础上 -1，跳到了位置 i。

        只要上述三种情况中的一种为真，则 f[i][j] 为真。

        至此我们解决了动态规划的【状态定义】&【状态转移方程】部分，但还缺少让状态递推下去的【有效值】即初始化环节。

        而回看我们的状态定义，我们事先是不可能知道经过「多大的步长」跳到「哪些位置」，最终可以到达最后一块石子。

        这时候需要利用【对偶性】将跳跃过程【翻转】过来分析：

        我们知道起始状态是「经过步长为 1」的跳跃到达「位置 1」，如果从起始状态出发，存在一种方案到达最后一块石子的话，那么必然存在一条反向路径，它是以从「最后一块石子」开始，并以「某个步长 k」开始跳跃，最终以回到位置 1。

        因此我们可以设 f[1][1] = true，作为我们的起始值。

        本质上是利用了【路径可逆】的性质，将问题进行了【等效对偶】。表面上我们是进行【正向递推】，但事实上是在验证是否存在某条【反向路径】到达位置1。

  1. class Solution {
  2.     public boolean canCross(int[] ss) {
  3.         int n = ss.length;
  4.         // check first step
  5.         if (ss[1] != 1) return false;
  6.         boolean[][] f = new boolean[n + 1][n + 1];
  7.         // 所谓的路径可逆，就是可以理解为反向到达第一块石头就到达了终点，所以为true
  8.         f[1][1] = true;
  9.         for (int i = 2; i < n; i++) {
  10.             for (int j = 1; j < i; j++) {
  11.                 int k = ss[i] - ss[j];
  12.                 // 我们知道从位置 j 到位置 i 是需要步长为 k 的跳跃
  13.  
  14.                 // 而从位置 j 发起的跳跃最多不超过 j + 1
  15.                 // 因为每次跳跃，下标至少增加 1，而步长最多增加 1 
  16.                 if (k <= j + 1) {
  17.                     f[i][k] = f[j][k - 1] || f[j][k] || f[j][k + 1];
  18.                 }
  19.             }
  20.         }
  21.         // 跳跃的步数是不会超过列表长度即n的
  22.         for (int i = 1; i < n; i++) {
  23.             //f[n - 1][i]含义为经步长i所到达的n - 1位置处能否反向回到第一块石头处，步长i我们是不知道的，需要遍历
  24.             if (f[n - 1][i]) return true;
  25.         }
  26.         return false;
  27.     }
  28. }
  29. 作者：宫水三叶

        时空复杂度为O(n^2)。

BFS：

        事实上，前面我们也说到，解决超时 DFS 问题，除了增加「记忆化」功能以外，还能使用带标记的 BFS。因为两者都能解决 DFS 的超时原因：大量的重复计算。

        但为了「记忆化搜索」&「动态规划」能够更好的衔接，所以把 BFS 放到最后。

        它更多是作为「记忆化搜索」的另外一种实现形式。

  1. class Solution {
  2.     Map<Integer, Integer> map = new HashMap<>();
  3.     public boolean canCross(int[] ss) {
  4.         int n = ss.length;
  5.         for (int i = 0; i < n; i++) {
  6.             map.put(ss[i], i);
  7.         }
  8.         // check first step
  9.         if (!map.containsKey(1)) return false;
  10.  
  11.         boolean[][] vis = new boolean[n][n];
  12.         Deque<int[]> d = new ArrayDeque<>();
  13.         vis[1][1] = true;
  14.         d.addLast(new int[]{1, 1});
  15.  
  16.         while (!d.isEmpty()) {
  17.             int[] poll = d.pollFirst();
  18.             int idx = poll[0], k = poll[1];
  19.             if (idx == n - 1) return true;
  20.             for (int i = -1; i <= 1; i++) {
  21.                 if (k + i == 0) continue;
  22.                 int next = ss[idx] + k + i;
  23.                 if (map.containsKey(next)) {
  24.                     int nIdx = map.get(next), nK = k + i;
  25.                     if (nIdx == n - 1) return true;
  26.                     if (!vis[nIdx][nK]) {
  27.                         vis[nIdx][nK] = true;
  28.                         d.addLast(new int[]{nIdx, nK});
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.  
  34.         return false;
  35.     }
  36. }
  37. 作者：宫水三叶

        时空复杂度均为O(n^2)。

LeetCode417.太平洋大西洋水流问题：

问题描述：

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

代码分析：

        整理题意，需要我们统计能够同时流向两片海域的格子。

        常规的想法很直白，就是遍历每一个点，看这个点能否同时到达两片海域。

        代码如下：

  1. class Solution {
  2. private:
  3.     int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
  4.  
  5.     void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {
  6.         if (visited[x][y]) return; //判断是否访问过的优先级是最高的
  7.  
  8.         visited[x][y] = true; //能到达的节点全部标记，不用撤销
  9.  
  10.         for (int i = 0; i < 4; i++) {
  11.             int nextx = x + dir[i][0];
  12.             int nexty = y + dir[i][1];
  13.             if (nextx < 0 || nextx >= heights.size() || nexty < 0 || nexty >= heights[0].size()) continue; //越界判断
  14.             if (heights[x][y] < heights[nextx][nexty]) continue; // 高度不合适
  15.  
  16.             dfs (heights, visited, nextx, nexty);
  17.         }
  18.         return;
  19.     }
  20.  
  21.     bool isResult(vector<vector<int>>& heights, int x, int y) {
  22.         vector<vector<bool>> visited = vector<vector<bool>>(heights.size(), vector<bool>(heights[0].size(), false));
  23.  
  24.         //注意：isResult函数包含了dfs函数的预处理
  25.         // 深搜，将x,y出发 能到的节点都标记上。 
  26.         dfs(heights, visited, x, y);
  27.         bool isPacific = false;
  28.         bool isAtlantic = false;
  29.  
  30.         // 以下就是判断x，y出发，是否到达太平洋和大西洋
  31.         //太平洋为左、上边界 
  32.         for (int j = 0; j < heights[0].size(); j++) {
  33.             if (visited[0][j]) {
  34.                 isPacific = true;
  35.                 break;
  36.             }
  37.         }
  38.         for (int i = 0; i < heights.size(); i++) {
  39.             if (visited[i][0]) {
  40.                 isPacific = true;
  41.                 break;
  42.             }
  43.         }
  44.         //大西洋为右、下边界
  45.         for (int j = 0; j < heights[0].size(); j++) {
  46.             if (visited[heights.size() - 1][j]) {
  47.                 isAtlantic = true;
  48.                 break;
  49.             }
  50.         }
  51.         for (int i = 0; i < heights.size(); i++) {
  52.             if (visited[i][heights[0].size() - 1]) {
  53.                 isAtlantic = true;
  54.                 break;
  55.             }
  56.         }
  57.         if (isAtlantic && isPacific) return true;
  58.         return false;
  59.     }
  60. public:
  61.  
  62.     vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
  63.         vector<vector<int>> result;
  64.         // 遍历每一个点，看是否能同时到达太平洋和大西洋 
  65.         for (int i = 0; i < heights.size(); i++) {
  66.             for (int j = 0; j < heights[0].size(); j++) {
  67.                 if (isResult(heights, i, j)) result.push_back({i, j});
  68.             }
  69.         }
  70.         return result;
  71.     }
  72. };
  73. 作者：代码随想录

        上述解法遍历每个节点做isResult操作为m * n，同时每一个节点都要深搜，又是m * n，总时间复杂度为O(m^2 * n^2)，很显然超时了。

        优化一下思路：从源点（格子）流向汇点（海域）是按照高度从高到低（非严格）的规则，那么反过来从海域到格子则是按照从低到高（非严格）规则进行，同时本身处于边缘的格子与海域联通。

        因此我们可以使用两遍 DFS/BFS 进行求解：分别从与当前海域直接相连的边缘格子出发，统计能够流向当前海域的格子集合，两片海域求得的集合交集即是答案！

法一：多源BFS

        使用 BFS 进行求解：目的是构造出两个答案矩阵 res1​ 和 res2​，resk[i][j]=true 代表格子 (i,j) 能够流向海域，起始将所有与海域相连的格子放入队列，然后跑一遍 BFS ，所有能够进入队列的格子均能够与海域联通。

        最后统计所有满足 res1[i][j]=res2[i][j]=true 的格子即是答案。

  1. class Solution {
  2.     int n, m;
  3.     int[][] g;
  4.  
  5.     public List<List<Integer>> pacificAtlantic(int[][] heights) {
  6.         //注意是g引用指向heights！
  7.         g = heights;
  8.         m = g.length; n = g[0].length;
  9.         Deque<int[]> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
  10.         boolean[][] res1 = new boolean[m][n], res2 = new boolean[m][n];
  11.         //初始化两片海域的连通性数组和BFS栈
  12.         for (int i = 0; i < m; i++) {
  13.             for (int j = 0; j < n; j++) {
  14.                 if (i == 0 || j == 0) {
  15.                     res1[i][j] = true;
  16.                     d1.addLast(new int[]{i, j});
  17.                 }
  18.                 if (i == m - 1 || j == n - 1) {
  19.                     res2[i][j] = true;
  20.                     d2.addLast(new int[]{i, j});
  21.                 }
  22.             }
  23.         }
  24.         bfs(d1, res1); bfs(d2, res2);
  25.         List<List<Integer>> ans = new ArrayList<>();
  26.         for (int i = 0; i < m; i++) {
  27.             for (int j = 0; j < n; j++) {
  28.                 if (res1[i][j] && res2[i][j]) {
  29.                     List<Integer> list = new ArrayList<>();
  30.                     list.add(i); list.add(j);
  31.                     ans.add(list);
  32.                 }
  33.             }
  34.         }
  35.         return ans;
  36.     }
  37.  
  38.     int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
  39.  
  40.     void bfs(Deque<int[]> d, boolean[][] res) {
  41.         while (!d.isEmpty()) {
  42.             int[] info = d.pollFirst();
  43.             int x = info[0], y = info[1], t = g[x][y];
  44.             for (int[] di : dirs) {
  45.                 int nx = x + di[0], ny = y + di[1];
  46.                 if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
  47.                 //若res[nx][ny]为true，则表明该位置处能够与海域连通，即该位置已经被拓展过了
  48.                 if (res[nx][ny] || g[nx][ny] < t) continue;
  49.                 d.addLast(new int[]{nx, ny});
  50.                 res[nx][ny] = true;
  51.             }
  52.         }
  53.     }
  54. }
  55. 作者：宫水三叶

        BFS部分和统计答案部分的复杂度均为O(m * n)，整体时间复杂度为O(m * n)。

法二：DFS

  1. class Solution {
  2.     int n, m;
  3.     int[][] g;
  4.  
  5.     public List<List<Integer>> pacificAtlantic(int[][] heights) {
  6.         g = heights;
  7.         m = g.length; n = g[0].length;
  8.         boolean[][] res1 = new boolean[m][n], res2 = new boolean[m][n];
  9.  
  10.         for (int i = 0; i < m; i++) {
  11.             for (int j = 0; j < n; j++) {
  12.                 if (i == 0 || j == 0) {
  13.                     /*注意此处与dfs函数中的写法，
  14.                      *为何没有像上一种方法对于res1和res2的初始化？
  15.                      *且只要当前节点没联通过（即没被处理访问过），就在dfs中标记为合法？
  16.                      *原因是，最先被这两层循环遍历到的点是第一层的边缘格子
  17.                      *其当然可以被直接标记（相当于初始化了）
  18.                      *随后dfs的逻辑也是将不合法的直接过滤掉，进入dfs的一定是合法的
  19.                      *所以res的作用为 1.判断连通 2.判断是否访问过
  20.                     */
  21.                     if (!res1[i][j]) dfs(i, j, res1);
  22.                 }
  23.                 if (i == m - 1 || j == n - 1) {
  24.                     if (!res2[i][j]) dfs(i, j, res2);
  25.                 }
  26.             }
  27.         }
  28.         List<List<Integer>> ans = new ArrayList<>();
  29.         for (int i = 0; i < m; i++) {
  30.             for (int j = 0; j < n; j++) {
  31.                 if (res1[i][j] && res2[i][j]) {
  32.                     //最终只有合法且能同时通达两片海域的点才能加入结果集
  33.                     List<Integer> list = new ArrayList<>();
  34.                     list.add(i); list.add(j);
  35.                     ans.add(list);
  36.                 }
  37.             }
  38.         }
  39.         return ans;
  40.     }
  41.  
  42.     int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
  43.  
  44.     void dfs(int x, int y, boolean[][] res) {
  45.         //逻辑为已经确保进入dfs的都是未访问过的且合法的点
  46.         res[x][y] = true;
  47.         for (int[] di : dirs) {
  48.             int nx = x + di[0], ny = y + di[1];
  49.             if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
  50.             if (res[nx][ny] || g[nx][ny] < g[x][y]) continue;
  51.             dfs(nx, ny, res);
  52.         }
  53.     }
  54. }
  55. 作者：宫水三叶

        时间复杂度同上。

法三：并查集

        其中维护连通性部分可以使用「并查集」来做：起始将与海域 A 联通的边缘格子与 S 联通，将与海域 B 联通的边缘格子与 T 联通，然后跑一遍 DFS/BFS，最后将既和 S 联通又和 T 联通的格子加入答案。

  1. class Solution {
  2.     int N = 200 * 200 + 10;
  3.     int[] p1 = new int[N], p2 = new int[N];
  4.     int n, m, tot, S, T;
  5.     int[][] g;
  6.     void union(int[] p, int a, int b) {
  7.         p[find(p, a)] = p[find(p, b)];
  8.     }
  9.     int find(int[] p, int x) {
  10.         if (p[x] != x) p[x] = find(p, p[x]);
  11.         return p[x];
  12.     }
  13.     boolean query(int[] p, int a, int b) {
  14.         return find(p, a) == find(p, b);
  15.     }
  16.     int getIdx(int x, int y) {
  17.         return x * n + y;
  18.     }
  19.     public List<List<Integer>> pacificAtlantic(int[][] _g) {
  20.         g = _g;
  21.         m = g.length; n = g[0].length; tot = m * n; S = tot + 1; T = tot + 2;
  22.         for (int i = 0; i <= T; i++) p1[i] = p2[i] = i;
  23.         for (int i = 0; i < m; i++) {
  24.             for (int j = 0; j < n; j++) {
  25.                 int idx = getIdx(i, j);
  26.                 if (i == 0 || j == 0) {
  27.                     if (!query(p1, S, idx)) dfs(p1, S, i, j);
  28.                 }
  29.                 if (i == m - 1 || j == n - 1) {
  30.                     if (!query(p2, T, idx)) dfs(p2, T, i, j);
  31.                 }
  32.             }
  33.         }
  34.         List<List<Integer>> ans = new ArrayList<>();
  35.         for (int i = 0; i < m; i++) {
  36.             for (int j = 0; j < n; j++) {
  37.                 int idx = getIdx(i, j);
  38.                 if (query(p1, S, idx) && query(p2, T, idx)) {
  39.                     List<Integer> list = new ArrayList<>();
  40.                     list.add(i); list.add(j);
  41.                     ans.add(list);
  42.                 }
  43.             }
  44.         }
  45.         return ans;
  46.     }
  47.     int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
  48.     void dfs(int[] p, int ori, int x, int y) {
  49.         union(p, ori, getIdx(x, y));
  50.         for (int[] di : dirs) {
  51.             int nx = x + di[0], ny = y + di[1];
  52.             if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
  53.             if (query(p, ori, getIdx(nx, ny)) || g[nx][ny] < g[x][y]) continue;
  54.             dfs(p, ori, nx, ny);
  55.         }
  56.     }
  57. }
  58. 作者：宫水三叶

        时间复杂度同上。

LeetCode433.最小基因变化：

问题描述：

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

  • 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

提示：

  • start.length == 8
  • end.length == 8
  • 0 <= bank.length <= 10
  • bank[i].length == 8
  • start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

代码分析：

法一：BFS

        为了方便，我们令 S=start、 T=end，将每个基因序列视为「状态」。

        容易想到使用 BFS 进行求解，并使用「哈希表」记录到达某个状态所消耗的步数（同时为了快速判断某个状态是否合法，我们使用 Set 结构对 bank[i] 进行转存）。

        起始将 S 加入队列，并更新到达 S 所使用的步数为 0，然后进行常规的 BFS 过程：每次取出队头元素，尝试替换当前状态的某一位，来得到新的状态（限定新状态必须合法，即必须出现在 Set 中），如果新状态合法并且没有在记录步数的哈希表中出现过，则将新状态入队并更新得到新状态所用步数，否则丢弃新状态。

        重复上述过程直到找到 T（返回具体步数） 或者队列为空（返回 −1）。

  1. class Solution {
  2.     static char[] items = new char[]{'A', 'C', 'G', 'T'};
  3.     public int minMutation(String startGene, String endGene, String[] bank) {
  4.         //新的状态必须在存放bank的Set中
  5.         Set<String> set = new HashSet<>();
  6.         for(String s : bank) 
  7.             set.add(s);
  8.         Deque<String> d = new ArrayDeque<>();
  9.         //哈希表记录到达某个状态所消耗的步数
  10.         Map<String, Integer> map = new HashMap<>();
  11.         //初始化
  12.         d.addLast(startGene);
  13.         map.put(startGene, 0);
  14.  
  15.         while(!d.isEmpty()) {
  16.             int size = d.size();
  17.             while(size-- > 0) {
  18.                 String s = d.pollFirst();
  19.                 char[] cs = s.toCharArray();
  20.                 int step = map.get(s);
  21.                 //尝试替换当前状态的某一位，来得到新的状态
  22.                 for(int i = 0; i < 8; ++i) {
  23.                     for(char c : items) {
  24.                         if(cs[i] == c)
  25.                             continue;
  26.                         char[] clone = cs.clone();
  27.                         clone[i] = c;
  28.                         String sub = String.valueOf(clone);
  29.  
  30.                         if(!set.contains(sub)) continue;
  31.                         if(map.containsKey(sub)) continue;
  32.                         if(sub.equals(endGene)) return step + 1;  
  33.  
  34.                         map.put(sub, step + 1);
  35.                         d.addLast(sub);  
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.         return -1;
  41.     }
  42. }
  43. 作者：宫水三叶

       时间复杂度：n为 bank 的数组长度（合法状态数），将 bank 存入Set 的复杂度为O(n)，每个状态经过一步操作最多拓展出C = 8 * 4 = 32个新基因，因此BFS过程为O(C * n)。总体为O(C * n)。

        空间复杂度为o(n)。

法二：双向BFS

        双向与常规相比，能够有效解决搜索空间爆炸的问题：

  1. class Solution {
  2.     static char[] items = new char[]{'A', 'C', 'G', 'T'};
  3.     Set<String> set = new HashSet<>();
  4.     public int minMutation(String startGene, String endGene, String[] bank) {
  5.         for(String s : bank) 
  6.             set.add(s);
  7.         if(!set.contains(endGene)) return -1;
  8.         Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
  9.         d1.addLast(startGene);d2.addLast(endGene);
  10.         Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
  11.         m1.put(startGene, 0);m2.put(endGene, 0);
  12.  
  13.         while(!d1.isEmpty() && !d2.isEmpty()) {
  14.             int t = -1;
  15.             //每次选择拓展量少的搜索，保证start的规模不大于end的规模
  16.             if(d1.size() <= d2.size()) t = update(d1, m1, m2);
  17.             else t = update(d2, m2, m1);
  18.             if(t != -1) return t; 
  19.         }
  20.         return -1;
  21.         
  22.     }
  23.     public int update(Deque<String> d, Map<String, Integer> cur, Map<String, Integer> other) {
  24.         int m = d.size();
  25.         while(m-- > 0) {
  26.             String s = d.pollFirst();
  27.             char[] cs = s.toCharArray();
  28.             int step = cur.get(s);
  29.             for(int i = 0; i < 8; ++i) {
  30.                 for(char c : items) {
  31.                     if(cs[i] == c) continue;
  32.                     char[] clone = cs.clone();
  33.                     clone[i] = c;
  34.                     String sub = String.valueOf(clone);
  35.                     if(!set.contains(sub) || cur.containsKey(sub)) continue;
  36.                     //此处相信不难理解
  37.                     if(other.containsKey(sub)) return other.get(sub) + step + 1;
  38.                     d.addLast(sub);
  39.                     cur.put(sub, step + 1);
  40.                 }
  41.             }
  42.         }
  43.         return -1;
  44.     }
  45. }
  46. 作者：宫水三叶

        时间和空间复杂度仍同朴素的BFS一样。

法三：A* 算法

        若不考虑 bank 的限制，对于一个特定状态而言，我们可以任意选择一位替换为 4 类字符之一，因此对于任意状态 x 而言，其与目标状态 T 的「理论最小转换步数」为两者对应位置不同字符的数量，而由于存在 bank 限制，实际最小步数必然满足「大于等于」该理论最小转换步数。

        基于此，我们可以计算当前状态到目标状态的「理论最小转换步数」作为启发式函数，进行启发式搜索。

        具体的，我们使用优先队列（堆）维护所有的状态，每次优先「启发值 = 理论最小转换步数」的状态进行优先出队拓展。

        当然，这里一下子突然提到启发式搜索，萌新们可能不太适应，我们将会在之后的题目中详解Astar算法。

        我们直接上代码：

  1. class Solution {
  2.  
  3.     class Node {
  4.         String s;
  5.         int val;
  6.         Node(String _s) { //构造函数
  7.             s = _s;
  8.             for (int i = 0; i < 8; i++) {
  9.                 if (s.charAt(i) != T.charAt(i)) val++;
  10.             }
  11.         }
  12.     }
  13.  
  14.     static char[] items = new char[]{'A', 'C', 'G', 'T'};
  15.     String S, T;
  16.  
  17.     public int minMutation(String start, String end, String[] bank) {
  18.         Set<String> set = new HashSet<>();
  19.         for (String s : bank) set.add(s);
  20.         S = start; T = end;
  21.         PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
  22.         Map<String, Integer> map = new HashMap<>();
  23.         q.add(new Node(S));
  24.         map.put(S, 0);
  25.         while (!q.isEmpty()) {
  26.             Node node = q.poll();
  27.             char[] cs = node.s.toCharArray();
  28.             int step = map.get(node.s);
  29.             for (int i = 0; i < 8; i++) {
  30.                 for (char c : items) {
  31.                     if (cs[i] == c) continue;
  32.                     char[] clone = cs.clone();
  33.                     clone[i] = c;
  34.                     String sub = String.valueOf(clone);
  35.                     if (!set.contains(sub)) continue;
  36.                     if (sub.equals(T)) return step + 1;
  37.                     if (!map.containsKey(sub) || map.get(sub) > step + 1) {
  38.                         map.put(sub, step + 1);
  39.                         q.add(new Node(sub));
  40.                     }
  41.                 }
  42.             }
  43.         }
  44.         return -1;
  45.     }
  46. }
  47. 作者：宫水三叶

        启发式搜索分析时空复杂度的意义不大。

法三：建图 + DFS

        由 start 和 bank[i] 组成合法点集，且点集中任意两点之间存在无向边的充要条件是：点 u 和点 v 所代表的字符中，仅有一个位置字符不同。

        因此我们可以将所有的点存入 list 中，假设 list 长度为 n。同时为了方便，我们人为确保 start 出现在头部（点编号为 1），end 出现在尾部（点编号为 n）。

        遍历 list 进行建图（对于两字符串中仅有一位置不同的点进行连边操作），然后跑一遍从 1 到 n 的 DFS。

        由于图中可能有环或无解，因此必须「设定一个最大搜索深度」并增加「最优解剪枝」，确保搜索过程结束。

        最大搜索深度的设定可以利用反证法：如果 start 能够到达 end，那么最优路径中必然不存在环（否则可以把环去掉，得到一条更短的路径），即最优路径所经过的点的数量必然不超过 n。

  1. class Solution {
  2.     int N = 15, M = 15 * 15 * 2 + 50, idx = 0, loc = 1;
  3.     int[] he = new int[N], e = new int[M], ne = new int[M];
  4.     int n, ans;
  5.     void add(int a, int b) {
  6.         e[idx] = b;
  7.         ne[idx] = he[a];
  8.         he[a] = idx++;
  9.     }
  10.     void dfs(int u, int fa, int depth) {
  11.         if(depth >= ans) return; // 最优解剪枝
  12.         if(u == n) {
  13.             ans = depth;
  14.             return;
  15.         }
  16.         for(int i = he[u]; i != -1; i = ne[i]) {
  17.             int j = e[i];
  18.             if(j == fa) continue;
  19.             dfs(j, u, depth + 1);
  20.         }
  21.     }
  22.     public int minMutation(String start, String end, String[] bank) {
  23.         List<String> list = new ArrayList<>();
  24.         list.add(start);
  25.         boolean ok = false;
  26.         for (String s : bank) {
  27.             if(s.equals(start)) continue;
  28.             if(s.equals(end)) {
  29.                 ok = true;
  30.                 continue;
  31.             }
  32.             list.add(s);
  33.         }
  34.         if(!ok) return -1;
  35.         list.add(end);
  36.         n = list.size();
  37.         ans = n;
  38.         Arrays.fill(he, -1);
  39.         for(int i = 0; i < n; ++i) {
  40.             for(int j = 0; j < n; ++j) {
  41.                 if(i == j) continue;
  42.                 int cnt = 0;
  43.                 for(int k = 0; k < 8 && cnt <= 1; ++k) {
  44.                     if(list.get(i).charAt(k) != list.get(j).charAt(k)) cnt++;
  45.                 }
  46.                 if(cnt == 1) {
  47.                     add(i + 1, j + 1);add(j + 1, i + 1);
  48.                 } 
  49.             }
  50.         }
  51.         dfs(1, -1, 0);
  52.         return ans == n ? -1 : ans;
  53.     }
  54. }
  55. 作者：宫水三叶

        时间复杂度：令 bank 的长度为 n，预处理list为O(n)；建图为O(C * n^2)，C = 8；DFS过程由于设定了最大搜索深度，为O(n^2)。因此总体为O(n^2)。

        空间复杂度最坏情况下为完全图，复杂度为O(n^2)。

LeetCode675.为高尔夫比赛砍树：

问题描述：

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：

  • 0 表示障碍，无法触碰
  • 1 表示地面，可以行走
  • 比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

示例 1：

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

代码分析：

        图论的问题只要不是很基础的BFS/DFS板子题等就都比较困难，对于各种集合的熟练灵活运用、建图逻辑的表示等都有一定不俗的要求。

        本题限定了我们只能按照「从低到高」的顺序砍树，并且图中不存在高度相同的两棵树，这意味着整个砍树的顺序是唯一确定的，即对所有有树的地方进行「高度」排序，即是完整的砍树路线。

        而另外一个更为重要的性质是：点与点之间的最短路径，不会随着砍树过程的进行而发生变化（某个树点被砍掉，只会变为平地，不会变为阻碍点，仍可通过）。

        综上，砍树的路线唯一确定，当我们求出每两个相邻的砍树点最短路径，并进行累加即是答案（整条砍树路径的最少步数）。

BFS：

        据上述，再结合数据范围只有 50，并且点与点之间边权为 1（每次移动算一步），我们可以直接进行 BFS 进行求解。

        先对整张图进行一次遍历，预处理出所有的树点（以三元组 (height,x,y) 的形式进行存储），并对其以 height 排升序，得到唯一确定的砍树路径。

        之后就是计算砍树路径中相邻点的最短距离，运用 BFS 求解任意两点的最短路径复杂度为 O(n×m)，我们最多有 n×m 个树点，因此整体复杂度为 O(n^2 ∗ m^2)。

        求解相邻点的最短距离的部分也是整个算法的复杂度上界，数据范围只有 50，计算量不超过 10^7，可以过。

  1. class Solution {
  2.     int N = 50;
  3.     int[][] g = new int[N][N];
  4.     int n, m;
  5.     public int cutOffTree(List<List<Integer>> forest) {
  6.         n = forest.size(); m = forest.get(0).size();
  7.         // 以三元组的形式存储整张图中所有的树点
  8.         List<int[]> list = new ArrayList<>();
  9.         for(int i = 0; i < n; ++i) {
  10.             for(int j = 0; j < m; ++j) {
  11.                 g[i][j] = forest.get(i).get(j);
  12.                 if(g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
  13.             }
  14.         }
  15.         // 对其以height排升序，得到唯一确定的砍树路径
  16.         Collections.sort(list, (a, b)->a[0]-b[0]);
  17.         int x = 0, y = 0, ans = 0;
  18.         // 对每两个相邻树点运用BFS求最短路
  19.         for(int[] ne : list) {
  20.             int nx = ne[1], ny = ne[2];
  21.             int d = bfs(x, y, nx, ny);
  22.             if(d == -1) return -1;
  23.             ans += d;
  24.             x = nx; y = ny;
  25.         } 
  26.         return ans;
  27.     }
  28.  
  29.     int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  30.     int bfs(int X, int Y, int P, int Q) {
  31.         if(X == P && Y == Q) return 0;
  32.         boolean[][] vis = new boolean[n][m];
  33.         Deque<int[]> d = new ArrayDeque<>();
  34.         d.addLast(new int[]{X, Y});
  35.         vis[X][Y] = true;
  36.         int ans = 0;
  37.  
  38.         while(!d.isEmpty()) {
  39.             int size = d.size();
  40.             while(size-- > 0) {
  41.                 int[] info = d.pollFirst();
  42.                 int x = info[0], y = info[1];
  43.                 for(int[] di : dirs) {
  44.                     int nx = x + di[0], ny = y + di[1];
  45.                     if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  46.                     if(g[nx][ny] == 0 || vis[nx][ny]) continue;
  47.                     if(nx == P && ny == Q) return ans + 1;
  48.                     d.addLast(new int[]{nx, ny});
  49.                     vis[nx][ny] = true;
  50.                 }
  51.             }
  52.             ans++;
  53.         } 
  54.         return -1;
  55.     }
  56. }
  57. 作者：宫水三叶

        时间复杂度：预处理所有的树点为O(n * m)，对树点进行排序为O(nm * log nm)，最多有n * m个树点，对每两个相邻树点运用BFS求最短路为O(n * m)，统计完整路径的复杂度为O(n^2 * m^2)。

        空间复杂度为O(n * m) 。

A*算法：

        由于问题的本质是求最短路，同时原问题的边权为 1，因此套用其他复杂度比 BFS 高的最短路算法，对于本题而言是没有意义，但运用启发式搜索 A* 算法来优化则是有意义。

        因为在 BFS 过程中，我们会无差别往「四联通」方向进行搜索，直到找到「当前树点的下一个目标位置」为止，而实际上，两点之间的最短路径往往与两点之间的相对位置相关。

        例如，当前我们在位置 S，我们目标位置是 T，而 T 在 S 的右下方，此时我们应当优先搜索方向"往右下方"的路径，当无法从"往右下方"的路径到达 T，我们再考虑搜索其他方向的路径：

        如何设计这样带有优先级的搜索顺序，则是 A* 算法「启发式函数」的设计过程，其本质是对应了对「最小步数」的估算，只有当我们确保「最小步数估算 <= 实际最小步数」，A* 算法的正确性才得以保证。

        因此我们往往会直接使用「理论最小步数」来作为启发式函数的，对于本题，可直接使用「曼哈顿距离」作为「理论最小步数」。

        因此，如果我们是要从源点 S 到汇点 T，并且当前位于中途点 x 的话，点 x 的最小步数估算包括两部分：到点 x 的实际步数 + 从点 x 到点 T 的理论最小步数（曼哈顿距离）。使用「优先队列」按照「总的最小步数估算」进行出队，即可实现 A* 算法的搜索顺序。

  1. class Solution {
  2.     int N = 50;
  3.     int[][] g = new int[N][N];
  4.     int n, m;
  5.     public int cutOffTree(List<List<Integer>> forest) {
  6.         n = forest.size(); m = forest.get(0).size();
  7.         List<int[]> list = new ArrayList<>();
  8.         for(int i = 0; i < n; ++i) {
  9.             for(int j = 0; j < m; ++j) {
  10.                 g[i][j] = forest.get(i).get(j);
  11.                 if(g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
  12.             }
  13.         }
  14.         Collections.sort(list, (a, b)->a[0]-b[0]);
  15.         int x = 0, y = 0, ans = 0;
  16.         for(int[] ne : list) {
  17.             int nx = ne[1], ny = ne[2];
  18.             int d = astar(x, y, nx, ny);
  19.             if(d == -1) return -1;
  20.             ans += d;
  21.             x = nx; y = ny;
  22.         } 
  23.         return ans;
  24.     }
  25.  
  26.     int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  27.  
  28.     int getIdx(int x, int y) {
  29.         return x * m + y;
  30.     }
  31.  
  32.     int f(int X, int Y, int P, int Q) { // 求曼哈顿距离
  33.         return Math.abs(X - P) + Math.abs(Y - Q);
  34.     }
  35.  
  36.     int astar(int X, int Y, int P, int Q) {
  37.         if(X == P && Y == Q) return 0;
  38.         Map<Integer, Integer> map = new HashMap<>();
  39.         PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0]-b[0]);
  40.         q.add(new int[]{f(X, Y, P, Q), X, Y});
  41.         map.put(getIdx(X, Y), 0);
  42.     
  43.         while(!q.isEmpty()) {
  44.             int[] info = q.poll();
  45.             int x = info[1], y = info[2], step = map.get(getIdx(x, y));
  46.             for(int[] di : dirs) {
  47.                 int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny);
  48.                 if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  49.                 if(g[nx][ny] == 0) continue;
  50.                 if(nx == P && ny == Q) return step + 1;
  51.                 if(!map.containsKey(nidx) || map.get(nidx) > step + 1) {
  52.                     q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny});
  53.                     map.put(nidx, step + 1);
  54.                 }
  55.             }
  56.         }
  57.         return -1;     
  58.     }
  59. }
  60. 作者：宫水三叶

        启发式搜索分析时空复杂度的意义不大。

A*算法 + 并查集预处理无解：

        我们知道，A* 算法使用到了「优先队列（堆）」来进行启发式搜索，而对于一些最佳路径方向与两点相对位置相反（例如 T 在 S 的右边，但由于存在障碍，最短路径需要先从左边绕一圈才能到 T），A* 反而会因为优先队列（堆）而多一个 log 的复杂度。

        因此一个可行的优化是，我们先提前处理「无解」的情况，常见的做法是在预处理过程中运用「并查集」来维护连通性。

        这种对于不影响复杂度上界的预处理相比后续可能出现的大量无效搜索（最终无解）的计算量而言，是有益的。

  1. class Solution {
  2.     int N = 50;
  3.     int[][] g = new int[N][N];
  4.     int n, m;
  5.     int[] p = new int[N * N + 10];
  6.  
  7.     List<int[]> list = new ArrayList<>();
  8.  
  9.     void union(int a, int b) {
  10.         p[find(a)] = p[find(b)];
  11.     }
  12.     boolean query(int a, int b) {
  13.         return find(a) == find(b);
  14.     }
  15.     int find(int x) {
  16.         if(p[x] != x) p[x] = find(p[x]);
  17.         return p[x];
  18.     }
  19.     int getIdx(int x, int y) {
  20.         return  x * m + y;
  21.     }
  22.  
  23.     public int cutOffTree(List<List<Integer>> forest) {
  24.         n = forest.size(); m = forest.get(0).size();
  25.         //预处理过程中，同时使用并查集维护连通性
  26.         for(int i = 0; i < n * m; ++i) p[i] = i;
  27.         //只与左和上方区域进行连通即可保证不重不漏
  28.         int[][] tempDirs = new int[][]{{0, -1}, {-1, 0}};
  29.  
  30.         for(int i = 0; i < n; ++i) {
  31.             for(int j = 0; j < m; ++j) {
  32.                 g[i][j] = forest.get(i).get(j);
  33.                 if(g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
  34.                 if(g[i][j] == 0) continue;
  35.  
  36.                 for(int[] di : tempDirs) {
  37.                     int nx = i + di[0], ny = j + di[1];
  38.                     if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  39.                     if(g[nx][ny] != 0) union(getIdx(i, j), getIdx(nx, ny));
  40.                 }
  41.             }
  42.         }
  43.         //若不满足所有树点都与(0, 0)相连通，则提前返回无解
  44.         for(int[] info : list) {
  45.             int x = info[1], y = info[2];
  46.             if(!query(getIdx(0, 0), getIdx(x, y))) return -1;
  47.         } 
  48.  
  49.         Collections.sort(list, (a, b)->a[0]-b[0]);
  50.         int x = 0, y = 0, ans = 0;
  51.         for(int[] ne : list) {
  52.             int nx = ne[1], ny = ne[2];
  53.             int d = astar(x, y, nx, ny);
  54.             if(d == -1) return -1;
  55.             ans += d;
  56.             x = nx; y = ny;
  57.         } 
  58.         return ans;
  59.     }
  60.  
  61.     int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  62.  
  63.     int f(int X, int Y, int P, int Q) { // 求曼哈顿距离
  64.         return Math.abs(X - P) + Math.abs(Y - Q);
  65.     }
  66.  
  67.     int astar(int X, int Y, int P, int Q) {
  68.         if(X == P && Y == Q) return 0;
  69.         Map<Integer, Integer> map = new HashMap<>();
  70.         PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0]-b[0]);
  71.         q.add(new int[]{f(X, Y, P, Q), X, Y});
  72.         map.put(getIdx(X, Y), 0);
  73.     
  74.         while(!q.isEmpty()) {
  75.             int[] info = q.poll();
  76.             int x = info[1], y = info[2], step = map.get(getIdx(x, y));
  77.             for(int[] di : dirs) {
  78.                 int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny);
  79.                 if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  80.                 if(g[nx][ny] == 0) continue;
  81.                 if(nx == P && ny == Q) return step + 1;
  82.                 if(!map.containsKey(nidx) || map.get(nidx) > step + 1) {
  83.                     q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny});
  84.                     map.put(nidx, step + 1);
  85.                 }
  86.             }
  87.         }
  88.         return -1;     
  89.     }
  90. }
  91. 作者：宫水三叶

        启发式搜索分析时空复杂度意义不大。

LeetCode752.打开转盘锁（类似127）：

问题描述：

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

代码分析：

        本题十分类似单词接龙，所以正好趁前面解决过127.还留有印象之际来把本题作为练习题。127.为困难，本题为中等，其实体现在数据范围上，思维上实际大差不差。

        分析题干，不难发现，本题属于「最短路/最小步数」问题。

双向BFS：

        我们再回顾一下双向BFS的思路：

  • 创建「两个队列」分别用于两个方向的搜索；
  • 创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
  • 为了尽可能让两个搜索方向“平均”，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
  • 如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。

        伪代码大致如下：

  1. d1、d2 为两个方向的队列
  2. m1、m2 为两个方向的哈希表，记录每个节点距离起点的
  3.     
  4. // 只有两个队列都不空，才有必要继续往下搜索
  5. // 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
  6. while(!d1.isEmpty() && !d2.isEmpty()) {
  7.     if (d1.size() < d2.size()) {
  8.         update(d1, m1, m2);
  9.     } else {
  10.         update(d2, m2, m1);
  11.     }
  12. }
  13.  
  14. // update 为将当前队列 d 中包含的元素取出，进行「一次完整扩展」的逻辑（按层拓展）
  15. void update(Deque d, Map cur, Map other) {}
  16.  
  17. 作者：宫水三叶

        代码如下：

  1. class Solution {
  2.     String t, s;
  3.     Set<String> set = new HashSet<>();
  4.  
  5.     public int openLock(String[] deadends, String target) {
  6.         s = "0000";
  7.         t = target;
  8.         if(s.equals(t)) return 0;
  9.         for(String d : deadends) set.add(d);
  10.         if(set.contains(s)) return -1;
  11.         int ans = bfs();
  12.         return ans;
  13.     }
  14.  
  15.     int bfs() {
  16.         Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>(); //d1正向，d2反向
  17.         //m1,m2分别记录两个方向出现的状态是经过多少次转换而来的
  18.         Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
  19.         d1.addLast(s);
  20.         m1.put(s, 0);
  21.         d2.addLast(t);
  22.         m2.put(t, 0);
  23.         /*
  24.          *只有两个队列都不空，才有必要继续往下搜索
  25.          *如果其中一个为空，说明从某个方向搜到底都搜不到该方向的目标节点，那么反向搜索也没必要进行了
  26.          */
  27.         while(!d1.isEmpty() && !d2.isEmpty()) {
  28.             int t = -1;
  29.             //尽可能从需要拓展量较小的队列拓展
  30.             if(d1.size() <= d2.size()) {
  31.                 t = update(d1, m1, m2);
  32.             } else {
  33.                 t = update(d2, m2, m1);
  34.             }
  35.             if(t != -1) return t;
  36.         }
  37.         return -1; 
  38.     }
  39.  
  40.     int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {
  41.         int m = deque.size();
  42.         while(m-- > 0) {
  43.             String poll = deque.pollFirst();
  44.             char[] pcs = poll.toCharArray();
  45.             int step = cur.get(poll);
  46.             //枚举替换哪个字符
  47.             for(int i = 0; i < 4; i++) {
  48.                 //能「正向转」也能「反向转」，这里直接枚举偏移量[-1, 1] 然后跳过 0
  49.                 for(int j = -1; j <= 1; j++) {
  50.                     if(j == 0) continue;
  51.                     //求得替换字符 str
  52.                     int origin = pcs[i] - '0';
  53.                     int next = (origin + j) % 10; //防止进位
  54.                     if(next == -1) next = 9; //强制 0 前面为 9
  55.  
  56.                     char[] clone = pcs.clone(); //clone()是浅拷贝
  57.                     clone[i] = (char)(next + '0');
  58.                     String str = String.valueOf(clone); //将基本数据类型转换成String
  59.  
  60.                     if(set.contains(str)) continue; //在dead名单中直接排除
  61.                     if(cur.containsKey(str)) continue; //在「当前方向」出现过重复了
  62.  
  63.                     //如果在「另一方向」找到，说明找到了最短路，否则加入队列
  64.                     if(other.containsKey(str)) {
  65.                         return step + 1 + other.get(str);
  66.                     } else {
  67.                         deque.addLast(str);
  68.                         cur.put(str, step + 1);
  69.                     }
  70.                 } 
  71.             }
  72.         }
  73.         return -1;
  74.     }
  75. }
  76. 作者：宫水三叶

AStar 算法：

        根据本题规则来设计A*的「启发式函数」。

        对于两个状态 a 和 b 可直接计算出「理论最小转换次数」：不同字符的转换成本之和 。

        需要注意的是：由于我们衡量某个字符 str 的估值是以目标字符串 target 为基准，因此我们只能确保 target 出队时为「距离最短」，而不能确保中间节点出队时「距离最短」，因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队，还要结合当前节点的「最小距离」是否被更新而决定是否入队。

        这一点十分关键，在代码层面上体现在 map.get(str).step > poll.step + 1 的判断上。

        我们还需要注意：通常需要先【确保有解】，A*的启发搜索才会发挥真正价值！而对于本题，除非 t 本身在 deadends 中，否则我们无法很好地提前判断「是否有解」。若存在无解的情况，A*效果不如「双向 BFS」。

  1. class Solution {
  2.     class Node {
  3.         String str; //对应字符串
  4.         int val, step; //估值（与目标字符串 target 的最小转换成本） 和 对应字符串是经过多少步转换而来
  5.         Node(String _str, int _val, int _step) {
  6.             str = _str;
  7.             val = _val;
  8.             step = _step;
  9.         }
  10.     }
  11.  
  12.     int f(String str) { //计算字符串的估值
  13.         int ans = 0;
  14.         for(int i = 0; i < 4; i++) {
  15.             int cur = str.charAt(i) - '0', target = t.charAt(i) - '0';
  16.             int a = Math.min(cur, target), b = Math.max(cur, target);
  17.             //在「正向转」和「反向转」之间取 min
  18.             int min = Math.min(b - a, a + 10 - b);
  19.             ans += min;
  20.         }
  21.         return ans;
  22.     }
  23.     
  24.     //此部分与“双向BFS”在很大程度上是相同的，仔细比照增改了哪些地方
  25.  
  26.     String t, s;
  27.     Set<String> set = new HashSet<>();
  28.  
  29.     public int openLock(String[] deadends, String target) {
  30.         s = "0000";
  31.         t = target;
  32.         if(s.equals(t)) return 0;
  33.         for(String d : deadends) set.add(d);
  34.         if(set.contains(s)) return -1;
  35.         PriorityQueue<Node> q = new PriorityQueue<>((a, b)->a.val-b.val);
  36.         Map<String, Node> map = new HashMap<>();
  37.         Node root = new Node(s, f(s), 0);
  38.         q.add(root);
  39.         map.put(s, root);
  40.  
  41.         while(!q.isEmpty()) {
  42.             Node poll = q.poll();
  43.             char[] pcs = poll.str.toCharArray();
  44.             int step = poll.step;
  45.             if(poll.str.equals(t)) return step;
  46.             for(int i = 0; i < 4; i++) {
  47.                 for(int j = -1; j <= 1; j++) {
  48.                     if(j == 0) continue;
  49.                     int cur = pcs[i] - '0';
  50.                     int next = (cur + j) % 10;
  51.                     if(next == -1) next = 9;
  52.  
  53.                     char[] clone = pcs.clone();
  54.                     clone[i] = (char)(next + '0');
  55.                     String str = String.valueOf(clone);
  56.  
  57.                     if(set.contains(str)) continue;
  58.                     //如果 str 还没被搜索过或者 str 的「最短距离」没有被更新，则入队
  59.                     if(!map.containsKey(str) || map.get(str).step > step + 1) {
  60.                         Node node = new Node(str, step + 1 + f(str), step + 1);
  61.                         map.put(str, node);
  62.                         q.add(node);
  63.                     } 
  64.                 }
  65.             }
  66.         }
  67.         return -1;
  68.     }
  69. }
  70. 作者：宫水三叶

IDA* 算法：

        首次讲解：采用了迭代加深算法的A*算法。

        由于IDA*改成了深度优先的方式，所以相对于A*算法有如下的优点：

  • 不需要判重，不需要排序，利于深度剪枝。
  • 空间需求减少：每个深度下实际上是一个深度优先搜索，不过深度有限制，使用 DFS 可以减小空间消耗。

        缺点如下：

  • 重复搜索：即使前后两次搜索相差微小，但回溯过程中每次深度变大都要再次从头搜索。

        本题使用IDA*的特点：

  • 仍然使用 f() 作为估值函数。
  • 利用旋转次数有限：总旋转次数不会超过某个阈值 max。
  • 利用「迭代加深」的思路找到最短距离。

        理想情况下，由于存在正向旋转和反向旋转，每一位转轮从任意数字开始到达任意数字，消耗次数不会超过 5 次，因此理想情况下可以设定 max ⁡= 5∗4。

        但考虑到 deadends 的存在，我们需要将 max 定义得更为保守一点：max = 10∗4。

        但这样的阈值设定，加上IDA*算法每次会重复遍历「距离小于与目标节点距离」的所有节点的特性，会有很大的 TLE 风险。

        因此我们需要使用动态阈值：不再使用固定的阈值，而是利用 target 计算出「最大的转移成本」作为我们的「最深数量级」。

  • PS.以上阈值分析是科学做法，本题我们可以利用数据弱的特点，直接使用 max = 5∗4 也可以通过并且效果也不错。
  • PS.max = 5∗4 也可能是个错误的阈值！考虑这种情况：起点为 0000 ，若 target 为 2222 ，并且将所有从 0000 到 2222 的正向转换的状态都放入 deadends 中。此时，我们只能将 0000 先变为 9999 再反向变为 2222 ！显然此时使用 max =  5∗4就不对了。但本题数据较弱仍可以通过。
  1. class Solution {
  2.     String s, t;
  3.     String cur;
  4.     Set<String> set = new HashSet<>();
  5.     Map<String, Integer> map = new HashMap<>();
  6.     public int openLock(String[] deadends, String target) {    
  7.         s = "0000";
  8.         t = target;
  9.         if(s.equals(t)) return 0;
  10.         for(String d : deadends) set.add(d);
  11.         if(set.contains(s)) return -1;
  12.  
  13.         int depth = 0, max = getMax(); //当前深度 和 最深数量级
  14.         cur = s;
  15.         map.put(cur, 0);
  16.         while(depth <= max && !dfs(0, depth)) {
  17.             map.clear();
  18.             cur = s;
  19.             map.put(cur, 0);
  20.             depth++;
  21.         }
  22.         return depth > max ? -1 : depth;
  23.     }
  24.         
  25.     int getMax() { //即最大的转移成本作为最深数量级
  26.         int ans = 0;
  27.         for(int i = 0; i < 4; i++) {
  28.             int origin = s.charAt(i) - '0', next = t.charAt(i) - '0';
  29.             int a = Math.min(origin, next), b = Math.max(origin, next);
  30.             int max = Math.max(b - a, a + 10 - b);
  31.             ans += max;
  32.         }
  33.         return ans;
  34.     }
  35.  
  36.     int f() { //计算字符串的估值即理论的最小转换次数
  37.         int ans = 0;
  38.         for(int i = 0; i < 4; i++) {
  39.             int origin = cur.charAt(i) - '0', next = t.charAt(i) - '0';
  40.             int a = Math.min(origin, next), b = Math.max(origin, next);
  41.             int min = Math.min(b - a, a + 10 - b);
  42.             ans += min;
  43.         }
  44.         return ans;
  45.     }
  46.  
  47.     boolean dfs(int u, int max) {
  48.         if(u + f() > max) return false;
  49.         if(f() == 0) return true; //即预计所剩步骤为0，已经到达目标字符串
  50.         String backup = cur; //用backup记录cur值以便回溯
  51.         char[] cs = cur.toCharArray();
  52.         for(int i = 0; i < 4; i++) {
  53.             for(int j = -1; j <= 1; j++) {
  54.                 if(j == 0) continue;
  55.                 int origin = cs[i] - '0';
  56.                 int next = (origin + j) % 10;
  57.                 if(next == -1) next = 9;
  58.                 char[] clone = cs.clone();
  59.                 clone[i] = (char)(next + '0');
  60.                 String str = String.valueOf(clone);
  61.                 if(set.contains(str)) continue;
  62.                 if(!map.containsKey(str) || map.get(str) > u + 1) {
  63.                     cur = str; //cur指向str，进入下一层dfs
  64.                     map.put(str, u + 1);
  65.                     if(dfs(u + 1, max)) return true;
  66.                     cur = backup; //将cur回溯
  67.                 } 
  68.             }
  69.         } 
  70.         return false;
  71.     }
  72. }    
  73. 作者：宫水三叶

        由此可以看出图论的题目是真的考验各方面的综合水平。

LeetCode773.滑动谜题：

问题描述：

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

示例 ：

输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]

提示：

  • board.length == 2
  • board[i].length == 3
  • 0 <= board[i][j] <= 5
  • board[i][j] 中每个值都 不同

代码分析：

        本题是【八数码问题】的简化版：将 3 * 3 变为 2 * 3，同时将「输出路径」变为「求最小步数」。

        通常此类问题可以使用「BFS」、「AStar 算法」、「康拓展开」进行求解。

        由于问题简化到了 2 * 3，我们使用前两种解法即可。

BFS：

        为了方便，将原来的二维矩阵转成字符串（一维矩阵）进行处理。

        这样带来的好处是直接可以作为哈希 Key 使用，也可以很方便进行「二维坐标」与「一维下标」的转换。

        由于固定是 2 * 3 的格子，因此任意的合法二维坐标（x , y）和对应一维下标 idx 可通过以下转换：

  • idx = x * 3 + y
  • x=idx/3,y=idx
  1. class Solution {
  2.     class Node {
  3.         String str;
  4.         int x, y;
  5.         Node(String _str, int _x, int _y) {
  6.             str = _str; x = _x; y = _y;
  7.         }
  8.     }
  9.  
  10.     int n = 2, m = 3;
  11.     String s, e;
  12.     int x, y;
  13.  
  14.     public int slidingPuzzle(int[][] board) {
  15.         s = "";
  16.         e = "123450";
  17.         for(int i = 0; i < n; i++) {
  18.             for(int j = 0; j < m; j++) {
  19.                 s += board[i][j];
  20.                 if(board[i][j] == 0) {
  21.                     x = i; y = j;
  22.                 }
  23.             }
  24.         }
  25.         int ans = bfs();
  26.         return ans;
  27.     }
  28.  
  29.     int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; //方向数组
  30.     
  31.     int bfs() {
  32.         Deque<Node> d = new ArrayDeque<>();
  33.         Map<String, Integer> map = new HashMap<>(); //存储当前状态和已经移动的次数
  34.         Node root = new Node(s, x, y);
  35.         d.addLast(root);
  36.         map.put(s, 0);
  37.         while(!d.isEmpty()) {
  38.             Node poll = d.pollFirst();
  39.             int step = map.get(poll.str);
  40.             if(poll.str.equals(e)) return step;
  41.             int dx = poll.x, dy = poll.y;
  42.             for(int[] di : dirs) {
  43.                 int nx = dx + di[0], ny = dy + di[1];
  44.                 if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  45.                 String nStr = update(poll.str, dx, dy, nx, ny);
  46.                 if(map.containsKey(nStr)) continue;
  47.                 Node next = new Node(nStr, nx, ny);
  48.                 d.addLast(next);
  49.                 map.put(nStr, step + 1);
  50.             }
  51.         }
  52.         return -1;
  53.     }
  54.  
  55.     String update(String cur, int i, int j, int p, int q) {
  56.         char[] cs = cur.toCharArray();
  57.         char tmp = cs[i * m + j];
  58.         cs[i * m + j] = cs[p * m + q];
  59.         cs[p * m + q] = tmp;
  60.         return String.valueOf(cs);
  61.     }
  62. }
  63. 作者：宫水三叶

A* 算法：

        首先设计本题的A*「启发式函数」。

        和前面题目类似，对于两个状态 a 和 b 可直接计算出「理论最小转换次数」：所有位置的数值「所在位置」与「目标位置」的曼哈顿距离之和（即横纵坐标绝对值之和） 。

  • 我们只需要计算「非空格」位置的曼哈顿距离即可，因为空格的位置会由其余数字占掉哪些位置而唯一确定
  • A* 求最短路的正确性：与之前做过的题目类似，由于我们衡量某个状态 str 的估值是以目标字符串 e=123450 为基准，因此我们只能确保 e 出队时为「距离最短」，而不能确保中间节点出队时「距离最短」，因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队，还要结合当前节点的「最小距离」是否被更新而决定是否入队。即这一点在代码层面体现为 map.get(nStr) > step + 1。
  • A* 在有解的情况下，才会发挥「启发式搜索」最大价值。因此如果我们能够提前判断无解的情况，对 A* 算法来说会是巨大的提升。

        而对于通用的 N * N 数码问题，判定有解的一个充要条件是：「逆序对」数量为偶数，如果不满足，必然无解，直接返回 −1 即可。（对该结论的充分性证明和必要性证明完全不在一个难度上，所以记住这个结论即可）

        但本题是2 * 3 的数码问题，结论是否还成立？答案是成立的，对于任意的 N∗M 的数码问题，只要确保 M 为奇数，逆序对数量为偶数，必然有解（因为此时四联通的操作不会改变奇偶性）。

  1. class Solution {
  2.     class Node {
  3.         String str;
  4.         int x, y, val;
  5.         Node(String _str, int _x, int _y, int _val) {
  6.             str = _str; x = _x; y = _y; val = _val;
  7.         }
  8.     }
  9.  
  10.     int f(String str) {
  11.         int ans = 0;
  12.         char[] cs1 = str.toCharArray(), cs2 = e.toCharArray();
  13.         for(int i = 0; i < n; i++) {
  14.             for(int j = 0; j < m; j++) {
  15.                 //跳过「空格」，计算其余数值的曼哈顿距离
  16.                 if(cs1[i * m + j] == '0' || cs2[i * m + j] == '0') continue;
  17.                 int cur = cs1[i * m + j], next = cs2[i * m + j];
  18.                 //计算在二维坐标下的曼哈顿距离之和
  19.                 int xd = Math.abs((cur - 1) / 3 - (next - 1) / 3);
  20.                 int yd = Math.abs((cur - 1) % 3 - (next - 1) % 3);
  21.                 ans += (xd + yd);
  22.             }
  23.         }
  24.         return ans;
  25.     }
  26.  
  27.     int n = 2, m = 3;
  28.     String s, e;
  29.     int x, y;
  30.  
  31.     public int slidingPuzzle(int[][] board) {
  32.         s = "";
  33.         e = "123450";
  34.         for(int i = 0; i < n; i++) {
  35.             for(int j = 0; j < m; j++) {
  36.                 s += board[i][j];
  37.                 if(board[i][j] == 0) {
  38.                     x = i; y = j;
  39.                 }
  40.             }
  41.         }
  42.         //提前判断无解情况
  43.         if(!check(s)) return -1;
  44.  
  45.         int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; //方向数组
  46.         PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
  47.         Map<String, Integer> map = new HashMap<>(); //存储当前状态和已经移动的次数
  48.         Node root = new Node(s, x, y, f(s));
  49.         q.add(root);
  50.         map.put(s, 0);
  51.         while(!q.isEmpty()) {
  52.             Node poll = q.poll();
  53.             int step = map.get(poll.str);
  54.             if(poll.str.equals(e)) return step;
  55.             int dx = poll.x, dy = poll.y;
  56.             for(int[] di : dirs) {
  57.                 int nx = dx + di[0], ny = dy + di[1];
  58.                 if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  59.                 String nStr = update(poll.str, dx, dy, nx, ny);
  60.                 if(!map.containsKey(nStr) || map.get(nStr) > step + 1) {
  61.                     Node next = new Node(nStr, nx, ny, step + 1 + f(nStr));
  62.                     q.add(next);
  63.                     map.put(nStr, step + 1);
  64.                 }
  65.             }
  66.         }
  67.         return 0x3f3f3f3f; //never
  68.     }
  69.  
  70.     String update(String cur, int i, int j, int p, int q) {
  71.         char[] cs = cur.toCharArray();
  72.         char tmp = cs[i * m + j];
  73.         cs[i * m + j] = cs[p * m + q];
  74.         cs[p * m + q] = tmp;
  75.         return String.valueOf(cs);
  76.     }
  77.  
  78.     boolean check(String str) {
  79.         char[] cs = str.toCharArray();
  80.         List<Integer> list = new ArrayList<>();
  81.         for(int i = 0; i < n * m; i++) {
  82.             if(cs[i] != '0') list.add(cs[i] - '0');
  83.         }
  84.         int cnt = 0;
  85.         for(int i = 0; i < list.size(); i++) {
  86.             for(int j = i + 1; j < list.size(); j++) {
  87.                 if(list.get(i) > list.get(j)) cnt++;
  88.             }
  89.         }
  90.         return cnt % 2 == 0;
  91.     }
  92. }
  93. 作者：宫水三叶

LeetCode815.公交路线：

问题描述：

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

  • 例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

示例 1：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。

提示：

  • 1 <= routes.length <= 500.
  • 1 <= routes[i].length <= 105
  • routes[i] 中的所有值 互不相同
  • sum(routes[i].length) <= 105
  • 0 <= routes[i][j] < 106
  • 0 <= source, target < 106

代码分析：

        题干表示为由一个车站可以进入一条或多条路线，问题为从【起点车站】到【终点车站】，所进入的最少路线为多少。

        我们抽象每个路线为一个点，当不同路线之间存在【公共车站】则为其增加一条边权为1的无向边。

朴素BFS：

        由于是在边权为1的图中求最短路，我们直接使用 BFS 即可。

        起始时将【起点车站】所能进入的路线进行入队，每次从队列中取出路线时，查看该路线是否包含【终点车站】：

  • 包含：返回进入该路线所花费的距离
  • 不包含：遍历该路线所包含的车站，将由这些车站所能进入的路线进行入队

        由于是求最短路，同一路线重复入队无意义，我们需要在新路线入队前判断是否曾经入队过。

  1. class Solution {
  2.     int s, t;
  3.     int[][] rs;
  4.     public int numBusesToDestination(int[][] routes, int source, int target) {
  5.         rs = routes; s = source; t = target;
  6.         if(s == t) return 0;
  7.         int ans = bfs();
  8.         return ans;
  9.     }
  10.  
  11.     int bfs() {
  12.         //记录某个车站可以进入的路线（其逻辑与路线包含的车站正好相反）
  13.         Map<Integer, Set<Integer> > map = new HashMap<>();
  14.         //队列存的是经过的路线
  15.         Deque<Integer> d = new ArrayDeque<>();
  16.         //哈希表记录的进入该路线所使用的距离
  17.         Map<Integer, Integer> m = new HashMap<>();
  18.  
  19.         //预处理路线-车站数组
  20.         int n = rs.length;
  21.         for(int i = 0; i < n; i++) {
  22.             for(int station : rs[i]) {
  23.                 //将从起点可以进入的路线加入队列
  24.                 if(station == s) {
  25.                     d.addLast(i);
  26.                     m.put(i, 1);
  27.                 }
  28.                 //更新map
  29.                 Set<Integer> set = map.getOrDefault(station, new HashSet<>());
  30.                 set.add(i);
  31.                 map.put(station, set);
  32.             }
  33.         }
  34.  
  35.         while(!d.isEmpty()) {
  36.             //取出当前所在的路线，与进入该路线所花费的距离
  37.             int poll = d.pollFirst();
  38.             int step = m.get(poll);
  39.  
  40.             //遍历该路线所包含的车站
  41.             for(int station : rs[poll]) {
  42.                 //若包含终点，返回进入该路线花费的距离即可
  43.                 if(station == t) return step;
  44.                 //将由该路线的车站发起的路线加入队列
  45.                 Set<Integer> lines = map.get(station);
  46.                 if(lines == null) continue;
  47.                 for(int nr : lines) {
  48.                     //判断是否重复入队可以通过哈希表m
  49.                     if(!m.containsKey(nr)) {
  50.                         m.put(nr, step + 1);
  51.                         d.add(nr);
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.         return -1;
  57.     }
  58. }
  59. 作者：宫水三叶

        时间复杂度：令路线的数量为 n，车站的数量为 m。建图的时间复杂度为O(\sum_{i=0}^{n-1}len(rs[i]))；BFS 部分每个路线只会入队一次，最坏情况下每个路线都包含所有车站，复杂度为 O(n∗m)。整体复杂度为 O(n*m+\sum_{i=0}^{n-1}len(rs[i]))。

双向BFS：

        建图方式不变，我们将【起点】和【终点】所能进入的路线分别放入两个方向的队列。

        如果【遇到公共的路线】或者【当前路线包含了目标位置】，说明找到了最短路径。

        此外，双向BFS在无解的情况下不如朴素BFS。因此可以先使用【并查集】进行预处理，判断【起点】和【终点】是否连通，若否直接返回-1，有解才调用双向BFS。

        由于使用【并查集】预处理的复杂度和建图是近似的，增加这样的预处理并不会越过时空复杂度的上限，因此这样的预处理是有益的。一定程度上可以最大化双向 BFS 减少搜索空间的效益。

  1. class Solution {
  2.     static int N = (int)1e6+10;
  3.     static int[] p = new int[N];
  4.  
  5.     int find(int x) {
  6.         if(p[x] != x) p[x] = find(p[x]);
  7.         return p[x];
  8.     }
  9.  
  10.     void union(int a, int b) {
  11.         p[find(a)] = p[find(b)];
  12.     }
  13.  
  14.     boolean query(int a, int b) {
  15.         return find(a) == find(b);
  16.     }
  17.  
  18.     int s, t;
  19.     int[][] rs;
  20.     public int numBusesToDestination(int[][] routes, int source, int target) {
  21.         rs = routes; s = source; t = target;
  22.         if(s == t) return 0;
  23.         for(int i = 0; i < N; i++) p[i] = i;
  24.         for(int[] r : rs) {
  25.             for(int loc : r) {
  26.                 union(loc, r[0]);
  27.             }
  28.         }
  29.         if(!query(s, t)) return -1;
  30.         int ans = bfs();
  31.         return ans;
  32.     }
  33.  
  34.     //记录某个车站可以进入的路线（其逻辑与路线包含的车站正好相反）
  35.     Map<Integer, Set<Integer> > map = new HashMap<>();
  36.     int bfs() {
  37.         //队列存的是经过的路线
  38.         Deque<Integer> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
  39.         //哈希表记录的进入该路线所使用的距离
  40.         Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
  41.  
  42.         //预处理路线-车站数组
  43.         int n = rs.length;
  44.         for(int i = 0; i < n; i++) {
  45.             for(int station : rs[i]) {
  46.                 //将从起点可以进入的路线加入正向队列
  47.                 if(station == s) {
  48.                     d1.addLast(i);
  49.                     m1.put(i, 1);
  50.                 }
  51.                 if(station == t) {
  52.                     d2.addLast(i);
  53.                     m2.put(i, 1);
  54.                 }
  55.                 //更新map
  56.                 Set<Integer> set = map.getOrDefault(station, new HashSet<>());
  57.                 set.add(i);
  58.                 map.put(station, set);
  59.             }
  60.         }
  61.  
  62.         //若【起点所发起的路线】和【终点所发起的路径】有交集，直接返回1
  63.         Set<Integer> s1 = map.get(s), s2 = map.get(t);
  64.         Set<Integer> tot = new HashSet<>();
  65.         /*
  66.         addAll是将实参的全部元素添加到集合中（Set不允许重复）
  67.         retainAll是求两个集合的交集
  68.         */
  69.         tot.addAll(s1); tot.retainAll(s2); 
  70.         if(!tot.isEmpty()) return 1;
  71.  
  72.         while(!d1.isEmpty() && !d2.isEmpty()) {
  73.             int res = -1;
  74.             if(d1.size() <= d2.size()) {
  75.                 res = update(d1, m1, m2);
  76.             } else {
  77.                 res = update(d2, m2, m1);
  78.             }
  79.             if(res != -1) return res;
  80.         }    
  81.         return 0x3f3f3f3f; //never
  82.     }
  83.  
  84.     int update(Deque<Integer> d, Map<Integer, Integer> cur, Map<Integer, Integer> other) {
  85.         int m = d.size();
  86.         while(m-- > 0) {
  87.             //取出当前所在的路线，与进入该路线所花费的距离
  88.             int poll = d.pollFirst();
  89.             int step = cur.get(poll);
  90.  
  91.             //遍历该路线所包含的车站
  92.             for(int station : rs[poll]) {
  93.                 //遍历将由该路线的车站发起的路线
  94.                 Set<Integer> lines = map.get(station);
  95.                 if(lines == null) continue;
  96.                 for(int nr : lines) {
  97.                     if(cur.containsKey(nr)) continue;
  98.                     if(other.containsKey(nr)) return step + other.get(nr);
  99.                     cur.put(nr, step + 1);
  100.                     d.add(nr);
  101.                     }
  102.                 }
  103.             }
  104.             return -1;
  105.         }
  106.     }

        时间复杂度：路线数量为n，车站的个数为m。并查集和建图的时间复杂度为O(\sum_{i=0}^{n-1}len(rs[i]))；BFS的时间复杂度为O(n * m)；整体时间复杂度为二者相加。

        至于为什么要取值 0x3f3f3f3f ？

LeetCode847.访问所有节点的最短路径：

问题描述：

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。

给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

示例 1：

输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]

提示：

  • n == graph.length
  • 1 <= n <= 12
  • 0 <= graph[i].length < n
  • graph[i] 不包含 i
  • 如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
  • 输入的图总是连通图

代码分析：

        我们令点的个数为n，边的条数为m。由于本题是【等权无向图】，要求从【所有点均未被访问】到【所有点均被访问】的最短路径。

        数据范围 n 最大只有12，可以使用【状态压缩】来代表【当前点的访问状态】：使用二进制表示长度为 32 的 int 的低 12 来代指点是否被访问过。

        状压的基本操作：P.S. (000...0101)_{2}代表编号为 0 和编号为 2 的节点已经被访问过，而编号为 1 的节点尚未被访问。有如下：

  • 假设变量 state 存放了【当前点的访问状态】，当需要检查编号为 x 的点是否被访问过时，使用位运算 a = (state >> x) & 1，若 a 为 1 则 x 访问过，反则反之。
  • 当需要标记编号为 x 的节点已经访问过了，使用位运算 state | ( 1 << x )。

状态压缩+BFS：

        由于是等权图，求从某个状态到另一状态的最短路，可以使用BFS。

        同时也需要知道下一步能往哪些点进行移动，因此除了记录当前的点访问状态 state ，还需要记录最后一步是在哪个点 u ，因此我们需要使用二元组 (state,u) 进行记录，同时使用 dist 来记录到达 (state,u) 使用的步长是多少。使用状态压缩可以快速知道当前节点为 i 时，其余节点的状态。

  • 由于点的数量较少，使用【邻接表】或者【邻接矩阵】来存图都可以。由于给出了 graph 数组，因此可以直接充当【邻接表】来使用，无须做额外的存图操作。
  1. class Solution {
  2.     int INF = 0x3f3f3f3f;
  3.     public int shortestPathLength(int[][] graph) {
  4.         int n = graph.length;
  5.         int mask = 1 << n; //相当于 2 ^ n 种状态
  6.  
  7.         //初始化所有的(state, u)距离为正无穷
  8.         int[][] dist  = new int[mask][n]; //记录到达(state, u)所使用的步长
  9.         for(int i = 0; i < mask; i++) Arrays.fill(dist[i], INF);
  10.  
  11.         //因为可以从任意起点出发，先将起始的起点状态入队，并设起点距离为 0
  12.         Deque<int[]> d = new ArrayDeque<>(); // state, u
  13.         for(int i = 0; i < n; i++) {
  14.             dist[1 << i][i] = 0;
  15.             d.addLast(new int[]{1 << i, i});
  16.         }
  17.  
  18.         //BFS过程，如果从点 u 能够到达点 i，则更新距离并进行入队
  19.         while(!d.isEmpty()) {
  20.             int[] poll = d.pollFirst();
  21.             int state = poll[0], u = poll[1], step = dist[state][u];
  22.             if(state == mask - 1) return step;
  23.             for(int i : graph[u]) { //graph[u] 存储所有与点 u 相连的所有点
  24.                 if(dist[state | (1 << i)][i] == INF) {
  25.                     dist[state | (1 << i)][i] = step + 1;
  26.                     d.addLast(new int[]{state | (1 << i), i});
  27.                 }
  28.             }
  29.         }
  30.         return -1;
  31.     }
  32. }
  33. 作者：宫水三叶

        时间复杂度：点（状态）数量为 n * 2^n，边的数量为 n^2 * 2^n，BFS的复杂度上界为点数加边数，整体复杂度为O(n^2 * 2^n)。

Floyd+状压DP：

        实际上，在上述方法中，我们已经使用了与DP状态定义分析类似的思路了。甚至，设计的元组 (state, u)也十分类似状态定义的两个维度。

  • 为何不使用 f[state][u] 为从【没有点被访问过】到【访问过的点状态为 state】，并最后一步落在点 u 的状态定义，然后跑一遍 DP 来做 ？
  • 因为如果从【常规的 DP 转移思路】出发，状态之间不存在拓扑序（有环），这就导致了我们在计算某个 f[state][u] 时，它所依赖的状态并不确保已经被计算/更新完成，所以我们无法使用常规的 DP 手段来求解。
  • 另，常规的 DP 手段是指：枚举所有与 u 相连的节点 v，使用 f[state'][u] 来更新 f[state][u] 的转移方式。

        常规的 DP 转移方式状态间不存在拓扑序，我们需要换一个思路进行转移。

        对于某个 state 而言，我们可以枚举其最后一个点 i 是哪一个（state 中已经被访问过的点），充当其达到 state 的最后一步，然后再枚举下一个点 j 是哪一个（state中未被访问的点），充当移动的下一步（前提为满足 state 的第 i 位为 1，而第 j 位为 0）。

        求解任意两点最短路径，可以使用 Floyd 算法，复杂度为O(n^3)。

  1. class Solution {
  2.     int INF = 0x3f3f3f3f;
  3.     public int shortestPathLength(int[][] graph) {
  4.         int n = graph.length;
  5.         int mask = 1 << n;
  6.  
  7.         //Floyd 求两点的最短路径
  8.         int[][] dist  = new int[n][n];
  9.         for(int i = 0; i < n; i++) {
  10.             for(int j = 0; j < n; j++) {
  11.                 dist[i][j] = INF;
  12.             }
  13.         }
  14.         for(int i = 0; i < n; i++) {
  15.             for(int j : graph[i]) dist[i][j] = 1;
  16.         }
  17.         for(int k = 0; k < n; k++) {
  18.             for(int i = 0; i < n; i++) {
  19.                 for(int j = 0; j < n; j++) {
  20.                     dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
  21.                 }
  22.             }
  23.         }
  24.  
  25.         //DP过程，如果从 i 能够到 j 的话，使用 i 到 j 的最短距离（步长）来转移
  26.         int[][] f = new int[mask][n];
  27.         //起始时，让所有状态的最短距离（步长）为正无穷
  28.         for(int i = 0; i < mask; i++) Arrays.fill(f[i], INF);
  29.         //由于可以将任意点作为起点出发，可以将这些起点的最短距离（步长）设置为 0
  30.         for(int i = 0; i < n; i++) f[1 << i][i] = 0;
  31.  
  32.         //枚举所有的 state
  33.         for(int state = 0; state < mask; state++) {
  34.             //枚举 state 中已经被访问过的点
  35.             for(int i = 0; i < n; i++) {
  36.                 if(((state >> i) & 1) == 0) continue;
  37.                 //枚举 state 中尚未被访问过的点
  38.                 for(int j = 0; j < n; j++) {
  39.                     if(((state >> j) & 1) == 1) continue;
  40.                     f[state | (1 <<j)][j] = Math.min(f[state | (1 << j)][j], f[state][i] + dist[i][j]);
  41.                 }
  42.             }
  43.         }
  44.         int ans = INF;
  45.         for(int i = 0; i < n; i++) ans = Math.min(ans, f[mask - 1][i]);
  46.         return ans;
  47.     }
  48. }
  49. 作者：宫水三叶

        时间复杂度：Floyd 复杂度为O(n^3)；DP共有 n * 2^n 个状态需要被转移，每次转移复杂度为O(n)，总复杂度为O(n^2 * 2^n)。整体复杂度为O(max(n^3, n^2 * 2^n))。

A* ：

        按照以上定义，从 state 到 state’ 的【理论最小修改成本】为两者二进制表示中不同位数的个数。需要注意的是，当且仅当在 state 中 1 的位置与 state’ 中 0 存在边，才有可能取到这个【理论最小修改成本】。

  1. class Solution {
  2.     int INF = 0x3f3f3f3f;
  3.     int n;
  4.  
  5.     int f(int state) { //理论最小修改成本
  6.         int ans = 0;
  7.         for(int i = 0; i < n; i++) {
  8.             if(((state >> i) & 1) == 0) ans++;
  9.         }
  10.         return ans;
  11.     }
  12.  
  13.     public int shortestPathLength(int[][] graph) {
  14.         int n = graph.length;
  15.         int mask = 1 << n;
  16.         int[][] dist = new int[mask][n];
  17.         for(int i = 0; i < mask; i++) 
  18.             for(int j = 0; j < n; j++) 
  19.                 dist[i][j] = INF;
  20.         
  21.         PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]);
  22.         for(int i = 0; i < n; i++) {
  23.             dist[1 << i][i] = 0;
  24.             q.add(new int[]{1 << i, i, f(1 << i)});
  25.         }
  26.         while(!q.isEmpty()) {
  27.             int[] poll = q.poll();
  28.             int state = poll[0], u = poll[1], step = dist[state][u];
  29.             if(state == mask - 1) return step;
  30.             for(int i : graph[u]) {
  31.                 int nState = state | (1 << i);
  32.                 if(dist[nState][i] > step + 1) {
  33.                     dist[nState][i] = step + 1;
  34.                     q.add(new int[]{nState, i, step + 1 + f(nState)});
  35.                 }
  36.             }
  37.         }
  38.         return -1;
  39.     }
  40. }
  41. 作者：宫水三叶

LeetCode863.二叉树中所有距离为K的结点：

问题描述：

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 k 。

返回到目标结点 target 距离为 k 的所有结点的值的列表。 答案可以以 任何顺序 返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

提示:

  • 节点数在 [1, 500] 范围内
  • 0 <= Node.val <= 500
  • Node.val 中所有值 不同
  • 目标结点 target 是树上的结点。
  • 0 <= k <= 1000

代码分析：

        树是一类特殊的图，我们可以将二叉树转换成图的形式，再进行【BFS/迭代加深】找到距离为 k 的节点集。

        由于二叉树每个点最多有两个子节点，点和边的数量接近，属于稀疏图，所以我们可以使用【邻接表】的形式来存储。

        建图方式为：对于二叉树中相互连通的节点（root 与root.left、root 与 root.right），建立一条无向边。需要遍历整棵树，使用 DFS 或者 BFS。

        利用每个节点具有唯一的值这一特性，我们可以直接使用节点值进行建图 和搜索。

建图+BFS：

  1. class Solution {
  2.     //根据数据范围最多有501个点，每个点最多有2条无向边（两个子节点）
  3.     int N = 510, M = N * 4;
  4.     /* he 数组：存储【是某个节点所对应的边的集合（链表）】的头结点
  5.      * e 数组：由于访问某一条边指向的节点
  6.      * ne 数组：由于是以链表的形式进行存边，该数组就是用于找到下一条边
  7.      */
  8.     int[] he = new int[N], e = new int[M], ne = new int[M];
  9.     int idx;
  10.  
  11.     void add(int a, int b) {
  12.         e[idx] = b;
  13.         ne[idx] = he[a];
  14.         he[a] = idx++;
  15.     }
  16.     boolean[] vis = new boolean[N]; //标记是否访问过
  17.  
  18.     public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
  19.         List<Integer> ans = new ArrayList<>();
  20.         Arrays.fill(he, -1);
  21.         dfs(root);
  22.         Deque<Integer> d = new ArrayDeque<>();
  23.         d.addLast(target.val);
  24.         vis[target.val] = true;
  25.         while(!d.isEmpty() && k >= 0) {
  26.             int size = d.size();
  27.             while(size-- > 0) {
  28.                 int poll = d.pollFirst();
  29.                 if(k == 0) {
  30.                     ans.add(poll);
  31.                     continue;
  32.                 }
  33.                 for(int i = he[poll]; i != -1; i = ne[i]) {
  34.                     int j = e[i];
  35.                     if(!vis[j]) {
  36.                         d.addLast(j);
  37.                         vis[j] = true;
  38.                     }
  39.                 }
  40.             }
  41.             k--;
  42.         }
  43.         return ans;
  44.     }
  45.  
  46.     void dfs(TreeNode root) {
  47.         if(root == null) return;
  48.         if(root.left != null) {
  49.             add(root.val, root.left.val);
  50.             add(root.left.val, root.val);
  51.             dfs(root.left);
  52.         }
  53.         if(root.right != null) {
  54.             add(root.val, root.right.val);
  55.             add(root.right.val, root.val);
  56.             dfs(root.right);
  57.         }
  58.     }
  59. }
  60. 作者：宫水三叶

        时间复杂度：通过 DFS 建图的复杂度为O(n)；通过 BFS遍历整棵树（找到距离 target 为 k 的节点）的复杂度为O(n)；整体为O(n)。

建图+迭代加深：

        需要结合题意，搜索深度为 k 的这一层即可。

  1. class Solution {
  2.     //根据数据范围最多有501个点，每个点最多有2条无向边（两个子节点）
  3.     int N = 510, M = N * 4;
  4.     int[] he = new int[N], e = new int[M], ne = new int[M];
  5.     int idx;
  6.  
  7.     void add(int a, int b) {
  8.         e[idx] = b;
  9.         ne[idx] = he[a];
  10.         he[a] = idx++;
  11.     }
  12.     boolean[] vis = new boolean[N]; //标记是否访问过
  13.  
  14.     public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
  15.         List<Integer> ans = new ArrayList<>();
  16.         Arrays.fill(he, -1);
  17.         dfs(root);
  18.         vis[target.val] = true;
  19.         find(target.val, k, 0, ans);
  20.         return ans;
  21.     }
  22.  
  23.     void find(int root, int max, int cur, List<Integer> ans) {
  24.         if(cur == max) {
  25.             ans.add(root);
  26.             return;
  27.         }
  28.         for(int i = he[root]; i != -1; i = ne[i]) {
  29.             int j = e[i];
  30.             if(!vis[j]) {
  31.                 vis[j] = true;
  32.                 find(j, max, cur + 1, ans);
  33.             }
  34.         }
  35.     }
  36.  
  37.     void dfs(TreeNode root) {
  38.         if(root == null) return;
  39.         if(root.left != null) {
  40.             add(root.val, root.left.val);
  41.             add(root.left.val, root.val);
  42.             dfs(root.left);
  43.         }
  44.         if(root.right != null) {
  45.             add(root.val, root.right.val);
  46.             add(root.right.val, root.val);
  47.             dfs(root.right);
  48.         }
  49.     }
  50. }
  51. 作者：宫水三叶

        时间复杂度同上。

Map存储邻接节点（省去存图操作）：

  1. class Solution {
  2.     Map<Integer, List<Integer>> adj = new HashMap<>(); //邻接表，键为节点，值为该节点的邻接节点
  3.     Set<Integer> visit = new HashSet<>(); //也可以使用 boolean[] vis = new boolean[N];
  4.     
  5.     public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
  6.         List<Integer> ans = new ArrayList<>();
  7.         dfs(root); //构建无向图
  8.         //图的BFS遍历
  9.         Deque<Integer> d = new ArrayDeque<>();
  10.         d.addLast(target.val);
  11.         visit.add(target.val);
  12.         while(!d.isEmpty() && k >= 0) {
  13.             int size = d.size(); //此处是多源，一次遍历一整层
  14.             for(int i = 0; i < size; i++) {
  15.                 int cur = d.pollFirst();
  16.                 if(k == 0) {
  17.                     ans.add(cur);
  18.                     continue;
  19.                 }
  20.                 //把邻接节点放入队列
  21.                 List<Integer> adjNodes = adj.get(cur);
  22.                 if(adjNodes == null) continue;
  23.                 for(int node : adjNodes) {
  24.                     if(!visit.contains(node)) {
  25.                         d.addLast(node);
  26.                         visit.add(node);
  27.                     }
  28.                 }
  29.             }
  30.             k--;
  31.         }
  32.         return ans;
  33.     }
  34.  
  35.     void add(int a, int b) {
  36.         if(adj.get(a) == null) {
  37.             List<Integer> list = new ArrayList<>();
  38.             list.add(b);
  39.             adj.put(a, list);
  40.         } else {
  41.             List<Integer> list = adj.get(a);
  42.             list.add(b);
  43.             adj.put(a, list);
  44.         }
  45.     }
  46.  
  47.     void dfs(TreeNode root) {
  48.         if(root == null) return;
  49.         if(root.left != null) {
  50.             add(root.val, root.left.val);
  51.             add(root.left.val, root.val);
  52.             dfs(root.left);
  53.         }
  54.         if(root.right != null) {
  55.             add(root.val, root.right.val);
  56.             add(root.right.val, root.val);
  57.             dfs(root.right);
  58.         }
  59.     }
  60. }
  61. 作者：神木

        在此补充一下建图步骤的解释：

LeetCode864.获取所有钥匙的最短路径：

问题描述：

给定一个二维网格 grid ，其中：

  • '.' 代表一个空房间
  • '#' 代表一堵墙
  • '@' 是起点
  • 小写字母代表钥匙
  • 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例 1：

输入：grid = ["@.a.#","###.#","b.A.B"]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 30
  • grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及 'A'-'F'
  • 钥匙的数目范围是 [1, 6] 
  • 每个钥匙都对应一个 不同 的字母
  • 每个钥匙正好打开一个对应的锁

代码分析：

        做完之前的847.，相信我们对于【状态压缩】有了一定的了解，我们来看处理方式类似的本题。

        其实本题也是一道常规的 BFS 搜索题，只不过需要在 BFS 过程中记录收集到的钥匙状态。

        利用【钥匙数量不超过 6 ，并按照字母顺序排列】这一条件，我们可以用一个 int 类型二进制数 state 来代指当前收集到的钥匙情况：

  • 若 state 的二进制的第 k 位为 1 / 0，代表当前种类编号为 k 的钥匙【已被收集 / 未被收集】，后序移动若遇到对应的锁则【能通过 / 不能通过】。
  • 需注意：其中【钥匙种类编号】则按照小写字母先后顺序，从 0 开始进行划分对应。即字符为 a/b/c 的钥匙编号为 0/1/2。

        当使用了如上技巧，我们可以用【位运算】进行 钥匙检测 和 更新钥匙状态：

  • 钥匙检测：(state >> k) & 1，若返回 1，表明第 k 位为 1，当前持有种类编号为 k 的钥匙。
  • 更新钥匙收集状态：state |= 1 << k，将 state 的第 k 位设置为 1，表明当前新收集到种类编号为 k 的钥匙。

        接下来则是常规的BFS过程，设计思想为：

  1. 遍历棋盘找到起点位置并入队，队列维护 (x, y, state) 三元组状态【其中 (x,y) 代表当前所在的棋盘位置，state 代表当前的钥匙收集情况】 ，同时统计整个棋盘所包含的钥匙数量 cnt，并使用 数组/哈希表 记录到达每个状态所需要消耗的最小步数 step。
  2. 进行四联通方向的 BFS，转移过程中需要注意【遇到锁时，必须有对应钥匙才能通过】&&【遇到钥匙施，要先更新状态再入队】。
  3. 当BFS过程中遇到 state == (1 << cnt) - 1 时，表明所有钥匙均被收集完成，结束搜索。
  1. class Solution {
  2.     static int N = 35, K = 10, INF = 0x3f3f3f3f;
  3.     static int[][][] dist = new int[N][N][1 << K]; //动态规划表，存储每个位置的每一种收集状态所需的最小步长
  4.     static int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; //方向数组
  5.  
  6.     public int shortestPathAllKeys(String[] grid) {
  7.         int n = grid.length, m = grid[0].length(), cnt = 0;
  8.         Deque<int[]> d = new ArrayDeque<>();
  9.         for(int i = 0; i < n; i++) {
  10.             for(int j = 0; j < m; j++) {
  11.                 Arrays.fill(dist[i][j], INF);
  12.                 char c = grid[i].charAt(j);
  13.                 if(c == '@') {
  14.                     d.addLast(new int[]{i, j, 0});
  15.                     dist[i][j][0] = 0;
  16.                 } else if(c >= 'a' && c <= 'z') cnt++;
  17.             }
  18.         }
  19.         while(!d.isEmpty()) {
  20.             int[] info = d.pollFirst();
  21.             int x = info[0], y = info[1], cur = info[2], step = dist[x][y][cur];
  22.             for(int[] di : dirs) {
  23.                 int nx = x + di[0], ny = y + di[1];
  24.                 if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  25.                 char c = grid[nx].charAt(ny);
  26.                 if(c == '#') continue;
  27.                 //如果走到锁处，检测是否持有种类编号相对应的钥匙
  28.                 if((c >= 'A' && c <= 'Z') && (cur >> (c - 'A') & 1) == 0) continue;
  29.                 int ncur = cur;
  30.                 //如果走到钥匙处，更新钥匙收集状态
  31.                 if(c >= 'a' && c <= 'z') ncur |= 1 << (c - 'a');
  32.                 if(ncur == (1 << cnt) - 1) return step + 1;
  33.                 //如果不能更新动态规划表存储的最小步长，则此状态作废
  34.                 if(step + 1 >= dist[nx][ny][ncur]) continue;
  35.                 dist[nx][ny][ncur] = step + 1;
  36.                 d.addLast(new int[]{nx, ny, ncur});
  37.             }
  38.         }
  39.         return -1;
  40.     }
  41. }
  42. 作者：宫水三叶

LeetCode1036.逃离大迷宫：

问题描述：

在一个 10^6 x 10^6 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [s_{x}, s_{y}] 开始出发，意图赶往目标方格 target = [t_{x}, t_{y}] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [x_{i}, y_{i}] 表示坐标为 (x_{i}, y_{i}) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

示例 1：

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。

提示：

  • 0 <= blocked.length <= 200
  • blocked[i].length == 2
  • 0 <= x_{i}, y_{i} < 10^6
  • source.length == target.length == 2
  • 0 <= s_{x}, s_{y}, t_{x}, t_{y} < 10^6
  • source != target
  • 题目数据保证 source 和 target 不在封锁列表内

代码分析：

BFS+给定障碍物所能围成的最大面积：

        整理题意为：在一个足够大的空间里，有少数的障碍物，求两点是否连通。

        当两点相隔较远时，常规BFS做法可能会搜完整个棋盘（大小为10^6 * 10^6），导致TLE。

        考虑什么情况下两点之间会不连通？两点中的任意一点被障碍物围住时！这个应该没啥疑问。

        一个较容易想到的思路是：从 source 跑一遍BFS，然后从 target 跑一遍BFS，同时设定一个最大访问点数量 MAX。若从两者出发能够访问的点数量都能超过 MAX，说明两点均未被困住，最终必然连通。

        考虑如何确定 MAX 的取值范围？直观感受上 MAX 应该是与 blocked 大小相关的数，但我们还是考虑从单秒计算量上界进行反推，两边BFS的复杂度均为O(max)，因此直接设置 MAX = 1e5 比较合理。

        更小的 MAX 需要证明：在给定数量障碍物的前提下，障碍物所能围成的最大面积为多少。我们直接给出提示：任何一条封闭图形的直边都可以通过调整为斜边来围成更大的面积：

        我们可以得出结论：组成封闭图形的边不可能有直边，同时由于是封闭图形，斜边必然是单点衔接（不可能为平行，因为无法封闭）。同时，想要达到最大面积，应当尽可能利用边界作为围成图形的某些边。

        为了方便计算，我们可以把【利用边界所能围成的最大封闭图形】的形状强行转变为【由边界提供两边，障碍物提供一边的三角形】（如何强行转变？如果是其他图形，我们可以通过修改障碍物的直边成为一条完整的斜边，来组成封闭三角形，并且能确保围成的面积不变。）

        在给定 blocked 数组大小的情况下，根据【等差数列求和】可知，最大所能围成的面积为1+2+...+n-1=\frac{n*(n-1)}{2}。

        因此从 source 和 target 出发，能够访问的点数超过\frac{n*(n-1)}{2}个，那么两点并没有被围住，必然连通。

        编码方面，为了在BFS过程中记录某些点被访问过，可以通过计算某个位置哈希值来实现。

  1. class Solution {
  2.     int EDGE = (int)1e6, MAX = (int)1e5; //边界大小 最大访问节点数量
  3.     long BASE = 131L; //哈希算子
  4.     Set<Long> set = new HashSet<>();
  5.     int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
  6.  
  7.     public boolean isEscapePossible(int[][] blocked, int[] s, int[] t) {
  8.         for (int[] p : blocked) set.add(p[0] * BASE + p[1]); //障碍物坐标转化为一维数字放入集合
  9.         int n = blocked.length;
  10.         MAX = n * (n - 1) / 2; //可直接使用 1e5
  11.         return check(s, t) && check(t, s); //从目标节点和起始节点双向BFS
  12.     }
  13.  
  14.     boolean check(int[] a, int[] b) { //a代表起始点坐标，b代表目标点坐标
  15.         Set<Long> vis = new HashSet<>(); //判断点是否访问过
  16.         Deque<int[]> d = new ArrayDeque<>();
  17.         d.addLast(a);
  18.         vis.add(a[0] * BASE + a[1]);
  19.         while (!d.isEmpty() && vis.size() <= MAX) {
  20.             int[] poll = d.pollFirst();
  21.             int x = poll[0], y = poll[1];
  22.             if (x == b[0] && y == b[1]) return true;
  23.             for (int[] di : dir) {
  24.                 int nx = x + di[0], ny = y + di[1];
  25.                 if (nx < 0 || nx >= EDGE || ny < 0 || ny >= EDGE) continue;
  26.                 long hash = nx * BASE + ny;
  27.                 if (set.contains(hash)) continue;
  28.                 if (vis.contains(hash)) continue;
  29.                 d.addLast(new int[]{nx, ny});
  30.                 vis.add(hash);
  31.             }
  32.         }
  33.         return vis.size() > MAX;
  34.     }
  35. }
  36. 作者：宫水三叶

        时间复杂度：令 n 为blocked 数组大小，两次BFS的最大访问点数为\frac{n*(n-1)}{2}。整体复杂度为O(n^2)。

离散化+BFS（难）：

        利用障碍物最多只有200个，可以对大棋盘进行离散化，再进行常规的BFS。即我们可以将棋盘【压缩】成一个规模较小的但等价的新网格。

        我们以棋盘的每一行为例，可以发现，不同的行坐标只有：

  • 障碍所在的行，最多有n个；
  • source和target所在的行，最多有2个；
  • 网格的上下边界（即-1和10^6），有2个。

        因此不同的行坐标最多只有 n+4 个，可以考虑对行坐标进行离散化，具体规则如下：

我们将行坐标进行升序排序；

  • 将上边界离散化为 −1。上边界是排序后的第 0 个行坐标；
  • 如果排序后的第 i 个行坐标与第 i−1 个行坐标相同，那么它们离散化之后的值也相同；
  • 如果排序后的第 i 个行坐标与第 i−1 个行坐标相差 1，那么它们离散化之后的值也相差 1；
  • 如果排序后的第 i 个行坐标与第 i−1 个行坐标相差超过 1，那么它们离散化之后的值相差 2。

        这样的正确性在于：在离散化前，若两个行坐标本身相邻，那么离散后其也必须相邻；若其本身不相邻，则可以把它们之间间隔的若干行直接【压缩】成一行，即行坐标相差2。

        对于列坐标的离散化方法也是如此。在离散化完成之后，新的网格规模不会超过 2(n+4) * 2(n+4)，进行广度优先搜索需要的时间是可接受的。

  1. class Solution {
  2.     int N = 500, EDGE = (int)1e6;
  3.     boolean[][] vis = new boolean[N][N];
  4.     boolean[][] block = new boolean[N][N];
  5.     public boolean isEscapePossible(int[][] blocked, int[] s, int[] t) {
  6.         List<int[]> list = new ArrayList<>();
  7.         list.add(new int[]{-1, -1, 0});
  8.         list.add(new int[]{EDGE, EDGE, 0});
  9.         for (int[] p : blocked) list.add(new int[]{p[0], p[1], 0});
  10.         list.add(new int[]{s[0], s[1], 1});
  11.         list.add(new int[]{t[0], t[1], 2});
  12.         Collections.sort(list, (a,b)->a[0]-b[0]);
  13.         int n = list.size();
  14.         for (int i = 0, idx = 1; i < n; ) {
  15.             int j = i, cur = list.get(i)[0];
  16.             while (j < n && cur == list.get(j)[0]) j++;
  17.             for (int k = i; k < j; k++) list.get(k)[0] = idx;
  18.             if (j < n && list.get(j)[0] - cur == 1) idx++;
  19.             else idx += 2;
  20.             i = j;
  21.         }
  22.         Collections.sort(list, (a,b)->a[1]-b[1]);
  23.         for (int i = 0, idx = 1; i < n; ) {
  24.             int j = i, cur = list.get(i)[1];
  25.             while (j < n && cur == list.get(j)[1]) j++;
  26.             for (int k = i; k < j; k++) list.get(k)[1] = idx;
  27.             if (j < n && list.get(j)[1] - cur == 1) idx++;
  28.             else idx += 2;
  29.             i = j;
  30.         }
  31.         int mr = 0, mc = 0;
  32.         int a = 0, b = 0, c = 0, d = 0;
  33.         for (int[] info : list) {
  34.             int x = info[0], y = info[1], state = info[2];
  35.             if (state == 1) {
  36.                 a = x; b = y;
  37.             } else if (state == 2) {
  38.                 c = x; d = y;
  39.             } else {
  40.                 block[x][y] = true;
  41.             }
  42.             mr = Math.max(mr, x);
  43.             mc = Math.max(mc, y);
  44.         }
  45.         int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
  46.         Deque<int[]> de = new ArrayDeque<>();
  47.         de.addLast(new int[]{a, b});
  48.         vis[a][b] = true;
  49.         while (!de.isEmpty()) {
  50.             int[] poll = de.pollFirst();
  51.             int x = poll[0], y = poll[1];
  52.             if (x == c && y == d) return true;
  53.             for (int[] di : dir) {
  54.                 int nx = x + di[0], ny = y + di[1];
  55.                 if (nx <= 1 || nx >= mr || ny <= 1 || ny >= mc) continue;
  56.                 if (vis[nx][ny] || block[nx][ny]) continue;
  57.                 de.addLast(new int[]{nx, ny});
  58.                 vis[nx][ny] = true;
  59.             }
  60.         }
  61.         return false;
  62.     }
  63. }
  64. 作者：宫水三叶

        时空复杂度同上。

LeetCode1345.跳跃游戏IV：

问题描述：

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

  • i + 1 需满足：i + 1 < arr.length
  • i - 1 需满足：i - 1 >= 0
  • j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

提示：

  • 1 <= arr.length <= 5 * 10^4
  • -10^8 <= arr[i] <= 10^8

代码分析：

        记数组 arr 的长度为 n。根据题目描述，该数组可以抽象成一个无向无权图，数组元素为图的顶点，相邻下标元素之间有一条无向边相连，所有的值相同元素之间也有无向边相连。求“从第一个元素到最后一个元素的最少操作数”即求“从第一个元素到最后一个元素的最短路径长度”。最短路问题可以用BFS求解，时间复杂度为 O(V+E)，其中 V 为图的顶点数，E 为图的边数。

        在此题中，V = n，E 可达到 O(n^2) 数量级，按照常规方法使用广搜会超时。超时的主要原因是所有的值相同元素构成了一个稠密子图，普通的广搜会对这个稠密子图中的所有边都访问一次。但对于无权图的最短路问题，这样的访问时不必要的。

  • 在第一次访问到这个子图中的某个节点时，即会将这个子图的所有其他未在队列中的节点都放入队列。
  • 在第二次访问到这个子图中的节点时，就不需要去考虑这个子图中的其他节点了，因为所有其他节点都已经在队列中或者已经被访问过了。
  • 因此解题时，先需要找出所有的值相同的子图，用一个哈希表保存。在第一次把这个子图的所有节点放入队列后，把该子图清空，就不会重复访问该子图的其他边了。 

单向BFS：

        为了方便，我们记跳跃规则为【前后跳】和【等值跳】。为了方便【等值跳】，我们使用哈希表记录某个值有哪些下标。

        进行BFS时，若当前走到的位置为 t，可以将 t-1、t+1 和与 arr[t] 等值的位置进行入队。为防止重复入队，可以用 dist 数组记录到达某个位置的最小步数（初始化为 INF），只有 dist[ne] 为 INF 时，该点没有被遍历过，可以入队并更新最小步数。

        但使用 dist 并不能确保时间复杂度O(n)，因为每次都需要遍历与 arr[t] 等值的下标，为确保等值下标的遍历只会发生一次，需要在将等值下标添加到队列后，将 arr[t] 从哈希表中移除。

        接下来对上文移除的正确性加以证明：

  1. class Solution {
  2.     int INF = 0x3f3f3f3f;
  3.     public int minJumps(int[] arr) {
  4.         int n = arr.length;
  5.         //创建等值下标表
  6.         Map<Integer, List<Integer>> map = new HashMap<>();
  7.         //倒序插入list（给deque增加一个同层【下标越大，优先出队】的作用）
  8.         for(int i = n - 1; i >= 0; i--) {
  9.             List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
  10.             list.add(i);
  11.             map.put(arr[i], list); 
  12.         }
  13.         //记录到达某位置的最小步数
  14.         int[] dist = new int[n];
  15.         Arrays.fill(dist, INF);
  16.  
  17.         Deque<Integer> d = new ArrayDeque<>();
  18.         d.addLast(0);
  19.         dist[0] = 0;
  20.         while(!d.isEmpty()) {
  21.             //将t-1,t+1,arr[t]等值点的位置入队
  22.             int t = d.pollFirst(), step = dist[t];
  23.             if(t == n - 1) return step;
  24.             if(t + 1 < n && dist[t + 1] == INF) {
  25.                 d.addLast(t + 1);
  26.                 dist[t + 1] = step + 1;
  27.             }
  28.             if(t - 1 >= 0 && dist[t - 1] == INF) {
  29.                 d.addLast(t - 1);
  30.                 dist[t - 1] = step + 1;
  31.             }
  32.             List<Integer> list = map.getOrDefault(arr[t], new ArrayList<>());
  33.             for(int ne : list) {
  34.                 if(dist[ne] == INF) {
  35.                     d.addLast(ne);
  36.                     dist[ne] = step + 1;
  37.                 }
  38.             }
  39.             //别忘记首次添加所有与arr[t]等值的点后就立刻要清空当前下标的等值表
  40.             map.remove(arr[t]);
  41.         }
  42.         return -1;
  43.     }
  44. }
  45. 作者：宫水三叶

双向BFS：

        双向BFS能够解决搜索空间爆炸问题，因此本方法可以不进行哈希表的 remove 操作，在测试案例不严格的情况下也可以通过（但如果为了确保O(n)，还是需要 remove 的）。

  1. class Solution {
  2.     int[] arr;
  3.     int INF = 0x3f3f3f3f;
  4.     int n;
  5.     Map<Integer, List<Integer>> map = new HashMap<>();
  6.     public int minJumps(int[] _arr) {
  7.         arr = _arr;
  8.         n = arr.length;
  9.         if(n == 1) return 0;
  10.         for(int i = n - 1; i >= 0; i--) {
  11.             List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
  12.             list.add(i);
  13.             map.put(arr[i], list); 
  14.         }
  15.         
  16.         Deque<Integer> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
  17.         int[] dist1 = new int[n], dist2 = new int[n];
  18.         Arrays.fill(dist1, INF);
  19.         Arrays.fill(dist2, INF);
  20.         d1.addLast(0);
  21.         dist1[0] = 0; 
  22.         d2.addLast(n - 1);
  23.         dist2[n - 1] = 0;
  24.         while(!d1.isEmpty() && !d2.isEmpty()) {
  25.             //将t-1,t+1,arr[t]等值点的位置入队
  26.             int t = -1;
  27.             if(d1.size() < d2.size()) t = update(d1, d2, dist1, dist2);
  28.             else t = update(d2, d1, dist2, dist1);
  29.             if(t != -1) return t;
  30.         }
  31.         return -1;
  32.     }
  33.  
  34.     int update(Deque<Integer> d1, Deque<Integer> d2, int[] dist1, int[] dist2) {
  35.         int m = d1.size();
  36.         while(m-- > 0) {
  37.             int t = d1.pollFirst(), step = dist1[t];
  38.             if(t + 1 < n) {
  39.                 if(dist2[t + 1] != INF) return step + 1 + dist2[t + 1];
  40.                 if(dist1[t + 1] == INF) {
  41.                     d1.addLast(t + 1);
  42.                     dist1[t + 1] = step + 1;
  43.                 }
  44.             }
  45.             if(t - 1 >= 0) {
  46.                 if(dist2[t - 1] != INF) return step + 1 + dist2[t - 1];
  47.                 if(dist1[t - 1] == INF) {
  48.                     d1.addLast(t - 1);
  49.                     dist1[t - 1] = step + 1;
  50.                 }
  51.             }
  52.             List<Integer> list = map.getOrDefault(arr[t], new ArrayList<>());
  53.             for(int ne : list) {
  54.                 if(dist2[ne] != INF) return step + 1 + dist2[ne];
  55.                 if(dist1[ne] == INF) {
  56.                     d1.addLast(ne);
  57.                     dist1[ne] = step + 1;
  58.                 }
  59.             }
  60.             map.remove(arr[t]);
  61.         } 
  62.         return -1;    
  63.     }
  64. }
  65. 作者：宫水三叶

LeetCode.跳跃游戏专栏：

本系列题目是贪心算法与搜索的经典合集，我们将其单独拎出来

LeetCode55.I：

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 3 * 10^4
  • 0 <= nums[i] <= 10^5

        思路的关键点在于：不一定要明确当前跳几步为最优，而是考虑最大的跳跃步数即跳跃覆盖范围。

        问题便转化为：最终的跳跃覆盖范围能否包含终点。

        贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

  • 下标 i 每次只能在 cover 的范围里移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。
  • cover 每次只取 max （该元素数值补充后的范围即成为 cover 本身范围）且固定左边界而拓展右边界。
  • 如果 cover 大于等于了终点下标， 直接 return true 。
  • 在这里，每层循环中 cover 肯定比下标 i 的增长速率要快得多。把 i 限制在 cover 里是本题的解题关键（体现点之一就是考虑并解决了中间隔断的情况）
  1. class Solution {
  2. public:
  3.     bool canJump(vector<int>& nums) {
  4.         int cover = 0;
  5.         if(nums.size() == 1) return true;
  6.         for(int i = 0; i <= cover; i++) {
  7.             cover = max(i + nums[i], cover);
  8.             if(cover >= nums.size() - 1) return true;
  9.         }
  10.         return false;
  11.     }
  12. };

LeetCode45.II：

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i] 
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是2。
从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。

提示:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

        本题题干与上题一致，上题中，若覆盖范围包含了终点下标，就立刻停止模拟并返回布尔结果即可；本题进行了升级，有效和无效点位对计数是有影响的，关键是计数的时机。

        本题贪心思路：

  • 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。我们可以对每一个能作为 起跳点 的格子都尝试跳一次（在上题是cover范围内），把 能跳到最远的距离 不断更新（在上题是cover自身）。
  • 如果从这个 起跳点 起跳叫做第 1 次 跳跃，那么从后面 3 个格子起跳 都 可以叫做第 2 次 跳跃（注意此设定，决定了本题计数的时机）。
  • 我们紧接上一点，因此，当上一次跳跃结束时，从下一个格子开始，直到上一次能跳到的最远距离，都是下一次跳跃的起跳点。

  1. class Solution {
  2. public:
  3.     int jump(vector<int>& nums) {
  4.         int ans = 0, start = 0, end = 1;
  5.         //最初版本是约束了当前起跳点范围结束的格子，两层循环复杂度较高
  6.         while(end < nums.size()) {
  7.             int maxPos = 0;
  8.             for(int i = start; i < end; i++) {
  9.                 //能跳到的最远距离
  10.                 maxPos = max(maxPos, i + nums[i]);
  11.             }
  12.             //下一次起跳点开始的格子
  13.             start = end;
  14.             //下一次起跳点结束的格子
  15.             end = maxPos + 1;
  16.             ans++;
  17.         }
  18.         return ans;
  19.     }
  20. };

        我们对这种两层循环的写法进行优化：

  • 事实上，下标 i 是从头跑到尾的。
  • 只需在本次跳跃完成时，更新下一次能跳到的最远距离即可，并以此刻作为更新跳跃次数的时机。（此处为不同于最初版本的贪心算法：为了求最小步数，我们只有当不得不跳时才计数）
  1. class Solution {
  2. public:
  3.     int jump(vector<int>& nums) {
  4.         //end为当前能跳跃到的位置的边界下标，maxPos为在边界范围内能跳跃到的最远位置下标
  5.         int ans = 0, end = 0, maxPos = 0;
  6.         for(int i = 0; i < nums.size() - 1; i++) {
  7.             //继续往下遍历，统计边界范围内，哪一格能跳得更远，每走一步就更新一次能跳跃的最远位置下标
  8.             //实际上在统计下一步的最优情况
  9.             maxPos = max(maxPos, i + nums[i]);
  10.             //如果到达边界就一定要跳跃，下一跳的边界下标为之前求出的最佳情况maxPos
  11.             if(i == end) {
  12.                 end = maxPos;
  13.                 ans++;
  14.             }
  15.         }    
  16.         return ans;
  17.     }
  18. };

 LeetCode1306.III：

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。

注意，不管是什么情况下，你都无法跳到数组之外。

示例 1：

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3

提示：

  • 1 <= arr.length <= 5 * 10^4
  • 0 <= arr[i] < arr.length
  • 0 <= start < arr.length

广搜：

        本题与贪心算法关系不大，但是有了之前题目的铺垫，我们可以将细节部分的思路应用于本题。我们可以用广搜得到从 start 开始能够到达的所有位置。如果其中正好有我们所需要的点就return true。

DFS转换为二叉树：

        可以抽象为一棵二叉树，左右孩子分别对应当前位置往左跳和往右跳的数组中对应的元素。深搜前需要划清楚边界条件，由于无法跳到数组之外，i < 0 || i >= arr.szie()。同时，若已经遍历过该节点，那么它的左右孩子节点一定被遍历过，因此构建 used 数组来记录重复情况，具体见代码。

  1. class Solution {
  2. public:
  3.     bool canReach(vector<int>& arr, int start) {
  4.         vector<bool> used(arr.size(), false);
  5.         return binary(arr, start, used);
  6.     }
  7.  
  8.     bool binary(vector<int> & arr, int i, vector<bool> &used) {
  9.         if(i < 0 || i >= arr.size() || used[i]) return false;
  10.         if(arr[i] == 0) return true;
  11.         used[i] = true;
  12.         return binary(arr, i + arr[i], used) || binary(arr, i - arr[i], used);
  13.     } 
  14. };

LeetCode1340.V：

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

  • i + x ，其中 i + x < arr.length 且 0 < x <= d 。
  • i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

示例 1：

输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。

提示：

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 10^5
  • 1 <= d <= arr.length

        本题和图论有关的是构造有向无环图+拓扑排序解，这种方法我们等会再讨论。标准做法是从高到低的记忆化搜索或是从低到高的动态规划。

递归：

        先贴一下 Ikaruga 的递归解法。

        分析题目：

  • 只能往左右两个方向跳并且只能往低的格子上跳，并且跳过去的部分不能比起跳点高。
  • 可以从任意点开始跳，但不能跳到外边。

        开始递归：

  • 若当前高度比起跳点高，就结束；若可以跳，就挨着跳。
  • 起跳点的 可跳跃次数 是所有能跳到的点的 最大可跳跃次数 + 1。
  • 递归进入这个点，计算它的 可跳跃次数。
  • 如果左右两边都没有可以继续跳的点，那么这个点的 可跳跃次数 为 0（递归出口）。
  • 使用 vector<int> &steps 记忆化已经确定的 可跳跃次数，并使用 ans 保存最大的结果。
  1. class Solution {
  2. public:
  3.     //函数的重载
  4.     void maxJumps(vector<int> &arr, int d, int cur, vector<int> &steps, int &ans) {
  5.         if(steps[cur] != -1) return;
  6.         //确定左右边界
  7.         int l = max(0, cur - d);
  8.         int r = min((int)arr.size() - 1, cur + d);
  9.         
  10.         //计算起跳点能到达的所有点的最大可跳跃次数
  11.         int step = 0;
  12.         for(int direction = -1; direction <= 1; direction += 2) { //控制方向
  13.             for(int i = cur + direction; i <= r && i >= l; i += direction) { //一直朝某个方向
  14.                 if(arr[cur] <= arr[i]) break; //高度超过就结束，如果可以跳就挨着跳
  15.                 //递归进入该点,出来的时候step已经为计算好的可跳跃次数
  16.                 maxJumps(arr, d, i, steps, ans);
  17.                 step = max(step, steps[i]);
  18.             }
  19.         }
  20.         //最终要回到起跳点
  21.         steps[cur] = step + 1;
  22.         ans = max(ans, steps[cur]);
  23.     }
  24.  
  25.     int maxJumps(vector<int>& arr, int d) {
  26.         vector<int> steps(arr.size(), -1);
  27.         int ans = 0;
  28.         for(int i = 0; i < arr.size(); i++) {
  29.             maxJumps(arr, d, i, steps, ans);
  30.         }
  31.         return ans;
  32.     }
  33. };

记忆化搜索：

        记忆化搜索以深搜为基础，在第一次搜索到某个状态时，会将该状态与其对应的值存储下来，这样在接下来的搜索中，如果搜到相同的状态就直接拿来用即可。

        因此，记搜和动态规划十分相似，大部分题目若能用动规则一定可以用记搜解决，反之亦然。因为记搜和动规均要求搜索状态满足拓扑序（即不会出现环）。不然无法进行状态转移。

        本题中，用 dp[i] 表示从位置 i 开始跳跃，最多可以访问的下标个数。可以写出如下的状态转移方程：

dp[i] = max(dp[j]) + 1

        其中 j 需要满足三个条件：

  • 0 <= j < arr.length，即 j 必须在数组 arr 的范围内；
  • i - d <= j <= i + d，即 j 到 i 的距离不能超过给定的 d；
  • 从 arr[j] 到 arr[i] 的这些元素除了 arr[i] 本身之外，都必须小于 arr[i]，这是题目中的要求。

        对于任意的位置 i，根据第二个条件，我们只需要在其左右两侧最多扫描 d 个元素，就可以找出所有满足条件的位置 j。随后我们通过这些 j 的 dp 值对位置 i 进行状态转移，就可以得到 dp[i] 的值。

        如何保证在处理到位置 i 时，所有满足条件的位置 j 都已经被处理过了呢？如果用常规的动态规划方法（例如根据位置从小到大或者从大到小进行动态规划），并不能保证这一点，因为 j 分布在位置 i 的两侧。采用记忆化搜索：当我们需要 dp[j] 的值时，如果我们之前已经计算过，就直接返回这个值（记忆）；如果我们之前没有计算过，就先将 dp[i] 搁在一边，转而去计算 dp[j]（搜索），当 dp[j] 计算完成后，再用其对 dp[i] 进行状态转移。

        记忆化搜索一定能在有限时间内停止吗？如果不能在有限时间内停止，则说明出现了环，即假若需要计算dp[i]，最终直到某次搜索时发现当前dp值]需要循环依赖dp[i]，则出现了环。但是根据本题条件三：arr[j] 一定小于 arr[i]，即搜索每深入一层，就跳到了高度更小的位置，因此不存在环！因此记搜可以与常规动态规划有相同的时间复杂度。

  1. class Solution {
  2. private:
  3.     vector<int> f;    
  4. public:
  5.     void dfs(vector<int> &arr, int id, int d, int n) {
  6.         if(f[id] != -1) return;
  7.         f[id] = 1;
  8.         for(int i = id - 1; i >= 0 && id - i <= d && arr[id] > arr[i]; --i) { //三条件
  9.             dfs(arr, i, d, n);
  10.             f[id] = max(f[id], f[i] + 1);
  11.         }
  12.         for(int i = id + 1; i < n && i - id <= d && arr[id] > arr[i]; ++i) { //三条件
  13.             dfs(arr, i, d, n);
  14.             f[id] = max(f[id], f[i] + 1);
  15.         }
  16.     }
  17.  
  18.     int maxJumps(vector<int>& arr, int d) {
  19.         int n = arr.size();
  20.         f.resize(n, -1);
  21.         for(int i = 0; i < n; i++) {
  22.             dfs(arr, i, d, n);
  23.         }
  24.         return *max_element(f.begin(), f.end());
  25.     }
  26. };
        时间复杂度为O(nd)，n为arr数组长度。

LeetCode1696.VI：

给你一个下标从 0 开始的整数数组 nums 和一个整数 k。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [ i + 1, min(n - 1, i + k) ] 包含两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n-1），你的得分为经过的所有数字之和。

请你返回你能得到的最大得分。

示例 1：

输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。

提示：

  •  1 <= nums.length, k <= 10^5
  • -10^4 <= nums[i] <= 10^4

动态规划+优先队列优化：

        可以用 f[i] 表示从下标 0 跳到下标 i 的最大得分，有如下状态转移方程：

f[i]=max(f[j])_{max(0, i-k)\leqslant j< i}+nums[i]

        即是考虑从下标 j 跳到下标 i 的，那么 j 与 i 的间隔不能超过 k，即 i−k ≤ j；并且 j 不能超过边界，即 j ≥ 0。

        边界条件为 f[0] = nums[0]，最终答案即为 f[n-1]。

        以上时间复杂度为O(n*k)，会超出时间限制，因此需要优化。

        由于我们要最大化 f[j]，因此可以使用优先队列（堆）维护所有的 (f[j], j) 二元组，这样优先队列的堆顶元素就是我们的最优转移。同时需要注意的是，对于当前的 i，优先队列中的最大值的 j 可能已经不满足 max(0, i - k) ≤ j ≤ i 的限制，并且随着 i 的增加，原本不满足限制的 j 仍然是不满足限制的。因此堆顶元素一旦不满足限制，我们就可以把它永久从堆中移除。

        我们也可以使用平衡树代替优先队列，时间复杂度不变。

  1. class Solution {
  2. public:
  3.     int maxResult(vector<int>& nums, int k) {
  4.         int n = nums.size();
  5.         //优先队列中的二元组即为 (f[j], j)
  6.         priority_queue<pair<int, int>> q;
  7.         q.emplace(nums[0], 0);
  8.         int ans = nums[0];
  9.         for(int i = 1; i < n; ++i) {
  10.             //堆顶的 j 不满足限制
  11.             while(i - q.top().second > k) q.pop();
  12.             ans = q.top().first + nums[i];
  13.             q.emplace(ans, i);
  14.         }
  15.         return ans;
  16.     }
  17. };

        时间复杂度：O(n * logn)。

动态规划+单调队列：

        也可以使用单调队列对状态转移方程进行优化。

        对于 j1​ < j2​，如果 f[j1] ≤ f[j2]，那么在 i > j2​ 之后，j1​ 将永远不可能作为状态转移方程中最优的 j。这是因为 f[j2] 不劣于 f[j1]，并且 j2​ 的下标更大，满足限制的最远位置也大于 j1​，因此无论什么时候从 j1 转移都不会比从 j2​ 转移要优，因此我们可以将 j​1 从候选的 j 值集合中永远的移除。

        基于这个思路，我们可以使用一个【严格单调递减】的队列存储所有的候选 j 值集合，这里【严格单调递减】的意思是：从队首到队尾的所有 j 值，它们的下标严格单调递增，而对应的 f[j] 值严格单调递减。这样一来，当我们枚举到 i 时，队首的 j 就是我们的最优转移。与优先队列类似，此时队首的 j 可能已经不满足限制，因此我们需要不断弹出队首元素，直到其满足限制为止。在转移完成之后，i 就是候选的 j 值，因此我们将 i 加入队尾，并且不断弹出弹出队尾元素直到队列为空或者队尾的 j 值满足 f[j] > f[i]。

  1. class Solution {
  2. public:
  3.     int maxResult(vector<int>& nums, int k) {
  4.         int n = nums.size();
  5.         //单调队列中的二元组即为 (f[j], j)
  6.         deque<pair<int, int>> q;
  7.         q.emplace_back(nums[0], 0);
  8.         int ans = nums[0];
  9.         for(int i = 1; i < n; ++i) {
  10.             //队首的 j 不满足限制
  11.             while(i - q.front().second > k) q.pop_front();
  12.             ans = q.front().first + nums[i];
  13.             //队尾的 j 不满足单调性
  14.             while(!q.empty() && ans >= q.back().first) q.pop_back();
  15.             q.emplace_back(ans, i);
  16.         }
  17.         return ans;
  18.     }
  19. };

        时间复杂度为O(n)。

LeetCode1871.VII：

给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump。一开始，你在下标 0 处，且该位置的值一定为 ‘0’。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：

  • i + minJump <= j <= min(i + maxJump, s.length - 1)，并且 s[j] == '0'。

如果你可以到达 s 的下标 s.length - 1 处，请你返回 true，否则返回 false。

        正常的暴力思路，从当前位置起点 i = 0 开始，每次都将接下来 [i + minJump, i + maxJump] （并且 s 中为 ‘0’）的位置标记为【可以跳跃到】，接着依次以新拓展的点为起点，继续向后跳跃，重复上述......

方法一：BFS+剪枝

        暴力的根本在于，每次跳跃都需要 O(maxJump-minJump) 的时间遍历。

        事实上，有很多点已经尝试更新过了。

        因此需要记录已经更新到的位置，并且只需要修改左边界即可。

  1. class Solution {
  2.     public boolean canReach(String s, int minJump, int maxJump) {
  3.         if(s.charAt(s.length() - 1) == '1') return false;
  4.         LinkedList<Integer> queue = new LinkedList<>();
  5.         queue.addLast(0);
  6.         int pos = 0;
  7.         while(queue.size() > 0) {
  8.             int min = Math.max(pos, queue.peekLast() + 1);
  9.             int cur = queue.removeFirst();
  10.             int max = Math.min(cur + maxJump, s.length() - 1);
  11.             min = Math.max(cur + minJump, min);
  12.             for(int i = min; i <= max; i++) {
  13.                 if(s.charAt(i) == '0') {
  14.                     if(i == s.length() - 1) return true;
  15.                     queue.addLast(i); 
  16.                 }
  17.             }
  18.             pos = max + 1;
  19.         }
  20.         return false;
  21.     }
  22. }

        要注意领会 min 取初值时 max(pos, queue.peekLast() + 1) 和后期取 max(cur + minJump, min) 的作用。若不是很好理解，看一下接下来的版本：

  1. class Solution {
  2.     public boolean canReach(String s, int minJump, int maxJump) {
  3.         Queue<Integer> q = new ArrayDeque<>();
  4.         q.add(0); 
  5.         // position：当前跳跃开始的位置
  6.         int position = 0;
  7.         while (!q.isEmpty()) {
  8.             int i = q.poll();
  9.             int left = Math.max(i + minJump, position + 1);
  10.             int right = Math.min(i + maxJump, s.length() - 1);
  11.             for (int j = left; j <= right; j++) {
  12.                 if (s.charAt(j) == '0'){
  13.                     q.add(j);
  14.                     if (j == s.length() - 1) {
  15.                         return true; 
  16.                     }
  17.                 }
  18.             }
  19.             // 更新下一次跳跃开始的位置
  20.             position = i + maxJump;
  21.         }
  22.         return false;
  23.     }
  24. }

方法二：动态规划+前缀和优化

        用 f(i) 表示能否从位置 0 按照给定的规则跳到位置 i。

        如果 s[i] 为 1，我们无法跳到位置 i，此时 f(i)=false。

        如果 s[i] 为 0，我们可以枚举位置 j，表示最后一步是从位置 j 跳到位置 i 的。位置 j 需要满足 j∈[i−maxJump,i−minJump] 并且 j≥0，只要存在一个 j 满足 f(j)=true，那么 f(i) 就为 true。因此我们可以写出状态转移方程：

f(i)=any(f(j)), j\in (i-maxJump,i-minJump),j\geqslant 0

        若字符串 s 的长度为 n，按照上述状态转移方程进行动态规划后，最终的答案即为 f(n - 1)。

        而该方程的转移时间为 O(n)，动态规划的总时间复杂度为 O(n^2)，TLE，需要优化。

        为了方便，用 left_{i} 和 right_{i} 表示位置 i 在状态转移中所对应 j 的区间。在大部分情况下，有：

\left [ left_{i}, right_{i} \right ]=\left [ i-maxJump, i-minJump \right ]

        但由于有 j ≥ 0 的限制，需要对该区间进行一些处理，具体的处理方法参考代码部分。

        根据前情提示，f(i) 的值为 true，当且仅当 s[i] 为 0，并且区间 \left [ left_{i}, right_{i} \right ] 中存在一个位置作为下标对应的 f 值也为 true。若将 true 视为 1，false 视为 0，则其等价为：

  • f(i) 的值为 true，当且仅当 s[i] 为 0，并且 \sum_{j=left_{i}}^{right_{i}}f(j)的值不为0。

        由于\sum_{j=left_{i}}^{right_{i}}f(j)是数组 f 的一段连续区间的求和，因此我们可以在动态规划的同时维护数组 f 的前缀和数组 pre，其中：

pre(i)=\sum_{j=0}^{i}f(i)

        这样就可以通过：

\sum_{j=left_{i}}^{right_{i}}f(j)=pre(right_{i})-pre(left_{i}-1)

        在 O(1) 的时间快速进行状态转移了，使得动态规划的总时间减少为 O(n)。这里同样需要处理 left_{i} ≤ 0 的情况，具体参考代码。

        细节如下：

        动态规划的边界条件为 f(0)=true。在进行状态转移时，可以从 i=minJump 开始，保证 right_{i} ≥ 0，这样就只需特殊处理 left_{i}。

  1. class Solution {
  2. public:
  3.     bool canReach(string s, int minJump, int maxJump) {
  4.         int n = s.size();
  5.         vector<int> f(n), pre(n);
  6.         f[0] = 1;
  7.         //由于从 i = minJump 开始动态规划，因此需将 [0, minJump] 部分的前缀和预处理出来
  8.         for(int i = 0; i < minJump; ++i) {
  9.             pre[i] = 1;
  10.         }
  11.         for(int i = minJump; i < n; ++i) {
  12.             int left = i - maxJump, right = i - minJump;
  13.             if(s[i] == '0') {
  14.                 int total = pre[right] - (left <= 0 ? 0 : pre[left - 1]);
  15.                 f[i] = (total != 0);
  16.             }
  17.             pre[i] = pre[i - 1] + f[i];
  18.         }
  19.         return f[n - 1];
  20.     }
  21. };

        时间复杂度：O(n)，n 为字符串 s 的长度。

完结......（90000字）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/434002
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号