Re: [閒聊] 每日leetcode
3479. Fruits Into Baskets III
跟昨天那題題目一樣
不過範圍變大, 所以不能暴力解
思路：
根據題目, 可以把這題簡化成
對每一個fruits[i], 找出所有值大於fruits[i]的basket
並且將fruits[i]放到其中index最小的basket
這樣就先把basket按照大小排序, 用basketIdx記錄原本的index經過排序後的順序
接著用二分搜尋法找到j,basket[j]是第一個 >= fruit[i]的basket
假設basket長度是n, 找出 j ~ n 這個區間內, basketIdx中最小的值
阿要找區間最小值, 那就用segmentTree
找到記得把這個值mark起來, 以防重複使用 , 如果找不到的話, ans就+1
最後回傳ans就好
golang code :
type segmentTree struct {
nums []int
array [][2]int
}
func buildTree(nums []int) *segmentTree {
n := len(nums)
array := make([][2]int, 4*n)
res := &segmentTree{nums, array}
res.build(0, 0, n-1)
return res
}
func (tree *segmentTree) build(node, l, r int) {
if r == l {
tree.array[node][0] = tree.nums[l]
tree.array[node][1] = l
return
}
m := l + (r-l)/2
tree.build(node*2+1, l, m)
tree.build(node*2+2, m+1, r)
if tree.array[2*node+1][0] > tree.array[2*node+2][0] {
tree.array[node][0], tree.array[node][1] = tree.array[2*node+2][0], tree.
array[2*node+2][1]
} else {
tree.array[node][0], tree.array[node][1] = tree.array[2*node+1][0], tree.
array[2*node+1][1]
}
}
func (tree *segmentTree) query(node, boundaryL, boundaryR, queryL, queryR int)
(int, int) {
if boundaryL > queryR || boundaryR < queryL {
return math.MaxInt64, -1
}
if boundaryL >= queryL && boundaryR <= queryR {
return tree.array[node][0], tree.array[node][1]
}
boundaryM := boundaryL + (boundaryR-boundaryL)/2
a, idxL := tree.query(node*2+1, boundaryL, boundaryM, queryL, queryR)
b, idxR := tree.query(node*2+2, boundaryM+1, boundaryR, queryL, queryR)
if a < b {
return a, idxL
}
return b, idxR
}
func (tree *segmentTree) modify(node, idx, val, l, r int) {
if l == r {
tree.array[node][0] = val
return
}
m := l + (r-l)/2
if idx <= m {
tree.modify(node*2+1, idx, val, l, m)
} else {
tree.modify(node*2+2, idx, val, m+1, r)
}
if tree.array[2*node+1][0] > tree.array[2*node+2][0] {
tree.array[node][0], tree.array[node][1] = tree.array[2*node+2][0], tree.
array[2*node+2][1]
} else {
tree.array[node][0], tree.array[node][1] = tree.array[2*node+1][0], tree.
array[2*node+1][1]
}
}
func numOfUnplacedFruits(fruits []int, baskets []int) int {
n := len(fruits)
basketsIdx, baskets2 := make([]int, n), make([]int, n)
for i := 0; i < n; i++ {
basketsIdx[i] = i
}
ans := 0
slices.SortFunc(basketsIdx, func(a, b int) int { return baskets[a] - baskets[
b] })
for idx := range basketsIdx {
baskets2[idx] = baskets[basketsIdx[idx]]
}
tree := buildTree(basketsIdx)
for _, fruitNum := range fruits {
idx := sort.SearchInts(baskets2, fruitNum)
if idx < n {
tmp, changedIdx := tree.query(0, 0, n-1, idx, n-1)
if tmp != math.MaxInt64 {
ans++
tree.modify(0, changedIdx, math.MaxInt64, 0, n-1)
}
}
}
return n - ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1754498493.A.E0A.html
推
08/07 00:41,
4月前
, 1F
08/07 00:41, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1492 之 1554 篇)：