12
返回列表 发新帖
楼主: xiaohao2
跳转到指定楼层
上一主题 下一主题
收起左侧

google挂经

🔗
小北637 2019-11-19 07:52:30 | 只看该作者
全局:
第一题G4G上有完整的解题思路,感觉最快就是segment tree的 n + logn了
(不知道楼主碰到的是不是🇮🇳面试官,他们好爱G4G的…)
回复

使用道具 举报

🔗
zhuanye3 2019-11-21 16:36:59 | 只看该作者
全局:
kzhu 发表于 2019-11-17 06:56
第一题可以用RMQ做。这是一个DP的算法,预处理时间nlgn,查询O(1)。思想是用一个dp(i,j)记录以i开头长度为2 ...

这个区间DP的想法真的妙啊!!!
回复

使用道具 举报

🔗
aegis_bing 2019-11-24 14:59:07 | 只看该作者
全局:
小北637 发表于 2019-11-19 07:52
第一题G4G上有完整的解题思路,感觉最快就是segment tree的 n + logn了
(不知道楼主碰到的是不是🇮 ...

请问G4G是?

评分

参与人数 1大米 +1 收起 理由
besimple1024 + 1 欢迎来一亩三分地论坛!

查看全部评分

回复

使用道具 举报

🔗
vanbasten23 2019-11-29 23:46:50 | 只看该作者
全局:

geekforgeek

评分

参与人数 1大米 +1 收起 理由
aegis_bing + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
张欣 2019-12-23 08:45:23 | 只看该作者
全局:
Round2可以先找N的约数,再call 846的function。
回复

使用道具 举报

🔗
betterztt 2020-1-2 12:10:00 | 只看该作者
全局:
xiaohao2 发表于 2019-11-16 11:22
求区间最大值不能像prefix sum那样做吧,最大值不像sum那样是简单的加和关系。预处理O(n^2)是指计算所有( ...

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

使用道具 举报

🔗
ypcu327 2020-2-19 12:25:33 | 只看该作者
全局:
想请问楼主 第二轮的第一题需要做到O(n)
如果排序的话 时间复杂度就至少是nlog(n)
回复

使用道具 举报

🔗
renbaoshan 2020-2-19 16:35:08 | 只看该作者
全局:
本帖最后由 renbaoshan 于 2020-2-19 16:52 编辑

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.     int query(SgNode* cur, int a, int b) {
  26.         if (!cur || a > b) {
  27.             return INT_MIN;
  28.         }
  29.         int s = cur->start, e = cur->end;
  30.         if (a > e || b < s) {
  31.             return INT_MIN;
  32.         }
  33.         if (a <=s && e <= b) {
  34.             return cur->val;
  35.         }
  36.         return max(query(cur->left, a, b), query(cur->right, a, b));
  37.     }
  38. public:
  39.     MaxValueQuerier(vector<int>& nums) {
  40.         int n = nums.size();
  41.         root = build(nums, 0, n - 1);
  42.     }

  43.     int query(int a, int b) {
  44.         return query(root, a, b);
  45.     }
  46. };
复制代码
回复

使用道具 举报

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表