今天 很难过 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/cn.aspx?n=bbs/Marginalman/M.1787418392.A.507.html