DFS
深度优先搜索（ Depth First Search）：
一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(n!)。
题目
矩阵中的路径
典型题例：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
示例 ：
matrix= [ ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"] ] str="BCCE" , return "true" str="ASAE" , return "false"
思路
(DFS)O(n23k)
在深度优先搜索中，最重要的就是考虑好搜索顺序。
我们先枚举单词的起点，然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符。
时间复杂度分析:
单词起点一共有n2个，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有三种选择。所以总时间复杂度是O(n23k)。
代码：
class Solution { public: bool hasPath(vector<vector<char>>& matrix, string &str) { //枚举所有的起点 for(int i = 0; i < matrix.size(); i ++) for(int j = 0; j < matrix[i].size(); j ++) if(dfs(matrix, str, 0, i, j)) //从第零个字符位置开始枚举，当前起点为i, j return true; return false; } //u->当前枚举路径的长度，x,y为当前枚举路径的终点 bool dfs(vector<vector<char>> &matrix, string &str, int u, int x, int y){ if(matrix[x][y] != str[u]) return false; //矩阵x ,y位置与当前字符串枚举位置不同 //在满足当前枚举字符与矩阵位置字符匹配，且当前位置为最后一个字符时为ture if(u == str.size() - 1) return true; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //定义四个方向左上右下 char t = matrix[x][y]; matrix[x][y] = '*'; //过程中需要将已经使用过的字母改成一个特殊字母 for(int i = 0; i < 4; i ++){ int a = x + dx[i], b = y + dy[i]; if(a >= 0 && a <matrix.size() && b >= 0 && b < matrix[a].size()){ if(dfs(matrix, str, u + 1, a, b)) return true; } } matrix[x][y] = t; //回溯现场 return false; } };
数字排列
典型题例：
输入一组数字（可能包含重复数字），输出其所有的排列方式。
示例 ：
输入：[1,2,3] 输出： [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
思路
核心：
( 回 溯 ) O ( n ! ) O ( n ! )
由于有重复元素的存在，这道题的枚举顺序和 Permutations 不同。
- 先将所有数从小到大排序，这样相同的数会排在一起；
- 从左到右依次枚举每个数，每次将它放在一个空位上；
- 对于相同数，我们人为定序，就可以避免重复计算：我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 startstart，我们在枚举当前数时，只枚举start+1，start+2，...，nstart+1，start+2，...，n这些位置。
- 不要忘记递归前和回溯时，对状态进行更新。
时间复杂度分析：
搜索树中最后一层共 n! 个节点，前面所有层加一块的节点数量相比于最后一层节点数是无穷小量，可以忽略。且最后一层节点记录方案的计算量是O(n)O(n)，所以总时间复杂度是O(n×n!)。
代码：
class Solution { public: vector<vector<int>> ans; //定义返回的答案 vector<int> path; // vector<vector<int>> permutation(vector<int>& nums) { path.resize(nums.size()); //重新指定容器的长度为nums.size(); sort(nums.begin(), nums.end()); //对数组进行排序； dfs(nums, 0 , 0, 0); return ans; } void dfs(vector<int> &nums, int u, int start, int state){ if (u == nums.size()){ ans.push_back(path); return; } if (!u || nums[u] != nums[u - 1]) start = 0; for (int i = start; i < nums.size(); i ++) if (!(state >> i & 1)){ path[i] = nums[u]; dfs(nums, u + 1, i + 1, state + (1 << i)); } } };
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
