Re: [閒聊] 每日leetcode
2471. Minimum Number of Operations to Sort a Binary Tree by Level
思路
就bfs並且用一個array記錄每一個level所有node的值
接著將array的值複製到另外一個矩陣copy_arr
再把copy_arr排列好
最後去比對array跟copy_arr的每個值
如果array[i]跟copy_arr[i]同
就去找array[i]在copy_arr的哪個index並且換過去
每換一次ans就+1
直到array[i]跟copy_arr[i]相等再將i+1去比較下一個值
這樣就可以得到答案了
golang code :
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minimumOperations(root *TreeNode) int {
queue := []*TreeNode{root}
ans := 0
for len(queue) > 0 {
cnt := len(queue)
arr := []int{}
for cnt > 0 {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
arr = append(arr, node.Left.Val)
queue = append(queue, node.Left)
}
if node.Right != nil {
arr = append(arr, node.Right.Val)
queue = append(queue, node.Right)
}
cnt--
}
tmp := make([]int, len(arr))
copy(tmp, arr)
slices.Sort(tmp)
swap := 0
i := 0
for i < len(arr) {
if arr[i] != tmp[i] {
j := sort.SearchInts(tmp, arr[i])
arr[i], arr[j] = arr[j], arr[i]
swap++
} else {
i++
}
}
ans += swap
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.132 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734957149.A.8AD.html
→
12/23 20:41,
11月前
, 1F
12/23 20:41, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1219 之 1554 篇)：