364. Nested List Weight Sum II

I made a mistake in first place where I was trying to get the maximum level for each nested list. This will get sum -2 for case [[-1], [[-1]]], which is wrong. We actually only need to get the maximum level once and pass the maximum level decreasingly down along the nested list.

1:  /**  
2:   * // This is the interface that allows for creating nested lists.  
3:   * // You should not implement it, or speculate about its implementation  
4:   * class NestedInteger {  
5:   *  public:  
6:   *   // Return true if this NestedInteger holds a single integer, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class Solution {  
19:  private:  
20:    int max_depth = 0;  
21:  public:  
22:    int depthSumInverse(vector<NestedInteger>& nestedList) {  
23:      depth(nestedList, 1);  
24:      return helper(nestedList, max_depth);  
25:    }  
26:    void depth(vector<NestedInteger> &nestedList, int d) {  
27:      max_depth = max(d, max_depth);  
28:      for (int i = 0; i < nestedList.size(); i++) {  
29:        if (!nestedList[i].isInteger()) depth(nestedList[i].getList(), d+1);  
30:      }  
31:    }  
32:    int helper(vector<NestedInteger> &nestedList, int d) {  
33:      int sum = 0;  
34:      for (int i = 0; i < nestedList.size(); i++) {  
35:        if (nestedList[i].isInteger()) sum += d * nestedList[i].getInteger();  
36:        else sum += helper(nestedList[i].getList(), d-1);  
37:      }  
38:      return sum;  
39:    }  
40:  };  

339. Nested List Weight Sum

The problem requires a depth so I intuitively think of DFS. And yes, DFS works fine with this problem. The idea is loop through the input list, check if it is an integer. If so, add the integer to the sum. If not, recursively call itself and add the returned value to the sum. After I'm done with the loop, return the sum.

1:  /**  
2:   * // This is the interface that allows for creating nested lists.  
3:   * // You should not implement it, or speculate about its implementation  
4:   * class NestedInteger {  
5:   *  public:  
6:   *   // Return true if this NestedInteger holds a single integer, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class Solution {  
19:  public:  
20:    int depthSum(vector<NestedInteger>& nestedList) {  
21:      return helper(nestedList, 1);  
22:    }  
23:    int helper(vector<NestedInteger> &nestedList, int d) {  
24:      int sum = 0;  
25:      for (int i = 0; i < nestedList.size(); i++) {  
26:        if (nestedList[i].isInteger()) sum += d * nestedList[i].getInteger();  
27:        else sum += helper(nestedList[i].getList(), d+1);  
28:      }  
29:      return sum;  
30:    }  
31:  };  

341. Flatten Nested List Iterator

Since there could be a lot of nested list, the intuition is to use stack, i.e. stack up the nested list and deal with the most inner list first.
The idea is keep stacking up all the elements in the list until the top element in the stack is not a nested list any more.
So in the constructor, we stack up all the elements in the list. Since we call hasNext() before next(), we'll process the stack mainly in the hasNext() interface. We get the top element in the stack. There'll be two cases:

Case 1: top element is an integer.
This is the easiest case where we return true. Since the next() interface needs this element so we'll leave the pop action in next().

Case 2: top element is a list.
Now we need to get the list and pop out this element in the stack. And then push all the elements in the list into stack. And then go back and check the top element again.

1:  /**  
2:   * // This is the interface that allows for creating nested lists.  
3:   * // You should not implement it, or speculate about its implementation  
4:   * class NestedInteger {  
5:   *  public:  
6:   *   // Return true if this NestedInteger holds a single integer, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class NestedIterator {  
19:  private:  
20:    stack<NestedInteger> stk;  
21:  public:  
22:    NestedIterator(vector<NestedInteger> &nestedList) {  
23:      for (int i = nestedList.size()-1; i >= 0; i--) {  
24:        stk.push(nestedList[i]);  
25:      }  
26:    }  
27:    int next() {  
28:      int val = stk.top().getInteger();  
29:      stk.pop();  
30:      return val;  
31:    }  
32:    bool hasNext() {  
33:      while (!stk.empty()) {  
34:        NestedInteger cur = stk.top();  
35:        if (cur.isInteger()) return true;  
36:        stk.pop();  
37:        vector<NestedInteger> &list = cur.getList();  
38:        for (int i = list.size()-1; i >= 0; i--) {  
39:          stk.push(list[i]);  
40:        }  
41:      }  
42:      return false;  
43:    }  
44:  };  
45:  /**  
46:   * Your NestedIterator object will be instantiated and called as such:  
47:   * NestedIterator i(nestedList);  
48:   * while (i.hasNext()) cout << i.next();  
49:   */  

When I revisited this problem, I tried to flat the list in next() function as following. However, it will get a runtime error if the input is "[[]]". The reason is the hasNext() simply checks if the stack is empty and thus will return true here. But in fact, it should be false. So we must flat the list in hasNext() function. Also I made a syntax error in line 32.

1:  /**  
2:   * // This is the interface that allows for creating nested lists.  
3:   * // You should not implement it, or speculate about its implementation  
4:   * class NestedInteger {  
5:   *  public:  
6:   *   // Return true if this NestedInteger holds a single integer, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class NestedIterator {  
19:  private:  
20:    stack<NestedInteger> stk;  
21:  public:  
22:    NestedIterator(vector<NestedInteger> &nestedList) {  
23:      int n = nestedList.size();  
24:      for (int i = n-1; i >= 0; i--) {  
25:        stk.push(nestedList[i]);  
26:      }  
27:    }  
28:    int next() {  
29:      while (!stk.top().isInteger()) {  
30:        NestedInteger t = stk.top();  
31:        stk.pop();  
32:        vector<NestedInteger> &list = t.getList();  
33:        int n = list.size();  
34:        for (int i = n-1; i >= 0; i--) {  
35:          stk.push(list[i]);  
36:        }  
37:      }  
38:      int ret = stk.top().getInteger();  
39:      stk.pop();  
40:      return ret;  
41:    }  
42:    bool hasNext() {  
43:      return !stk.empty();  
44:    }  
45:  };  
46:  /**  
47:   * Your NestedIterator object will be instantiated and called as such:  
48:   * NestedIterator i(nestedList);  
49:   * while (i.hasNext()) cout << i.next();  
50:   */