推 sustainer123: 打完週賽還有每日一題 充實的週末 06/16 12:03
推 JenniferLope: 大師 06/16 12:04
→ JIWP: 我沒打周賽，我爛，對不起 06/16 12:04
→ sustainer123: 我週賽陪跑的 每次都只寫得出前兩題 漬 06/16 12:05
→ JIWP: 我只寫的出第一題 06/16 12:06
推 oin1104: 我哭了 怎麼周賽有hard 每日也有 06/16 12:07
到底誰會在周日早上刷leetcode
330. Patching Array
有一個由小到大排序的array:nums
以及一個整數n
請問最少要往nums裡面插入幾個數字
才可以用nums裡的元素組合出1~n之間的所有元素?
思路:
假設cur是到nums[i]可以組合出的最大範圍1~cur
這時候如果nums[i+1]不是cur+1
就要想辦法組合出cur+1~nums[i+1]之間的元素
舉例來說:[1、2、10]
1、2可以組合出1~3之間的所有數
而第三個元素是10，所以你要想辦法湊出4~9
最直接的方法就是先加入4，這時你就可以組合出1~3+4
還缺8、9，所以再加入8，就可以組合出1~3+4+8
可以得出一個判斷式，當你的nums[i+1]>cur+1時
你就要插入cur+1，一直到nums[i+1]<=cur+1或是cur>=n
這樣就可以得到答案了
golang code：
func minPatches(nums []int, n int) int {
cur, ans, l := 0, 0, len(nums)
for i := 0; i < l; i++ {
for nums[i] > cur+1 {
cur += cur + 1
ans++
if cur >= n {
return ans
}
}
cur += nums[i]
if cur >= n {
return ans
}
}
for cur < n {
cur += cur + 1
ans++
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.34.11 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718510587.A.80E.html