Square第二轮电面 2015/10/1

Standard segment tree solution:

1. #include <iostream>
   
2. #include <vector>
   
3. #include <assert.h>
   
4. 
   
5. using namespace std;
   
6. 
   
7. struct Node {
   
8.     Node* left, *right;
   
9.     int start, end, maxHei;
   
10.     Node(int s, int e): start(s), end(e), maxHei(0), left(NULL), right(NULL) {}
    
11. };
    
12. 
    
13. class SegTree {
    
14. public:
    
15.     SegTree(int mr): minRange(1), maxRange(mr) {
    
16.         root = build(minRange, maxRange); // Initialize a range with height 0.
    
17.     }
    
18.    
    
19.     void drop(int position, int size) {
    
20.         int start = position, end = position + size - 1;
    
21.         int newHei = query(root, start, end) + size;
    
22.         modify(root, start, end, newHei);
    
23.     }
    
24.    
    
25.     int getHeight() {
    
26.         return root->maxHei;
    
27.     }
    
28.    
    
29. private:
    
30.     Node* root;
    
31.     int minRange, maxRange;
    
32.    
    
33.     Node* build(int start, int end) {
    
34.         if(start > end) return NULL;
    
35.         if(start == end) {
    
36.             Node* newnode = new Node(start, start);
    
37.             return newnode;
    
38.         }
    
39.         Node* node = new Node(start, end);
    
40.         int mid = start + (end - start) / 2;
    
41.         node->left = build(start, mid);
    
42.         node->right = build(mid+1, end);
    
43.         return node;
    
44.     }
    
45.    
    
46.     int query(Node* node, int start, int end) {
    
47.         if(!node) return INT_MIN;
    
48.         if(node->start >= start && node->end <= end) return node->maxHei;
    
49.         if(node->start > end || node->end < start) return INT_MIN;
    
50.         return max(query(node->left, start, end), query(node->right, start, end));
    
51.     }
    
52.    
    
53.     void modify(Node* node, int start, int end, int newHei) {
    
54.         if(node->start > end || node->end < start) return;
    
55.         if(node->start == node->end) {
    
56.             node->maxHei = newHei;
    
57.             return;
    
58.         }
    
59.         modify(node->left, start, end, newHei);
    
60.         modify(node->right, start, end, newHei);
    
61.         node->maxHei = max(node->left->maxHei, node->right->maxHei);
    
62.     }
    
63.    
    
64. };
    
65. 
    
66. int main(int argc, const char * argv[]) {
    
67.     int maxRange = 10;
    
68.     SegTree seg(maxRange);
    
69.     seg.drop(1, 2);
    
70.     seg.drop(5, 3);
    
71.     assert(seg.getHeight() == 3);
    
72.     seg.drop(2, 4);
    
73.     assert(seg.getHeight() == 7);
    
74.     seg.drop(8, 3);
    
75.     assert(seg.getHeight() == 7);
    
76.     seg.drop(1, 4);
    
77.     assert(seg.getHeight() == 11);
    
78.     seg.drop(7, 2);
    
79.     return 0;
    
80. }

复制代码

这题首先区间范围并没有给定。可能是 0 - DOUBLE_MAX。再者 position都是double的数字。所以segment tree似乎无法真正解决。

还没仔细学习线段树，自己先想了个方法来实现。基本思想就保存每次掉下来一个箱子之后他的start， end， 和height。然后根据height的高低来进行保存。从高往低，遍历每一个箱子。如果新掉下来的箱子start和end掉在某个箱子的位置范围内，就根据那个箱子的高度加上新的箱子的size得到新箱子的高度，然后保存。最后由于我们需要根据height来保存，所以要做一个排序。
时间复杂度有点高。drop是O(nlogn)， getHeight是O(1)。自己写了一些test case跑了一下没发现问题。请大神帮忙看一下。如果有问题，请留言。谢谢

1. class Solution:
   
2.         def __init__(self):
   
3.                 self.boxes = []
   
4. 
   
5.         def drop(self, pos, size):
   
6.                 start = pos
   
7.                 end = pos + size
   
8.                 if not self.boxes:
   
9.                         self.boxes.append([start, end, size])
   
10.                 else:
    
11.                         for i in xrange(len(self.boxes)-1, -1, - 1):
    
12.                                 s = self.boxes[i][0]
    
13.                                 e = self.boxes[i][1]
    
14.                                 h = self.boxes[i][2]
    
15.                                 if s < start < e or s < end < e:
    
16.                                         self.boxes.append([start, end, h + size])
    
17.                                         break
    
18.                                 if i == 0:
    
19.                                         self.boxes.append([start, end, size])
    
20.                 self.boxes.sort(key=lambda x: [x[2], x[0], x[1]])
    
21. 
    
22.         def getHeight(self):
    
23.                 if not self.boxes:
    
24.                         return 0
    
25.                 return self.boxes[-1][2]
    
26. 
    
27. s = Solution()
    
28. s.drop(1, 4)
    
29. s.drop(2, 3)
    
30. s.drop(1,1)
    
31. s.drop(6,10)
    
32. s.drop(10, 1)
    
33. print(s.getHeight())

复制代码