Re: [閒聊] 每日leetcode
2561. Rearranging Fruits
思路:
用一個map紀錄每個cost的數量, 如果再basket1就+1反之就-1
並紀錄最小的cost : minCost
每個cost的數量應該是偶數
如果是奇數就回傳-1
再來用一個array來放要交換的cost
把每個cost在map中紀錄的數量/2放到array裡
假設2有4個, 那只要把2個2放到array就好
把array進行排列, 因為是求最小cost
所以只要對array的前一半進行計算
如果array[i] < minCost*2, 答案就加上array[i]
反之就加上minCost*2
會這麼計算是因為
如果我要交換costA、costB, 有兩種方法
第1種是 costA、costB直接互換 , 這樣cost會是min(costA,costB)
第2種是 costA跟minCost互換、costB再跟minCost互換, 這樣cost是2*minCost
golang code :
func minCost(basket1 []int, basket2 []int) int64 {
rec := make(map[int]int, 0)
n, ans, minNum := len(basket1), 0, math.MaxInt64
for key := range basket1 {
rec[basket1[key]]++
rec[basket2[key]]--
}
arr := make([]int, 0, n)
for num, val := range rec {
tmp := abs(val)
if tmp&1 == 1 {
return -1
}
minNum = min(minNum, num)
for i := 0; i < tmp/2; i++ {
arr = append(arr, num)
}
}
slices.Sort(arr)
for i := 0; i < len(arr)/2; i++ {
if arr[i] > minNum*2 {
ans += minNum * 2
} else {
ans += arr[i]
}
}
return int64(ans)
}
func abs(num int) int {
if num > 0 {
return num
}
return -num
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.215.96 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1754126634.A.B1D.html
推
08/02 17:24,
4月前
, 1F
08/02 17:24, 1F
→
08/02 17:25,
4月前
, 2F
08/02 17:25, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1489 之 1548 篇)：