目錄
221. 最大正方形 Maximal Square??????
222. 完全二叉樹的節(jié)點個數(shù) Count Complete Tree Nodes??????
?? 每日一練刷題專欄???
Rust每日一練 專欄
Golang每日一練 專欄
Python每日一練 專欄
C/C++每日一練 專欄
Java每日一練 專欄
221. 最大正方形 Maximal Square
在一個由?'0'?和?'1'?組成的二維矩陣內(nèi)，找到只包含?'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.lengthn == matrix[i].length1 <= 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：?動態(tài)規(guī)劃
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：?動態(tài)規(guī)劃優(yōu)化
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. 完全二叉樹的節(jié)點個數(shù) Count Complete Tree Nodes
給你一棵?完全二叉樹?的根節(jié)點?root?，求出該樹的節(jié)點個數(shù)。
完全二叉樹的定義如下：在完全二叉樹中，除了最底層節(jié)點可能沒填滿外，其余每層節(jié)點數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置。若最底層為第?h?層，則該層包含?1~2^h?個節(jié)點。
示例 1：
輸入：root = [1,2,3,4,5,6] 輸出：6
示例 2：
輸入：root = [] 輸出：0
示例 3：
輸入：root = [1] 輸出：1
提示：
- 樹中節(jié)點的數(shù)目范圍是
[0, 5 * 10^4] 0 <= Node.val <= 5 * 10^4- 題目數(shù)據(jù)保證輸入的樹是?完全二叉樹?
進(jìn)階：遍歷樹來統(tǒng)計節(jié)點是一種時間復(fù)雜度為?O(n)?的簡單解決方案。你可以設(shè)計一個更快的算法嗎？
代碼1： dfs
完全二叉樹，可以通過比較根節(jié)點左子樹高度和右子樹高度來確定它是否可以被視為完全二叉樹。如果左右高度相等，則該樹是滿二叉樹，節(jié)點個數(shù)為?2??12h?1；否則，該樹可以被分成一棵滿二叉樹和一顆子樹，遞歸計算子樹的節(jié)點數(shù)?
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))
}
注：位運算符?<<?要求右側(cè)的操作數(shù)必須為無符號整數(shù)類型。在 Go 語言中，如果左側(cè)操作數(shù)不是無符號整數(shù)，右側(cè)操作數(shù)必須用無符號整數(shù)類型轉(zhuǎn)換。?
代碼2：bfs
將根節(jié)點放入隊列中，然后對于隊列中的每一個節(jié)點，將它的左右子節(jié)點入隊，統(tǒng)計隊列的大小即為節(jié)點個數(shù)
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
?? 每日一練刷題專欄???
? 持續(xù)，努力奮斗做強刷題搬運工！
?? 點贊，你的認(rèn)可是我堅持的動力！?
???收藏，你的青睞是我努力的方向！?
? 評論，你的意見是我進(jìn)步的財富！??
??主頁：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.zghlxwxcb.cn/news/detail-473424.html |
文章來源：http://www.zghlxwxcb.cn/news/detail-473424.html到了這里，關(guān)于Golang每日一練(leetDay0079) 最大正方形、完全二叉樹節(jié)點數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
