城堡白嫖OA，似乎有了新题？

白嫖OA

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题翻了地里好久 一直没找到

我只写了naive的解法，大佬可以分享下思路

谢谢楼主 这个是fulltime SDE 的OA吗？现在已经在面fulltime了吗

claire612777 发表于 2021-5-5 02:03
谢谢楼主 这个是fulltime SDE 的OA吗？现在已经在面fulltime了吗

投的是fall的 intern

请问第一题的解法有么，谢谢啦

第一题在楼主链接的帖子那里回复了。

第二题：

1. const int N = 2e5;
   
2. 
   
3. vector<int> lightBulbs(vector<int> a, vector<int> &b) {
   
4. 
   
5.   // Linear time sieve
   
6.   int lp[N + 1];
   
7.   vector<int> pr;
   
8.   for (int i = 2; i <= N; ++ i) {
   
9.     if (lp[i] == 0) {
   
10.       lp[i] = i;
    
11.       pr.push_back(i);
    
12.     }
    
13.     for (int p : pr) {
    
14.       if (p > lp[i] || i * p > N) break;
    
15.       lp[i * p] = p;
    
16.     }
    
17.   }
    
18. 
    
19.   auto prime_factors = [&](int x) {
    
20.     unordered_set<int> ps;
    
21.     while (x != 1) {
    
22.       ps.insert(lp[x]);
    
23.       x /= lp[x];
    
24.     }
    
25.     return ps;
    
26.   };
    
27. 
    
28.   map<int, int> cnts;
    
29. 
    
30.   for (int x : b)
    
31.     for (auto p : prime_factors(x)) ++ cnts[p];
    
32. 
    
33.   for (int i = 0; i < a.size(); i ++)
    
34.     for (auto p : prime_factors(i + 1))
    
35.       a[i] = (a[i] + cnts[p]) % 2;
    
36. 
    
37.   return a;
    
38. }
    

复制代码

[i][i]时间复杂度 O(M + 2 N log M)，其中：O(M) 是筛法的复杂度 - https://cp-algorithms.com/algebra/prime-sieve-linear.html， O(2N logM) 是遍历两个数组的每个元素的质因数的复杂度。[/i][/i]