Re: [閒聊] 每日leetcode

[sixB (6B)]

330.

原本想無腦bitset解==

n range to INT_MAX is too mean :(

開始想怎麼擺比較快

要怎麼不開格子 怎麼紀錄

原本想從n to 0

空格可以兩倍兩倍減

看到第一個test case 123, n=6

改成0 to n

可以兩倍+1 (the next)

實際做起來就是看他next *2什麼時候超過

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {

        sort(nums.begin(), nums.end());
        int res = 0;
        long long lln = n;
        long long next = 1;
        for(int i = 0; i < nums.size() and nums[i] <= lln; i++){
            if(next > lln) {
                //cout << '\n' << "next : " << next << " n : " << n;
                break;
            }
            while( next < nums[i]){
                next = next * 2 ;
                res++;
                //cout << next << ', ';
            }
            next += nums[i];
            //cout << next << '; ';
        }
        while(next <= lln ){
            next = next * 2 ;
            res++;
            //cout << next << '- ';
        }
        return res;
        /*
        bitset<100000> check;
        check[0] = true;
        //int all = nums[0];
        int res = 0;

        for(int i = 0; i< nums.size(); i++){
            //cout << check << '\n';
            check |= check << nums[i];
            //all += nums[i];
        }
        //cout << check;
        for(int i = 1; i <= n; i++){
            if(!check[i]){
                check |= check << i;
                res++;
            }
        }
        return res;
        */
    }

};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.51.8.50 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718569456.A.A13.html
推 Smallsh: 大師