• 341.扁平化嵌套列表迭代器 | N叉树的最大深度


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

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

    实现扁平迭代器类 NestedIterator :

    NestedIterator(List 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 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,1,2,1,1]。

    思路:N叉树,读到整数就放到结果数组里,读到列表就继续递归

    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 &getList() const;
    16. * };
    17. */
    18. class NestedIterator {
    19. private:
    20. vector<int> vals;
    21. vector<int>::iterator cur;
    22. void dfs(const vector &nestedList) {
    23. for (auto &nest : nestedList) {
    24. if (nest.isInteger()) //是整数,就添加到结果数组里
    25. {
    26. vals.push_back(nest.getInteger());
    27. }
    28. else //是列表,就继续递归
    29. {
    30. dfs(nest.getList());
    31. }
    32. }
    33. }
    34. public:
    35. NestedIterator(vector &nestedList) {
    36. dfs(nestedList);
    37. cur = vals.begin();//迭代器指向结果数组的第一个元素
    38. }
    39. int next() {
    40. return *cur++;
    41. }
    42. bool hasNext() {
    43. return cur != vals.end();//vals.end()指向数组最后一个元素的后一个位置
    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. */

     559.N叉树的最大深度

    给定一个 N 叉树,找到其最大深度。

    最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

    N 叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)。

    示例 1:

    输入:root = [1,null,3,2,4,null,5,6]
    输出:3

    1. /*
    2. // Definition for a Node.
    3. class Node {
    4. public:
    5. int val;
    6. vector children;
    7. Node() {}
    8. Node(int _val) {
    9. val = _val;
    10. }
    11. Node(int _val, vector _children) {
    12. val = _val;
    13. children = _children;
    14. }
    15. };
    16. */
    17. class Solution {
    18. public:
    19. int maxDepth(Node* root) {
    20. if(root==nullptr)
    21. return 0;
    22. int res=0;
    23. for(Node* child:root->children)
    24. {
    25. res=max(res,maxDepth(child));
    26. }
    27. return res+1;
    28. }
    29. };

  • 相关阅读:
    【webrtc】老版本的OnReceivedPayloadData 及VCMPacket
    JAVA --- Collectioncenter
    快速排序详解
    LabVIEW使用源代码控制
    android 12.0app应用卸载黑名单
    C++对象模型(14)-- 构造函数语义学:拷贝构造函数和赋值运算赋
    【无标题】
    axure制作菜单下拉、隐藏、点击选中效果
    【机器学习】21天挑战赛学习笔记(四)
    c++day4
  • 原文地址:https://blog.csdn.net/weixin_50437588/article/details/126237165