Golang每日一练(leetDay0068) 二叉树右视图、岛屿数量

2023-05-29 115

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0068) 二叉树右视图、岛屿数量

199. 二叉树的右视图 Binarytree Right Side View

给定一个二叉树的 根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]

输出: [1,3,4]

示例 2:

输入: [1,null,3]

输出: [1,3]

示例 3:

输入: []

输出: []

提示:

二叉树的节点个数的范围是 [0,100]

-100 <= Node.val <= 100

代码：

package main
import "fmt"
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func (root *TreeNode) RightSideView() []int {
  var res []int
  if root == nil {
    return res
  }
  queue := []*TreeNode{root}
  for len(queue) > 0 {
    n := len(queue)
    for i := 0; i < n; i++ {
      node := queue[i]
      if i == n-1 {
        res = append(res, node.Val)
      }
      if node.Left != nil {
        queue = append(queue, node.Left)
      }
      if node.Right != nil {
        queue = append(queue, node.Right)
      }
    }
    queue = queue[n:]
  }
  return res
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func ArrayToString(arr []int) string {
  res := "["
  for i := 0; i < len(arr); i++ {
    res += fmt.Sprint(arr[i])
    if i != len(arr)-1 {
      res += ","
    }
  }
  return res + "]"
}
func main() {
  nums := []int{1, 2, 3, null, 5, null, 4}
  root := buildTree(nums)
  fmt.Println(ArrayToString(root.RightSideView()))
  nums = []int{1, null, 3}
  root = buildTree(nums)
  fmt.Println(ArrayToString(root.RightSideView()))
}

输出：

[1,3,4]

[1,3]

200. 岛屿数量 Number-of-islands

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [

["1","1","1","1","0"],

["1","1","0","1","0"],

["1","1","0","0","0"],

["0","0","0","0","0"]]

输出：1

示例 2：

输入：grid = [

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]]

输出：3

提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 300

grid[i][j] 的值为 '0' 或 '1'

代码：

package main
import "fmt"
func numIslands(grid [][]byte) int {
  // 迭代整个网格，遇到陆地时就进行 DFS 搜索，找到一个区域后计数器加一
  m, n := len(grid), len(grid[0])
  var count int
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == '1' {
        count++
        dfs(grid, i, j, m, n)
      }
    }
  }
  return count
}
// DFS 搜索函数，将所有和当前岛屿相邻的陆地都标记为已遍历
func dfs(grid [][]byte, i, j, m, n int) {
  // 避免越界
  if i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == '0' {
    return
  }
  // 标记当前位置为已遍历
  grid[i][j] = '0'
  // DFS 搜索四周的陆地
  dfs(grid, i+1, j, m, n)
  dfs(grid, i-1, j, m, n)
  dfs(grid, i, j+1, m, n)
  dfs(grid, i, j-1, m, n)
}
func main() {
  grid1 := [][]byte{
    {'1', '1', '1', '1', '0'},
    {'1', '1', '0', '1', '0'},
    {'1', '1', '0', '0', '0'},
    {'0', '0', '0', '0', '0'},
  }
  fmt.Println(numIslands(grid1))
  grid2 := [][]byte{
    {'1', '1', '0', '0', '0'},
    {'1', '1', '0', '0', '0'},
    {'0', '0', '1', '0', '0'},
    {'0', '0', '0', '1', '1'},
  }
  fmt.Println(numIslands(grid2))
}