leetcode 695
广度优先搜索一层一层遍历，每一层遍历到的所有新节点，要用队列先存储起来以备下一层遍历的时候再遍历；而深度优先搜索在遍历到一个新节点时立马对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。
从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。
在程序实现 DFS 时需要考虑以下问题：
- 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。也可以使用递归栈。
- 标记：和 BFS 一样同样需要对已经遍历过得节点进行标记。
class Solution { public int maxAreaOfIsland(int[][] grid) { int m=grid.length; int n=grid[0].length; int maxv=0; for (int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==1){ maxv=Math.max(maxv,dfs(grid,i,j)); } } } return maxv; } public int dfs(int[][] grid,int i,int j){ int m=grid.length; int n=grid[0].length; if(i<0||i>=m||j<0||j>=n) return 0;//注意这个是有可能的，因为比方是在0，0起点或者边界的时候都会出现越界，因为最后一行 if(grid[i][j]==0) return 0; grid[i][j]=0; return dfs(grid,i-1,j)+dfs(grid,i,j-1)+dfs(grid,i+1,j)+dfs(grid,i,j+1)+1;//不要忘记+1，处理当前的数值 } }
leetcode 547
这道题虽然说是用了深度遍历，但其实只是用了深度遍历的思想，也就是从行方向遍历，对每个人进行DFS，看与每个列方向的关系，遍历结束则返回结果。
class Solution { public int findCircleNum(int[][] M) { int[] vis=new int[M.length]; int count=0; for(int i=0;i<M.length;i++){ if(vis[i]==0) { dfs1(M,i,vis); count++; } } return count; } public void dfs1(int[][] M,int i,int[]vis){ for(int j=0;j<M.length;j++){ if(M[i][j]==1&&vis[j]==0){ vis[j]=1; dfs1(M,j,vis);//一定要注意逻辑顺序 //如果出现stackflow那么说明一定是循环哪里的逻辑出现了问题导致死循环 } } } }
leetcode 200
class Solution { int[][] dir={{1,0},{0,1},{0,-1},{-1,0}}; public int numIslands(char[][] grid) { if(grid==null||grid.length==0) return 0; int m=grid.length; int n=grid[0].length; int count=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]=='1'){ dfs(grid,i,j); grid[i][j]='0'; count++; } } } return count; } public void dfs(char[][]grid,int i,int j){ int m=grid.length; int n=grid[0].length; if(i<0||j>=n||i>=m||j<0||grid[i][j]=='0'){return;}//如果越界则返回,注意范围设置 grid[i][j]='0'; for (int k=0;k<4;k++){ dfs(grid,i+dir[k][0],j+dir[k][1]); } } }
leetcode 130
这道题的关键是读懂题，理解题的解题思路，因为要处理围着X的O，但是对于边缘的O以及与边缘O相互连通的O都不能进行处理，那么这个时候就有相应的不同条件下的不同处理方法
class Solution { public void solve(char[][] board) { if(board==null||board.length==0) return;//边界条件要处理 int m=board.length; int n=board[0].length; boolean flag; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ flag=(i==0||i==m-1||j==0||j==n-1); //以边界O开始遍历 if(flag&&board[i][j]=='O'){ dfs(board,i,j); // board[i][j]='#'; } // if(board[i][j]=='O') board[i][j]='X'; //这里有可能里面的数据还没处理到，有可能到后面本应该是# } } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='O') board[i][j]='X'; if(board[i][j]=='#') board[i][j]='O'; } } } public void dfs(char[][] board,int i,int j){ int m=board.length; int n=board[0].length; if(i<0||i>=m||j<0||j>=n||board[i][j]=='X'||board[i][j]=='#') return; board[i][j]='#';//这里你可能把边上的O遍历出来的联通的所有的O都进行了换值，也就是都处理，主要是为了防止替换内部的O为X的时候弄错，所以给个标记，但是后面要再给还原回来。 dfs(board,i-1,j); dfs(board,i,j-1); dfs(board,i+1,j); dfs(board,i,j+1); } }
leetcode 257
二叉树的所有路径
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res=new ArrayList<>(); if(root==null) return res;//注意判断边界情况 dfs(res,"",root); return res; } public void dfs(List<String> res, String pes, TreeNode root){ if(root==null) return; if(root.left==null&&root.right==null){ res.add(pes+root.val); return; } pes+=root.val+"->"; dfs(res,pes,root.left);//注意这里是字符值传递，不会影响下一语句 dfs(res,pes,root.right); } }
leetcode 51 N皇后 Hard
总体而言这道题的思路如下：（这道题难度之所以是hard，是由于循环太容易把自己写糊涂了！！！）
- 首先你要清楚每个皇后必须要分别占一行一列，也就是不能出现基本的在同一行或在同一列的皇后（这里还没有考虑斜线）
- 斜线方面主要是考虑如何记录哪些斜线不能再放皇后，哪些可以继续放皇后
- 第一个皇后从第一行第一列开始放起，放第二行皇后的位置，然后不断第一个皇后的列，直到把所有皇后都放好了（此时行号为N）再将最后一个皇后退栈，重新回溯遍历。
import java.util.Arrays; import java.lang.Character; class Solution { int n; public char[][] que; public boolean uncol[]; public boolean un45[]; public boolean un135[]; public List<List<String>> res; public List<List<String>> solveNQueens(int n) { res=new ArrayList<>(); que=new char[n][n]; // Arrays.fill(que,'.'); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ que[i][j] = '.'; } } // Arrays.fill(que,'.'); uncol=new boolean[n]; un45=new boolean[2*n-1];//主要是用来存一共可能存的索引总数可能为2*n-1 un135=new boolean[2*n-1]; this.n=n; back(0); return res; } public void back(int row){ if(row==n){ List<String> list=new ArrayList<>(); for(char[] ch:que){ list.add(new String(ch)); } res.add(list); return;//结束最后一个点的back } for(int col=0;col<n;col++){ int un451=row+col; int un1351=n-1-(row-col); if(uncol[col]||un45[un451]||un135[un1351]) continue; que[row][col]='Q'; uncol[col]=un45[un451]=un135[un1351]=true; back(row+1); uncol[col]=un45[un451]=un135[un1351]=false; que[row][col]='.'; } } }