Re: [閒聊] 每日leetcode
3495. Minimum Operations to Make Array Elements Zero
思路:
從題目可以知道1個數字x要變成0需要花的次數
是取決於floor(log4(x)) + 1
假設位於 4^n ~ 4^(n+1) -1間的數字有i個
那需要花費的次數就為(n+1) * i
接著照上面的方法計算出每個query所需要的總次數 step
因為每次可以選兩個數次出來/4
所以要將step / 2, 如果是奇數還要再 + 1
最後算完所有query就可以得到答案了
golang code :
func minOperations(queries [][]int) int64 {
ans := 0
interval := make([][2]int, 0, 31)
for i := 0; i < 31; i++ {
interval = append(interval, [2]int{1 << (2 * i), 1<<(2*(i+1)) - 1})
}
for _, query := range queries {
n := int(log4(float64(query[1])))
l, r := -1, -1
s := 0
for l != query[0] {
l, r = max(interval[n][0], query[0]), min(interval[n][1], query[1])
num := (r - l + 1)
s += num * (n + 1)
n--
}
if s&1==1{
ans += s/2+1
}else{
ans += s/2
}
}
return int64(ans)
}
func log4(x float64) float64 {
return math.Log(x) / math.Log(4)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1757181252.A.9ED.html
討論串 (同標題文章)
完整討論串 (本文為第 1515 之 1548 篇)：