首页 > 求解答
头像
牛客95937762号
发布于 2021-05-15 13:20
+ 关注

求解答

1.     假设你的同事写了一个资源节点类KNode,它里面可能存着单个int(表示资源ID),也可能存着一个KNode列表,表示一组资源节点:
class KNode {
  value;

  constructor(v) {
    this.value = v;
  }

  getInt() {} // return number

  isInt() {} // return boolean

  getList() {} // return [KNode]: KNode对象的数组
}

现需要实现一个迭代器KNodeIterator,包含如下接口:

class KNodeIterator {
  kNodes;

  constructor(v) {
    this.kNodes = v; // 要求O(1)
  }

  hasNext() {} // return boolean 要求平均时间复杂度O(1): 大多数情况下O(1), 最坏情况下允许O(N

  next() {} // return number 要求O(1)
}

为简化这个问题,你仅需要正确支持迭代器的经典用例:

const iter = new KNodeIterator(kNodes);

while (iter.hasNext()) {
  const resourceId = iter.next();
  console.log('resourceId - ', resourceId);
}


提示: 迭代器需要在迭代(next/hasNext)的时候尽可能高效,在不迭代的时候(例如构造)不应过度使用计算资源

输入: [5,[4],[3,[]],[2,1]]
输出: [5,4,3,2,1]
解释: 所有数字和列表都需要用KNode包裹,注意空列表和嵌套空列表。上述输入将被这样构造:
const kNodes = new KNode([
  new KNode(5),
  new KNode([new KNode(4)]),
  new KNode([new KNode(3), new KNode([])]),
  new KNode([new KNode(2), new KNode(1)]),
]);

重复调用 next 直到 hasNext 返回falsenext 返回的元素的顺序应该是:[5,4,3,2,1]
 
输入: [1,[3,[7]],8]
输出: [1,3,7,8]



全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐