Question

341. 扁平化嵌套列表迭代器

English Version

题目描述

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

• NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
• int next() 返回嵌套列表的下一个整数。
• boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。

你的代码将会用下述伪代码检测：

initialize iterator with nestedList
res = []
while iterator.hasNext()
  append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

 

示例 1：

输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 _next _直到 _hasNex_t 返回 false，_next _返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 _next _直到 _hasNex_t 返回 false，_next _返回的元素的顺序应该是: [1,4,6]。

 

提示：

• 1 <= nestedList.length <= 500
• 嵌套列表中的整数值在范围 [-106, 106] 内

解法

方法一：递归

根据题意要求可以将 NestedInteger 数据结构视作一个 N 叉树，当元素为一个整数时，该节点是 N 叉树的叶子节点，当元素为一个整数数组时，该节点是 N 叉树的非叶子节点，数组中的每一个元素包含子树的所有节点。故直接递归遍历 N 叉树并记录所有的叶子节点即可。

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#  def isInteger(self) -> bool:
#    """
#    @return True if this NestedInteger holds a single integer, rather than a nested list.
#    """
#
#  def getInteger(self) -> int:
#    """
#    @return the single integer that this NestedInteger holds, if it holds a single integer
#    Return None if this NestedInteger holds a nested list
#    """
#
#  def getList(self) -> [NestedInteger]:
#    """
#    @return the nested list that this NestedInteger holds, if it holds a nested list
#    Return None if this NestedInteger holds a single integer
#    """


class NestedIterator:
  def __init__(self, nestedList: [NestedInteger]):
    def dfs(nestedList):
      for e in nestedList:
        if e.isInteger():
          self.vals.append(e.getInteger())
        else:
          dfs(e.getList())

    self.vals = []
    dfs(nestedList)
    self.cur = 0

  def next(self) -> int:
    res = self.vals[self.cur]
    self.cur += 1
    return res

  def hasNext(self) -> bool:
    return self.cur < len(self.vals)


# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *   // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *   public boolean isInteger();
 *
 *   // @return the single integer that this NestedInteger holds, if it holds a single integer
 *   // Return null if this NestedInteger holds a nested list
 *   public Integer getInteger();
 *
 *   // @return the nested list that this NestedInteger holds, if it holds a nested list
 *   // Return null if this NestedInteger holds a single integer
 *   public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

  private List<Integer> vals;

  private Iterator<Integer> cur;

  public NestedIterator(List<NestedInteger> nestedList) {
    vals = new ArrayList<>();
    dfs(nestedList);
    cur = vals.iterator();
  }

  @Override
  public Integer next() {
    return cur.next();
  }

  @Override
  public boolean hasNext() {
    return cur.hasNext();
  }

  private void dfs(List<NestedInteger> nestedList) {
    for (NestedInteger e : nestedList) {
      if (e.isInteger()) {
        vals.add(e.getInteger());
      } else {
        dfs(e.getList());
      }
    }
  }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

/**
 * // 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) {
    dfs(nestedList);
  }

  int next() {
    return vals[cur++];
  }

  bool hasNext() {
    return cur < vals.size();
  }

private:
  vector<int> vals;
  int cur = 0;

  void dfs(vector<NestedInteger>& nestedList) {
    for (auto& e : nestedList) {
      if (e.isInteger()) {
        vals.push_back(e.getInteger());
      } else {
        dfs(e.getList());
      }
    }
  }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (this NestedInteger) IsInteger() bool {}
 *
 * // 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
 * // So before calling this method, you should have a check
 * func (this NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (this *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (this NestedInteger) GetList() []*NestedInteger {}
 */

type NestedIterator struct {
  iterator    []int
  index, length int
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
  result := make([]int, 0)
  var traversal func(nodes []*NestedInteger)
  traversal = func(nodes []*NestedInteger) {
    for _, child := range nodes {
      if child.IsInteger() {
        result = append(result, child.GetInteger())
      } else {
        traversal(child.GetList())
      }
    }
  }
  traversal(nestedList)
  return &NestedIterator{iterator: result, index: 0, length: len(result)}
}

func (this *NestedIterator) Next() int {
  res := this.iterator[this.index]
  this.index++
  return res
}

func (this *NestedIterator) HasNext() bool {
  return this.index < this.length
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   If value is provided, then it holds a single integer
 *   Otherwise it holds an empty nested list
 *   constructor(value?: number) {
 *     ...
 *   };
 *
 *   Return true if this NestedInteger holds a single integer, rather than a nested list.
 *   isInteger(): boolean {
 *     ...
 *   };
 *
 *   Return the single integer that this NestedInteger holds, if it holds a single integer
 *   Return null if this NestedInteger holds a nested list
 *   getInteger(): number | null {
 *     ...
 *   };
 *
 *   Set this NestedInteger to hold a single integer equal to value.
 *   setInteger(value: number) {
 *     ...
 *   };
 *
 *   Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *   add(elem: NestedInteger) {
 *     ...
 *   };
 *
 *   Return the nested list that this NestedInteger holds,
 *   or an empty list if this NestedInteger holds a single integer
 *   getList(): NestedInteger[] {
 *     ...
 *   };
 * };
 */

class NestedIterator {
  private vals: number[];
  private index: number;

  constructor(nestedList: NestedInteger[]) {
    this.index = 0;
    this.vals = [];
    this.dfs(nestedList);
  }

  dfs(nestedList: NestedInteger[]) {
    for (const v of nestedList) {
      if (v.isInteger()) {
        this.vals.push(v.getInteger());
      } else {
        this.dfs(v.getList());
      }
    }
  }

  hasNext(): boolean {
    return this.index < this.vals.length;
  }

  next(): number {
    return this.vals[this.index++];
  }
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * var obj = new NestedIterator(nestedList)
 * var a: number[] = []
 * while (obj.hasNext()) a.push(obj.next());
 */

// #[derive(Debug, PartialEq, Eq)]
// pub enum NestedInteger {
//   Int(i32),
//   List(Vec<NestedInteger>)
// }
struct NestedIterator {
  index: usize,
  vals: Vec<i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl NestedIterator {
  fn dfs(nestedList: &Vec<NestedInteger>, vals: &mut Vec<i32>) {
    for ele in nestedList.iter() {
      match ele {
        NestedInteger::Int(val) => vals.push(*val),
        NestedInteger::List(list) => Self::dfs(list, vals),
      }
    }
  }

  fn new(nestedList: Vec<NestedInteger>) -> Self {
    let mut vals = vec![];
    Self::dfs(&nestedList, &mut vals);
    Self {
      vals,
      index: 0,
    }
  }

  fn next(&mut self) -> i32 {
    let res = self.vals[self.index];
    self.index += 1;
    res
  }

  fn has_next(&self) -> bool {
    self.index < self.vals.len()
  }
}/**
 * Your NestedIterator object will be instantiated and called as such:
 * let obj = NestedIterator::new(nestedList);
 * let ret_1: i32 = obj.next();
 * let ret_2: bool = obj.has_next();
 */

方法二：直接展开

调用 hasNext 时，如果 nestedList 的第一个元素是列表类型，则不断展开这个元素，直到第一个元素是整数类型。 调用 Next 方法时，由于 hasNext() 方法已确保 nestedList 第一个元素为整数类型，直接返回即可。

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (this NestedInteger) IsInteger() bool {}
 *
 * // 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
 * // So before calling this method, you should have a check
 * func (this NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (this *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (this NestedInteger) GetList() []*NestedInteger {}
 */

type NestedIterator struct {
  nested *list.List
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
  nested := list.New()
  for _, v := range nestedList {
    nested.PushBack(v)
  }
  return &NestedIterator{nested: nested}
}

func (this *NestedIterator) Next() int {
  res := this.nested.Front().Value.(*NestedInteger)
  this.nested.Remove(this.nested.Front())
  return res.GetInteger()
}

func (this *NestedIterator) HasNext() bool {
  for this.nested.Len() > 0 && !this.nested.Front().Value.(*NestedInteger).IsInteger() {
    front := this.nested.Front().Value.(*NestedInteger)
    this.nested.Remove(this.nested.Front())
    nodes := front.GetList()
    for i := len(nodes) - 1; i >= 0; i-- {
      this.nested.PushFront(nodes[i])
    }
  }
  return this.nested.Len() > 0
}