Becomin' Charles

SIP 是 MacOS 的一项新特性，System Integrity Protection，系统完整性保护，主要用于阻止系统运行未授权的代码。除了通过 App Store 正规途径分发软件给用户，开发者还可以通过公正，直接分发软件给用户。除此以外的软件分发，都是不被授权的。

执行命令：

1

csrutil status

可以判断系统的 SIP 特性当前状态是否开启。

关机后重启进入恢复模式，才可以在命令行关闭 SIP 特性。

1

csrutil disable

可以关闭 SIP 特性，但是关闭 SIP，会导致系统处于某种危险状态中，这时候运行不安全的软件，就不会被系统阻止，要谨防系统遭到入侵。

重启进入恢复模式的方法是，启动时候，按住 ⌘+R 组合键。如果想要恢复 SIP 的话，还是需要进入恢复模式。执行 csrutil enable 就可以恢复 SIP 了。

学会了使用 Provider 后，真是感觉无比畅快，恨不得每个页面都替换成使用 Provider 来开发。不过今天遇到了一个问题：

1

Unhandled Exception: A SettingsProvider was used after being disposed.

场景是这样的，我有一个 SettingsProvider 保存着“设置”页面的状态，这个页面也就是一般的 App 用于放置“退出登录”按钮的，也正式这个功能引发了问题。

业务逻辑是这样的，当用户点击退出登录按钮的时候，为了防止连续重复请求，我会先把按钮设置成禁用，并展示 Indicator，然后，发起网络请求，去服务器注销 Push Alias，以及注销当前客户端的登录态。

注销成功，或者注销失败，我会解除按钮的禁用，而注销成功后，我会把页面跳转到 Login。这里有些很复杂的情况需要交代：

1. 注销 Push Alias 是在极光；
2. 注销成功后，才能在自己的 Server 注销 registration_id；
3. 完成操作 2，才可以去服务器注销本地登录态；
4. 完成操作 2，才可以销毁本地保存的登录态，不然无法执行 2（需要登录态）；
5. 操作 1 可能会阻塞整个流程导致最终无法退出登录；
6. 完成操作 4 后，需要跳转到 Login。

其实上面一些事情的操作顺序也好，约束条件也好，都还可以进一步推敲，我要说的是，当我执行到 6 的时候，爆了一个 Uncaught Exception，就是上面说的那个 A SettingsProvider was used after being disposed.

经过我在网上搜索和反复比对后我发现，这个错误的成因是这样的。我在网络请求成功或者失败的回调里，尝试解放退出按钮的状态，但是这个时候，异步的执行已经把整个页面给 Pop 掉了，导致了 Provider 的 Listener 提前被 dispose 了，这时候，再去 notifyListeners() 就会导致上面的问题。这个问题提示很难被理解，也很难解决。

网上一种说法，你需要把 Provider 放到更加高一层级的节点上去，这肯定不是一个正确的解，因为这个错误的发生不是 Provider 被销毁，而是因为页面跳走，Provider 的 Listener 被 dispose 导致的。

我用的解决办法是，在调用的时候，用 Provider 的属性 hasListeners 来提前判断一下，是否还有需要通知的对象，然后再调用 notifyListeners()，就不会引发这个错误了。

1
2
3
4
5
6
7
8
9
10
11
12
13

set isWaiting(bool val) {
  _isWaiting = val;
  if (hasListeners) {
    notifyListeners();
  }
}

set buttonValid(bool val) {
  _buttonValid = val;
  if (hasListeners) {
    notifyListeners();
  }
}

代码示例如上。上面这个问题的解决，给我的启示是，当进行异步编程的时候，各种任务同步或异步的发起并执行，各种任务结束的时刻不同，这时候决不能对任务完结的顺序有任何侥幸，否则会给程序代理很多不可预测的问题。

– UPDATE–

最近又遇到个问题，我也续在这里吧，跟这个问题对称的，也是调用方法的时候，报对象已经被 dispose 了，说对称，因为这回是 Provider 被 dispose 了。场景是这样的，在 Provider 里面，触发网络请求，网络请求是异步的，在网络请求回来后，处理完数据，调用 notifyListeners() 是比较常见的一种方法，但是因为这是一个异步的方法，所以，这时候，因为某些原因，Provider 自己已经被 dispose 了，同样会引起 Uncaught Exception。

这个情况怎么处理呢？我这里也写一个，不过未必是最好的，可能也是 SO 看到的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

_disposed = false;

@override
dispose() {
  _disposed = true;
  super.dispose();
}

void updateData() async {
  await DioUtils.instance.requestNetwork(
    url,
    onSuccess: (data) {
      // do something
      if (!_disposed) {
        notifyListeners();
      }
    },
    onError: (code, msg) {}
  );
}

...

这个方法使用一个类变量来记录 Provider 是否已经被 dispose，并在 dispose 的时候，改变值，这样就可以随时知道当前的 Provider 是否已经被 dispose 了。虽然不是很雅观，但是很直接地解决了问题。

– END –

以下内容来自网络：

为便捷纳税人开具增值税发票，提高发票开具效率和准确性，参照国家相关标准，采用QR码码制，制定本应用规范。

一、编码要求

（一）二维码编码格式采用信息容量大、可靠性高、保密防伪性强的QR码码制。

（二）本规范中QR码符号规格采用版本12（小于等于419字符）、18（大于419字符，小于等于816字符）和25（大于816字符，小于等于1451字符）规格，并根据内容长度自动匹配。

（三）本规范中QR码纠错信息能力等级采用M级别，可纠错15%的数据码字。

（四）本规范中的QR码编码字符集采用字母、数字、中文汉字方式进行编码。

二、编码内容和格式

便捷开票二维码编码内容如下：

编码格式字段说明表

便捷开票二维码内容格式如下：

　　起始符+版本号+base64（名称</>纳税人识别号</>地址电话</>开户行及账号</>CRC）+结束符

三、打印和显示要求

　　打印和显示二维码时，需遵循二维码大小、缩放比例的格式编排。

　　（一）二维码图案大小

　　 二维码图案大小的高度、宽度不小于2.0CM×2.0CM。

　　（二）二维码周边留白区域

　　二维码周围的空白区域宽度至少要大于10个码元宽度。

—完—

在一些特定的 App 里，我们不希望手机横屏的时候，App 发生旋转，比如微信，企业微信都是这样的。

代码可以这样设定：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import 'package:flutter/services.dart';

void main() async => {
  WidgetsFlutterBinding.ensureInitialized();
  await SystemChrome.setPreferredOrientations(
    [
      DeviceOrientation.portraitUp,   // 竖屏 Portrait 模式
      DeviceOrientation.portraitDown,
      // DeviceOrientation.landscapeLeft, // 横屏 Landscape 模式
      // DeviceOrientation.landscapeRight,
    ],
  );
  runApp(MainApp());
};

在 main 函数里，像上面那样设定，就可以做到全局禁用横屏模式了。

不过，在企业微信里，我发现，并不是彻底禁用了横屏模式，如果我在企业微信内部打开了一个网页，这种场景下，就是可以横屏过来用的。也就是，WebView 的场景下，我是可以横屏的，但是在其他界面下不可以横屏。这要怎么设置呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

@override
void initState() {
  super.initState();
  SystemChrome.setPreferredOrientations([
    DeviceOrientation.landscapeLeft,
    DeviceOrientation.landscapeRight,
    DeviceOrientation.portraitUp,
    DeviceOrientation.portraitDown,
  ]);
}

@override
void dispose() {
  SystemChrome.setPreferredOrientations([
    DeviceOrientation.portraitUp,
    DeviceOrientation.portraitDown,
  ]);
  super.dispose();
}

像这样，设置到一个 StatefulWidget 的 initState 和 dispose 里面就可以了。比如在我的代码里，我把 WebView 专门封装了一个页面，叫 WebPage，这样设定后，当用户进入网页的时候，可以横屏，但是退回后，就会强制恢复竖屏。

参考：http://kmanong.top/kmn/qxw/form/article?id=2735&cate=93

参考：https://stackoverflow.com/questions/49418332/flutter-how-to-prevent-device-orientation-changes-and-force-portrait

候选人来公司面试，我要求必须考察代码功力，一般我自己喜欢考个简单的算法题，有个同事，他喜欢考候选人写一个单例模式。单例模式可能是所有设计模式里，最最常用和常见的一个模式了。

在命令行执行：

1

xcrun simctl io booted recordVideo filename.mov

录制完毕后，使用⌃ + C 终止录制。

还有一种方法，使用 QuickTime 的录屏功能，可以录制指定的屏幕区域。

这道题目意思很简单，给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。本质上就是求，出现频次最高的数组元素，这在日常工作中也很常见。题目见传送门。

这道题，很有意思，也很无聊。很有意思是说，如果不让用类库的话，那么涉及到几种基础的数据结构和算法。如果让用类库的话，那么写起来也没什么难的，前提是你对类库足够熟悉的话，60 秒内绝对可以写出来。问题是，你不熟！

解题思路的话是这样的，首先，咱们必须统计出每个元素的出现频率。这里用到的数据结构是哈希表，通过哈希表，我们可以反复在 O(1) 时间内检索一个值。以数组元素作 key，元素的出现频率作 value，用 O(n) 的时间，可以完成对每个元素出现频率的统计。

然后，第二个步骤，方法就比较多了，如何找到频率最高的前 k 个元素呢？因为第一步有了哈希表，我们会有一些 <num, frequency> 的数值对，显然，要找到频次最高的前 k 个元素，最显然的办法，就是按照 frequency 进行排序，降序。然后取前 k 个 num 即可。

第二个方法，我们知道，可以使用到一个数据结构叫堆。我们可以构造一个最小堆，堆的大小是 k，然后，我们把数值对往堆里插，堆满了以后，堆顶就是到目前位置频次最低的元素。如果出现一个比堆顶频次大的元素，我们就把堆顶元素给换掉，最后我们就会得到频次最高的前 k 个元素。

第三个方法，我们可以用快速排序的 partition 方法，快速排序的原理是，找到一个分割点，然后把小于分割点的数字移到分割点前面，把大于分割点的数字移到分割点后面，最后计算出分割点的位置 k，这个就是第 k 大的元素。那么显然，分割点及以前的元素，就是前 k 个（降序原理相同）。

上面三个算法都很基础，都可以经常写写以保持手熟，其实建堆也好，partition 也好，都不是很好写的，知道原理很简单，写起来很不容易写对。

这篇文章想谈谈，用 Python 的类库怎么写，像我刚认真研究 Python 没几个月，就极其不熟练，基本可以说，离开了文档，我就寸步难行，很多基本的 API 都背不出来。就很惭愧。

我们显然可以用最基础的 dict 来统计元素的频次：

1
2
3
4
5
6

d = {}
for n in nums:
    if not d.get(n, False):
        d[n] = 1
    else:
        d[n] += 1

这个基础的 dict 的问题是，一开始，字典是空的，没有初始化，所以，每次操作，总要判断字典是否包含当前元素。这就给写代码带来很大的麻烦，如果字典可以初始化好，get 的时候，没有 key 就返回 0，有 key 就返回对应的值就好了。

其实，Python 里给我们提供了一个现成的数据结构，就叫 Counter。

1
2
3
4

import collections
freq = collections.Counter()
for n in nums:
    freq[n] += 1

大家看到，这个数据结构在使用的时候就方便多了。其实，还可以更方便，就是 freq = collections.Counter(nums) ，没错，在构造函数里直接搞定。那统计这个步骤就会非常简洁。

第二个步骤，排序，怎么做呢？其实这里有很多的写法。

1
2

res = sorted(freq.items(), key=lambda x: x[1], reverse=True)[:k]
return [x[0] for x in res]

我们提取哈希表的键值对为一个 list，然后外面用 sorted 进行排序，然后截取前 k 个，最后提取键生成了结果。

其实字典作为 iterateble 类型，本来就可以直接排序，但是，默认情况下，排序一个字典，返回的时候 key 的列表。而且是按照 key 值进行排序的。怎么写才能按照 value 排序呢？

1
2

res = sorted(freq, key=freq.get, reverse=True)[:k]
return res

于是，这么写比上面又简洁了点。我们直接用字典的值倒序排，然后返回字典的键列表，等于一行答案就出来了。

假如，你想用堆来解决问题，那就不得不用到 heapq 这个包。但是这个包一般的几个 API，heapify 也好，heappop，heappush，都是只接受一个值 item 和一个值的列表。对于这个场景来说，我们要操作的是 <num, frequency> 的数值对，就很麻烦，因为数值对有其默认的比较规则，这比较规则还不符合我们的需要，还要进行一些处理。

1
2
3
4
5
6
7
8
9
10
11

import heapq
h = []
l = [(v, k) for k, v in freq.items()]
for ele in l:
    if len(h) < k:
        heapq.heappush(h, ele)
    else:
        if ele[0] > h[0][0]:
            heapq.heappop(h)
            heapq.heappush(h, ele)
return [x[1] for x in h]

这里进行了多少种 trick 处理呢？

1. 将<键, 值> 对颠倒过来，因为这个 tuple 在 Python 里是按照前后顺序先后比较排序的；
2. 这里我们只用了 push 和 pop 两种 API，正好用的是最小堆，如果要用最大堆，在 Python 里是没有的，只能给值加 负号。如果我们要用 heapify 对堆进行整理，就要在 v 上加负号。

其实，在 heapq 里有更简单的 API，就是 nlargest：

1
2

import operator
heapq.nlargest(k, freq.items(), key=operator.itemgetter(1))

其实 heapq，直接就可以求前 K 大元素。这里的 key，我用了 operator.itemgetter 的这个高阶函数，当然，大家知道，这里可以写 lambda 算子的 lambda x: x[1] 。这样，我们就算用堆，也可以写得很简洁。

最后，我们回过头去看一眼 Counter 的，其实 Counter 有个 API，是 most_common(k)，那更简单：

1

return [x[0] for x in collections.Counter(nums).most_common(k)]

最后，变成了一行流，用 Counter 以及 most_common 接口，配合列表生成式，直接搞定了。

这就是为什么，人生苦短，我用 Python！其实，这个东西这么写法，这么多等价用法，难道没违背 Python 之禅么？

如题，题目意思非常简单，就是写一个二叉树的中序遍历。如果我们用递归来实现，简直太简单了。

1
2
3
4
5
6
7
8
9
10

class Solution:
    def __init__(self):
        self.res = []
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return self.res
        self.inorderTraversal(root.left)
        self.res.append(root.val)
        self.inorderTraversal(root.right)
        return self.re

算法思路极其明确，中序遍历左子树，然后遍历根节点，然后中序遍历右子树，打完收工。这个算法的时间复杂度也很好分析，因为每个节点刚好访问了一次，所以复杂度是 O(n)。那么空间复杂度是多少呢？

咱们先来看看，如果我们要用迭代法写一个二叉树的中序遍历，应该怎么写呢？我们都知道，递归是利用函数调用隐含的栈，保存了中间的现场，如果我们要用迭代法，需要手动来控制栈，我原本以为这是手到擒来的一个过程，可以随手写出来的，没想到，我栽了个大跟头。

我原本的思路是这样的，如果我要中序遍历一棵树，那么很简单啊，我会按照中序遍历左子树，然后根节点，然后中序遍历右子树的顺序。那么我用一个栈，弹出第一个要遍历的树，先把右子树压栈，然后把根节点压栈，然后把左子树压栈。迭代这个过程。

这个过程竟然完全没有写对……不信，你可以不看下面的代码自己写写看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stk, res = [root], []

        while stk:
            cur = stk.pop()
            if isinstance(cur, int):
                res.append(cur)
                continue
            if not cur:
                continue
            stk.append(cur.right)
            stk.append(cur.val)
            stk.append(cur.left)
        return res

当然，上面这个写法是对的，是我后来根据这个思路重写的。这里，我硬是把根节点的数字解出来和指针一起压进了栈里，才写出来了相对简洁的写法。不然，怎么判定当前的节点是不是根节点，就是个麻烦。

其实，这个思维相当于是广度优先了。每次访问一棵树，先按照正确的顺序，将树替换成下一层遍历的顺序，然后再顺次遍历。显然，还有更简洁的思路，就是按照深度优先的方式。我们遍历一棵树的时候，可以看成沿着树走迷宫，如果可以往左拐，就一直往左拐，一直到没有路了，我们再访问当前路口，然后，往右拐一下，再重复整个过程。

按这个思路写出代码：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stk, res = [], []
        while root or stk:
            while root:
                stk.append(root)
                root = root.left
            cur = stk.pop()
            res.append(cur.val)
            root = cur.right

        return res

这个算法同样是用栈，但是却简洁很多了，也没有用到 isinstance 这种判断，非常规整，然而在思路上却不那么平铺直叙了。大家可以细细品味一下。

这就是我以前常说的，有时候嘴巴说得头头是道，未必写得出来。其实这也就是我们练习写代码的意义所在。

这道题的意思比较简单，我就不在这里抄题目了，可以去这里查看。简单说，就是在给定字符串里，找到一个连续的子串，这个子串里所有的字符都不同，求这个其中长度最大的子串的长度。

做这种题目，首先要关注一下题目的规模，底下提示，这个给定的字符串，长度范围在 0 到 50000。一般来说，如果是求一个子串的题目，首先想的是，怎么在一个字符串里唯一确定一个子串呢？那就是确定这个子串的开头和结尾位置。

如果我们想穷举所有的子串的话，开头位置取值有 n 个可能，结尾位置取值也有 n 个可能，所以，整个搜索空间是 25 亿！所以，我们必然不能穷举。

那么怎么去设计算法呢？我们可以试试数学归纳法。

假设我们已经知道了如何求解以第 n 个字符结尾的最长子串，那么对于第 n + 1 个字符来说，怎么求解最长子串呢？如果我们知道以第 n 个字符结尾的子串，那么对于第 n + 1 个字符，有两种情况，第一，第 n + 1 个字符在最长子串中没出现过，那么，以第 n + 1 个字符为结尾的最长子串就是 substr + s[n + 1]，第二种情况，第 n + 1 个字符已经出现了，那么我们把它的位置算出来 pos，然后把 pos 及以前的字符删掉，然后把第 n + 1 个字符接在后面，就形成了以 第 n+1 个字符结尾的最长子串。

怎么求整体的最长子串呢？就是遍历每个结尾位置即可。最大的那个长度就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        @cache
        def longestSubstr(idx: int) -> (str, int):
            if idx == 0:
                return s[idx], 1
            sub, l = longestSubstr(idx - 1)
            if s[idx] not in sub:
                return sub + s[idx], l + 1
            else:
                pos = sub.index(s[idx])
                return sub[pos + 1:] + s[idx], l - pos
        ans = 0
        for i in range(len(s)):
            _, l = longestSubstr(i)
            ans = max(ans, l)
        return an

利用上面的原理，我设计了一个递归算法，计算以 idx 结尾的最长子串，就是计算 idx - 1 为结尾的子串，并进行两种情况而处理。

然后，我们很容易意识到，例如，计算以 下标5 结尾的子串时，要先计算 下标4 结尾的子串。假如我们用一个缓存，记录所有的中间结果，那么遍历的时候，就可以节省大量而时间。上面我用了 Python 的修饰符 @cache。最平凡的情况就是 idx = 0 的时候，显然此时最长子串就是 1，因为里面只有一个字符。

这个算法写出来后，我们就发现，动态规划的写法其实已经呼之欲出了。状态转移方程，就是 n 与 n - 1 之间的关系，前面也都说了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        curStr = ""
        res = 0
        n = len(s)

        for i in range(n):
            if s[i] in curStr:
                pos = curStr.index(s[i])
                curStr = curStr[pos + 1:] + s[i]
            else:
                curStr += s[i]
            res = max(res, len(curStr))
        return res

这个算法里，curStr 就是最长的无重复字符的子串。相当于我们一旦发现了重复字符，我们就把子串从重复字符开始的前缀给截掉。

这个算法的时间复杂度，大框架上是 O(n) 的，因为我们只遍历了一次字符串，这里消耗时间的还有一个地方，就是我们用了字符串的 index 操作，这个操作本质上也应该是 O(n) 的复杂度，不过我们可以用 一个 hash 来优化这个查询的复杂度到 O(1)。

从这个算法里，我们看到，遍历字符串结尾位置的时候，只要遍历一遍，那么子串开头的位置变化有什么特点呢？当我们没有截断子串的时候，开头的位置是不变的，当我们截断了的时候，开头位置往右移动（增大）。不难发现，子串的开始位置和结束位置，在遍历过程中，变化都是单调的。

这个特点就提醒我们，我们可以用一个开始位置或结束位置一直往右移动的滑动窗口来实现算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        freq = set()
        ans = 0
        n = len(s)

        right = -1

        for i in range(n):
            if i:
                freq.remove(s[i - 1])
            
            while right + 1 < n and s[right + 1] not in freq:
                freq.add(s[right + 1])
                right += 1
            
            ans = max(ans, right - i + 1)
        return ans

在这里，我们用一个数据结构集合（set），来记录字符是否出现。然后我们遍历子串的起始位置，然后向右扩展结束位置，如果发现重复字符，就把起始位置右移，没重复，就把结束位置右移。也是 O(n) 的复杂度。

当我们遍历一棵二叉树的时候，根据遍历根节点的顺序的不同，可以有三种方法，前序遍历（Preorder），中序遍历（Inorder），后序遍历（Postorder）。分别对应着先访问根节点，在先左子树，然后访问根节点，接着右子树，或者最后访问根节点。这是很基本的数据结构知识点。今天的题目就是，给定一个二叉树的前序遍历和中序遍历结果，根据这个还原出二叉树。

其实前序遍历加中序遍历结果，就会唯一确定一棵二叉树。现在无非怎么操作的问题。我们可以从一个实例来分析这个：

1
2

preorder = [1, 2, 3, 4, 5, 6, 7, 8, 9]
inorder  = [3, 2, 4, 1, 6, 5, 8, 7, 9]

前序遍历的第一个节点是 1，则，在中序遍历中 3，2，4，[1]，6，5，8，7，9，就把序列分成了两份，前半段是左子树，后半段就是右子树。前序遍历的第二个节点是 2，则中序中的前半段 3，[2]，4，通过 2 把它又分成了两段，3，就是左子树，4，就是右子树。正好对应着前序遍历的第三个节点和第四个节点……

从这个顺序里，我们可以发现，前序遍历序列，我们只要按顺序逐个处理，而中序遍历的，我们不断分割左右两半，然后就是递归地处理这个过程。基于这个原理，我们可以用 Python 很简洁地写出这个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        n = len(preorder)
        pre = iter(preorder)

        def rec(left: int, right: int) -> TreeNode:
            if left >= right:
                return None
            r = next(pre)
            m = inorder.index(r, left, right)
            ltree = rec(left, m)
            rtree = rec(m + 1, right)
            return TreeNode(r, ltree, rtree)

        return rec(0, n)

我们声明一个函数 rec，代表 reconstruction（重建），用下标 left 和 right 来标记中序遍历序列的下标。因为前序遍历序列的分析，就是按顺序，所以我们生成一个迭代器来操作它，而下标 left 和 right，作用就是探测已到达叶子节点的标记。因为 index 这个方法的搜索范围是左闭右开区间的，所以我们对 left 和 right 的取值控制也是左闭右开的，这点需要注意。（为什么递归终止条件是 left >= right，因为是左闭右开，一个有效区间必须满足 left < right，区间里面才会有元素。）

看这个递归体里，我们用迭代器访问前序遍历的序列，迭代器不断往前移动，刚好把每个元素都访问了一遍。所以，整个算法的时间复杂度是 O(n)。