# 2022-06-02 ## [200. Number of Islands](https://leetcode.com/problems/number-of-islands/) ### Description Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return *the number of islands*. An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. **Example 1:** ``` Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 ``` **Example 2:** ``` Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 ``` **Constraints:** * `m == grid.length` * `n == grid[i].length` * `1 <= m, n <= 300` * `grid[i][j]` is `'0'` or `'1'`. ### Solution #### Approach #0: BFS ```go var ( dx = []int{0, 1, 0, -1} dy = []int{1, 0, -1, 0} ) func numIslands(grid [][]byte) (ans int) { if len(grid) == 0 { return 0 } m, n := len(grid), len(grid[0]) var queue [][]int for i := 0; i < m; i++ { for j := 0; j < n; j++ { if grid[i][j] == '0' { continue } ans++ queue = append(queue, []int{i, j}) for len(queue) > 0 { x, y := queue[0][0], queue[0][1] queue = queue[1:] if grid[x][y] == '0' { continue } grid[x][y] = '0' for k := 0; k < 4; k++ { xx, yy := x+dx[k], y+dy[k] if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] > '0' { queue = append(queue, []int{xx, yy}) } } } } } return ans } ``` #### Approach #1: DFS ```go var ( dx = []int{0, 1, 0, -1} dy = []int{1, 0, -1, 0} ) func numIslands(grid [][]byte) (ans int) { if len(grid) == 0 { return 0 } m, n := len(grid), len(grid[0]) var dfs func(x, y int) dfs = func(x, y int) { if grid[x][y] == '0' { return } grid[x][y] = '0' for i := 0; i < 4; i++ { xx, yy := x+dx[i], y+dy[i] if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] > '0' { dfs(xx, yy) } } } for i := 0; i < m; i++ { for j := 0; j < n; j++ { if grid[i][j] == '0' { continue } ans++ dfs(i, j) } } return ans } ``` ## [547. Number of Provinces](https://leetcode.com/problems/number-of-provinces/) ### Description There are `n` cities. Some of them are connected, while some are not. If city `a` is connected directly with city `b`, and city `b` is connected directly with city `c`, then city `a` is connected indirectly with city `c`. A **province** is a group of directly or indirectly connected cities and no other cities outside of the group. You are given an `n x n` matrix `isConnected` where `isConnected[i][j] = 1` if the `ith` city and the `jth` city are directly connected, and `isConnected[i][j] = 0` otherwise. Return *the total number of **provinces***. **Example 1:** ![](https://img.content.cc/a/2022/06/02/11-25-17-523-314bbc33f9978523cac2568f40a62823-9812a9.jpeg) ``` Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2 ``` **Example 2:** ![](https://img.content.cc/a/2022/06/02/11-26-45-058-5d71df9065d2692b588c3876300432bc-551a9a.jpeg) ``` Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]] Output: 3 ``` **Constraints:** * `1 <= n <= 200` * `n == isConnected.length` * `n == isConnected[i].length` * `isConnected[i][j]` is `1` or `0`. * `isConnected[i][i] == 1` * `isConnected[i][j] == isConnected[j][i]` ### Solution #### Approach #0 ```go func findCircleNum(isConnected [][]int) (ans int) { if len(isConnected) == 0 { return 0 } m := len(isConnected) var dfs func(x, y int) dfs = func(x, y int) { for i := 0; i < m; i++ { if isConnected[y][i] == 0 { continue } isConnected[y][i] = 0 if isConnected[i][y] > 0 { dfs(y, i) } } } for i := 0; i < m; i++ { for j := 0; j < m; j++ { if isConnected[i][j] == 0 { continue } ans++ if isConnected[j][i] > 0 { dfs(i, j) } } } return ans } ``` #### Approach #1 ```go func findCircleNum(isConnected [][]int) (ans int) { if len(isConnected) == 0 { return 0 } m := len(isConnected) vis := make([]bool, m) var queue []int for i, ok := range vis { if !ok { ans++ queue = append(queue, i) for len(queue) > 0 { j := queue[0] vis[j] = true queue = queue[1:] for k := 0; k < m; k++ { if isConnected[j][k] == 1 && !vis[k] { queue = append(queue, k) } } } } } return ans } ``` ## [450. Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/) ### Description Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages: 1. Search for a node to remove. 2. If the node is found, delete the node. **Example 1:** ![](https://img.content.cc/a/2022/06/02/14-45-40-503-b016522688b499cfdd953d6ddfb1f730-e0dcb2.jpeg) ``` Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted. ``` **Example 2:** ``` Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0. ``` **Example 3:** ``` Input: root = [], key = 0 Output: [] ``` **Constraints:** * The number of nodes in the tree is in the range `[0, 10^4]`. * `-10^5 <= Node.val <= 10^5` * Each node has a **unique** value. * `root` is a valid binary search tree. * `-10^5 <= key <= 10^5` **Follow up:** Could you solve it with time complexity `O(height of tree)`? ### Solution #### Approach #0 ```go /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func deleteNode(root *TreeNode, key int) *TreeNode { var pre *TreeNode cur := root for cur != nil { if cur.Val == key { if cur.Left == nil { if cur == root { return root.Right } if pre.Val > cur.Val { pre.Left = cur.Right } else { pre.Right = cur.Right } return root } if cur.Right == nil { if cur == root { return root.Left } if pre.Val > cur.Val { pre.Left = cur.Left } else { pre.Right = cur.Left } return root } target := cur pre = cur cur = cur.Right for cur.Left != nil { pre = cur cur = cur.Left } if pre.Val > cur.Val { pre.Left = cur.Right } else { pre.Right = cur.Right } target.Val = cur.Val return root } pre = cur if cur.Val > key { cur = cur.Left } else { cur = cur.Right } } return root } ``` #### Approach #1: **Recursive** ```go /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func deleteNode(root *TreeNode, key int) *TreeNode { switch { case root == nil: return nil case root.Val > key: root.Left = deleteNode(root.Left, key) case root.Val < key: root.Right = deleteNode(root.Right, key) case root.Left == nil: return root.Right case root.Right == nil: return root.Left default: cur := root.Right for cur.Left != nil { cur = cur.Left } cur.Right = deleteNode(root.Right, cur.Val) cur.Left = root.Left return cur } return root } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://a.b.cr/dictionary/algorithm/diary/2022/06/2022-06-02.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.