昨日leetcode
今天 很難過
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
--
很姆的咪
姆之咪
--