输出倒逼思考

0%

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

发表于
分类于 ， Valine：
LeetCode 第 341 题“扁平化嵌套列表迭代器”题解及解题过程中的一丝小插曲。

0 前言

本文记录 LeetCode 第 341 题“扁平化嵌套列表迭代器”的求解过程，及遇到的一点小问题，原题链接。

1 题目描述

1.1 官方描述

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

1
2
3
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2:

1
2
3
输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

1.2 代码中的描述

上面是官方的文字描述，其实并不清晰，反而在代码里的注释说得很明白。大致是这样的：有一个 NestedInteger 类，这个类中有一个私有数据成员，这个数据成员可能是 int 型数字，也可能是元素类型为 NestedInteger 的 vector，NestedInteger 类同时提供下面的公有 API 可供外部调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 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;
};
  • 如果 NestedInteger 的数据成员是 int 型数字，则调用 isInteger 方法会得到 true，否则得到 false；
  • 如果 NestedInteger 的数据成员是 int 型数字，则调用 getInteger 方法会得到该数字，否则得到一个不确定值；
  • 如果 NestedInteger 的数据成员是元素类型为 NestedInteger 的 vector，则调用 getList 方法会得到该 vector，否则得到一个不确定值。

题目要求我们实现下面这样一个迭代器类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class NestedIterator {
  public:
      NestedIterator(vector<NestedInteger> &nestedList) {

      }

      int next() {

      }

      bool hasNext() {

      }
};

NestedIterator 类会被实例化并被这样调用：

1
2
NestedIterator i(nestedList);
while (i.hasNext()) cout << i.next();

其实就是想要得到输入的 nestedList 中的所有真正的数字，这和 1.1 中的描述就对应起来了，我们最终需要填充 NestedIterator 类中的构造函数、next 方法 和 hasNext 方法。

2 解题思路

题目的关键是将输入 nestedList 视作一个 N 叉树，这样题目便可以转化为 N 叉树的遍历问题，所有的叶子节点即所有的数字。例如，输入是[[1,1],2,[1,1]]，则其对应的 N 叉树结构为：

N 叉树举例

遍历的过程中，将得到的叶子节点值插入到一个 vector 中，用于被 next 方法间接调用输出数值。

3 代码实现

代码实现很简单，主要是新建递归方法 traverse、用于存储节点值的 result、用于遍历 result 的迭代器 iter：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class NestedIterator
{
public:
    NestedIterator(vector<NestedInteger> &nestedList)
        : result{},
          iter(result.begin())
    {
        traverse(nestedList);
    }

    int next()
    {
        return *(iter++);
    }

    bool hasNext()
    {
        return iter != result.end();
    }

private:
    std::vector<int> result;         // store all values of leaf nodes
    std::vector<int>::iterator iter; // iterstor of result

    /*
     * traverse the nestedList just like traversing a N tree, and store all values
     * in a vector
     */
    void traverse(vector<NestedInteger> &nestedList)
    {
        for (auto &item : nestedList)
        {
            if (item.isInteger())
                result.push_back(item.getInteger());
            else
                traverse(item.getList());
        }
    }
};

运行测试用例，然后报错了：😂

1
2
3
Line 830: Char 44: runtime error: applying non-zero offset 4 to null pointer (stl_iterator.h)
Line 830: Char 44: runtime error: applying non-zero offset 4 to null pointer (stl_iterator.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_iterator.h:835:44

向非空指针施加了数值为 4 的非零偏移量。根据错误信息很容易定位到 next 方法的函数体中：

1
return *(iter++);

应该是 iter 自增时出现了空指针自增的情况。在构造函数初始值列表中我们已经将 result 初始化为了空 vector，并将 iter 初始化为了 result 的首迭代器，此时 iter 确实尚且是个空指针，因为 result 为空，但 traverse 方法中我们向 result 插入了值啊！

问题其实在于，调用 traverse 更新 result 后，我们需要更新一下 iter 的值为 result 最新的首迭代器，使其脱离最初的空值，因为iter 不会随着 result 的更新而主动更新。小改一下代码即可 AC，时间复杂度 $\mathcal{O}(n)$，空间复杂度 $\mathcal{O}(n)$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class NestedIterator
{
public:
    NestedIterator(vector<NestedInteger> &nestedList)
        : result{},
          iter(nullptr)
    {
        traverse(nestedList);
        iter = result.begin();
    }

    int next()
    {
        return *(iter++);
    }

    bool hasNext()
    {
        return iter != result.end();
    }

private:
    std::vector<int> result;         // store all values of leaf nodes
    std::vector<int>::iterator iter; // iterstor of result

    /*
     * traverse the nestedList just like traversing a N tree, and store all values
     * in a vector
     */
    void traverse(vector<NestedInteger> &nestedList)
    {
        for (auto &item : nestedList)
        {
            if (item.isInteger())
                result.push_back(item.getInteger());
            else
                traverse(item.getList());
        }
    }
};

AC 结果如下：

  • 43/43 cases passed (8 ms)
  • Your runtime beats 83.97 % of cpp submissions
  • Your memory usage beats 44.22 % of cpp submissions (13.1 MB)

4 后记

用 vscode + LeetCode 插件刷题着实太香了。随着刷题量越来越大，笔记都放到 blog 上不太现实，可能需要找时间搭个 GitBook 专门用来放刷题笔记了，我的理解是 GitBook 和 Hexo 类似，都是基于 Node.js 的 markdown 静态渲染引擎，所以基本可以参考 blog 的搭建过程：

  • (a) 本地使用 vscode 撰写 markdown，通过 GitBook 引擎渲染成静态 HTML 文件；
  • (b) 将静态 HTML 文件 push 到远程服务器的 Git 仓库，触发 git hooks 将文件拷贝到服务器中预设的网页目录；
  • (c) DNS 服务商那里新建一个二级域名解析到远程服务器 IP，比如 gitbook.shipengx.com；
  • (d) 自定义 Nginx 配置，将新的二级域名解析目录指定到步骤 (b) 中的网页目录；
  • (e) 重启 Nginx，开始代理指向 gitbook.shipengx.com 的网络访问。
猜你喜欢
Thank you for your donate!