1图论：
1.1 133. Clone Graph
https://leetcode.com/problems/clone-graph/#/description
思路：这题可以对照拷贝随机链表那道题，首先拷贝图中的节点，然后拷贝每个结点的neighbors数组。
这题使用BFS，所有的BFS都可以看成是queue和unordered_map的组合实现的，该题模拟实现了一个queue，主要是因为后面要判断某个元素是否已经访问，所以使用一个vector来模拟操作，传统的queue会弹出元素，还需要一个vector来辅助，比较麻烦。拷贝节点前要使用一个if(Map.find(cur -> neighbors[i]) == Map.end())，没找到才将元素复制到一个map里面，key是旧节点，value是新节点，记住因为是拷贝，所以新节点必须是new出来的节点，不然指针还是指向原来的元素，出错。后面拷贝neighbor数组的时候也要注意这点，必须将map中的value当成拷贝数组中的元素（这点很重要）。 Map[qNode[j]] -> neighbors.push_back( Map[ qNode[j] -> neighbors[k] ] );
map操作总结：
插入使用insert函数，查找每个元素是否在map里面，使用map.find(),如果没找到就对应的指针指向map.end();
使用下标操作找到对应的value，如果需要找的key不在map里面，就会自动将可以保存起来，默认初始化，比如map里面没有1，执行下标操作map[1]之后，map里面就会有 1.
insert插入和make_pair组合使用。
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(node == NULL){ return NULL; } vector<UndirectedGraphNode *> qNode; unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> Map; qNode.push_back(node); Map.insert(make_pair(node,new UndirectedGraphNode(node -> label))); int start = 0; //clone nodes while(start < qNode.size()){ UndirectedGraphNode *cur = qNode[start]; for(int i= 0;i < cur -> neighbors.size();++i){ if(Map.find(cur -> neighbors[i]) == Map.end()){ qNode.push_back(cur -> neighbors[i]); Map.insert(make_pair(cur -> neighbors[i], new UndirectedGraphNode(cur -> neighbors[i] -> label))); } } ++start; } // clone neighbors for(int j = 0;j < qNode.size();++j){ for(int k = 0;k < qNode[j] -> neighbors.size();++k){ // UndirectedGraphNode *tmp = new UndirectedGraphNode(qNode[j] -> neighbors[k] -> label); Map[qNode[j]] -> neighbors.push_back(Map[qNode[j] -> neighbors[k]]); } } return Map[node]; } };
1.2 Topological Sorting
http://www.lintcode.com/en/problem/topological-sorting/
思路：三步走：
1）不断统计每个节点的入度，如果节点已经存在map里面，就执行增1操作，如果不在，就创建一个节点
2）找到入度为零的点，记得必须要从neighbor数组里面进行统计，这样才能得到链接关系。
3）不断的删除入度，将删除后入度为零的点加入到结果中，直到队列为空为止
/** * Definition for Directed graph. * struct DirectedGraphNode { * int label; * vector<DirectedGraphNode *> neighbors; * DirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { public: /** * @param graph: A list of Directed graph node * @return: Any topological order for the given graph. */ vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) { // write your code here //统计每个结点的入度 vector<DirectedGraphNode*> result; unordered_map<DirectedGraphNode*,int> Map; for(DirectedGraphNode* node : graph){ for(DirectedGraphNode* neigh : node -> neighbors) if(Map.find(neigh) != Map.end()){ Map[neigh] = Map[neigh] + 1; } else{ Map.insert(make_pair(neigh,1)); } } //找入度为零的节点 queue<DirectedGraphNode*> q; for(DirectedGraphNode* tmp : graph){ if(Map[tmp] == 0){ q.push(tmp); result.push_back(tmp); } } //不断删除入度 while(!q.empty()){ DirectedGraphNode* tmp = q.front(); q.pop(); for(DirectedGraphNode* neigh : tmp -> neighbors){ Map[neigh] = Map[neigh] - 1; if(Map[neigh] == 0){ q.push(neigh); result.push_back(neigh); } } } return result; } };
2.DFS 解决搜索all的问题,只要求所有方案的，肯定是排列组合的搜索问题，搜索问题都是递归求解。
Permutations排列问题的时间复杂度是n!（选第一个有n种情况，第二个有n-1种情况。。。。。）。需要将所有情况都走一遍的程序算法时间复杂度都是n!。
subsets复杂度分析：每个元素有选和不选两种选择，所以是2^n。
2.1 46. Permutations
https://leetcode.com/problems/permutations/#/description
思路：使用helper函数，这里使用一个整数n，递归的时候作为递归基，n = 0的时候，说明每个数都已经排列完了，就可以作为一次排列结果压入result中，for循环是关键，每次交换一次数，调用递归之后，需要将刚才调用的数交换回来。理解时候，可以先不管递归，先理一遍for循环，就可以知道第一个数放置的排列情况。
记住为什么这里是start + 1，而下面的subsets是i + 1？
答：permutations每次都是后面n - 1 个元素的全排列，比如[1,2,3]，第一位是1的时候，求2,3；第一位是2的时候，求1,3；第一位是3的时候，求1,2.
subsets中每次都是固定前面i个元素，求后面i - 1个元素的子集，前面是1的时候，求2,3的子集，前面是1,2的时候，求3的子集，所以是i + 1。
permutation一共运行sz次。
permutation从0开始到end，subsets从i + 1 ~end。
class Solution { public: void helper(vector<vector<int>>& result,vector<int>& nums,int n){ if(n == 0){ result.push_back(nums); } for(int i =0;i <= n;++i){ swap(nums[i],nums[n]); helper(result,nums,n - 1); swap(nums[n],nums[i]); } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> result; if(nums.size() == 0){ return result; } helper(result,nums,nums.size() - 1); return result; } };
2.2 78. Subsets
https://leetcode.com/problems/subsets/#/description
思路：更正不需要先排序。
首先要对数组排序，每次将比前面数大的数字加入到tmp数组里面，然后递归，接下来pop_back还原（pop_back可以将vector最后一个元素删掉）
helper中记住一定是i+1,而不是start + 1;因为在同一个循环当中，start值是不变的，这样就会使得递归次数变多，所以必须是i+1；注意！！start + 1使得循环次数要多很多，所以必须要使用 i + 1;
每个元素可以选也可以不选，时间复杂度是O(2^n)；
class Solution { public: void helper(vector<vector<int>>& result,vector<int>& nums,vector<int>& subset,int start){ result.push_back(subset); for(int i = start;i < nums.size();++i){ subset.push_back(nums[i]); helper(result,nums,subset,i + 1); subset.pop_back(); } } vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; if(nums.size() == 0){ return result; } vector<int> subset; sort(nums.begin(),nums.end()); helper(result,nums,subset,0); return result; } };
2.3 90. Subsets II
https://leetcode.com/problems/subsets-ii/#/description
s思路：1）该题需要一步一步的理清楚，helper(result,nums,tmp,i + 1);//这里记住是i+1,不要写成start+ 1；（因为在同一个循环当中，start值是不变的，这样就会使得递归次数变多，所以必须是i+1；）
2）
if(i != start && nums[i] == nums[i -1]){
continue;
}
对于有重复元素的处理一定需要排序。
去重的方法，有重复元素就跳过，进行下一次循环。举例{1,2,2}的集合一个元素的情况。
class Solution { public: void helper(vector<vector<int>>& result,vector<int>& nums,vector<int>& tmp,int start){ result.push_back(tmp); for(int i = start;i < nums.size();++i){ if(i != start && nums[i] == nums[i -1]){ continue; } tmp.push_back(nums[i]); helper(result,nums,tmp,i + 1);//这里记住是i+1,不要写成start+ 1； cout << i + 1 << " "; tmp.pop_back(); } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> result; if(nums.size() == 0){ return result; } vector<int> tmp; int start = 0; sort(nums.begin(),nums.end()); helper(result,nums,tmp,start); return result; } };
2.4 permutations II
https://leetcode.com/problems/permutations-ii/#/description
思路：综合permutation I和subsets II的去重方法，定义一个visit矩阵，
需要处理的情况是：我们先把Num排序，然后只能连续地选，这样就可以避免生成重复的solution.
例子：1 2 3 4 4 4 5 6 7 8
444这个的选法只能:4, 44, 444连续这三种选法
我们用一个visit的数组来记录哪些是选过的。
if(i != 0 && nums[i] == nums[i - 1] && visit[i - 1] == 0 || visit[i] == 1){ continue; }
i != 0才能保证后面判断 i - 1有效，nums[i] == nums[i - 1]前后两个元素相等才需要进行判断，visit[i - 1] == 0，第i - 1个元素没被访问，必须退出。前面属于一种情况，第二种情况就是
visit[i] == 1，这个时候该元素已经被访问了，就不需要计算，进入下一次循环。
class Solution { public: void helper(vector<vector<int>>& result,vector<int>& nums,vector<int>& tmp,vector<int>& visit){ if(tmp.size() == nums.size()){ result.push_back(tmp); } for(int i = 0;i <= nums.size() - 1;++i){ if(i != 0 && nums[i] == nums[i - 1] && visit[i - 1] == 0 || visit[i] == 1){ continue; } visit[i] = true; tmp.push_back(nums[i]); helper(result,nums,tmp,visit); tmp.pop_back(); visit[i] = false; } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<int> visit(nums.size(),0); vector<vector<int>> result; vector<int> tmp; if(nums.size() == 0){ return result; } sort(nums.begin(),nums.end()); helper(result,nums,tmp,visit); return result; } };
这里深入理解下permutation I 和permutation II，只记第二个有重复元素的版本就可以了
排列组合模板总结
使用范围
● 几乎所有的搜索问题
根据具体题目要求进行改动
● 什么时候输出
● 哪些情况需要跳过
2.5 N Queens N皇后问题
https://leetcode.com/problems/n-queens/#/description
思路：就是看成permutation那道题，求排列，把n个皇后看成n个数，每种排列就是一个皇后放置的方案，比如n = 4，那么vector<int> row{1,2,3,4}这种排列就代表皇后的放置方案中的一种可能结果，row[0] = 1，表示在第0行第1列放置一个皇后，row的大小代表行数。
1）何时将当前排列压入结果中？？
使用一个判断函数isValid函数:这里需要注意为什么rows = cols.size()，不需要减1操作，因为我们进行检查合法性操作的时候，肯定是要新建一行，就是判断下一行是否在column列rows行是否可以插入操作。所以不要rows减1；
bool isValid(vector<int>& cols,int column){//检查当前位置元素是否和已经放置的皇后冲突 int rows = cols.size(); for(int rowIndex = 0;rowIndex < rows;++rowIndex){ if(cols[rowIndex] == column){//列冲突 return false; } if(rowIndex + cols[rowIndex] == rows + column){//当前行已经放置皇后，检查下一行，所以rows不需要减1操作 return false;//left上角 -> right下角对角线冲突 } if(rowIndex - cols[rowIndex] == rows - column){//left下角 -> right上角对角线冲突 return false; } } return true; }
然后再写一个转化结果的字符串函数，使用字符串的append操作。
cols[column]等于放置皇后的那一列，看哪一列等于皇后所在列就置为Q，其他的都是空格。
vector<string> toStr(vector<int>& cols){ vector<string> resultRow; for(int column = 0;column < cols.size();++column){ string s; for(int j = 0;j < cols.size();++j){ j == cols[column] ? s.append("Q") : s.append("."); } resultRow.push_back(s); } return resultRow; }
class Solution { public: vector<string> toStr(vector<int>& cols){ vector<string> resultRow; for(int column = 0;column < cols.size();++column){ string s; for(int j = 0;j < cols.size();++j){ j == cols[column] ? s.append("Q") : s.append("."); } resultRow.push_back(s); } return resultRow; } bool isValid(vector<int>& cols,int column){//检查当前位置元素是否和已经放置的皇后冲突 int rows = cols.size(); for(int rowIndex = 0;rowIndex < rows;++rowIndex){ if(cols[rowIndex] == column){//列冲突 return false; } if(rowIndex + cols[rowIndex] == rows + column){//当前行已经放置皇后，检查下一行，所以rows不需要减1操作 return false;//left上角 -> right下角对角线冲突 } if(rowIndex - cols[rowIndex] == rows - column){//left下角 -> right上角对角线冲突 return false; } } return true; } void helper(vector<vector<string>>& result,vector<int>& cols,int n){ if(n == cols.size()){ result.push_back(toStr(cols)); } for(int column = 0;column < n;++column){ if(!isValid(cols,column)){ continue; } //接下来的push_back是对下一行进行操作放置皇后，新增加一行，新增加一个皇后才需要进行合法性判断 cols.push_back(column); helper(result,cols,n); cols.pop_back(); } } vector<vector<string>> solveNQueens(int n) { vector<vector<string>> result; if(n == 0){ return result; } vector<int> cols; helper(result,cols,n); return result; } };
if(judge(tmp,tmp.size(),vec[i]) == false){ //这里传tmp.size()而不是i，因为要保证是全排列，如果从i开始就得不到全排列，因为每次i都是从i = 0开始，
所以，这次i = 3不符合条件，下次会找到3的防止位置 continue; }
2.6 Palindrome Partitioning
https://leetcode.com/problems/palindrome-partitioning/#/description
将一个字符串拆分为回文子串，求出所有的可能结果。
思路：类比permutation思路，主要两个地方1）string subStr = s.substr(start,i + 1 - start);//start开始的i + 1 - start个元素
2）
if(start == s.size()){//如果是s.size() - 1那么最后一个元素就会丢掉
result.push_back(tmp);
return;
}
这又是一道需要用DFS来解的题目，既然题目要求找到所有可能拆分成回文数的情况，那么肯定是所有的情况都要遍历到，对于每一个子字符串都要分别判断一次是不是回文数，那么肯定有一个判断回文数的子函数，还需要一个DFS函数用来递归，再加上原本的这个函数，总共需要三个函数来求解。代码如下：
class Solution { public: bool isPalindrome(string s){ int i = 0,j = s.size() - 1; for(i,j;i < j;++i,--j){ if(s[i] != s[j]){ return false; } } return true; } void helper(vector<vector<string>>& result,string s,vector<string>& tmp,int start){ if(start == s.size()){//如果是s.size() - 1那么最后一个元素就会丢掉 result.push_back(tmp); return; } for(int i = start;i <= s.size() - 1;++i){ string subStr = s.substr(start,i + 1 - start);//start开始的i + 1 - start个元素 if(!isPalindrome(subStr)){ continue; } tmp.push_back(subStr); helper(result,s,tmp,i + 1); tmp.pop_back(); } } vector<vector<string>> partition(string s) { vector<vector<string>> result; if(s.size() == 0){ return result; } vector<string> tmp; helper(result,s,tmp,0); return result; } };
2.7 39. Combination Sum
https://leetcode.com/problems/combination-sum/#/description
数组中没有重复的元素，数组中元素可以使用多次，找到所有相加等于目标元素的集合。
思路：这题没说给定的数组是否有序，所以需要先对数组排序。如果数组中有重复元素，每个答案中不能有重复元素，那么就需要数组去重的方法，就是使用两个i,j，类比双指针套路；
第一点是记住每次递归的时候需要target - candidates[i]，压入结果的条件是target减到0，，
第二个很重要的点就是
if(target < candidates[i]){//这句很关键，不写的话没法target会小于0没法==0，超时。
break;
}这个是退出条件
第三个点就是helper(result,candidates,tmp,target - candidates[i],i);里面的i作为下一次的start，这里一定要想通，每次找候选数字，找到之后前面的数字肯定是没用的了，而该题每个答案是允许1，1,11，
这样的重复元素出现的，就是说每个数字可以使用多次，所以不需要i + 1,而是start = i;
for(int i = start;i < candidates.size();++i){ if(target < candidates[i]){//这句很关键，不写的话没法target会小于0没法==0，超时。 break; } tmp.push_back(candidates[i]); helper(result,candidates,tmp,target - candidates[i],i); tmp.pop_back(); }
class Solution { public: void helper(vector<vector<int> >& result,vector<int>& candidates,vector<int>& tmp,int target,int start){ if(target == 0){ result.push_back(tmp); return; } for(int i = start;i < candidates.size();++i){ if(target < candidates[i]){//这句很关键，不写的话没法target会小于0没法==0，超时。 break; } tmp.push_back(candidates[i]); helper(result,candidates,tmp,target - candidates[i],i); tmp.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int> > result; if(candidates.size() == 0){ return result; } vector<int> tmp; sort(candidates.begin(),candidates.end());//没说明数组是否有序，所以需要排序，如果说重复元素，还需要将数组去重 helper(result,candidates,tmp,target,0); return result; } };
2.8 40. Combination Sum II
https://leetcode.com/problems/combination-sum-ii/#/description
每个元素只能使用一次，找到所有组合等于target的元素集合。
思路：这题在上面的题目的基础上，结合了permutation II的重复元素处理方法，这题是给定的数组里面就有重复元素，但是数组中每个元素只能使用一次，使用一次的题目递归的start就必须每次i + 1, helper(result,candidates,tmp,target - candidates[i],i + 1,visited);
这题做个总结：给定的数组有重复元素，每次是对剩下的元素进行运算，那么就应该考虑当前元素和之前一个元素是否相当，相等就跳过。
permutation II是每次都要从头开始考虑整个数组的全排列，所以需要一个visited数组，判断当前元素是否已经排列过，subsets II是剩下的数组元素进行考虑每次 start = i + 1，所以不需要维护一个visited数组，这题也是对剩下元素进行操作，所以和subsets II很像，当然permutation II是都可以的方法。permutation II的if判断方法包含所有的情况，是万能方法。
if( candidates[i - 1] == candidates[i] && i != start){ continue;//permutation II有重复元素的排列 }
class Solution { public: void helper(vector<vector<int>>& result, vector<int>& candidates, vector<int>& tmp, int target,int start, vector<int>& visited){ if(target == 0){ result.push_back(tmp); } for(int i = start;i < candidates.size();++i){ if(target < candidates[i]){ break; } if(visited[i] == 1 || visited[i] == 0 && candidates[i - 1] == candidates[i] && i != start){ continue;//permutation II有重复元素的排列 } visited[i] = 1; tmp.push_back(candidates[i]); helper(result,candidates,tmp,target - candidates[i],i + 1,visited); tmp.pop_back(); visited[i] = 0; } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<vector<int>> result; if(candidates.size() == 0){ return result; } vector<int> tmp,reDupCan; vector<int> visited(candidates.size(),0); int start = 0; sort(candidates.begin(),candidates.end()); helper(result,candidates,tmp,target,start,visited); return result; } };
class Solution { public: void helper(vector<vector<int>>& result, vector<int>& candidates, vector<int>& tmp, int target,int start ){ if(target == 0){ result.push_back(tmp); } for(int i = start;i < candidates.size();++i){ if(target < candidates[i]){ break; } if( candidates[i - 1] == candidates[i] && i != start){//每次是对剩下的那部分进行运算 continue;//subsets II有重复元素的排列 } tmp.push_back(candidates[i]); helper(result,candidates,tmp,target - candidates[i],i + 1); tmp.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<vector<int>> result; if(candidates.size() == 0){ return result; } vector<int> tmp,reDupCan; int start = 0; sort(candidates.begin(),candidates.end()); helper(result,candidates,tmp,target,start); return result; } };
3、BFS宽度优先搜索
从起始状态A变化到目标状态B，最小需要多少步，使用BFS求解。
求最短是多少使用BFS；
求所有的最短是多少使用DFS。
广度优先搜索时间复杂度和答案个数有密切关系，O(X * N + m)，其中X是答案个数，N是总的节点数，m是BFS中访问的节点数目。
3.1 127. Word Ladder
https://leetcode.com/problems/word-ladder/#/description3
有一个起始单词变为目标单词，要求中间变化使用指定集合的元素。求出路径的长度。
思路：类比二叉树的层次遍历，主程序是差不多的，要注意的第一点是length初始化为1，不存在转化路径的时候返回0，题目中已经给出了，第二点是对于每个初始字符，要找到词典中和他相差一个编辑距离的单词，然后看这些单词是否已经访问或者是endword，如果不是就压入queue和unordered_set。
class Solution { public: vector<string> getString(string word,unordered_set<string>& wordListSet){//找到词典中对应Word一个距离的所有单词 vector<string> result; for(char c = 'a';c <= 'z';++c){ for(int i = 0;i < word.size();++i){ string s = word; if(c == s[i]){ continue; } s[i] = c; if(wordListSet.find(s) != wordListSet.end()){ result.push_back(s); } } } return result; } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { if(wordList.size() == 0){ return 0; } if(beginWord == endWord){ return 1;//读题，没转化数的时候才返回0 } // wordList.push_back(beginWord); // wordList.push_back(endWord);//必须利用list中的单词进行转化，start和end不一定在list中，如果end不在list中，肯定不能进行转化得到 unordered_set<string> hash,wordListSet; queue<string> q; hash.insert(beginWord); q.push(beginWord); for(string s : wordList){ wordListSet.insert(s); } int length = 1;//从1开始， while(!q.empty()){ ++length; int size = q.size(); for(int i = 0;i < size;++i){ string tmp = q.front(); q.pop(); for(string s : getString(tmp,wordListSet)){ if(hash.count(s) != 0){ continue; } if(s == endWord){//从1开始，则上一层就是路径长度，这时候q不包含endWord（s） return length; } hash.insert(s); q.push(s); } } } return 0 ; } };
3.2 126. Word Ladder II
https://leetcode.com/problems/word-ladder-ii/#/description
思路：这道题目太难，主要看思路。给出所有的路径。
使用BFS从end到start进行，如果按照正常的方法从start找end，然后根据这个来构造路径，代价会比较高，因为保存前驱结点容易，而保存后驱结点则比较困难。所以我们在广度优先搜索时反过来先从end找start，最后再根据生成的前驱结点映射从start往end构造路径，这样算法效率会有明显提高。