[TOC]
深度優(yōu)先遍歷
定義
「一條路走到底路克，不撞南墻不回頭」樟结。深度優(yōu)先遍歷 只要前面有可以走的路，就會(huì)一直向前走精算，直到無路可走才會(huì)回頭瓢宦；
無路可走有兩種情況：
① 遇到了墻；
② 遇到了已經(jīng)走過的路灰羽；
在無路可走的時(shí)候驮履，沿著原路返回，直到回到了還有未走過的路的路口廉嚼，嘗試?yán)^續(xù)走沒有走過的路徑玫镐；有一些路徑?jīng)]有走到，這是因?yàn)檎业搅顺隹诘≡耄绦蚓屯Ｖ沽耍?/p>
樹的深度優(yōu)先遍歷
二叉樹的深度優(yōu)先遍歷從「根結(jié)點(diǎn)」開始恐似，依次 「遞歸地」 遍歷「左子樹」的所有結(jié)點(diǎn)和「右子樹」的所有結(jié)點(diǎn)。
二叉樹的深度優(yōu)先遍歷還可以分為：前序遍歷傍念、中序遍歷和后序遍歷矫夷。
前序遍歷
對(duì)于任意一棵子樹，先輸出根結(jié)點(diǎn)憋槐，再遞歸輸出左子樹的 所有 結(jié)點(diǎn)双藕、最后遞歸輸出右子樹的 所有 結(jié)點(diǎn)。上圖前序遍歷的結(jié)果就是深度優(yōu)先遍歷的結(jié)果：[0阳仔、1忧陪、3、4近范、7嘶摊、2、5顺又、8更卒、9、6稚照、10]蹂空。中序遍歷
對(duì)于任意一棵子樹俯萌，先遞歸輸出左子樹的 所有 結(jié)點(diǎn)，然后輸出根結(jié)點(diǎn)上枕，最后遞歸輸出右子樹的 所有 結(jié)點(diǎn)咐熙。上圖中序遍歷的結(jié)果是：[3、1辨萍、7棋恼、4、0锈玉、8爪飘、5、9拉背、2师崎、10、6]椅棺。后序遍歷（重要）
對(duì)于任意一棵子樹犁罩，總是先遞歸輸出左子樹的 所有 結(jié)點(diǎn)，然后遞歸輸出右子樹的 所有 結(jié)點(diǎn)两疚，最后輸出根結(jié)點(diǎn)床估。后序遍歷體現(xiàn)的思想是：先必需得到左右子樹的結(jié)果，才能得到當(dāng)前子樹的結(jié)果诱渤，這一點(diǎn)在解決一些問題的過程中非常有用丐巫。上圖后序遍歷的結(jié)果是：[3、7源哩、4鞋吉、1鸦做、8励烦、9、5泼诱、10坛掠、6、2治筒、0]屉栓。
性質(zhì) 1：二叉樹的 前序遍歷 序列，根結(jié)點(diǎn)一定是 最先 訪問到的結(jié)點(diǎn)耸袜；
性質(zhì) 2：二叉樹的 后序遍歷 序列友多，根結(jié)點(diǎn)一定是 最后 訪問到的結(jié)點(diǎn)；
性質(zhì) 3：根結(jié)點(diǎn)把二叉樹的 中序遍歷 序列劃分成兩個(gè)部分堤框，第一部分的所有結(jié)點(diǎn)構(gòu)成了根結(jié)點(diǎn)的左子樹域滥，第二部分的所有結(jié)點(diǎn)構(gòu)成了根結(jié)點(diǎn)的右子樹纵柿。
圖的深度優(yōu)先遍歷
深度優(yōu)先遍歷有「回頭」的過程，在樹中由于不存在「環(huán)」（回路）启绰，對(duì)于每一個(gè)結(jié)點(diǎn)來說昂儒，每一個(gè)結(jié)點(diǎn)只會(huì)被遞歸處理一次。而「圖」中由于存在「環(huán)」（回路）委可，就需要 記錄已經(jīng)被遞歸處理的結(jié)點(diǎn)（通常使用布爾數(shù)組或者哈希表）渊跋，以免結(jié)點(diǎn)被重復(fù)遍歷到。
深度優(yōu)先遍歷的兩種實(shí)現(xiàn)方式
在深度優(yōu)先遍歷的過程中着倾，需要將 當(dāng)前遍歷到的結(jié)點(diǎn) 的相鄰結(jié)點(diǎn) 暫時(shí)保存 起來拾酝，以便在回退的時(shí)候可以繼續(xù)訪問它們。遍歷到的結(jié)點(diǎn)的順序呈現(xiàn)「后進(jìn)先出」的特點(diǎn)卡者，因此 深度優(yōu)先遍歷可以通過「椢⒈Γ」實(shí)現(xiàn)。
深度優(yōu)先遍歷有以下兩種方式：
編寫遞歸方法虎眨；
編寫棧蟋软，通過迭代的方式實(shí)現(xiàn)。
深度優(yōu)先的應(yīng)用
應(yīng)用 1：獲得圖（樹）的一些屬性
104. 二叉樹的最大深度（簡(jiǎn)單）
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue :=[]*TreeNode{root} // 輔助隊(duì)列,根節(jié)點(diǎn)入隊(duì)
depth := 0 // 初始化深度為0
for len(queue) > 0 { // 當(dāng)隊(duì)列不為空時(shí)嗽桩，循環(huán)以下操作
size := len(queue)//當(dāng)前隊(duì)列中元素個(gè)數(shù)size作為限定:當(dāng)前層級(jí)中節(jié)點(diǎn)數(shù)量
for i := 0; i < size; i++ { // 遍歷當(dāng)前層級(jí)中的節(jié)點(diǎn)
s := queue[0] // 獲取隊(duì)首元素
if s.Left != nil { // 如果左子樹不為空岳守，左子樹入隊(duì)
queue = append(queue, s.Left)
}
if s.Right != nil { // 如果右子樹不為空，右子樹入隊(duì)
queue = append(queue, s.Right)
}
queue = queue[1:] // 隊(duì)首元素出隊(duì)
}
depth++ // for循環(huán)結(jié)束后這一層級(jí)節(jié)點(diǎn)已經(jīng)訪問結(jié)束碌冶，深度加+1
}
return depth
}
111. 二叉樹的最小深度【簡(jiǎn)單/BFS/DFS】
// ============== 解法一： BFS 迭代實(shí)現(xiàn)湿痢，廣度優(yōu)先遍歷 ================
// https://www.cnblogs.com/Lusai/p/15709094.html
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue :=[]*TreeNode{root} // 查找隊(duì)列,將起點(diǎn)加入隊(duì)列
depth := 1 // root 本身就是一層，depth初始化為1
for len(queue)!=0{
size := len(queue)
// 將當(dāng)前隊(duì)列中的所有結(jié)點(diǎn)向四周擴(kuò)散
for i := 0; i < size; i++ {
cur := queue[0]
// 判斷是否到終點(diǎn)
if cur.Left == nil && cur.Right == nil {
return depth
}
// 將 cur的相鄰節(jié)點(diǎn)加入隊(duì)列
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
// 去掉當(dāng)前節(jié)點(diǎn)
queue = queue[1:]
}
// 這里增加深度
depth++
}
return depth
}
// ============== 解法二： DFS ================
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left != nil && root.Right == nil {
return 1 + minDepth(root.Left)
}
if root.Right != nil && root.Left == nil {
return 1 + minDepth(root.Right)
}
return 1 + Min(minDepth(root.Left), minDepth(root.Right))
}
112. 路徑總和(簡(jiǎn)單)
113. 路徑總和 II（中等）
翻轉(zhuǎn)二叉樹
相同的樹
對(duì)稱二叉樹
求根到葉子節(jié)點(diǎn)數(shù)字之和
236. 二叉樹的最近公共祖先（中等）
// ====== 解法二 利用hash表和存儲(chǔ)走過的路 ==============
/*
思路：我們可以用哈希表存儲(chǔ)所有節(jié)點(diǎn)的父節(jié)點(diǎn)扑庞，然后我們就可以利用節(jié)點(diǎn)的父節(jié)點(diǎn)信息從 p 結(jié)點(diǎn)開始不斷往上跳譬重，并記錄已經(jīng)訪問過的節(jié)點(diǎn)
，再?gòu)?q 節(jié)點(diǎn)開始不斷往上跳罐氨，如果碰到已經(jīng)訪問過的節(jié)點(diǎn)臀规，那么這個(gè)節(jié)點(diǎn)就是我們要找的最近公共祖先。
算法：
從根節(jié)點(diǎn)開始遍歷整棵二叉樹栅隐，用哈希表記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)指針塔嬉。
從 p 節(jié)點(diǎn)開始不斷往它的祖先移動(dòng)，并用數(shù)據(jù)結(jié)構(gòu)記錄已經(jīng)訪問過的祖先節(jié)點(diǎn)租悄。
同樣谨究，我們?cè)購(gòu)?q 節(jié)點(diǎn)開始不斷往它的祖先移動(dòng)，如果有祖先已經(jīng)被訪問過泣棋，即意味著這是 p 和 q 的深度最深的公共祖先送矩，即 LCA 節(jié)點(diǎn)抑淫。
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
parent := map[int]*TreeNode{}
visited := map[int]bool{}
var dfs func(*TreeNode)
dfs = func(r *TreeNode) {
if r == nil {
return
}
if r.Left != nil {
parent[r.Left.Val] = r
dfs(r.Left)
}
if r.Right != nil {
parent[r.Right.Val] = r
dfs(r.Right)
}
}
dfs(root)
for p != nil {
visited[p.Val] = true
p = parent[p.Val]
}
for q != nil {
if visited[q.Val] {
return q
}
q = parent[q.Val]
}
return nil
}
// func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// if root == nil {
// return nil
// }
// // 如果p,q為根節(jié)點(diǎn)，則公共祖先為根節(jié)點(diǎn)
// if root.Val == p.Val || root.Val == q.Val {
// return root
// }
// // 如果p,q在左子樹症副，則公共祖先在左子樹查找
// if find(root.Left, p) && find(root.Left, q) {
// return lowestCommonAncestor(root.Left, p, q)
// }
// // 如果p,q在右子樹，則公共祖先在右子樹查找
// if find(root.Right, p) && find(root.Right, q) {
// return lowestCommonAncestor(root.Right, p, q)
// }
// // 如果p,q分屬兩側(cè)，則公共祖先為根節(jié)點(diǎn)
// return root
// }
// func find(root, c *TreeNode) bool {
// if root == nil {
// return false
// }
// if root.Val == c.Val {
// return true
// }
// return find(root.Left, c) || find(root.Right, c)
// }
從前序與中序遍歷序列構(gòu)造二叉樹
從中序與后序遍歷序列構(gòu)造二叉樹
前序遍歷構(gòu)造二叉搜索樹
從先序遍歷還原二叉樹
二叉樹的前序遍歷
應(yīng)用 2：計(jì)算無向圖的連通分量
323
應(yīng)用 3：檢測(cè)圖中是否存在環(huán)
第 684 題：冗余連接（中等）
第 802 題：找到最終的安全狀態(tài)（中等）
應(yīng)用 4：二分圖檢測(cè)
第 785 題：判斷二分圖（中等）
應(yīng)用 5：拓?fù)渑判?/h3>
第 210 題：課程表 II（中等）
應(yīng)用 6：回溯算法獲得一個(gè)問題所有的解
回溯算法是深度優(yōu)先遍歷思想的應(yīng)用.回溯算法是一種通過不斷 嘗試 ，搜索一個(gè)問題的一個(gè)解或者 所有解 的方法。在求解的過程中棚辽，如果繼續(xù)求解不能得到題目要求的結(jié)果，就需要 回退 到上一步嘗試新的求解路徑冰肴∏辏回溯算法的核心思想是：在一棵 隱式的樹（看不見的樹） 上進(jìn)行一次深度優(yōu)先遍歷。
完成「力扣」第 22 題：括號(hào)生成（中等）熙尉；
完成「力扣」第 17 題：電話號(hào)碼的字母組合（中等）联逻；
完成「力扣」第 784 題：字母大小寫全排列（中等）。
Leetcode題
利用DFS通殺島嶼系列
二叉樹遍歷框架
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func traverse(root *TreeNode) {
traverse(root.Left)
traverse(root.Right)
}
二維矩陣的 DFS 代碼框架
// 二維矩陣遍歷框架一
func dfs_array(grid [][]int, visited [][]bool, i int, j int) {
row, col := len(grid), len(grid[0])
if i < 0 || i >= row || j < 0 || j >= col || visited[i][j] {
return
}
visited[i][j] = true
dfs_array(grid, visited, i-1, j) // 上
dfs_array(grid, visited, i+1, j) // 下
dfs_array(grid, visited, i, j-1) // 左
dfs_array(grid, visited, i, j+1) // 右
}
// 二維矩陣遍歷框架二
func dfs_array2(grid [][]int, visited [][]bool, i int, j int) {
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
row, col := len(grid), len(grid[0])
if i < 0 || i >= row || j < 0 || j >= col || visited[i][j] {
return
}
visited[i][j] = true
for _, v := range dir {
next_row := i + v[0]
next_col := j + v[1]
dfs_array2(grid, visited, next_row, next_col)
}
}
200. 島嶼數(shù)量(中等)
給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格检痰，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量包归。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成铅歼。此外公壤，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。
輸入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
輸出：1
輸入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
輸出：3
func main() {
grid := [][]byte{
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}}
fmt.Println(numIslands(grid))
}
/*
============ 解法一： DFS ========================
思路：
先找到島嶼椎椰，然后利用DFS將島嶼周邊相連的都變?yōu)楹＃@里不用visited來記錄了慨飘，可以直接利用=海來剪枝
*/
func numIslands(grid [][]byte) int {
row, col := len(grid), len(grid[0])
res := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == '1' {
res++
dfs_array2(grid, i, j)
}
}
}
return res
}
// 二維矩陣遍歷框架二
func dfs_array2(grid [][]byte, i int, j int) {
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
row, col := len(grid), len(grid[0])
if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == '0' {
return
}
grid[i][j] = '0'
for _, v := range dir {
next_row := i + v[0]
next_col := j + v[1]
dfs_array2(grid, next_row, next_col)
}
}
1254. 統(tǒng)計(jì)封閉島嶼的數(shù)目(中等)
二維矩陣 grid 由 0 （土地）和 1 （水）組成确憨。島是由最大的4個(gè)方向連通的 0 組成的群，封閉島是一個(gè) 完全 由1包圍（左瓤的、上休弃、右、下）的島圈膏。請(qǐng)返回 封閉島嶼 的數(shù)目塔猾。
輸入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
輸出：2
解釋：
灰色區(qū)域的島嶼是封閉島嶼，因?yàn)檫@座島嶼完全被水域包圍（即被 1 區(qū)域包圍）本辐。那么如何判斷「封閉島嶼」呢桥帆？其實(shí)很簡(jiǎn)單，把那些靠邊的島嶼排除掉慎皱，剩下的不就是 封閉島嶼
func main() {
grid := [][]int{
{1, 1, 1, 1, 1, 1, 1, 0},
{1, 0, 0, 0, 0, 1, 1, 0},
{1, 0, 1, 0, 1, 1, 1, 0},
{1, 0, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 0}}
fmt.Println(closedIsland(grid))
}
/*
=========== 解法一： DFS ===========
先把周邊的島嶼直接填海，再來做題叶骨，相當(dāng)于數(shù)據(jù)進(jìn)行一個(gè)預(yù)處理茫多。
*/
func closedIsland(grid [][]int) int {
row, col := len(grid), len(grid[0])
for j := 0; j < col; j++ {
dfs_array(grid, 0, j) // 把靠上邊的島嶼淹掉
dfs_array(grid, row-1, j) // 把靠下邊的島嶼淹掉
}
for i := 0; i < row; i++ {
dfs_array(grid, i, 0) // 把靠左邊的島嶼淹掉
dfs_array(grid, i, col-1) // 把靠右邊的島嶼淹掉
}
res := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == 0 { // 此題中0是島
res++
dfs_array(grid, i, j) // 因?yàn)檫B在一起算是一個(gè)島，所以這里是把連在一起的全都找出來忽刽，填海
}
}
}
return res
}
// 二維矩陣遍歷框架二
func dfs_array(grid [][]int, i int, j int) {
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
row, col := len(grid), len(grid[0])
if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 1 { // 此題中1是海
return
}
grid[i][j] = 1
for _, v := range dir {
next_row := i + v[0]
next_col := j + v[1]
dfs_array(grid, next_row, next_col)
}
}
1020. 飛地的數(shù)量(中等)
給你一個(gè)大小為 m x n 的二進(jìn)制矩陣 grid 天揖，其中 0 表示一個(gè)海洋單元格夺欲、1 表示一個(gè)陸地單元格。
一次 移動(dòng) 是指從一個(gè)陸地單元格走到另一個(gè)相鄰（上今膊、下些阅、左、右）的陸地單元格或跨過 grid 的邊界斑唬。
返回網(wǎng)格中 無法 在任意次數(shù)的移動(dòng)中離開網(wǎng)格邊界的陸地單元格的數(shù)量市埋。
輸入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
輸出：3
解釋：有三個(gè) 1 被 0 包圍。一個(gè) 1 沒有被包圍恕刘，因?yàn)樗谶吔缟稀?
輸入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
輸出：0
解釋：所有 1 都在邊界上或可以到達(dá)邊界缤谎。
func main() {
grid := [][]int{{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}}
fmt.Println(numEnclaves(grid))
}
func numEnclaves(grid [][]int) int {
// 先數(shù)據(jù)預(yù)處理一下，把靠邊的島嶼都填成海
row, col := len(grid), len(grid[0])
for j := 0; j < col; j++ {
dfs_array(grid, 0, j) // 把靠上邊的島嶼淹掉
dfs_array(grid, row-1, j) // 把靠下邊的島嶼淹掉
}
for i := 0; i < row; i++ {
dfs_array(grid, i, 0) // 把靠左邊的島嶼淹掉
dfs_array(grid, i, col-1) // 把靠右邊的島嶼淹掉
}
res := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == 1 { // 此題中1是島
res++
}
}
}
return res
}
func dfs_array(grid [][]int, i int, j int) {
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
row, col := len(grid), len(grid[0])
if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0 { // 此題中0是海
return
}
grid[i][j] = 0
for _, v := range dir {
next_row := i + v[0]
next_col := j + v[1]
dfs_array(grid, next_row, next_col)
}
}
695. 島嶼的最大面積（中等）
給你一個(gè)大小為 m x n 的二進(jìn)制矩陣 grid 褐着。島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合坷澡，這里的「相鄰」要求兩個(gè) 1 必須在 水平或者豎直的四個(gè)方向上 相鄰。你可以假設(shè) grid 的四個(gè)邊緣都被 0（代表水）包圍著含蓉。島嶼的面積是島上值為 1 的單元格的數(shù)目频敛。計(jì)算并返回 grid 中最大的島嶼面積。如果沒有島嶼馅扣，則返回面積為 0 姻政。
輸入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
輸出：6
解釋：答案不應(yīng)該是 11 ，因?yàn)閸u嶼只能包含水平或垂直這四個(gè)方向上的 1 岂嗓。
[圖片上傳失敗...(image-f9303f-1671480093471)]
// ================ 解法一： DFS ===================
func maxAreaOfIsland(grid [][]int) int {
row, col := len(grid), len(grid[0])
res := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == 1 { // 此題中1是島
res = max(res, dfs_array(grid, i, j))
}
}
}
return res
}
func dfs_array(grid [][]int, i int, j int) int {
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
row, col := len(grid), len(grid[0])
if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0 { // 此題中0是海
return 0
}
grid[i][j] = 0
count := 1 // 其實(shí)這里設(shè)置為1汁展，真的很不好理解
for _, v := range dir {
next_row := i + v[0]
next_col := j + v[1]
count += dfs_array(grid, next_row, next_col)
}
return count
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// ============== 解法二： BFS =========
func maxAreaOfIsland(grid [][]int) int {
row, col := len(grid), len(grid[0])
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
ans := 0
// 這里還真不能一次性把所有的島頭都找出來，因?yàn)檎翌^是找=1厌殉，如果不伴隨著填海一起找食绿，會(huì)有問題。
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == 0 {
continue
}
// 這里一定要注意公罕，找到島嶼的頭器紧，然后加入queue, count要從1開始，然后再把島嶼的頭填為海
queue := [][]int{{i, j}} // 找到頭
count := 1
grid[i][j] = 0
for len(queue) != 0 {
top := queue[0]
for _, v := range dir {
newRow, newCol := top[0]+v[0], top[1]+v[1]
if newRow < 0 || newRow >= row || newCol < 0 || newCol >= col || grid[newRow][newCol] == 0 {
continue
}
grid[newRow][newCol] = 0
count++
queue = append(queue, []int{newRow, newCol})
}
queue = queue[1:]
}
ans = max(ans, count)
}
}
return ans
}
1905. 統(tǒng)計(jì)子島嶼（中等）
給你兩個(gè) m x n 的二進(jìn)制矩陣 grid1 和 grid2 楼眷，它們只包含 0 （表示水域）和 1 （表示陸地）铲汪。一個(gè) 島嶼 是由 四個(gè)方向 （水平或者豎直）上相鄰的 1 組成的區(qū)域。任何矩陣以外的區(qū)域都視為水域罐柳。
如果 grid2 的一個(gè)島嶼掌腰，被 grid1 的一個(gè)島嶼 完全 包含，也就是說 grid2 中該島嶼的每一個(gè)格子都被 grid1 中同一個(gè)島嶼完全包含张吉，那么我們稱 grid2 中的這個(gè)島嶼為 子島嶼 齿梁。
請(qǐng)你返回 grid2 中 子島嶼 的 數(shù)目 。
輸入：grid1 = {{1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1}}, grid2 = {{1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}}
輸出：3
解釋：如上圖所示，左邊為 grid1 勺择，右邊為 grid2 创南。
grid2 中標(biāo)紅的 1 區(qū)域是子島嶼，總共有 3 個(gè)子島嶼省核。
[圖片上傳失敗...(image-58379c-1671480093471)]
func main() {
grid1 := [][]int{
{1, 1, 1, 0, 0},
{0, 1, 1, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 0, 0, 0},
{1, 1, 0, 1, 1}}
grid2 := [][]int{
{1, 1, 1, 0, 0},
{0, 0, 1, 1, 1},
{0, 1, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 1, 0}}
fmt.Println(countSubIslands(grid1, grid2))
}
/*
什么情況下 grid2 中的一個(gè)島嶼 B 是 grid1 中的一個(gè)島嶼 A 的子島稿辙？
當(dāng)島嶼 B 中所有陸地在島嶼 A 中也是陸地的時(shí)候，島嶼 B 是島嶼 A 的子島气忠。
反過來說邻储，如果島嶼 B 中存在一片陸地，在島嶼 A 的對(duì)應(yīng)位置是海水笔刹，那么島嶼 B 就不是島嶼 A 的子島芥备。
只要遍歷 grid2 中的所有島嶼，把那些不可能是子島的島嶼排除掉舌菜，剩下的就是子島萌壳。
*/
func countSubIslands(grid1 [][]int, grid2 [][]int) int {
// 先數(shù)據(jù)預(yù)處理一下
row, col := len(grid1), len(grid1[0])
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid2[i][j] == 1 && grid1[i][j] == 0 {
dfs_array(grid2, i, j)
}
}
}
// 現(xiàn)在 grid2 中剩下的島嶼都是子島，計(jì)算島嶼數(shù)量
res := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid2[i][j] == 1 {
res++
dfs_array(grid2, i, j)
}
}
}
return res
}
func dfs_array(grid [][]int, i int, j int) {
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
row, col := len(grid), len(grid[0])
if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0 { // 此題中0是海
return
}
grid[i][j] = 0
for _, v := range dir {
next_row := i + v[0]
next_col := j + v[1]
dfs_array(grid, next_row, next_col)
}
}
回溯算法 （處理 排列-組合-子集 問題）
回溯算法和我們常說的 DFS 算法非常類似日月，本質(zhì)上就是一種暴力窮舉算法袱瓮。回溯算法和 DFS 算法的細(xì)微差別是：**回溯算法是在遍歷「樹枝」爱咬，DFS 算法是在遍歷「節(jié)點(diǎn)」尺借。
https://labuladong.gitee.io/algo/4/31/106/
216. 組合總和 III（中等）
找出所有相加之和為 n 的 k 個(gè)數(shù)的組合，且滿足下列條件:
只使用數(shù)字1到9
每個(gè)數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 精拟。該列表不能包含相同的組合兩次燎斩，組合可以以任何順序返回。
輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了蜂绎。
輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
解釋:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
沒有其他符合的組合了栅表。
輸入: k = 4, n = 1
輸出: []
解釋: 不存在有效的組合。
在[1,9]范圍內(nèi)使用4個(gè)不同的數(shù)字师枣，我們可以得到的最小和是1+2+3+4 = 10怪瓶，因?yàn)?0 > 1，沒有有效的組合践美。
39. 組合總和（中等）
給你一個(gè) 無重復(fù)元素 的整數(shù)數(shù)組 candidates 和一個(gè)目標(biāo)整數(shù) target 洗贰，找出 candidates 中可以使數(shù)字和為目標(biāo)數(shù) target 的 所有 不同組合 ，并以列表形式返回陨倡。你可以按 任意順序 返回這些組合敛滋。candidates 中的 同一個(gè) 數(shù)字可以 無限制重復(fù)被選取 。如果至少一個(gè)數(shù)字的被選數(shù)量不同玫膀，則兩種組合是不同的矛缨。 對(duì)于給定的輸入，保證和為 target 的不同組合數(shù)少于 150 個(gè)帖旨。
輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選箕昭，2 + 2 + 3 = 7 。注意 2 可以使用多次解阅。
7 也是一個(gè)候選落竹， 7 = 7 。
僅有這兩種組合货抄。
輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]
40. 組合總和 II(中等)
給定一個(gè)候選人編號(hào)的集合 candidates 和一個(gè)目標(biāo)數(shù) target 述召，找出 candidates 中所有可以使數(shù)字和為 target 的組合。candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用 一次 蟹地。
注意：解集不能包含重復(fù)的組合积暖。
輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:[[1,1,6],[1,2,5],[1,7],[2,6]]
輸入: candidates = [2,5,2,1,2], target = 5,
輸出:[[1,2,2],[5]]
46. 全排列（中等）
給定一個(gè)不含重復(fù)數(shù)字的數(shù)組 nums ，返回其 所有可能的全排列 怪与。你可以 按任意順序 返回答案夺刑。
輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
輸入：nums = [0,1]
輸出：[[0,1],[1,0]]
輸入：nums = [1]
輸出：[[1]]
47. 全排列 II（中等）
給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ，按任意順序 返回所有不重復(fù)的全排列分别。
輸入：nums = [1,1,2]
輸出：[[1,1,2],[1,2,1],[2,1,1]]
輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
77. 組合(中等)
給定兩個(gè)整數(shù) n 和 k遍愿，返回范圍 [1, n] 中所有可能的 k 個(gè)數(shù)的組合。你可以按 任何順序 返回答案耘斩。
輸入：n = 4, k = 2
輸出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]
輸入：n = 1, k = 1
輸出：[[1]]
78. 子集（中等）
給你一個(gè)整數(shù)數(shù)組 nums 沼填，數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集（冪集）括授。解集 不能 包含重復(fù)的子集坞笙。你可以按 任意順序 返回解集。
輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
輸入：nums = [0]
輸出：[[],[0]]
90. 子集 II（中等）
給你一個(gè)整數(shù)數(shù)組 nums 荚虚，其中可能包含重復(fù)元素薛夜，請(qǐng)你返回該數(shù)組所有可能的子集（冪集）。解集 不能 包含重復(fù)的子集曲管。返回的解集中却邓，子集可以按 任意順序 排列。
輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
輸入：nums = [0]
輸出：[[],[0]]
劍指 Offer II 079. 所有子集（中等）
給定一個(gè)整數(shù)數(shù)組 nums 院水，數(shù)組中的元素 互不相同 腊徙。返回該數(shù)組所有可能的子集（冪集）。解集 不能 包含重復(fù)的子集檬某。你可以按 任意順序 返回解集撬腾。
輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
輸入：nums = [0]
輸出：[[],[0]]
劍指 Offer II 080. 含有 k 個(gè)元素的組合（中等）
給定兩個(gè)整數(shù) n 和 k，返回 1 ... n 中所有可能的 k 個(gè)數(shù)的組合恢恼。
輸入: n = 4, k = 2
輸出:
[ [2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
輸入: n = 1, k = 1
輸出: [[1]]
291. 單詞規(guī)律 II（會(huì)員/中等）
給你一種規(guī)律 pattern 和一個(gè)字符串 s民傻，請(qǐng)你判斷 s 是否和 pattern 的規(guī)律相匹配。如果存在單個(gè)字符到字符串的 雙射映射 ，那么字符串 s 匹配 pattern 漓踢，即：如果pattern 中的每個(gè)字符都被它映射到的字符串替換牵署，那么最終的字符串則為 s 。雙射 意味著映射雙方一一對(duì)應(yīng)喧半，不會(huì)存在兩個(gè)字符映射到同一個(gè)字符串奴迅，也不會(huì)存在一個(gè)字符分別映射到兩個(gè)不同的字符串。
輸入：pattern = "abab", s = "redblueredblue"
輸出：true
解釋：一種可能的映射如下：
'a' -> "red"
'b' -> "blue"
輸入：pattern = "aaaa", s = "asdasdasdasd"
輸出：true
解釋：一種可能的映射如下：
'a' -> "asd"
320. 列舉單詞的全部縮寫（會(huì)員/中等）
單詞的 廣義縮寫詞 可以通過下述步驟構(gòu)造：先取任意數(shù)量的 不重疊挺据、不相鄰 的子字符串取具，再用它們各自的長(zhǎng)度進(jìn)行替換。
例如扁耐，"abcde" 可以縮寫為：
"a3e"（"bcd" 變?yōu)?"3" ）
"1bcd1"（"a" 和 "e" 都變?yōu)?"1"）
"5" ("abcde" 變?yōu)?"5")
"abcde" (沒有子字符串被代替)
然而暇检，這些縮寫是 無效的 ：
"23"（"ab" 變?yōu)?"2" ，"cde" 變?yōu)?"3" ）是無效的婉称，因?yàn)楸贿x擇的字符串是相鄰的
"22de" ("ab" 變?yōu)?"2" 块仆， "bc" 變?yōu)?"2") 是無效的，因?yàn)楸贿x擇的字符串是重疊的
給你一個(gè)字符串 word 酿矢，返回 一個(gè)由 word 的所有可能 廣義縮寫詞 組成的列表 榨乎。按 任意順序 返回答案。
輸入：word = "word"
輸出：["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]
輸入：word = "a"
輸出：["1","a"]
