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

news/2024/6/1 22:52:25 标签: golang, 动态规划, dfs, bfs, 二分法

目录

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： 暴力枚举

package main

import (
	"fmt"
)

func maximalSquare(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])
	maxLen := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				curLen := 1
				flag := true
				for k := 1; k+i < m && k+j < n && flag; k++ {
					for l := 0; l <= k; l++ {
						if matrix[i+k][j+l] == '0' || matrix[i+l][j+k] == '0' {
							flag = false
							break
						}
					}
					if flag {
						curLen++
					}
				}
				if curLen > maxLen {
					maxLen = curLen
				}
			}
		}
	}
	return maxLen * maxLen
}

func main() {
	matrix := [][]byte{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}
	fmt.Println(maximalSquare(matrix))
	matrix = [][]byte{{'0', '1'}, {'1', '0'}}
	fmt.Println(maximalSquare(matrix))
	matrix = [][]byte{{'0'}}
	fmt.Println(maximalSquare(matrix))
}

代码2： 动态规划

package main

import (
	"fmt"
)

func maximalSquare(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])
	maxLen := 0
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				if i == 0 || j == 0 {
					dp[i][j] = 1
				} else {
					dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
				}
				if dp[i][j] > maxLen {
					maxLen = dp[i][j]
				}
			}
		}
	}
	return maxLen * maxLen
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	matrix := [][]byte{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}
	fmt.Println(maximalSquare(matrix))
	matrix = [][]byte{{'0', '1'}, {'1', '0'}}
	fmt.Println(maximalSquare(matrix))
	matrix = [][]byte{{'0'}}
	fmt.Println(maximalSquare(matrix))
}

代码3： 动态规划优化

package main

import (
	"fmt"
)

func maximalSquare(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])
	maxLen := 0
	cur := make([]int, n)
	pre := make([]int, n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				if i == 0 || j == 0 {
					cur[j] = 1
				} else {
					cur[j] = min(pre[j], min(cur[j-1], pre[j-1])) + 1
				}
				if cur[j] > maxLen {
					maxLen = cur[j]
				}
			} else {
				cur[j] = 0
			}
		}
		cur, pre = pre, cur
	}
	return maxLen * maxLen
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	matrix := [][]byte{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}
	fmt.Println(maximalSquare(matrix))
	matrix = [][]byte{{'0', '1'}, {'1', '0'}}
	fmt.Println(maximalSquare(matrix))
	matrix = [][]byte{{'0'}}
	fmt.Println(maximalSquare(matrix))
}

输出：

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；否则，该树可以被分成一棵满二叉树和一颗子树，递归计算子树的节点数 

package main

import "fmt"

const null = -1 << 31

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var left, right uint
	left, right = 0, 0
	for node := root; node != nil; node = node.Left {
		left++
	}
	for node := root; node != nil; node = node.Right {
		right++
	}
	if left == right {
		return (1 << left) - 1
	} else {
		return countNodes(root.Left) + countNodes(root.Right) + 1
	}
}

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 main() {
	nums := []int{1, 2, 3, 4, 5, 6}
	root := buildTree(nums)
	fmt.Println(countNodes(root))
	nums = []int{}
	root = buildTree(nums)
	fmt.Println(countNodes(root))
	nums = []int{1}
	root = buildTree(nums)
	fmt.Println(countNodes(root))
}

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

代码2：bfs

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

package main

import "fmt"

const null = -1 << 31

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}
	q := []*TreeNode{root}
	count := 0
	for len(q) > 0 {
		size := len(q)
		count += size
		for i := 0; i < size; i++ {
			node := q[i]
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		q = q[size:]
	}
	return count
}

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 main() {
	nums := []int{1, 2, 3, 4, 5, 6}
	root := buildTree(nums)
	fmt.Println(countNodes(root))
	nums = []int{}
	root = buildTree(nums)
	fmt.Println(countNodes(root))
	nums = []int{1}
	root = buildTree(nums)
	fmt.Println(countNodes(root))
}

代码3：二分法

package main

import "fmt"

const null = -1 << 31

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left, right := countHeight(root.Left), countHeight(root.Right)
	if left == right {
		return (1 << left) + countNodes(root.Right)
	} else {
		return (1 << right) + countNodes(root.Left)
	}
}

func countHeight(root *TreeNode) uint {
	if root == nil {
		return 0
	}
	return countHeight(root.Left) + 1
}

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 main() {
	nums := []int{1, 2, 3, 4, 5, 6}
	root := buildTree(nums)
	fmt.Println(countNodes(root))
	nums = []int{}
	root = buildTree(nums)
	fmt.Println(countNodes(root))
	nums = []int{1}
	root = buildTree(nums)
	fmt.Println(countNodes(root))
}

输出：

6
0
1

🌟 每日一练刷题专栏 🌟

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

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

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

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

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

Rust每日一练 专栏

（2023.5.16~）更新中...

Golang每日一练 专栏

（2023.3.11~）更新中...

Python每日一练 专栏

（2023.2.18~2023.5.18）暂停更

C/C++每日一练 专栏

（2023.2.18~2023.5.18）暂停更

Java每日一练 专栏

（2023.3.11~2023.5.18）暂停更


http://www.niftyadmin.cn/n/367893.html

相关文章

C#，码海拾贝（23）——求解“复系数线性方程组“的“全选主元高斯消去法“之C#源代码，《C#数值计算算法编程》源代码升级改进版

C#，码海拾贝（23）——求解“复系数线性方程组“的“全选主元高斯消去法“之C#源代码，《C#数值计算算法编程》源代码升级改进版

using System; namespace Zhou.CSharp.Algorithm { /// <summary> /// 求解线性方程组的类 LEquations /// 原作 周长发 /// 改编 深度混淆 /// </summary> public static partial class LEquations { /// <summary&g…
阅读更多...
ubuntu安装搜狗输入法，图文详解+踩坑解决

ubuntu安装搜狗输入法，图文详解+踩坑解决

搜狗输入法已支持Ubuntu16.04、18.04、19.10、20.04、20.10&#xff0c;本教程系统是基于ubuntu18.04 一、添加中文语言支持 系统设置—>区域和语言—>管理已安装的语言—>在“语言”tab下—>点击“添加或删除语言”。 弹出“已安装语言”窗口&#xff0c;勾选中文…
阅读更多...
价值1000元的稀有二开版的无限坐席在线客服系统源码+教程

价值1000元的稀有二开版的无限坐席在线客服系统源码+教程

demo软件园每日更新资源,请看到最后就能获取你想要的: 1.价值1000元的稀有二开版的无限坐席在线客服系统源码教程 价值1000元的稀有二开版的无限坐席在线客服系统源码 直接一键安装的&#xff0c;启动两个端口就行了&#xff0c;安装倒是简单 类型&#xff1a;在线客服系统 …
阅读更多...
网站部署与上线（2）远程连接云服务器或虚拟机

网站部署与上线（2）远程连接云服务器或虚拟机

文章目录 搭建服务器部署环境配置pm2 可能听说过Windows系统提供的远程桌面。实际上&#xff0c;Linux中也提供了类似的功能&#xff0c;其远程连接基于命令行。 在Windows端连接Linux需要使用SSH软件&#xff0c;最流行的有Xshell和SecureCRT。 首先确定需要连接的云服务器或虚…
阅读更多...
web练习第二周

web练习第二周

前言&#xff1a;&#xff08;博主个人学习笔记&#xff0c;不用看&#xff09;web练习第二周&#xff0c;仅做出前3题。相比于第一周&#xff0c;难度大幅增加&#xff0c;写题时就算看了wp还是像个无头苍蝇一样到处乱创&#xff0c;大多都是陌生知识点&#xff0c;工具的使用…
阅读更多...
SpringBoot——原理（自动配置+原理分析-源码跟踪）

SpringBoot——原理（自动配置+原理分析-源码跟踪）

源码跟踪 从Springboot的启动类进入&#xff0c;进行分析. 源码跟踪技巧 在以后接触各种框架的时候&#xff0c;如果需要查看源码&#xff0c;需要找到关键点和核心流程&#xff0c;先在宏观对整个原理和流程有一个认识&#xff0c;之后再去了解其中的细节。 按住Ctrl左键进…
阅读更多...
ClickHouse安装部署

ClickHouse安装部署

—仅供学习 如有侵权 请联系删除– 一、下载 选择Tgz安装包安装 下载地址&#xff1a;Index of /clickhouse/tgz/ 选择stable目录下的安装包&#xff0c;采用21.9.4.35版本&#xff0c;分别是&#xff1a; [roothadoop08 resources]# ll 总用量 1023548 -rw-r--r--. 1 root …
阅读更多...
Redis五大基本数据结构（原理）

Redis五大基本数据结构（原理）

一、 Redis数据结构-String String是Redis中最常见的数据存储类型&#xff1a; 其基本编码方式是RAW&#xff0c;基于简单动态字符串&#xff08;SDS&#xff09;实现&#xff0c;存储上限为512mb。 如果存储的SDS长度小于44字节&#xff0c;则会采用EMBSTR编码&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023