4专题总结-图论和DFS、BFS
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 = ;
//clone nodes
while(start < qNode.size()){
UndirectedGraphNode *cur = qNode[start];
for(int i= ;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 = ;j < qNode.size();++j){
for(int k = ;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]; }
};
clone graph
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] + ;
}
else{
Map.insert(make_pair(neigh,));
}
}
//找入度为零的节点
queue<DirectedGraphNode*> q;
for(DirectedGraphNode* tmp : graph){
if(Map[tmp] == ){
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] - ;
if(Map[neigh] == ){
q.push(neigh);
result.push_back(neigh);
}
}
}
return result;
}
};
topological sorting
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 == ){
result.push_back(nums);
}
for(int i =;i <= n;++i){
swap(nums[i],nums[n]);
helper(result,nums,n - );
swap(nums[n],nums[i]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size() == ){
return result;
}
helper(result,nums,nums.size() - );
return result;
}
};
permutations
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 + );
subset.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size() == ){
return result;
}
vector<int> subset;
sort(nums.begin(),nums.end());
helper(result,nums,subset,);
return result;
}
};
subsets
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 -]){
continue;
}
tmp.push_back(nums[i]);
helper(result,nums,tmp,i + );//这里记住是i+1,不要写成start+ 1；
cout << i + << " ";
tmp.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size() == ){
return result;
}
vector<int> tmp;
int start = ;
sort(nums.begin(),nums.end());
helper(result,nums,tmp,start);
return result;
}
};
subsets ii
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 != && nums[i] == nums[i - ] && visit[i - ] == || visit[i] == ){
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 = ;i <= nums.size() - ;++i){
if(i != && nums[i] == nums[i - ] && visit[i - ] == || visit[i] == ){
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(),);
vector<vector<int>> result;
vector<int> tmp;
if(nums.size() == ){
return result;
}
sort(nums.begin(),nums.end());
helper(result,nums,tmp,visit);
return result;
}
};
permutations II
这里深入理解下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 = ;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 = ;column < cols.size();++column){
string s;
for(int j = ;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 = ;column < cols.size();++column){
string s;
for(int j = ;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 = ;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 = ;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 == ){
return result;
}
vector<int> cols;
helper(result,cols,n);
return result;
}
};
N Queens
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 = ,j = s.size() - ;
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() - ;++i){
string subStr = s.substr(start,i + - start);//start开始的i + 1 - start个元素
if(!isPalindrome(subStr)){
continue;
}
tmp.push_back(subStr);
helper(result,s,tmp,i + );
tmp.pop_back();
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
if(s.size() == ){
return result;
}
vector<string> tmp;
helper(result,s,tmp,);
return result;
}
};
131. Palindrome Partitioning
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 == ){
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() == ){
return result;
}
vector<int> tmp;
sort(candidates.begin(),candidates.end());//没说明数组是否有序，所以需要排序，如果说重复元素，还需要将数组去重
helper(result,candidates,tmp,target,);
return result;
}
};
conbination sum
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 - ] == 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 == ){
result.push_back(tmp);
}
for(int i = start;i < candidates.size();++i){
if(target < candidates[i]){
break;
}
if(visited[i] == || visited[i] == && candidates[i - ] == candidates[i] && i != start){
continue;//permutation II有重复元素的排列
}
visited[i] = ;
tmp.push_back(candidates[i]);
helper(result,candidates,tmp,target - candidates[i],i + ,visited);
tmp.pop_back();
visited[i] = ;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
if(candidates.size() == ){
return result;
}
vector<int> tmp,reDupCan;
vector<int> visited(candidates.size(),);
int start = ;
sort(candidates.begin(),candidates.end());
helper(result,candidates,tmp,target,start,visited);
return result;
}
};
combination sum II使用permutation II的判断方法
class Solution {
public:
void helper(vector<vector<int>>& result,
vector<int>& candidates,
vector<int>& tmp,
int target,int start
){
if(target == ){
result.push_back(tmp);
}
for(int i = start;i < candidates.size();++i){
if(target < candidates[i]){
break;
}
if( candidates[i - ] == candidates[i] && i != start){//每次是对剩下的那部分进行运算
continue;//subsets II有重复元素的排列
}
tmp.push_back(candidates[i]);
helper(result,candidates,tmp,target - candidates[i],i + );
tmp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
if(candidates.size() == ){
return result;
}
vector<int> tmp,reDupCan;
int start = ;
sort(candidates.begin(),candidates.end());
helper(result,candidates,tmp,target,start);
return result;
}
};
使用subsets II 的if判断方法
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 = ;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() == ){
return ;
}
if(beginWord == endWord){
return ;//读题，没转化数的时候才返回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开始，
while(!q.empty()){
++length;
int size = q.size();
for(int i = ;i < size;++i){
string tmp = q.front();
q.pop();
for(string s : getString(tmp,wordListSet)){
if(hash.count(s) != ){
continue;
}
if(s == endWord){//从1开始，则上一层就是路径长度，这时候q不包含endWord（s）
return length;
}
hash.insert(s);
q.push(s);
}
}
}
return ;
}
};
Word Ladder
3.2 126. Word Ladder II
https://leetcode.com/problems/word-ladder-ii/#/description
思路：这道题目太难，主要看思路。给出所有的路径。
使用BFS从end到start进行，如果按照正常的方法从start找end，然后根据这个来构造路径，代价会比较高，因为保存前驱结点容易，而保存后驱结点则比较困难。所以我们在广度优先搜索时反过来先从end找start，最后再根据生成的前驱结点映射从start往end构造路径，这样算法效率会有明显提高。
最新文章
- AngularJS事件绑定的使用详解
- Ink – 帮助你快速创建响应式邮件（Email）的框架
- mongodb版本管理
- Spring MVC 下index.jsp访问
- CSS——LESS【转】
- 366. Fibonacci
- Android清理设备内存具体完整演示样例(二)
- 应用docker化
- 深入Spring Boot: 怎样排查 java.lang.ArrayStoreException
- [UE4]Slot
- Angular-1.6 路由 简单使用
- 20165211 2017-2018-2 《Java程序设计》第7周学习总结
- codevs 1462 素数和
- java EE ME SE有什么关系
- Bootstrap的介绍和响应式媒体查询
- 在Eclipse中使用Struts和Hibernate框架搭建Maven Web项目
- 【SSH网上商城项目实战07】Struts2和Json的整合
- 初识ExtJS 6----自学笔记（一）
- python 调试模式pdb(转)
- poj Sudoku（数独） DFS