两种方式处理已经访问过的节点：一种是用visited存储已经访问过的1；另一种是通过改变原始数值的值，比如将1改成-1，这样小于等于0的都会停止。
Number of Islands 用了第一种方式，Number of Distinct Islands用了第二种方式
注意：如果采用更改原数组的方式，一定要注意加引用！！！
Number of Islands变种，假设给的矩阵四周都是陆地，和陆地相连不算island。
方法：与Number of Islands的search函数是一样的，只是需要进行预处理 ，即先把与四周的1相连的全变成0，然后再做与Number of Islands一样的操作
200. Number of Islands
个人理解dfs、bfs的时间复杂度都是 o(m*n)
时间复杂度o(m*n)
1.这种写法要改变原始输入数组的值
错误版本：
条件判断顺序写错：grid[x][y] == '0' || x < 0 || x >= length || y < 0 || y >= width
这种写法要报数组越界的错误，因为grid[x][y]会先访问，实际上x、y这个时候可能就越界了，grid[x][y]必须放在这几个越界判断的后面
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int length = grid.size();
if(length <= )
return ;
int width = grid[].size();
int count = ;
for(int i = ;i < length;i++){
for(int j = ;j < width;j++){
if(grid[i][j] == ''){
search(grid,i,j,length,width);
count++;
}
}
}
return count;
}
void search(vector<vector<char>>& grid,int x,int y,int length,int width){
if(x < || x >= length || y < || y >= width || grid[x][y] == '')
return;
grid[x][y] = '';
search(grid,x-,y,length,width);
search(grid,x+,y,length,width);
search(grid,x,y-,length,width);
search(grid,x,y+,length,width);
}
};
整体思路，从第一点开始找1，如果找到1，把所有的与这个1相连的1置为0，因为这些1与这个1属于同一个岛屿，用dfs去找把所有的1找到
https://blog.csdn.net/xudli/article/details/45912547
2.不改变原始输入的值，还是用dfs
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int width = grid.size();
if(width <= )
return ;
int length = grid[].size();
if(length <= )
return ;
int count = ;
vector<vector<bool>> visited(width,vector<bool>(length,false));
for(int i = ;i < width;i++){
for(int j = ;j < length;j++){
if(grid[i][j] == '' && visited[i][j] == false){
search(grid,i,j,visited);
count++;
}
}
}
return count;
}
void search(vector<vector<char>> grid,int x,int y,vector<vector<bool>>& visited){
if(x < || x >= grid.size() || y < || y >= grid[].size() || grid[x][y] == '' || visited[x][y] == true)
return;
visited[x][y] = true;
search(grid,x-,y,visited);
search(grid,x+,y,visited);
search(grid,x,y-,visited);
search(grid,x,y+,visited);
}
};
http://www.cnblogs.com/grandyang/p/4402656.html
bfs的两种方法：
方法一：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if(m <= )
return ;
int n = grid[].size();
if(n <= )
return ;
queue<pair<int,int>> q;
int res = ;
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(grid[i][j] == ''){
q.push(make_pair(i,j));
res++;
grid[i][j] = '';
while(!q.empty()){
int x= q.front().first;
int y = q.front().second;
q.pop();
//grid[x][y] = '0';
for(auto dir : dirs){
int x_cur = x + dir[];
int y_cur = y + dir[];
if(x_cur < || x_cur >= m || y_cur < || y_cur >= n || grid[x_cur][y_cur] == '')
continue;
q.push(make_pair(x_cur,y_cur));
grid[x_cur][y_cur] = '';
}
}
}
}
}
return res;
}
vector<vector<int>> dirs{{-,},{,},{,-},{,}};
};
方法二：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if(m <= )
return ;
int n = grid[].size();
if(n <= )
return ;
vector<vector<bool>> visited(m,vector<bool>(n,false));
queue<pair<int,int>> q;
int res = ;
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(grid[i][j] == '' && visited[i][j] == false){
q.push(make_pair(i,j));
res++;
visited[i][j] = true;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(auto dir : dirs){
int x_cur = x + dir[];
int y_cur = y + dir[];
if(x_cur < || x_cur >= m || y_cur < || y_cur >= n || grid[x_cur][y_cur] == '' || visited[x_cur][y_cur] == true)
continue;
visited[x_cur][y_cur] = true;
q.push(make_pair(x_cur,y_cur));
}
}
}
}
}
return res;
}
vector<vector<int>> dirs{{-,},{,},{,-},{,}};
};
错误方法一：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if(m <= )
return ;
int n = grid[].size();
if(n <= )
return ;
queue<pair<int,int>> q;
int res = ;
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(grid[i][j] == ''){
q.push(make_pair(i,j));
res++;
while(!q.empty()){
int x= q.front().first;
int y = q.front().second;
q.pop();
grid[x][y] = '';
for(auto dir : dirs){
int x_cur = x + dir[];
int y_cur = y + dir[];
if(x_cur < || x_cur >= m || y_cur < || y_cur >= n || grid[x_cur][y_cur] == '')
continue;
q.push(make_pair(x_cur,y_cur));
}
}
}
}
}
return res;
}
vector<vector<int>> dirs{{-,},{,},{,-},{,}};
};
这个错误的方法与方法一类似，但是这个方法会在大数组的时候报超时，这是因为每次进行将1变成0的操作都是在队列弹出之后，这样会导致许多重复计算。
如下图，从右下角的1开始遍历，会先遍历到左下角和右上角，这种情况没问题，但是当左下角和右上角都要遍历到左上角时，都会把左上角这个1加入队列进行一次计算，但是正确写法却不用。因为正确写法，在加入队列的时候就已经置为0了，下一次再访问到这个位置肯定不会再加入队列了。
694 Number of Distinct Islands
存储搜索到的每个岛的形状，利用set来保证存储的形状不一样。形状的存储是根据每个遍历节点到每个岛的左上点的x、y差值，所以用pair的形式。因为每个岛有多个点，所以用vector存储
用unordered_set编译会报错
class Solution {
public:
int numberofDistinctIslands(vector<vector<int>> &grid) {
int m = grid.size();
if(m <= )
return ;
int n = grid[].size();
if(n <= )
return ;
set<vector<pair<int,int>>> shapes;
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(grid[i][j] == ){
vector<pair<int,int>> shape;
numberofDistinctIslands(grid,i,j,i,j,shape);
shapes.insert(shape);
}
}
}
return shapes.size();
}
void numberofDistinctIslands(vector<vector<int>>& grid,int x0,int y0,int i,int j,vector<pair<int,int>>& shape){
if(i < || i >= grid.size() || j < || j >= grid[].size() || grid[i][j] <= )
return;
grid[i][j] = -;
shape.push_back({x0 - i ,y0 - j});
numberofDistinctIslands(grid,x0,y0,i - ,j,shape);
numberofDistinctIslands(grid,x0,y0,i + ,j,shape);
numberofDistinctIslands(grid,x0,y0,i,j - ,shape);
numberofDistinctIslands(grid,x0,y0,i,j + ,shape);
}
};
695. Max Area of Island
自己写的
记录每个岛屿的节点个数就好了。每次大的循环是一个岛屿，每次递归是一个节点，所以在每次递归的时候++就好了，然后比较所有岛屿中最大的
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size();
if(m <= )
return ;
int n = grid[].size();
if(n <= )
return ;
int max_num = ;
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(grid[i][j] == ){
int num = ;
maxAreaOfIsland(grid,i,j,num);
if(num > max_num)
max_num = num;
}
}
}
return max_num;
}
void maxAreaOfIsland(vector<vector<int>>& grid,int i,int j,int& num){
if(i < || i >= grid.size() || j < || j >= grid[].size() || grid[i][j] <= )
return;
grid[i][j] = -;
num++;
maxAreaOfIsland(grid,i - ,j,num);
maxAreaOfIsland(grid,i + ,j,num);
maxAreaOfIsland(grid,i,j - ,num);
maxAreaOfIsland(grid,i,j + ,num);
}
};
130. Surrounded Regions
在4条边上的O肯定不会被包围。
在4条边上找O，然后寻找这个O的岛屿，然后把这4条边能生成的岛屿全变成$，最后再将O变成X，$变成O。
这里第一个代码换了一种迭代的写法，每次判断的依据是以下一个节点为依据，后一个代码是自己经常使用的迭代写法，都是可以的。
class Solution {
public:
void solve(vector<vector<char> >& board) {
int m = board.size();
if(m <= )
return;
int n = board[].size();
if(n <= )
return;
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if((i == || i == board.size() - || j == || j == board[].size() - ) && board[i][j] == 'O')
solve(board,i,j);
}
}
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(board[i][j] == 'O')
board[i][j] = 'X';
if(board[i][j] == '$')
board[i][j] = 'O';
}
}
return;
}
void solve(vector<vector<char> >& board,int i,int j){
board[i][j] = '$';
if(i >= && board[i-][j] == 'O')
solve(board,i - ,j);
if(i < board.size() - && board[i+][j] == 'O')
solve(board,i + ,j);
if(j >= && board[i][j-] == 'O')
solve(board,i,j - );
if(j < board[].size() - && board[i][j+] == 'O')
solve(board,i,j + );
return;
}
};
自己最常写的。
class Solution {
public:
void solve(vector<vector<char> >& board) {
int m = board.size();
if(m <= )
return;
int n = board[].size();
if(n <= )
return;
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if((i == || i == board.size() - || j == || j == board[].size() - ) && board[i][j] == 'O')
solve(board,i,j);
}
}
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(board[i][j] == 'O')
board[i][j] = 'X';
if(board[i][j] == '$')
board[i][j] = 'O';
}
}
return;
}
void solve(vector<vector<char> >& board,int i,int j){
if(i < || i >= board.size() || j < || j >= board[].size() || board[i][j] != 'O')
return;
board[i][j] = '$';
solve(board,i - ,j);
solve(board,i + ,j);
solve(board,i,j - );
solve(board,i,j + );
}
};
并查集：
是不是在一个集合里面
指向自己的优化
hash-map就可以解决
操作：1.查询
非递归比递归好。每次递归调用，程序保存了上一次调用的结果
集合代表
2.合并
434. Number of Islands II(lintcode)
https://www.cnblogs.com/grandyang/p/5190419.html
n代表行数、m代表列数，x是在行上的位置，y是在列上的位置，所以在roots中的坐标应该是：m * x + y
roots表示所有节点所属于的根，即属于哪一个集合，初始为-1表示没有属于任何一个集合。
count表示集合个数，如果本身是一个重来没属于任何结合的位置，遍历到的时候就需要 count++。
核心思路：两个相邻的位置不属于同一个集合，这表明需要更新集合。
class Solution {
public:
/**
* @param n: An integer
* @param m: An integer
* @param operators: an array of point
* @return: an integer array
*/
vector<int> numIslands2(int n, int m, vector<Point> &operators) {
// write your code here
vector<int> result;
int count = ;
vector<vector<int>> dirs{{, -}, {-, }, {, }, {, }};
vector<int> roots(m*n,-);
for(int i = ;i < operators.size();i++){
int x = operators[i].x;
int y = operators[i].y;
int index = m * x + y;
if(roots[index] == -){
roots[index] = index;
count++;
}
for(auto dir : dirs){
int dx = x + dir[];
int dy = y + dir[];
int cur_index = m * dx + dy;
if(dx < || dx >= n || dy < || dy >= m || roots[cur_index] == -)
continue;
int p = findroot(roots,cur_index),q = findroot(roots,index);
if(p != q){
roots[p] = q;
count--;
}
}
result.push_back(count);
}
return result;
}
int findroot(vector<int> roots,int index){
int root = roots[index];
while(root != index){
index = root;
root = roots[index];
}
return root;
}
};
178. Graph Valid Tree
https://www.cnblogs.com/grandyang/p/5257919.html
这道题给了我们一个无向图，让我们来判断其是否为一棵树，我们知道如果是树的话，所有的节点必须是连接的，也就是说必须是连通图，而且不能有环，所以我们的焦点就变成了验证是否是连通图和是否含有环。
这个题与Number of Islands II的查找操作有点不太一样，Number of Islands II中根节点存储的是自己的下标，这个题的根节点存储的是-1，所以find函数不太一样。
class Solution {
public:
/**
* @param n: An integer
* @param edges: a list of undirected edges
* @return: true if it's a valid tree, or false
*/
bool validTree(int n, vector<vector<int>> &edges) {
// write your code here
vector<int> roots(n,-);
for(int i = ;i < edges.size();i++){
int p = findRoot(roots,edges[i][]);
int q = findRoot(roots,edges[i][]);
if(p == q)
return false;
roots[p] = q;
}
return edges.size() == n-;
}
int findRoot(vector<int> roots,int index){
while(roots[index] != -)
index = roots[index];
return index;
}
};