Golang每日一练(leetDay0079) 最大正方形、完全二叉树节点数

目录

221. 最大正方形 Maximal Square  🌟🌟

222. 完全二叉树的节点个数 Count Complete Tree Nodes  🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C 每日一练 专栏

Java每日一练 专栏

---

221. 最大正方形 Maximal Square

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

代码1： 暴力枚举

1.  
   package main
2.  
    
3.  
   import (
4.  
   "fmt"
5.  
   )
6.  
    
7.  
   func maximalSquare(matrix [][]byte) int {
8.  
   m, n := len(matrix), len(matrix[0])
9.  
   maxLen := 0
10.  
    for i := 0; i < m; i {
11.  
    for j := 0; j < n; j {
12.  
    if matrix[i][j] == '1' {
13.  
    curLen := 1
14.  
    flag := true
15.  
    for k := 1; k i < m && k j < n && flag; k {
16.  
    for l := 0; l <= k; l {
17.  
    if matrix[i k][j l] == '0' || matrix[i l][j k] == '0' {
18.  
    flag = false
19.  
    break
20.  
    }
21.  
    }
22.  
    if flag {
23.  
    curLen
24.  
    }
25.  
    }
26.  
    if curLen > maxLen {
27.  
    maxLen = curLen
28.  
    }
29.  
    }
30.  
    }
31.  
    }
32.  
    return maxLen * maxLen
33.  
    }
34.  
     
35.  
    func main() {
36.  
    matrix := [][]byte{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}
37.  
    fmt.Println(maximalSquare(matrix))
38.  
    matrix = [][]byte{{'0', '1'}, {'1', '0'}}
39.  
    fmt.Println(maximalSquare(matrix))
40.  
    matrix = [][]byte{{'0'}}
41.  
    fmt.Println(maximalSquare(matrix))
42.  
    }

代码2： 动态规划

1.  
   package main
2.  
    
3.  
   import (
4.  
   "fmt"
5.  
   )
6.  
    
7.  
   func maximalSquare(matrix [][]byte) int {
8.  
   m, n := len(matrix), len(matrix[0])
9.  
   maxLen := 0
10.  
    dp := make([][]int, m)
11.  
    for i := 0; i < m; i {
12.  
    dp[i] = make([]int, n)
13.  
    for j := 0; j < n; j {
14.  
    if matrix[i][j] == '1' {
15.  
    if i == 0 || j == 0 {
16.  
    dp[i][j] = 1
17.  
    } else {
18.  
    dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) 1
19.  
    }
20.  
    if dp[i][j] > maxLen {
21.  
    maxLen = dp[i][j]
22.  
    }
23.  
    }
24.  
    }
25.  
    }
26.  
    return maxLen * maxLen
27.  
    }
28.  
     
29.  
    func min(a, b int) int {
30.  
    if a < b {
31.  
    return a
32.  
    }
33.  
    return b
34.  
    }
35.  
     
36.  
    func main() {
37.  
    matrix := [][]byte{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}
38.  
    fmt.Println(maximalSquare(matrix))
39.  
    matrix = [][]byte{{'0', '1'}, {'1', '0'}}
40.  
    fmt.Println(maximalSquare(matrix))
41.  
    matrix = [][]byte{{'0'}}
42.  
    fmt.Println(maximalSquare(matrix))
43.  
    }

代码3： 动态规划优化

1.  
   package main
2.  
    
3.  
   import (
4.  
   "fmt"
5.  
   )
6.  
    
7.  
   func maximalSquare(matrix [][]byte) int {
8.  
   m, n := len(matrix), len(matrix[0])
9.  
   maxLen := 0
10.  
    cur := make([]int, n)
11.  
    pre := make([]int, n)
12.  
    for i := 0; i < m; i {
13.  
    for j := 0; j < n; j {
14.  
    if matrix[i][j] == '1' {
15.  
    if i == 0 || j == 0 {
16.  
    cur[j] = 1
17.  
    } else {
18.  
    cur[j] = min(pre[j], min(cur[j-1], pre[j-1])) 1
19.  
    }
20.  
    if cur[j] > maxLen {
21.  
    maxLen = cur[j]
22.  
    }
23.  
    } else {
24.  
    cur[j] = 0
25.  
    }
26.  
    }
27.  
    cur, pre = pre, cur
28.  
    }
29.  
    return maxLen * maxLen
30.  
    }
31.  
     
32.  
    func min(a, b int) int {
33.  
    if a < b {
34.  
    return a
35.  
    }
36.  
    return b
37.  
    }
38.  
     
39.  
    func main() {
40.  
    matrix := [][]byte{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}
41.  
    fmt.Println(maximalSquare(matrix))
42.  
    matrix = [][]byte{{'0', '1'}, {'1', '0'}}
43.  
    fmt.Println(maximalSquare(matrix))
44.  
    matrix = [][]byte{{'0'}}
45.  
    fmt.Println(maximalSquare(matrix))
46.  
    }

输出：

4
1
0

---

222. 完全二叉树的节点个数 Count Complete Tree Nodes

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2^h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

• 树中节点的数目范围是[0, 5 * 10^4]
• 0 <= Node.val <= 5 * 10^4
• 题目数据保证输入的树是 完全二叉树 

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

代码1： dfs

完全二叉树，可以通过比较根节点左子树高度和右子树高度来确定它是否可以被视为完全二叉树。如果左右高度相等，则该树是满二叉树，节点个数为 2ℎ−12h−1；否则，该树可以被分成一棵满二叉树和一颗子树，递归计算子树的节点数 

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
   const null = -1 << 31
6.  
    
7.  
   type TreeNode struct {
8.  
   Val int
9.  
   Left *TreeNode
10.  
    Right *TreeNode
11.  
    }
12.  
     
13.  
    func countNodes(root *TreeNode) int {
14.  
    if root == nil {
15.  
    return 0
16.  
    }
17.  
    var left, right uint
18.  
    left, right = 0, 0
19.  
    for node := root; node != nil; node = node.Left {
20.  
    left
21.  
    }
22.  
    for node := root; node != nil; node = node.Right {
23.  
    right
24.  
    }
25.  
    if left == right {
26.  
    return (1 << left) - 1
27.  
    } else {
28.  
    return countNodes(root.Left) countNodes(root.Right) 1
29.  
    }
30.  
    }
31.  
     
32.  
    func buildTree(nums []int) *TreeNode {
33.  
    if len(nums) == 0 {
34.  
    return nil
35.  
    }
36.  
    root := &TreeNode{Val: nums[0]}
37.  
    Queue := []*TreeNode{root}
38.  
    idx := 1
39.  
    for idx < len(nums) {
40.  
    node := Queue[0]
41.  
    Queue = Queue[1:]
42.  
    if nums[idx] != null {
43.  
    node.Left = &TreeNode{Val: nums[idx]}
44.  
    Queue = append(Queue, node.Left)
45.  
    }
46.  
    idx
47.  
    if idx < len(nums) && nums[idx] != null {
48.  
    node.Right = &TreeNode{Val: nums[idx]}
49.  
    Queue = append(Queue, node.Right)
50.  
    }
51.  
    idx
52.  
    }
53.  
    return root
54.  
    }
55.  
     
56.  
    func main() {
57.  
    nums := []int{1, 2, 3, 4, 5, 6}
58.  
    root := buildTree(nums)
59.  
    fmt.Println(countNodes(root))
60.  
    nums = []int{}
61.  
    root = buildTree(nums)
62.  
    fmt.Println(countNodes(root))
63.  
    nums = []int{1}
64.  
    root = buildTree(nums)
65.  
    fmt.Println(countNodes(root))
66.  
    }

注：位运算符 << 要求右侧的操作数必须为无符号整数类型。在 Go 语言中，如果左侧操作数不是无符号整数，右侧操作数必须用无符号整数类型转换。 

代码2：bfs

将根节点放入队列中，然后对于队列中的每一个节点，将它的左右子节点入队，统计队列的大小即为节点个数

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
   const null = -1 << 31
6.  
    
7.  
   type TreeNode struct {
8.  
   Val int
9.  
   Left *TreeNode
10.  
    Right *TreeNode
11.  
    }
12.  
     
13.  
    func countNodes(root *TreeNode) int {
14.  
    if root == nil {
15.  
    return 0
16.  
    }
17.  
    q := []*TreeNode{root}
18.  
    count := 0
19.  
    for len(q) > 0 {
20.  
    size := len(q)
21.  
    count = size
22.  
    for i := 0; i < size; i {
23.  
    node := q[i]
24.  
    if node.Left != nil {
25.  
    q = append(q, node.Left)
26.  
    }
27.  
    if node.Right != nil {
28.  
    q = append(q, node.Right)
29.  
    }
30.  
    }
31.  
    q = q[size:]
32.  
    }
33.  
    return count
34.  
    }
35.  
     
36.  
    func buildTree(nums []int) *TreeNode {
37.  
    if len(nums) == 0 {
38.  
    return nil
39.  
    }
40.  
    root := &TreeNode{Val: nums[0]}
41.  
    Queue := []*TreeNode{root}
42.  
    idx := 1
43.  
    for idx < len(nums) {
44.  
    node := Queue[0]
45.  
    Queue = Queue[1:]
46.  
    if nums[idx] != null {
47.  
    node.Left = &TreeNode{Val: nums[idx]}
48.  
    Queue = append(Queue, node.Left)
49.  
    }
50.  
    idx
51.  
    if idx < len(nums) && nums[idx] != null {
52.  
    node.Right = &TreeNode{Val: nums[idx]}
53.  
    Queue = append(Queue, node.Right)
54.  
    }
55.  
    idx
56.  
    }
57.  
    return root
58.  
    }
59.  
     
60.  
    func main() {
61.  
    nums := []int{1, 2, 3, 4, 5, 6}
62.  
    root := buildTree(nums)
63.  
    fmt.Println(countNodes(root))
64.  
    nums = []int{}
65.  
    root = buildTree(nums)
66.  
    fmt.Println(countNodes(root))
67.  
    nums = []int{1}
68.  
    root = buildTree(nums)
69.  
    fmt.Println(countNodes(root))
70.  
    }

代码3：二分法

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
   const null = -1 << 31
6.  
    
7.  
   type TreeNode struct {
8.  
   Val int
9.  
   Left *TreeNode
10.  
    Right *TreeNode
11.  
    }
12.  
     
13.  
    func countNodes(root *TreeNode) int {
14.  
    if root == nil {
15.  
    return 0
16.  
    }
17.  
    left, right := countHeight(root.Left), countHeight(root.Right)
18.  
    if left == right {
19.  
    return (1 << left) countNodes(root.Right)
20.  
    } else {
21.  
    return (1 << right) countNodes(root.Left)
22.  
    }
23.  
    }
24.  
     
25.  
    func countHeight(root *TreeNode) uint {
26.  
    if root == nil {
27.  
    return 0
28.  
    }
29.  
    return countHeight(root.Left) 1
30.  
    }
31.  
     
32.  
    func buildTree(nums []int) *TreeNode {
33.  
    if len(nums) == 0 {
34.  
    return nil
35.  
    }
36.  
    root := &TreeNode{Val: nums[0]}
37.  
    Queue := []*TreeNode{root}
38.  
    idx := 1
39.  
    for idx < len(nums) {
40.  
    node := Queue[0]
41.  
    Queue = Queue[1:]
42.  
    if nums[idx] != null {
43.  
    node.Left = &TreeNode{Val: nums[idx]}
44.  
    Queue = append(Queue, node.Left)
45.  
    }
46.  
    idx
47.  
    if idx < len(nums) && nums[idx] != null {
48.  
    node.Right = &TreeNode{Val: nums[idx]}
49.  
    Queue = append(Queue, node.Right)
50.  
    }
51.  
    idx
52.  
    }
53.  
    return root
54.  
    }
55.  
     
56.  
    func main() {
57.  
    nums := []int{1, 2, 3, 4, 5, 6}
58.  
    root := buildTree(nums)
59.  
    fmt.Println(countNodes(root))
60.  
    nums = []int{}
61.  
    root = buildTree(nums)
62.  
    fmt.Println(countNodes(root))
63.  
    nums = []int{1}
64.  
    root = buildTree(nums)
65.  
    fmt.Println(countNodes(root))
66.  
    }

输出：

6
0
1

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

这篇好文章是转载于：学新通技术网