Becomin' Charles

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

在命令行执行：

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)。

这个题目太简单了，我就不贴题目的原文了。意思是这样的，给你一个字符数组（字符串），然后，你要原地把这个数组的元素顺序反转。这道题目是非常平凡的，常规解法是使用双指针，头尾指针向中间夹逼，交换头尾指针指向的字符。

1
2
3
4
5
6
7

class Solution:
    def reverseString(self, s: List[str]) -> None:
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 

用 Python 写，会非常短小。时间复杂度是 O(n)，空间复杂度是 O(1)。

假如，让你为这个题目设计一个递归算法，你会怎么写呢？

方案一：假设我们掌握了一个把下标 [i, j] 范围内的字符顺序反转的方法。

那么对于这个题目来说，我们只要交换头尾两个字符，然后，用递归方法去计算中间剩余部分即可。

1
2
3
4
5
6
7

class Solution:
    def reverseString(self, s: List[str]) -> None:
        def reverse(i: int, j: int) -> None:
            if i < j:
                s[i], s[j] = s[j], s[i]
                reverse(i + 1, j - 1)
        reverse(0, len(s) - 1

这个方法和上面双指针其实如出一辙。

方案二：深度优先搜索，从当前位置探索最后一个字符，找到后，把最后一个字符放到正确位置，然后回溯。

1
2
3
4
5
6
7
8
9
10

class Solution:
    def reverseString(self, s: List[str]) -> None:
        n = len(s)
        def dfs(i: int):
            if i == n:
                return
            c = s[i]
            dfs(i + 1)
            s[n - 1 - i] = c
        dfs(0

这里很有意思的一点，就是这个变量 c 可不可以不要？为什么？

你还能想出其他的递归设计方法么？欢迎给我留言。

这是今天的打卡题目，看标题，就知道这是系列题目，不过那不重要的。我们先来看看题目：

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：
输入：nums = [9], target = 3
输出：0  

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

377. 组合总和IV <– 传送门

如果说，2～3 个月前，这种题我是不可能做出来的，不知道你信不信，现在总算是稍微觉得经过自己努力我也可以做出来了。看来这个还需要坚持和训练，就可以克服的。

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：
输入：4
输出：7
解释：7 = 4 * 3 / 2 + 1

示例 2：
输入：10
输出：12
解释：12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

1006. 笨阶乘 <— 传送门