📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: waye_tt
跳转到指定楼层
上一主题 下一主题
收起左侧

Google电面4/17

🔗
yanshuining 2017-6-10 01:47:18 | 只看该作者
全局:
liuhuan2002767 发表于 2017-6-9 17:38
这题就是用线段树啊,成段更新

我面试也碰到过这题,一开始我用线段树解,但是面试官不满意,说,调用update的次数很少,所以我最后用了interval。
回复

使用道具 举报

🔗
codemonk 2017-8-26 11:24:49 | 只看该作者
全局:
写了 fenwick tree 和 segment tree with lazy propagation 两个解法。通过这题我学会了lazy propagation
  1. class FenwickTree{
  2. public:
  3.     // idea:
  4.     // 1. toggle [i,j] is equivalent to toggle [1,i] then toggle[1,j]
  5.     // 2. let tree[i] stores the **total number of toggles** in the corresponding binary range
  6.     // 3. for a bulb x,
  7.     //    (i) sum of toggles in [1,x] is odd, if x belongs to [i,j] and x being toggled odd times, i.e. [1,j] will covers x odd times, while [1,i] covers x even times (or 0 time).
  8.     //   (ii) sum of toggles in [1,x] is even, if x is out of[i,j] or x is in [i,j] && x being toggled even times.
  9.     FenwickTree(int n_) {
  10.         n = n_;
  11.         tree.resize(n+1, 0);
  12.     }
  13.     vector<int> tree;
  14.     int n;
  15.     void update(int i, int add) {
  16.         for(; i > 0; i -= i&(-i))
  17.             tree[i] += add;
  18.     }
  19.    
  20.     int query(int i) {
  21.         int ans = 0;
  22.         for(; i <= n; i += i&(-i))
  23.             ans += tree[i];
  24.         return ans;
  25.     }
  26.    
  27.     bool isOn(int i) {
  28.         return query(i) & 1;
  29.     }
  30.    
  31.     void toggle(int start, int end) {
  32.         update(start-1, 1);
  33.         update(end, 1);
  34.     }
  35.    
  36.     void run() {
  37.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  38.         cout << endl;
  39.         toggle(2,5);
  40.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  41.         cout << endl;
  42.         toggle(3,8);
  43.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  44.         cout << endl;
  45.         toggle(4,6);
  46.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  47.         cout << endl;
  48.     }
  49. };

  50. class SegmentTree{ // muse use lazy propagation to guarantee log(n) complexity for update() on a range of indices.
  51.     // worst case space complexity O(4*N) with lazy propagation.
  52.     // to learn lazy propagation: http://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/
  53. public:  
  54.     struct TreeNode{
  55.         int lb, ub, count;
  56.         TreeNode *left, *right;
  57.         TreeNode(int lb_, int ub_) {
  58.             lb = lb_;
  59.             ub = ub_;
  60.             count = 0;
  61.             left = right = nullptr;
  62.         }
  63.     };
  64.     TreeNode* root;
  65.     int n;
  66.     unordered_map<TreeNode*, int> lazy;
  67.    
  68.     SegmentTree(int n_) {
  69.         n = n_;
  70.     }
  71.    
  72.     TreeNode* build(int lb, int ub){
  73.         if(lb > ub) return nullptr;
  74.         TreeNode* node = new TreeNode(lb, ub);
  75.         if(lb == ub) return node;
  76.         int mid = lb + (ub - lb) / 2;
  77.         node->left = build(lb, mid);
  78.         node->right = build(mid+1, ub);
  79.         return node;
  80.     }
  81.    
  82.     void update(TreeNode* node, int lo, int hi, int add) {
  83.         if(lazy[node] != 0) {
  84.             node->count += (node->ub - node->lb + 1) * lazy[node];
  85.             if(node->left) lazy[node->left] += lazy[node];
  86.             if(node->right) lazy[node->right] += lazy[node];
  87.             lazy[node] = 0;
  88.         }
  89.         if(!node || node->ub < lo || node->lb > hi) return;
  90.         if(lo <= node->lb && node->ub <= hi) {
  91.             node->count += (node->ub - node->lb + 1) * add;
  92.             if(node->left) lazy[node->left] += add;
  93.             if(node->right) lazy[node->right] += add;
  94.             return;
  95.         }
  96.         update(node->left, lo, hi, add);
  97.         update(node->right, lo, hi, add);
  98.         node->count = (node->left ? node->left->count : 0) + (node->right ? node->right->count : 0);
  99.     }
  100.    
  101.     int query(TreeNode* node, int start, int end){
  102.         if(lazy[node] != 0) {
  103.             node->count += (node->ub - node->lb + 1) * lazy[node];
  104.             if(node->left) lazy[node->left] += lazy[node];
  105.             if(node->right) lazy[node->right] += lazy[node];
  106.             lazy[node] = 0;
  107.         }
  108.         if(!node || start > node->ub || end < node->lb) return 0;
  109.         if(start <= node->lb && node->ub <= end) return node->count;
  110.         return query(node->left, start, end) + query(node->right, start, end);
  111.     }
  112.    
  113.     void toggle(int start, int end) {
  114.         update(root, start, end, 1);
  115.     }

  116.     bool isOn(int i) {
  117.         return query(root, i, i) & 1;
  118.     }

  119.     void run() {
  120.         root = build(1, n);
  121.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  122.         cout << endl;
  123.         toggle(2,5);
  124.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  125.         cout << endl;
  126.         toggle(3,8);
  127.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  128.         cout << endl;
  129.         toggle(4,6);
  130.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  131.         cout << endl;
  132.     }
  133. };

  134. int main() {
  135.     FenwickTree ft(10); // 10 bulbs
  136.     ft.run();
  137.     cout << "----------" << endl;
  138.     SegmentTree st(10);
  139.     st.run();
  140. }
复制代码
回复

使用道具 举报

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

本版积分规则

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