昨日leetcode

[sixB (6B)]

今天 很難過

phone interview被洗臉

久違打開力扣找手感QQ

今天的是easy 寫個昨天的

蠻好寫的 hard爽題==

很直覺的二分搜 交集加加減減 然後就找到了

我連compress都有想到 神了

using ll = long long;
class Solution {
public:
    void select(int k, vector<ll>& coins, vector<vector<ll>>& dst){
        int n = coins.size();
        std::string bitmask(k, 1);
        bitmask.resize(n, 0);
        //cout << endl << k << endl;

        vector<ll> cur;
        do {
            ll mul = 1;
            for (int i = 0; i < n; i++) // [0..n-1] integers
            {
                if (bitmask[i]) mul = lcm(mul, coins[i]);
            }
            dst[k].emplace_back(mul);
            //cout << mul << " ";
        } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
        ranges::sort(dst[k]);
        //compress(dst[k]);
    }
    void compress(vector<ll>& coins){
        int n = coins.size();
        for(int i = n-1; i > 0; i--){
            for(int j = 0; j < i; j++){
                if(coins[i] % coins[j] == 0){
                    //cout << "pop " << coins[i] << endl;
                    coins.erase(coins.begin() + i);
                    break;
                }
            }
            // coins[i] can be divide by coins[j] and no remain
        }
        //for(auto coin: coins) //cout << coin << " ";
        //cout << endl;
    }
    long long findKthSmallest(vector<int>& org_coins, int k) {
        vector<ll> coins(org_coins.begin(), org_coins.end());
        ranges::sort(coins);
        compress(coins);
        int n = coins.size();
        ll l = 0;
        ll r = coins[0];
        r *= (ll)k;
        // k of c[0], and r/c[1] of c[1]...
        vector<vector<ll>> combines(n+1);
        for(int i = 1; i <= coins.size(); i++){
            // select i coins
            select(i, coins, combines);
        }

        ll num = 0;
        while(l < r){
            ll m = l + (r-l)/2;
            //cnt <= m coin num
            ll cnt = 0;
            for(int i = 1; i <= n; i++){
                for(ll num: combines[i]){
                    if(num > m) break;
                    if(i&1) cnt += m/num;
                    else cnt -= m/num;
                }
            }
            if(cnt == k){
                r = m;
                break;
            }
            else if(cnt > k){
                r = m-1;
            }
            else if(cnt < k){
                l = m+1;
            }
        }
        //cout << r << endl;
        ll res = 0;
        for(int coin: coins){
            ll cnt = r/coin;
            res = max(res, cnt * coin);
        }
        return res;
    }
};


--
我覺得我真的是垃圾

面試前面20分鐘看著題目完全理解錯方向

HR一開始跟我說不考lc這種刷題的

要手搓底層套件

我就一直以為他想跟我討論架構

然後我就腦袋一片空白 靠杯這個我不會啊

問了一堆大方向的東西

他就跟我說你知道這個對解題沒幫助

我更茫了

愣在那邊不知道怎麼講話

時間快到了突然看懂要幹嘛

靠邀直接當leetcode題打就好了啊

但我那個時候剩十分鐘

更慌了 講個幾句他好像覺得我終於有點反應

然後我整個腦袋卡住

timesout

每次都是面完之後豁然開朗

為什麼這麼簡單都不會為什麼我這麼笨


但HR說的也沒錯

真的跟lc不一樣 他的題目我寫不出來
-----
Sent from JPTT on my iPad

--
很姆的咪

姆之咪

http://i.imgur.com/5sw7QOj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.194.11 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1787418392.A.507.html
→ sixB: 嗎的很久沒寫 coding style怎麼這麼像c啊醜死了
推 devilkool: 大師
推 oin1104: 大師