今天 很難過 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://webptt.com/m.aspx?n=bbs/Marginalman/M.1787418392.A.507.html