Re: [閒聊] 每日leetcode
已經沒有人寫了嗎
2197.
不知道幾個禮拜前的
寫錯好幾版還有MLE
終於改出來惹
2289ms 我真的好爛
醜醜ㄉ：（
class Solution {
public:
vector<int> replaceNonCoprimes(vector<int>& nums) {
vector<int> res;
int n = nums.size();
bool left = false;
bitset<100001> b1;
unordered_map<int, int> p1;
get_bp(nums[0], b1, p1);
for(int i = 1; i < n; i++){
bitset<100001> b2;
unordered_map<int, int> p2;
get_bp(nums[i], b2, p2);
if((b1 & b2).any()){
b1 |= b2;
comb_p(p1, p2);
left = true;
}
else if(left){
int rlen = res.size();
for(int j = rlen-1; j >= 0; j--){
bitset<100001> lb;
unordered_map<int, int> lp;
get_bp(res[j], lb, lp);
if((b1 & lb).any()){
b1 |= lb;
comb_p(p1, lp);
res.pop_back();
}
else{
left = false;
break;
}
}
left = false;
if((b1 & b2).any()){
b1 |= b2;
comb_p(p1, p2);
left = true;
}
else {
res.emplace_back(p2i(p1));
b1 = b2;
p1 = p2;
}
}
else {
res.emplace_back(p2i(p1));
b1 = b2;
p1 = p2;
}
}
if(left){
int rlen = res.size();
for(int j = rlen-1; j >= 0; j--){
bitset<100001> lb;
unordered_map<int, int> lp;
get_bp(res[j], lb, lp);
if((b1 & lb).any()){
b1 |= lb;
comb_p(p1, lp);
res.pop_back();
}
else break;
}
}
res.emplace_back(p2i(p1));
return res;
}
void comb_p(unordered_map<int, int>& p1, unordered_map<int, int>& p2){
for(auto [key, val]: p2){
p1[key] = max(p1[key], val);
}
}
void get_bp(int num, bitset<100001>& b, unordered_map<int, int>& p){
for(int i = 2; i*i <= num; i++){
while((num % i) == 0){
p[i]++;
b[i] = 1;
num /= i;
}
}
if(num > 1){
b[num] = 1;
p[num]++;
}
}
int p2i(unordered_map<int, int>& p){
int mul = 1;
for(auto [key, val]: p){
mul *= pow(key, val);
}
return mul;
}
bitset<100001> get_b(int num){
bitset<100001> b;
for(int i = 2; i*i <= num; i++){
while((num % i) == 0){
b[i] = 1;
num /= i;
}
}
if(num > 1){
b[num] = 1;
}
return b;
}
unordered_map<int, int> get_p(int num){
unordered_map<int, int> primes;
for(int i = 2; i*i <= num; i++){
while((num % i) == 0){
primes[i]++;
num /= i;
}
}
if(num > 1){
primes[num]++;
}
return primes;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.99.218 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1759084903.A.E9E.html
→
09/29 09:38,
2月前
, 1F
09/29 09:38, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1527 之 1548 篇)：