岛屿数量

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;}
};