Re: [閒聊] 每日leetcode

[yam276 (虛構史學家)]

※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 330. Patching Array
: 有一個由小到大排序的array:nums
: 以及一個整數n
: 請問最少要往nums裡面插入幾個數字
: 才可以用nums裡的元素組合出1~n之間的所有元素?
: 思路:

看了破站視頻教學

就是可以倍數成長覆蓋範圍

然後看後面有沒有數字可以增加覆蓋

有就不用自己再增加新數字直接用

一旦超過n就可以收工


Code:

impl Solution {
    pub fn min_patches(nums: Vec<i32>, n: i32) -> i32 {
        let mut miss: i64 = 1;
        let mut added = 0;
        let mut i = 0;
        let len = nums.len();

        while miss <= n as i64 {
            if i < len && nums[i] as i64 <= miss {
                miss += nums[i] as i64;
                i += 1;
            } else {
                miss += miss;
                added += 1;
            }
        }

        added
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718538974.A.515.html
→ digua: 大師
→ yam276: 恨Hard
→ JIWP: 大師