google挂经

第一题G4G上有完整的解题思路，感觉最快就是segment tree的 n + logn了
(不知道楼主碰到的是不是🇮🇳面试官，他们好爱G4G的…)

kzhu 发表于 2019-11-17 06:56
第一题可以用RMQ做。这是一个DP的算法，预处理时间nlgn，查询O(1)。思想是用一个dp(i,j)记录以i开头长度为2 ...

这个区间DP的想法真的妙啊！！！

小北637 发表于 2019-11-19 07:52
第一题G4G上有完整的解题思路，感觉最快就是segment tree的 n + logn了
(不知道楼主碰到的是不是🇮 ...

请问G4G是？

aegis_bing 发表于 2019-11-24 14:59
请问G4G是？

geekforgeek

Round2可以先找N的约数，再call 846的function。

xiaohao2 发表于 2019-11-16 11:22
求区间最大值不能像prefix sum那样做吧，最大值不像sum那样是简单的加和关系。预处理O(n^2)是指计算所有( ...

感觉可以用BIT做，只不过把区间sum 换成了区间的最大值
build tree的时间是O(n), query的时间是O(logn+k)

想请问楼主 第二轮的第一题需要做到O（n）
如果排序的话 时间复杂度就至少是nlog（n）

Round 1用segment tree
建树需要O(n) 每次query O(logn)

1. struct SgNode {
   
2.     int val;
   
3.     int start;
   
4.     int end;
   
5.     SgNode* left;
   
6.     SgNode* right;
   
7.     SgNode(int x, int s, int e): val(x), start(s), end(e), left(NULL), right(NULL) {}
   
8. };
   
9. class MaxValueQuerier {
   
10. private:
    
11.     SgNode* root;
    
12.     SgNode* build(vector<int>& nums, int s, int e) {
    
13.         if (s > e) {
    
14.             return nullptr;
    
15.         }               if (s == e) {
    
16.             return new SgNode(nums[s], s, e);
    
17.         }
    
18.         SgNode* cur = new SgNode(nums[s], s, e);
    
19.         int mid = s + (e - s)/2;
    
20.         cur->left = build(nums, s, mid);
    
21.         cur->right = build(nums, mid+1, e);
    
22.         cur->val = max(cur->left->val, cur->right->val);
    
23.         return cur;
    
24.     }
    
25. 
    
26.     int query(SgNode* cur, int a, int b) {
    
27.         if (!cur || a > b) {
    
28.             return INT_MIN;
    
29.         }
    
30.         int s = cur->start, e = cur->end;
    
31.         if (a > e || b < s) {
    
32.             return INT_MIN;
    
33.         }
    
34.         if (a <=s && e <= b) {
    
35.             return cur->val;
    
36.         }
    
37.         return max(query(cur->left, a, b), query(cur->right, a, b));
    
38.     }
    
39. public:
    
40.     MaxValueQuerier(vector<int>& nums) {
    
41.         int n = nums.size();
    
42.         root = build(nums, 0, n - 1);
    
43.     }
    
44. 
    
45.     int query(int a, int b) {
    
46.         return query(root, a, b);
    
47.     }
    
48. };

复制代码

kzhu 发表于 2019/11/17 06:56:11
第一题可以用RMQ做。这是一个DP的算法，预处理时间nlgn，查询O(1)。思想是用一个dp(i,j)记录以i开头长度为...

跟线段树复杂度一样的