339. Nested List Weight Sum
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list[[1,1],2,[1,1]], return10. (four 1's at depth 2, one 2 at depth 1)
Example 2:
Given the list[1,[4,[6]]], return27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)
S: DFS O(N)
class Solution {
public:
int depthSum(vector<NestedInteger>& nestedList) {
return getDepth(nestedList, 1);
}
int getDepth(vector<NestedInteger>& nestedList, int depth) {
int result = 0;
for (const auto& i : nestedList) {
if (i.isInteger()) {
result += i.getInteger() * depth;
} else {
vector<NestedInteger> next = i.getList();
result += getDepth(next, depth + 1);
}
}
return result;
}
};
364. Nested List Weight Sum II
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Different from theprevious questionwhere weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.
Example 1:
Given the list[[1,1],2,[1,1]], return8. (four 1's at depth 1, one 2 at depth 2)
Example 2:
Given the list[1,[4,[6]]], return17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)
S: 推到下层处理 O(n*k)
因为depth是自底而上的，初始层不能直接得到depth，逆向思维：
- 把初始层的integer值加到之后的每一层, 假设有n层，最终初始层integer的值为integer*n
- 合并next level，因为不知道最大depth，把所有比初始层低1层的nestedlist合并处理
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
return getSum(nestedList, 0);
}
int getSum(vector<NestedInteger> nestList, int intSum) {
vector<NestedInteger> next;
for (const auto i : nestList) {
if (i.isInteger()) {
intSum += i.getInteger();
}
vector<NestedInteger> curList = i.getList();
for (const auto& ne : curList) {
next.push_back(ne);
}
}
int listSum = next.size() > 0? getSum(next, intSum) : 0;
return listSum + intSum;
}
};
341. Flatten Nested List Iterator
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
S1: 用数组存储flatten后的结果再遍历
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (const auto& i : nestedList) {
pushResult(i);
}
idx = 0;
}
void pushResult(NestedInteger nest) {
if (nest.isInteger()) {
result.push_back(nest.getInteger());
} else {
vector<NestedInteger> lists = nest.getList();
for (const auto& i : lists) {
pushResult(i);
}
}
}
int next() {
int num = result[idx++];
return num;
}
bool hasNext() {
return idx < result.size();
}
private:
vector<int> result;
int idx;
};
S2： stack + iterator
用stack存储每层的begin()和end()
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
begins.push(nestedList.begin());
ends.push(nestedList.end());
}
int next() {
int num = begins.top()->getInteger();
begins.top()++;
return num;
}
bool hasNext() {
while (!begins.empty()) {
if (begins.top() == ends.top()) {
begins.pop();
ends.pop();
} else if (begins.top()->isInteger()) {
return true;
} else {
auto top = begins.top();
begins.top()++; //注意这里的顺序，先存储原来的top，再将top加1，再用原top访问下一层
begins.push(top->getList().begin());
ends.push(top->getList().end());
}
}
return false;
}
private:
stack<vector<NestedInteger>::iterator> begins, ends;
};