目錄
DFS
BFS
LetCode
DFS
代碼結構
200. 島嶼數量
463. 島嶼的周長
BFS
代碼結構
542. 01 矩陣
102. 二叉樹的層序周遊
DFS
注标記是否通路過方法：1、直接修改輸入的資料 2、利用額外的資料結構（矩陣或hash表）
Step4: 判斷是否通路過 和 抵達目的地，通路過就不嘗試，抵達目的地傳回true
代碼結構：
DFS(輸入資料：矩陣或連結清單或樹，起始點){
建棧
存儲通路過節點seen: Map 或 改變輸入資料
while( 棧不為空 ) {
通路棧頂，pop()
for(從棧頂出發通路，所有下一個節點（狀态））
if (如果沒有通路 或 合法)
加入棧，加入seen或改變輸入資料
}
}
BFS
代碼結構：
BFS(輸入資料：矩陣或連結清單或樹，起始點){
建隊列
存儲通路過節點seen: Map 或 改變輸入資料
while( 隊列不為空 ) {
通路隊頭，poll()
for(從隊頭出發通路，所有下一個節點（狀态））
if (如果沒有通路 或 合法)
加入隊，通路：加入seen或改變輸入資料
if(到達終點)傳回
}
}
LetCode
DFS
代碼結構
DFS(輸入資料：矩陣或連結清單或樹，起始點){
建棧
存儲通路過節點seen: Map 或 改變輸入資料
while( 棧不為空 ) {
通路棧頂，pop()
for(從棧頂出發通路，所有下一個節點（狀态））
if (如果沒有通路 或 合法)
加入棧，加入seen或改變輸入資料
}
}
200. 島嶼數量
public int numIslands(char[][] grid) {
int count = 0 ;
int [] dx = new int[] {0,-1,0,1} ;
int [] dy = new int[] {-1,0,1,0} ;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == '1') {
DFS(grid, i, j, dx, dy) ;
count ++ ;
}
}
}
return count ;
}
public static void DFS(char[][] grid, int x, int y, int[] dx, int[] dy) {
Stack<Integer[]> stack = new Stack<Integer[]>() ;
grid[x][y] = '0' ;
stack.push(new Integer[] {x,y}) ;
while(!stack.isEmpty()) {
Integer [] temp = stack.pop() ;
x = temp[0]; y = temp[1] ;
for( int d = 0; d < 4; d++) {
int i = x + dx[d] , j = y + dy[d] ;
if( i>=0 && i < grid.length && j>=0 && j < grid[0].length && grid[i][j] != '0') {
grid[i][j] = '0';
stack.push(new Integer[] {i,j}) ;
}
}
}
}
注意四個方向的走法。
463. 島嶼的周長
class Solution {
public int islandPerimeter(int[][] grid) {
int count = 0 ;
int[] dx = {0,-1,0,1} ;
int[] dy = {-1,0,1,0} ;
for( int i = 0; i < grid.length; i ++){
for( int j = 0; j < grid[0].length; j ++){
if(grid[i][j] == 1){
count = DFS(grid, dx, dy, i, j) ;
return count ;
}
}
}
return count ;
}
public int DFS(int[][] grid, int[] dx, int[] dy, int x, int y){
int count = 0 ;
Stack<int []> stack = new Stack<>() ;
grid[x][y] = 2;
stack.push(new int[] {x,y}) ;
while(!stack.isEmpty()){
int [] temp = stack.pop() ;
for( int k = 0; k < 4; k ++){
int x1 = temp[0] + dx[k], y1 = temp[1] + dy[k];
if( x1 >= 0 && x1 < grid.length && y1 >= 0 && y1 < grid[0].length ){
if(grid[x1][y1] == 1){
stack.push(new int[] {x1,y1}) ;
grid[x1][y1] = 2;
}
if(grid[x1][y1] == 0){
count ++ ;
}
} else { // 邊界
count ++ ;
}
}
}
return count ;
}
}
BFS
代碼結構
BFS(輸入資料：矩陣或連結清單或樹，起始點){
建隊列
存儲通路過節點tag: Map 或 改變輸入資料 , 最短路徑使用tag矩陣
while( 隊列不為空 ) {
通路隊頭，poll()
for(從隊頭出發通路，所有下一個節點（狀态））
if (如果沒有通路 或 合法)
加入隊，通路：加入seen或改變輸入資料
if(到達終點)傳回
}
}
542. 01 矩陣
public class Solution {
public static void main(String[] args) {
int [][] matrix = new int[][] {{1,0,0},{1,1,1},{1,1,1}} ;
updateMatrix(matrix) ;
}
public static int[][] updateMatrix(int[][] matrix) {
int[][] result = new int[matrix.length][matrix[0].length] ;
int[] dx = new int [] {0,-1,0,1} ;
int[] dy = new int [] {-1,0,1,0} ;
for( int i = 0; i < matrix.length; i ++) {
for ( int j = 0; j < matrix[0].length; j ++) {
if( matrix[i][j] == 0) {
result[i][j] = 0 ;
} else {
BFS(matrix, result,dx,dy,i,j) ;
}
}
}
return result ;
}
public static void BFS(int[][] matrix, int[][] result, int[] dx, int[] dy, int x, int y) {
Queue<Integer[]> queue = new LinkedList<Integer[]>() ;
int[][] tag =new int[matrix.length][matrix[0].length];
queue.add(new Integer[] {x,y}) ;
while(!queue.isEmpty()) {
Integer[] temp = queue.poll() ;
int x1 = temp[0], y1 = temp[1] ;
for(int d = 0; d < 4; d ++) {
int i = x1 + dx[d], j = y1 + dy[d] ;
if(i>=0 && i < matrix.length && j>=0 && j < matrix[0].length && tag[i][j] == 0) {
queue.add(new Integer[] {i,j}) ;
tag[i][j] = tag[x1][y1] + 1 ;
if(matrix[i][j] == 0) { // 找到
result[x][y] = tag[i][j] ;
return ;
}
}
}
}
}
}
102. 二叉樹的層序周遊
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>() ;
if(root == null) {
return result ;
}
BFS(root,result) ;
return result ;
}
public static void BFS(TreeNode root, List<List<Integer>> result) {
Queue<TreeNode> queue = new LinkedList<TreeNode>() ;
queue.add(root) ;
while(!queue.isEmpty()) {
int len = queue.size() ;
List<Integer> temp = new ArrayList<Integer>() ;
for (int i = 0; i < len; i++) { // 目前層資料全部出完
TreeNode node = queue.poll() ;
temp.add(node.val) ;
if( node.left != null) {
queue.add(node.left) ;
}
if( node.right != null) {
queue.add(node.right) ;
}
}
result.add(temp) ;
}
}
}
待更.....