Becomin' Charles

本原文发布于 2021-09-06

在有些场景下，App 为了防止用户误触返回按钮或者误触返回键，导致未保存的结果返回，都会想办法拦截用户的返回行为。WillPopScope 就是做这个用的。这个组件会提供一个回调 onWillPop，当用户尝试返回的时候，会被调用，如果返回 false，则会阻止用户的返回行为。

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

@override
Widget build(BuildContext context) {
  return WillPopScope(
    child: Scaffold(
      bottomNavigationBar: BottomNavigationBar(
        items: _items,
        currentIndex: _currentIndex,
        onTap: onTap,
      ),
      body: IndexedStack(
        children: _pageList,
        index: _currentIndex,
      ),
    ),
    onWillPop: () {
      var now = DateTime.now().millisecondsSinceEpoch;
      if (now - _lastClickExitTime > _exitDuration) {
        Fluttertoast.showToast(msg: "再按一次退出应用");
        _lastClickExitTime = now;
      } else {
        SystemNavigator.pop(animated: true);
      }
      return Future.value(false);
    },
  );
}

我一开始没有太注意这个类，和一个安卓的同事搭档的时候，看到他引入了这个组件，才想明白了，很多安卓手机上，有实体或者模拟的返回键，很容易误触，所以确实很需要这个回调。上面是一个使用 onWillPop 防止误触返回的例子。

不过，随着研发的深入，我发现一个很严重的问题。在 iOS 上我有一个习惯动作，就是从屏幕的左边沿，向右滑动，就可以返回上一个屏幕，在 iOS 上，这个动作有个专有名词，叫 Swipe Back，右滑返回。如果我用一个 WillPopScope 套住 Scaffold 的话，iOS 上这个页面，Swipe Back 就会完全失效。手指滑动上去，完全没有反应。而且令人发指的是，onWillPop 也完全不会被触发。等于说，在 iOS 上，这个类的作用仅有一个，就是 Swipe Back 手势被取消，回调也永远不会触发。

这真是太不美了，经过搜索，我发现这个是官方一个很著名的 issue #14203，2018 年 1 月打开，无数人反馈，至今没有一个明确的回应。有人（可能是官方）表示，这本来就是一个期望中的行为，只是文档没有说明。

也有观点认为，“只是拦截这个动作，而且 onWillPop 也可以返回 true，还是允许返回的，为什么在 iOS 就彻底失灵了呢？” —— 我也是这么想的。不过，我细细一想，也有点能理解实现者的做法，在 iOS 上，这个动作会有个配套的动画，右滑的时候，会好像翻书一样的视觉效果。如果这时候 App 不允许用户返回的话，滑到一半，这个动画的物理表现到底是怎么样的呢？像皮筋一样弹回？还是怎么做呢？确实有点恼火。还不如完全就没响应。

不过，这就太苦了我们这种想要在 iOS 上保证交互效果的开发。有某个老哥做了一个 CupertinoWillPopScope 插件，试图要去解决这个问题，不过我看了一眼，很不喜欢他的实现。他的实现其实基于一个事实，就是 WillPopScope 里，如果 onWillPop 为 null 的话，在 iOS 上，就不会阻止 Swipe Back，这个我自己写个变量也可以控制，何至于引入一个插件，一个变量就能解决的事情。

我自己遇到的一个场景，也确实很恼火，在 App 里，我引用了 flutter_inappwebview 这个插件，主要是提供了一个查看网页的 WebView，在 WebView 里，我想实现的效果是，Swipe Back 的时候，如果网页有 history，只是返回上一页，如果没有 history，就退出 WebView。这就需要我每次都能拦截 Swipe Back 这个动作，然后判定后决定到底是在网页里后退，还是干脆退出 WebView。

不过，因为刚才说的 WillPopScope 的问题，导致了很奇怪的局面。当我用了以后。在 iOS 上，效果诡异，我永远失去了 Swipe Back 退出 WebView 的能力，但是，在网页上后退却不受影响。只是退到第一页的时候，就再也滑不动了，不能滑动退出 WebView。如果我去掉 WillPopScope，则不论你在哪个页面，都会导致滑动直接退出 WebView，无法实现返回上一页的功能。

只剩下一个办法，就是通过判断 canGoBack，来决定是否绑定 onWillPop，就可以完全实现我的想法，不过 canGoBack 又是一个 Future 类型，我又不知道怎么写了。唉。问题仍然还是没有解决的，我特别记录在此，给遇到同样问题的同学一些参考，同时也希望高手看到了不吝赐教。

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

@override
Widget build(BuildContext context) {
  mUrl = ModalRoute.of(context)?.settings.arguments.toString() ?? "";
  final double pixel = MediaQuery.of(context).size.width / 375;
  return WillPopScope(
    child: Scaffold(
      appBar: MyAppBar.create(
        title: _pageTitle ?? "",
        pixel: pixel,
        actions: [
          IconButton(
            onPressed: () {
              NavigatorUtils.goBack(context);
            },
            icon: Icon(Icons.close),
          ),
        ],
      ),
      body: _webPageContent(),
    ),
    onWillPop: !_canGoBack
        ? null
        : () /** 此逻辑在 iOS 下无效 */ {
            var canGoBack = webViewController?.canGoBack() ?? Future.value(false);
            canGoBack.then((value) {
              if (value) {
                webViewController?.goBack();
              } else {
                Navigator.pop(context);
              }
            });
            return Future.value(false);
          },
  );
}

上述代码里，_canGoBack 这个变量，是我自己模拟的，但是这个变量的效果和 flutter_inappwebview 提供的就不太一样了，插件提供的 API，返回一个 Future<bool> 类型，在任何时候都可以判定当前网页是否存在 history 栈，但是我自己实现的 _canGoBack 变量，只是判定该网页已经不是首次加载的那个，经历过跳转。在我的场景里，大多数网页，只是看一眼就返回了，用户不会循着链接一层层深入，所以在很大程度上可以达到我要的效果，但是，显然没有真正解决这个问题，如果用户浏览了两个页面，就会退回我上文说的效果了。只是略微好了一点点。

– End –

– Update –

现在已经是 2022 年 11 月 17 日了，这个问题官方仍然没有好的解决方法，只是我在上述方案后面，又有了新的一些探索和问题。特此记录一下。

就我现在的理解来看，上述方案的实现背后，有一些关键性的事实：

第一，App 层面，默认是可以响应 Swipe Back 这个行为的，但是，套上 WillPopScope，提供 onWillPop 回调后，Swipe Back 失效（这是上文已经分析过的内容）；

第二，flutter_inappwebview 这个插件提供的 WebView 组件，内部本身可以响应 Swipe Back 这个动作，因为在 iOS 上，这个插件是用 WKWebView 实现的，所以其行为来自 iOS 系统本身的默认行为，这就是为什么开启 onWillPop 后，虽然不能 Swipe Back 退出 WebView，但是如果你在 WebView 内部多次跳转链接，可以用 Swipe Back 后退；本质上，就是有两层，外层是 App 层面的交互行为，内层是 WebView 内部的交互行为，这两者是分离的（从原文的描述中，可以体会到这一点，这里明确总结出来）；

第三，现在遇到的困扰，就是 Swipe Back 这个动作，在穿越 WebView 和 Flutter App 中间的界限的时候，出现了衔接的问题。这个地方本来就需要衔接，因为 App 和 WebView 都可以响应 Swipe Back 动作，那么应该谁来处理这个事件，程序员就需要自己决定。本来，如果 onWillPop 回调，在 iOS 上没有 bug 的话，一切都很美，可惜事与愿违；

第四，上述解决方案，就是在通过编程，来确立 App 和 WebView 谁来接管 Swipe Back 动作的边界，也即设立了一个 _canGoBack 的变量，作为 flag。核心原理是，内部 history 可以执行 goBack 的时候，就由内部接管，不能执行的时候，就由外部接管。程序员要做的，就是在恰当的时候，正确设定 flag 的值。

原文方案里，我只是在 WebView:onLoadStop 事件中，设定 _canGoBack 的值为 true/false，也即，如果内部 WebView 加载了超过一个页面，那么就由内部接管事件，这个时候开启 onWillPop 捕获，会自动屏蔽 iOS 下 App 级别的事件处理。

现在我们的业务场景遇到一个新的问题，就是 WebView 加载的内嵌页面，可能是一个 SPA，单页应用，这种类型的应用，在页面内部的路由切换，浏览器不需要重新加载，这个时候，就不会触发 onLoadStart/onLoadStop 事件，导致我们设定 flag 的意图无法实现，此种情景下，就会让 back 按钮一点就会退出整个 WebView。

其实，这个问题，也是一个“传统”的难题。比如，大家有没有这种经历，就是去你去街边小店，点餐的时候，从公众号里，点开一个界面，点到一半，想看一下上一步的内容，点了一下后退，结果整个界面被关掉了，十分恼火。微信发展这么多年，腾讯那么强大，竟然在这个小问题上还是没有完美解决，当然，也可能是点餐界面的开发者太垃圾，不管怎么说，都说明这个问题真的很难，很普遍。

那么在我们这里，这种情况是否有解决方案呢？办法总比困难多，目前，我们想到了一个部分解决问题的方法。就是利用 js 回调通信解决。我认真研究了一下单页应用的原理，在 SPA 内部，路由也是一个老生常谈的问题，就是在页面没有加载的情况下，如何根据用户的操作来切换场景。这也是一个经典的面试题。

SPA 的路由实现，其目标是浏览器不重新加载，全部交由页面的 js 来操控界面的绘制和场景的切换。如果通过地址栏 location 改变路径，可能会造成浏览器重新加载。那么常用的方案有两种，第一，使用 http 协议中的 fragment，也有叫 hash 的，就是一个带有 # 号的网址，浏览器在处理的时候，会自动把 # 后面的部分，理解为页面内部的锚点，不会发起 HTTP 请求，第二，使用 history API，这是现代浏览器都支持的一个内部对象，专门管理浏览器的状态，可以通过 pushState，replaceState，go，back，forward 等 API 进行操作。

使用 hash 进行路由的时候，可以直接更改 location，浏览器不会发送请求，但是，会进行处理。使用 pushState 的时候，浏览器完全不会进行处理，所以，哪怕你发个真实的 path 过去，浏览器也不会刷新。这种方式，可以把地址伪装成真实 URL 的样子，看起来很友好。

我发现 spec 里提到，使用 hash 的时候，浏览器会触发一个事件叫 hashchange，这是一个标准的事件，通过注入 js handler，来捕获 hashchange 事件，我们可以知道，内部页面发生了路由，可以进行 goBack，这时候设定 flag，就可以沿用原文中提到的逻辑了。

但是 pushState 本身就不会触发任何事件，每个框架会个自创建事件进行绑定，我们作为 WebView 的实现方，不太好做通用的方案。

– End Update –

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) 的复杂度。