推 oin1104: 你好厲害 送我模型 11/08 22:58
1611. Minimum One Bit Operations to Make Integers Zero
思路:
這題觀察一下可以知道
先考慮最左邊的是1的bit
想要讓 2^k 變成 0, 需要 2^(k+1) - 1次操作
在這個過程中 0 ~ 2^(k+1) - 1 的值都會出現
所以想要求將n變成0要幾次操作
要先知道讓n變成0, 跟0變成n需要的操作是一樣多次
假設n最左邊值是1的bit在第x位
那答案就會是 2^(x+1)-1 - minimumOneBitOperations(n - 2^x)
golang code :
func minimumOneBitOperations(n int) int {
if n <= 1 {
return n
}
k := 0
for i := 1; i <= n; i <<= 1 {
k++
}
return 1<<k-1 - minimumOneBitOperations(n-(1<<(k-1)))
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.179.245 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1762613720.A.A0B.html