面经/LintCode/LeetCode题目想法和代码分享

开个贴子，记录并分享一些地里面经，LintCode和LeetCode题目的个人思路与代码。
地里的面经题目，我会给出原链接，完整的思路和代码。LintCode和LeetCode相关的代码大家都能找到，我就不贴自己的了。主要是分享一些我个人觉得难以注意到的题目相关的知识点。
解题语言为C++，可能经常会涉及到一些C++独有的特性。
开贴的目的主要是分享并且督促懒惰的自己。争取每天至少分享两道题。
post的代码争取做到bug free，但我离大神差的很远，如果代码有bug或者针对某道题大家有更好的解法，欢迎指出，我定虚心接受。

littlebearull 发表于 2016-7-7 07:48
您好！看过这个题原贴中的回复，好像是说用TreeMap做（太复杂，我放弃了~）。这里楼主说用Treap ...

可能我原文没有解释清楚。其实Treap就是一种自平衡的BST。这道题用Treap或者普通的BST其实做法都是一样的，都是每个节点存一个额外的值，这个值为所有子结点加自身的数量，这个改造后的结构又称为Rank Tree。至于为什么会提到Treap，是因为Treap是自平衡搜索树中比较好实现的一种，在面试中有可能写出来。如果不用Treap，只实现普通的BST的话，findByRank的worst run time是O(n)。而Treap的自平衡性质保证了这个操作为O(logn)。不管Rank Tree是用Treap，BST还是Black-Red Tree来实现的，我们都还需要一个额外的hash table，key为id，value为pointer to tree node，来更新某个id所对应的score。
如果相同的score可以是不同的rank的，那key为score，但是相同的score我们不放在linked list里，而是应该容许node with duplicate key，就像STL里的multimap/multiset一样。

举例说明：
括号外的数为score，括号里的数为所有子节点加自己的数量(nodes)。
       3(6)
      /        \
    2(4)    4(1)
   /      \
  2(2)   2(1)
/
1(1)
我们首先想找rank为5的node。从root出发，我们知道整个树一共有6个nodes。root的左子树一共有4个nodes，root的右子树一共有1个nodes。所以我们可知root即是rank为5的root。
我们想找rank为4的node。从root出发，我们知道左子树一共有4个nodes，而且全部小于root，所以排名第四的肯定在root的左子树中。
然后我们以2(4)为root，知道以其为root的树一共有4个nodes，而其左子树有两个，所以rank为4的node肯定在右子树中。
而右子树只有一个点，我们可知2(1)即是rank为4的node。代码如下：

1. 
   
2. struct node {
   
3.   int id;
   
4.   int score;
   
5.   int nodes;
   
6.   node* left;
   
7.   node* right;
   
8. }
   
9. int findByRank(node* root, int rank) {
   
10.   if (!root || rank <= 0) {
    
11.     return -1;
    
12.   }
    
13.   int left_nodes = root->left ? root->left->nodes : 0;
    
14.   if (left_nodes >= rank) {
    
15.     return findByRank(root->left, rank);
    
16.   }
    
17.   rank -=left_nodes;
    
18.   if (rank == 1) {
    
19.     return root->id;
    
20.   }
    
21.   return findByRank(root->right, --rank)
    
22. }
    

复制代码

如果相同score相同rank也好办，每个node里可以有一个unordered_set来存同样score的id。findByRank代码是差不多一样的，只不过返回一系列score相同的一系列id。

当我们要删除某个score时，还是从root出发，每个经过的点的nodes--，这个操作跟正常从一个BST里删除node是基本一样的，runtime也为log(n)。更新score的话，我们可以先删除，再插入。
insertNode, deleteNode, findRank的代码就不写了。addUser的代码如下：

1. 
   
2. unorderd_map<int, node*> hash_;
   
3. node* root_;
   
4. 
   
5. //return pointer to newly inserted node
   
6. node* insertNode(node* root, int score);
   
7. 
   
8. void deleteNode(node* root, node* target);
   
9. 
   
10. //return rank
    
11. int findRank(node* root, node* target);
    
12. 
    
13. //return id
    
14. int findByRank(node* root, int rank);
    
15. 
    
16. int addUser(int id, int score) {
    
17.   auto it = hash_.find(id);
    
18.   if (it != hash_.end()) {
    
19.     deleteNode(root_, it->second);
    
20.   }
    
21.   hash_[id] = insertNode(root_, score);
    
22.   return findRank(root_, hash_[id]);
    
23. }

复制代码

如果相同的score是不同的rank且我们有很多duplicate key，我们其实可以用pair(score, id)作为Tree的key，主要用score来排序，如果score相同用id来排序，这样findRank这个操作还是O(logn)。我们还可以每个node有一个额外的timestamp，我们用pair(score, timestamp)作为Tree的key，这样相同的score，后插入的id会有lower/higher rank。
大概就是这样，如果还有哪儿没明白的话再告诉我。

yoo 发表于 2016-6-22 12:44
恩，具体找到[1,0] 和[4,2,3]的代码要怎么写呢？ input可以有n那么长，可以有k个这样的cycle

我们只需要知道有多少个cycle，每个cycle的长度是多少就可以了，代码如下

1. 
   
2. vector<int> findCycles(const vector<int>& in) {
   
3.   vector<int> res;
   
4.   int s = in.size();
   
5.   if (s == 0) {
   
6.     return res;
   
7.   }
   
8.   unordered_set<int> visited;
   
9.   for (int i = 0; i < s; ++i) {
   
10.     if (visited.find(i) != visited.end()) {
    
11.       continue;
    
12.     }
    
13.     visited.insert(i);
    
14.     int len = 1;
    
15.     int next = in[i];
    
16.     while (i != next) {
    
17.       visited.insert(next);
    
18.       ++len;
    
19.       next = in[next];
    
20.     }
    
21.     res.push_back(len);
    
22.   }
    
23.   return res;
    
24. }
    

复制代码

Helicopter Path
地里面经
详见snapchat跪经+面经合辑第三轮题目

这道题跟之前做过的Rain Path很相似，区别在于：
Rain Path是求从src到dst最高高度最小的路径。
Helicopter Path是求从src到dst高度之和最小的路径。其中路径上下一个点的高度必需不小于前一个点。

我的思路还是heap+bfs：
从src开始我们做bfs。heap顶端的点是目前高度之和最小的点，我们把它作为一次循环的起点，如果下一个点我们还没有走过，且它的高度>=现在点的高度，我们就把下一个点的高度与现在已经积累的高度之和相加，并把它添加到heap中。
如果下一个点我们已经走过，但是它的高度之和>我们从一条新的路径到达这个点的高度之和的话，我们就用较小的高度之和的取代原本的。如果这个点已经在heap中了，我们需要先把它从heap中删除，在把其新的高度之和插入heap中。这步操作有没有很眼熟？没错就是前几天LFU那道题中我提到过的hash heap。这道题很巧合的跟Rain Path和LFU都有思路上的重合。
下面的代码我“偷懒”了，还是用的multimap模拟的hash heap。

1. 
   
2. class Solution {
   
3. public:
   
4.         int minimumHeightsSum(const pair<int, int>& src, const pair<int, int>& dst, const vector<vector<int>>& matrix) const {
   
5.                 const vector<pair<int, int>> directions{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
   
6.                 int sum = 0;
   
7.                 int n = matrix.size();
   
8.                 if (n == 0) {
   
9.                         return 0;
   
10.                 }
    
11.                 int m = matrix.size();
    
12.                 if (m == 0) {
    
13.                         return 0;
    
14.                 }
    
15. 
    
16.                 unordered_map<int, int> visited;                                //key: index, value: cumulated sum
    
17.                 //below two data structue simulate hash heap
    
18.                 unordered_map<int, MyHeap::iterator> hash;                //key: index, value: position of index in heap
    
19.                 MyHeap heap;                                                                //key: cumulated sum, value: index
    
20. 
    
21.                 int src_index = src.first * n + src.second;
    
22.                 int dst_index = dst.first * n + dst.second;
    
23.                 visited[src_index] = matrix[src.first][src.second];
    
24.                 auto res_it = heap.emplace(visited[src_index], src_index);
    
25.                 hash[src_index] = res_it;
    
26.                 while (!heap.empty()) {
    
27.                         auto cur_it = heap.begin();
    
28.                         int cur_sum = cur_it->first;
    
29.                         int cur_x = cur_it->second / n;
    
30.                         int cur_y = cur_it->second % n;
    
31.                         for (const auto& d : directions) {
    
32.                                 int next_x = cur_x + d.first;
    
33.                                 int next_y = cur_y + d.second;
    
34.                                 int next_index = next_x * n + next_y;
    
35.                                 if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m && matrix[next_x][next_y] >= matrix[cur_x][cur_y]) {                        
    
36.                                         auto v_it = visited.find(next_index);
    
37.                                         if (v_it == visited.end()) {
    
38.                                                 //if next point has not been visited
    
39.                                                 int next_sum = cur_sum + matrix[next_x][next_y];
    
40.                                                 visited[next_index] = next_sum;
    
41.                                                 auto res_it = heap.emplace(visited[next_index], next_index);
    
42.                                                 hash[next_index] = res_it;
    
43.                                         }
    
44.                                         else {
    
45.                                                 int next_sum = v_it->second;
    
46.                                                 if (next_sum > cur_sum + matrix[next_x][next_y]) {
    
47.                                                         //if current next_sum > new next_sum
    
48.                                                         auto h_it = hash.find(next_index);
    
49.                                                         if (h_it != hash.end()) {
    
50.                                                                 //if next point is already in heap
    
51.                                                                 heap.erase(h_it->second);
    
52.                                                         }
    
53.                                                         visited[next_index] = cur_sum + matrix[next_x][next_y];
    
54.                                                         auto res_it = heap.emplace(visited[next_index], next_index);
    
55.                                                         hash[next_index] = res_it;
    
56.                                                 }
    
57.                                         }
    
58.                                         if (next_index == dst_index) {
    
59.                                                 return visited[dst_index];
    
60.                                         }
    
61.                                 }
    
62.                         }
    
63.                         hash.erase(cur_it->second);
    
64.                         heap.erase(cur_it);
    
65.                 }
    
66.                 return -1;
    
67.         }
    
68. 
    
69. private:
    
70.         using MyHeap = multimap<int, int, less<int>>;
    
71. };
    

复制代码

Bomberman
地里面经
详见G家面经，已跪第四轮题目

我们先假设input为一个n x m的matirx，每个element的值可以为-1/0/1。
-1 代表wall，0代表空位，可放炸弹，1代表敌人。
这道题最容易想到的肯定是暴力解法。思路为：
我们扫描整个matrix，当遇到一个可以放炸弹的空位时，我们水平往左扫，每遇到一个敌人，我们这个空位放置炸弹可以炸死的敌人数量就加一，直到我们遇到墙或者到头。同理，再水平向右，垂直上下扫。
扫描完整个matrix之后，我们便可以得到在某个位置放置炸弹能炸死最多敌人的数量。

我们很容易就可以发现暴力解法的话，我们会有很多重复的扫描，用下面的matirx做例
0 0 1 1 -1
1 1 -1 0 0
0 -1 0 0 1
1 1 1 1 1
我们放置炸弹在matrix[0][0]时，可炸死2（水平） + 2（垂直）个敌人。当我们扫描到matrix[0][1]时，我们这个时候并不知道垂直线上我们可以炸死多少人，但水平线上的结果是已知的。因matrix[0][0]和matrix[0][1]水平线上的结果是一样的。
当遇到重复计算的问题的时候，我们很容易就可以想到要用DP。
下面的代码是我个人使用DP的一种解法:

1. 
   
2. class Solution {
   
3. public:
   
4.         //0 empty
   
5.         //1 enemy
   
6.         //-1 wall
   
7.         int mostKills(const vector<vector<int>>& board) {
   
8.                 int res = 0;
   
9.                 int m = board.size();
   
10.                 if (m == 0) {
    
11.                         return res;
    
12.                 }
    
13.                 int n = board[0].size();
    
14.                 if (n == 0) {
    
15.                         return res;
    
16.                 }
    
17.                 vector <vector<pair<int, int>>> f(m + 1, vector<pair<int, int>>(n + 1, pair<int, int>(-1, -1)));
    
18.                 for (int i = 1; i <= m; ++i) {
    
19.                         for (int j = 1; j <= n; ++j) {
    
20.                                 if (board[i - 1][j - 1] == -1) {
    
21.                                         continue;
    
22.                                 }
    
23.                                 if (f[i][j - 1].second == -1) {
    
24.                                         f[i][j].second = 0;
    
25.                                         int k = j;
    
26.                                         while (k <= n && board[i - 1][k - 1] != -1) {
    
27.                                                 f[i][j].second += board[i - 1][k - 1];
    
28.                                                 ++k;
    
29.                                         }
    
30.                                 }
    
31.                                 else {
    
32.                                         f[i][j].second = f[i][j - 1].second;
    
33.                                 }
    
34.                                 if (f[i - 1][j].first == -1) {
    
35.                                         f[i][j].first = 0;
    
36.                                         int k = i;
    
37.                                         while (k <= m && board[k - 1][j - 1] != -1) {
    
38.                                                 f[i][j].first += board[k - 1][j - 1];
    
39.                                                 ++k;
    
40.                                         }
    
41.                                 }
    
42.                                 else {
    
43.                                         f[i][j].first = f[i - 1][j].first;
    
44.                                 }
    
45.                                 if (board[i - 1][j - 1] == 0) {
    
46.                                         res = max(res, f[i][j].first + f[i][j].second);
    
47.                                 }
    
48.                         }               
    
49.                 }
    
50.                 return res;
    
51.         }
    
52. }
    

复制代码

上面代码的一些值得注意的地方：
建立f时，我使用了n + 1和m + 1作为size，方便处理边界情况，这是大家都知道的DP题很常见的一个小技巧。
我存储的状态为pair<int, int>，其中first代表垂直能炸死敌人的数量，second代表水平能炸死敌人的数量。
当我们遇到空位时，我们会保存此时能炸死敌人的数量；当我们遇到敌人位时，我们还是会计算f，但不保存结果。
感觉上，f可用滚动数组进行空间上的优化。

补充内容 (2016-6-21 10:10):
19楼有这道题的另一个版本。
这道题LeetCode上已经有了No.361 Bomb Enemy

RainPath
地里面经
详见热乎的G家onsite面经第三轮题目

先假设这个问题是一维的，那么从src能够淹没到dst的日期取决于他俩之间最高的bar的高度。
转换为一个matrix的话，我们其实就是要找一条从src到dst的路径，这条路径上最高bar的高度越小越好。然后最短日期其实就是这条路径上最高bar的高度+1。
我们可以用BFS，然后把一般BFS其中的queue换成priority queue，在priority queue顶端的是当前未走过的高度最小的bar的index。

1. 
   
2. class Solution {
   
3. public:        
   
4.         int leastDays(const pair<int, int>& src, const pair<int, int>& dst, const vector<vector<int>>& matrix) const {
   
5.                 const vector<pair<int, int>> directions{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
   
6.                 int n = matrix.size();
   
7.                 if (n == 0) {
   
8.                         return 0;
   
9.                 }
   
10.                 int m = matrix.size();
    
11.                 if (m == 0) {
    
12.                         return 0;
    
13.                 }
    
14.                 int highest = matrix[src.first][src.second];
    
15.                 unordered_set<pair<int, int>, MyHash> visited;
    
16.                 priority_queue<pair<int, int>, vector<pair<int, int>>, MyComp> pq(MyComp{matrix});
    
17.         
    
18.                 visited.insert(src);
    
19.                 pq.push(src);
    
20.                 while (!pq.empty()) {
    
21.                         auto p = pq.top();
    
22.                         pq.pop();
    
23.                         int value = matrix[p.first][p.second];
    
24.                         highest = max(highest, value);        
    
25.                         for (const auto& d : directions) {
    
26.                                 pair<int, int> next(p.first + d.first, p.second + d.second);
    
27.                                 if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < m && visited.find(next) == visited.end()) {
    
28.                                         if (next == dst) {
    
29.                                                 highest = max(highest, matrix[dst.first][dst.second]);
    
30.                                                 return highest + 1;
    
31.                                         }
    
32.                                         int next_value = matrix[next.first][next.second];
    
33.                                         pq.push(next);
    
34.                                         visited.insert(next);
    
35.                                 }
    
36.                         }
    
37.                 }
    
38.                 return highest + 1;
    
39.         }
    
40. 
    
41. private:
    
42.         struct MyHash {
    
43.                 inline std::size_t operator()(const std::pair<int, int>& p) const {
    
44.                         return (hash<int>()(p.first) + hash<int>()(p.second));
    
45.                 }
    
46.         };
    
47. 
    
48.         class MyComp {
    
49.                 const vector<vector<int>>* matrix;
    
50.         public:
    
51.                 MyComp(const vector<vector<int>>& m) {
    
52.                         matrix = &m;
    
53.                 }
    
54.                 bool operator() (const pair<int, int>& rhs, const pair<int, int>& lhs) const {
    
55.                         int rhs_val = (*matrix)[rhs.first][rhs.second];
    
56.                         int lhs_val = (*matrix)[lhs.first][lhs.second];
    
57.                         return rhs_val != lhs_val ? rhs_val > lhs_val : rhs > lhs;
    
58.                 }
    
59.                
    
60.         };
    
61. };
    

复制代码

上面代码的一些值得注意的地方：
stl并未提供pair<int, int>的default hash function，需要自己建立一个。
MyComp是我自己建立的，用为给priority_queue使用的custom comparator。
我把matrix作为一个const reference传到了MyComp里，这样我只需要matrix元素的index就可以进行两个元素的比较，尽量节省了空间。
请注意这里：
priority_queue<pair<int, int>, vector<pair<int, int>>, MyComp> pq(MyComp{matrix});
我使用了{}来construct MyComp，如果直接写pq(MyComp(matrix))的话，不能compile。
因为MyComp overload了overprator ()，compiler会认为MyComp(matirx)是一个function call。

补充内容 (2016-6-21 10:11):
19楼有这道题的补充。

Longest Consecutive Sequence
LeetCode No.128

这道题我在讨论区里看到一个十分简短精妙的C++代码。代码如下：

1. 
   
2. int longestConsecutive(vector<int> &num) {
   
3.     unordered_map<int, int> m;
   
4.     int r = 0;
   
5.     for (int i : num) {
   
6.         if (m[i]) continue;
   
7.         r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1);
   
8.     }
   
9.     return r;
   
10. }
    

复制代码

我们先来分析一下代码：
用[100, 4, 200, 1, 3, 2]做例
当我们扫到4时，4此时并不在map里。
跳过if (m) continue;
此时m[i + 1] 和 m[i - 1]即m[5]和m[3]都不存在，m[i + 1] + m[i - 1] + 1 = 1
m[i - m[i - 1]] 即m[4 - m[3]] => m[4 - 0] => m[4] = 1
同理我们跳过m[i + m[i + 1]]
最后，m[4] == 1。
当我们扫到3时，
3虽然在map里，但m[3] == 0，还是跳过if (m) continue;
这时m[i + 1] + m[i - 1] + 1 => m[4] + m[2] + 1 = 1 + 0 + 1 = 2
m[i - m[i - 1]] => m[3 - m[2]] => m[3]
m[i + m[i + 1]] => m[3 + m[4]] => m[3 + 1] => m[4] = 2
最后, m[3] == 2, m [4] == 2
当我们扫到2时，
2虽然在map里，但m[2] == 0，还是跳过if (m) continue;
这时m[i + 1] + m[i - 1] + 1 => m[3] + m[1] + 1 = 2 + 1 + 1 = 4
m[i - m[i - 1]] => m[2 - m[1]] => m[1]
m[i + m[i + 1]] => m[2 + m[3]] => m[2 + 2] => m[4]
最后, m[1] == m[2] == m [4] == 4, m[3] == 2

这段代码虽然很精妙，但是我觉得要是在面试中这么写出来多半是给自己挖坑。
原因就在于，当 k 不在unorered_map里时，m[k]被假设值为0。
在c++ 官网上对于unorered_map的[] operator注解到

If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).

而对于int的default constructor返回的值是什么呢？0 or undefined?
这段代码确实在LeetCode和很多c++ compiler上运行的结果都是正确的。
但是我感觉如果面试官看到这种写法，肯定是要跟你扣C++的细节的。如果不是C++大神的话，这种坑还是不要给自己挖。

dg7743 发表于 2016-6-14 13:23
Bomberman
地里面经
详见G家面经，已跪第四轮题目

感觉写的好复杂，没有仔细看，为什么这里while (k <= n && board[i - 1][k - 1] != -1)还有个循环。直接从左上到右下遍历一次，从右下到左上遍历一次就可以了

dg7743 发表于 2016-6-14 13:41
RainPath
地里面经
详见热乎的G家onsite面经第三轮题目

这里你把x轴和y轴分开考虑写起来比你用pair会好，而且不用自定义hash，因为你是在一个matrix里面，所以直接可以把x和y映射到一维空间内（一一对应）。

ryancooper 发表于 2016-6-14 17:12
感觉写的好复杂，没有仔细看，为什么这里while (k

我也觉得我的写法不够简练。你可不可以再详细解释一下的你想法呢？

ryancooper 发表于 2016-6-14 17:15
这里你把x轴和y轴分开考虑写起来比你用pair会好，而且不用自定义hash，因为你是在一个matrix里面，所以直 ...

不太明白你说的“把x轴和y轴分开考虑写起来”的意思。我明白对于matrix问题，我们都可以做一个二维到一维的映射，即index = x * n + y。这里使用了pair也是平常没有注意到pair没有default hash的问题，做这道题时发现还有这么个情况就保留了这个写法。谢谢你的建议。

Flatten Nested List Iterator
LeetCode 341

这道题思路不难，但我觉得很考验面试者的C++水平
LeetCode已经提供了NestedInteger这个class，并且给出如下的API，让我们填写。

1. 
   
2. class NestedIterator {
   
3. public:
   
4.     NestedIterator(vector<NestedInteger> &nestedList) {
   
5.         
   
6.     }
   
7. 
   
8.     int next() {
   
9.         
   
10.     }
    
11. 
    
12.     bool hasNext() {
    
13.         
    
14.     }
    
15. };
    

复制代码

这个API有一个很大的问题，就是Java或者Python的iterator class确实是这样的，但C++ STL中的iterator可不是这样的API。
我在面试时遇到了这道题，当时还没有在LeetCode上刷到这道题。面试官是Java背景的，并且出题时并没有给我这么多细节，一切让我自己Design。
这道题很明显的体现了用C++面试，有时会自行提高难度。
首先我们来设计一下NestedInteger，我当时给出的答案大概是这样的：

1. 
   
2. class NestedInteger {
   
3.         class NestedInteger_node {
   
4.                 int val;
   
5.                 list<NestedInteger_node> *ptr;
   
6.         }；
   
7. 
   
8.         list<NestedInteger_node> l_;
   
9. 
   
10. }；
    

复制代码

list中每一个node要不然就是存有一个数字，要不然它其中的ptr不为nullptr，指向另一个list。
然后NestedIterator又该长怎么样呢？我们当然可以用LeetCode提供的API，但你如果面的是一个很看重C++水平的公司，如Bloomberg，多半会给面试官不熟悉STL的感觉。
所以我们来仿照STL设计API（给我出这道题的公司并不是用C++）。
首先我们在使用STL容器的iterator时，一般都是类似这么使的：
map<int, int> m;
......
for (map<int, int>::iterator it = m.begin(); it  != m.end(); ++it) {
*it
......
可以看出iterator是嵌套在容器里的。我们需要begin()，和end()来获得iterator的首尾。我们需要overload operator++和operator*。
所以我们的NestedIterator大概应该长这样：

1. 
   
2. class NestedInteger {
   
3. public:        
   
4.         class iterator {
   
5.         public:
   
6.         
   
7.                 friend class NestedInteger ;
   
8.                
   
9.                 iterator() {
   
10.                 }
    
11.                
    
12.                 //pre
    
13.                 iterator& operator++() {
    
14.                 }
    
15. 
    
16.                 //post
    
17.                 iterator operator++(int) {
    
18.                 }
    
19. 
    
20.                 int& operator*() {
    
21.                 }
    
22.         };
    
23.         
    
24.         iterator begin() {
    
25.         }
    
26. 
    
27.         iterator end() {
    
28.         }
    
29.         
    
30. private:
    
31.         class NestedInteger_node {
    
32.                 int val;
    
33.                 list<NestedInteger_node> *ptr;
    
34.         }；
    
35. 
    
36.         list<NestedInteger_node> l_;
    
37. };
    

复制代码

我面试的时候写完了operator++和operator*，这两个相当于next()和hasNext()。但是我们可以看出如果这道题如果要精益求精的，其难度要比LeetCode所给的API要高出不少。
有很多细节需要注意，比如overload operator时pre++和post++对应的function是什么? end() 返回的iterator结尾应该如何设计？因为我们要比较 it != end()，我们是不是还需要overload operator!= ?
这些细节在我们在LeetCode上实现时是不用考虑的，但你如果面试的是一家看重C++的公司，被问了这道题，并且你也表明C++是你的主语言的话。这些还是很重要的，至少会是加分的（当然如果对某些地方不熟悉，不要自行挖坑）。
当我们dereferrence iterator时，返回的是容器中某个元素的referrence，我们可以修改这个元素的值。这道题虽然无所谓，但是有些类似的设计iterator的题，我们只是想按某种规定的顺序读取容器，并不想对其进行修改的话，我们应该实现的是const_iterator。这也是一个值得注意的细节。

dg7743 发表于 2016-6-15 10:51
Flatten Nested List Iterator
LeetCode 341

如果真是考察你的C++的话，你写的Iterator其实准确来说要继承自std::iterator，同时你得指定你的iterator所属的category。按照你现在的写法，是不能和符合STL container定义的容器一起用的。所以面试的时候按照Java那种接口的设计其实就挺好的了。