leetCode刷题-图、回溯相关

岛屿数量

class Solution {
private:int mi;int mj;
public:int numIslands(vector<vector<char>>& grid) {mi = grid.size() - 1;    // i的范围 0~mimj = grid[0].size() - 1; // j的范围 0~mjint landnum = 0;bool sea = false;do {pair<int, int> res = find_land(grid);if (res.first==-1&&res.second==-1)sea = true;else {landnum++;moveland(grid, res.first, res.second);}}while (!sea) ;return landnum;}pair<int, int> find_land(vector<vector<char>>& grid) {// 找到陆地返回坐标// 没找到返回-1,-1for (int i=0;i<mi+1;i++){for(int j=0;j<mj+1;j++){if(grid[i][j]=='1') {return make_pair(i,j);}}}return make_pair(-1,-1);}void moveland(vector<vector<char>>& grid, int i, int j) {// 将ij连通的全部土地变为水grid[i][j] = '0';if (i - 1 >= 0 && grid[i-1][j]=='1') {moveland(grid, i - 1, j);}if (j - 1 >= 0 && grid[i][j-1]=='1') {moveland(grid, i, j - 1);}if (j + 1 <= mj && grid[i][j+1]=='1') {moveland(grid, i, j + 1);}if (i + 1 <= mi && grid[i+1][j]=='1') {moveland(grid, i+1, j);}return;}
};

橘子腐烂（多源扩散，广度优先）

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int min = 0;int res = 0;for(int i=0; i<grid.size();i++){for(int j=0; j<grid[0].size();j++){if(grid[i][j]==2){res = bfs(grid,i,j,0);}}}//检查：如果为1int Max = -1;for(int i=0; i<grid.size();i++){for(int j=0; j<grid[0].size();j++){if(grid[i][j]==1){res = -1;}if(Max < grid[i][j]) Max = grid[i][j];}}if(res!=-1) return max(Max-2, 0);else return -1;}int bfs(vector<vector<int>>& grid, int i, int j, int min){//起始点为：ijqueue<pair<int,int>> bfs_q;int lay1 = 1;int lay2 = 0;int laynum = 1;bfs_q.push(make_pair(i,j));while(!bfs_q.empty()){//出队pair<int,int>point = bfs_q.front();bfs_q.pop();lay1--;//本层--//四个方向只要是好橘子就入队///if(point.first-1>=0 && (grid[point.first-1][point.second]==1 ||grid[point.first-1][point.second] > laynum+2)){grid[point.first-1][point.second]=laynum+2;//腐烂bfs_q.push(make_pair(point.first-1,point.second));lay2++;}if(point.second-1>=0 && (grid[point.first][point.second-1]==1 ||grid[point.first][point.second-1] > laynum+2)){grid[point.first][point.second-1]=laynum+2;bfs_q.push(make_pair(point.first,point.second-1));lay2++;}if(point.first+1<=grid.size()-1 && (grid[point.first+1][point.second]==1 ||grid[point.first+1][point.second] > laynum+2)){grid[point.first+1][point.second]=laynum+2;bfs_q.push(make_pair(point.first+1,point.second));lay2++;}if(point.second+1<=grid[0].size()-1 && (grid[point.first][point.second+1]==1 ||grid[point.first][point.second+1] > laynum+2)){grid[point.first][point.second+1]=laynum+2;bfs_q.push(make_pair(point.first,point.second+1));lay2++;}///if(lay1==0){laynum++;lay1 = lay2;lay2 = 0;}}return laynum-2;}void printgrid(vector<vector<int>>& grid){cout<<"打印图："<<endl;for(int i=0; i<grid.size();i++){for(int j=0; j<grid[0].size();j++){cout<<grid[i][j]<<" ";}cout<<endl;}}
};

课程表（有向图、拓扑图、判断是否有环） 

全排列（插入法、回溯法）

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {//全排列queue<vector<int>>q_anss;vector<vector<int>>anss;// for(int num : nums){//     cout<<num;// }// cout<<endl;vector<int>ans = nums;if(nums.size()) q_anss.push(ans);int lay1 = 1;int lay2 = 0;for(int lay = 0; lay < nums.size(); lay++){//lay为确定下标为lay及其之前的元素// cout<<"进入外层循环(下面要固定的下标)lay = "<<lay<<endl;//下面要固定下标为laywhile(lay1){  //在原有的解空间里改动【0~lay】已经确定//取出向量vector<int>out_vec = q_anss.front();// cout<<lay1<<"取出向量：";// for(int num:out_vec) cout<<num<<" ";// cout<<endl;q_anss.pop();lay1--;//加入向量for(int j=lay;j<nums.size();j++){// cout<<"   把这个数放在前面(lay号位)"<<nums[j]<<"->index="<<lay<<endl;vector<int> out_vec_copy = out_vec;int temp=out_vec_copy[j];out_vec_copy[j]=out_vec_copy[lay];out_vec_copy[lay]=temp;// cout<<"   操作后的新的数组为(并入队)：";// for(int num:out_vec_copy) cout<<num<<" ";// cout<<endl;q_anss.push(out_vec_copy);lay2++;}}// cout<<"lay位置所有情况都已经固定（更新层）lay = "<<lay<<endl;// cout<<endl;//层更新if(lay1==0){lay1 = lay2;lay2 = 0;}}//将队列的内容放入向量中while(!q_anss.empty()){anss.push_back(q_anss.front());q_anss.pop();}return anss;}
};

全部子集【二进制法、增添法（类似回溯法）】

vector<vector<int>> subsets_1(vector<int>& nums){vector<vector<int>>anss;//构造vector<int>binary;for(int i=0;i<nums.size()+1;i++){binary.push_back(0);}//开始递增:所有情况while(!binary[0]){incrementBinary(binary);// printbinary(binary);vector<int> ans;for(int i=1;i<binary.size();i++){    if(binary[i]==1) ans.push_back(nums[i-1]);}anss.push_back(ans);}return anss;
}void incrementBinary(std::vector<int>& binary) {int n = binary.size();for (int i = n - 1; i >= 0; --i) {if (binary[i] == 0) {binary[i] = 1;return;} else {binary[i] = 0;}}
}void printbinary(std::vector<int>& binary) {for(int k=0;k<binary.size();k++) cout<<binary[k];cout<<endl;
}

 树的层序遍历：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>>anss_index;queue<vector<int>>q_IdxSet;vector<int>ans;ans.push_back(-1);q_IdxSet.push(ans);anss_index.push_back(ans);int lay1 = 1;int lay2 = 0;for(int lay=0;lay<nums.size();lay++){while(lay1){//本层还有的话就一直取//取vector<int>ans_out = q_IdxSet.front();q_IdxSet.pop();lay1--;//根据取的存:从最大的下标开始for(int k=1+ans_out.back();k<nums.size();k++){vector<int>ans_in = ans_out;//复制一份再添加ans_in.push_back(k);q_IdxSet.push(ans_in);anss_index.push_back(ans_in);lay2++;}}if(lay1==0){lay1 = lay2;lay2 = 0;}}vector<vector<int>>anss;for(int i=0;i<anss_index.size();i++){vector<int>ans;for(int j=0;j<anss_index[i].size();j++){if(anss_index[i][j]!=-1) ans.push_back(nums[anss_index[i][j]]);}anss.push_back(ans);}return anss;}
};

9键打字（还是和上面的解法一样）

class Solution {
public:vector<string> letterCombinations(string digits) {vector<string>ans;vector<vector<char>>keyboard;keyboard.push_back({});keyboard.push_back({});keyboard.push_back({'a','b','c'});keyboard.push_back({'d','e','f'});keyboard.push_back({'g','h','i'});keyboard.push_back({'j','k','l'});keyboard.push_back({'m','n','o'});keyboard.push_back({'p','q','r','s'});keyboard.push_back({'t','u','v'});keyboard.push_back({'w','x','y','z'});//开始层序遍历解空间queue<string> q;q.push("");int lay1 = 1;int lay2 = 0;for(int lay=0;lay<digits.size();lay++){while(lay1){//先取string out_string = q.front();q.pop();lay1--;//再存for(int j = 0;j<keyboard[int(digits[lay])-48].size();j++){string in_string = out_string;in_string+=keyboard[int(digits[lay])-48][j];q.push(in_string);lay2++;}}if(lay1==0){lay1 = lay2;lay2 = 0;}}//将q转为answhile(!q.empty()){if(q.front()!="")ans.push_back(q.front());q.pop();}return ans;}
};

单词搜索【递归、空间超过】

class Solution {
private:bool ans;
public:bool exist(vector<vector<char>>& board, string word) {ans = false;for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){if(board[i][j]==word[0]) {map<string,bool>trace_m;dfs(board,word,i,j,0,trace_m);}}}return ans;}void dfs(vector<vector<char>>& board, string word, int i, int j, int idx , map<string,bool> trace_m){//越界if(i<0 || j<0 || i>=board.size() || j>=board[0].size()) return;if(idx==word.size())return;//字母不符合if(board[i][j]!=word[idx]) return;//解决回头文string add = to_string(i) + to_string(j);if(trace_m.count(add) && trace_m[add])return;trace_m[add] = true;if(idx==word.size()-1){ans = true; return;}dfs(board,word,i-1,j,idx+1,trace_m);dfs(board,word,i+1,j,idx+1,trace_m);dfs(board,word,i,j+1,idx+1,trace_m);dfs(board,word,i,j-1,idx+1,trace_m);}
};//题解给的
class Solution {
public://visited是原件传入，k为下标//check(board, visited, i, j, word, 0);bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {if (board[i][j] != s[k]) { //模式匹配失败return false;} else if (k == s.length() - 1) { //越界return true;}//模式匹配成功+不越界visited[i][j] = true;//标记vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};bool result = false;for (const auto& dir: directions) {//dir表示四个方向int newi = i + dir.first, newj = j + dir.second;//新坐标if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {//没有越界if (!visited[newi][newj]) {//没被访问过//bool flag = check(board, visited, newi, newj, s, k + 1);if (flag) {result = true;break;}//}}}visited[i][j] = false;return result;}bool exist(vector<vector<char>>& board, string word) {int h = board.size(), w = board[0].size();vector<vector<int>> visited(h, vector<int>(w));  //初始化二维数组for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) { //每个地方都调用checkbool flag = check(board, visited, i, j, word, 0);//每次从头遍历都用一个新的visitif (flag) {return true;}}}return false;}
};

N皇后（广度优先）

class Solution {vector<vector<string>> ans;
public:vector<vector<string>> solveNQueens(int n) {vector<string> CB = initChess(n);//广度优先算法queue<vector<string>> q_CB;q_CB.push(CB);int lay1 = 1;int lay2 = 0;for(int lay = 0; lay<n; lay++){while(lay1){//取棋盘vector<string> CB_out = q_CB.front();q_CB.pop();lay1--;//生成新棋盘(条件：CB_out是活棋)if(!isDied(CB_out,lay)){//遍历这一行，只要是0就可以下Qfor(int j = 0; j < n; j++){if(CB_out[lay][j] == '0'){vector<string> CB_in = writeQ(CB_out,lay,j);q_CB.push(CB_in);lay2++;//判断是否是最终结果if(lay==n-1 && isSuccess(CB_in)){ans.push_back(CB_in);}}}//只要是0就可以下Q}}//while(lay1){if(lay1==0){lay1 = lay2;lay2 = 0;}}return ans;}vector<string> initChess(int n){string row = "";for(int i=0;i<n;i++){row+="0";}// cout<<row;vector<string> chessB;for(int i=0;i<n;i++){chessB.push_back(row);}return chessB;}void printChess(vector<string>cB){cout<<"打印棋盘"<<endl;for(int i=0;i<cB.size();i++){cout<<cB[i]<<endl;}cout<<endl;}bool isDied(vector<string>& CB,int row){//看看第row行是否都是“.”int pointnum = 0;for(int i=0;i<CB.size(); i++){if(CB[row][i] == '.') pointnum++;}if(pointnum == CB.size()) return true;else return false;}bool isSuccess(vector<string>& CB){//看看第-1行是否有n-1个“.”int pointnum = 0;for(int i=0;i<CB.size(); i++){if(CB[CB.size()-1][i] == '.') pointnum++;}if(pointnum == CB.size()-1) return true;else return false;}//下棋//vector<string> CB_in = writeQ(CB_out,lay,j);vector<string> writeQ(vector<string>CB, int row, int j){//横向for(int i=0;i<CB.size();i++){CB[row][i] = '.';}for(int i=0;i<CB.size();i++){CB[i][j] = '.';}CB[row][j] = 'Q';//斜向for(int i = row+1;i<CB.size();i++){if(j-i+row >=0 && j-i+row<=CB.size()-1) CB[i][j-i+row] = '.';if(j+i-row >=0 && j+i-row<=CB.size()-1) CB[i][j+i-row] = '.';}return CB;}
};