Leetcode 679 24 Game 的 Python 函数式实现

Leetcode 679 24 Game (Hard)

先来介绍一下24点游戏题目，大家一定都玩过，就是给定4个牌面数字，用加减乘除计算24点。

本篇会用两种偏函数式的 Python 3解法来AC 24 Game。

Leetcode 679 24 Game (Hard) > You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]

Output: True

Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]

Output: False

itertools.permutations

先来介绍一下Python itertools.permutations 的用法，正好用Leetcode 中的Permutation问题来示例。Permutations 的输入可以是List，返回是 generator 实例，用于生成所有排列。简而言之，python 的 generator 可以和List一样，用 for 语句来全部遍历产生的值。和List不同的是，generator 的所有值并不必须全部初始化，一般按需产生从而大量减少内存占用。下面在介绍 yield 时我们会看到如何合理构造 generator。

Leetcode 46 Permutations (Medium) > Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]

Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

用 permutations 很直白，代码只有一行。

{linenos

# AC
# Runtime: 36 ms, faster than 91.78% of Python3 online submissions for Permutations.
# Memory Usage: 13.9 MB, less than 66.52% of Python3 online submissions for Permutations.

from itertools import permutations
from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return [p for p in permutations(nums)]

itertools.combinations

有了排列就少不了组合，itertools.combinations 可以产生给定List的k个元素组合 \(\binom{n}{k}\)，用一道算法题来举例，同样也是一句语句就可以AC。

Leetcode 77 Combinations (Medium)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. You may return the answer in any order.

Example 1:

Input: n = 4, k = 2

Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]

Example 2:

Input: n = 1, k = 1

Output: [[1]]

{linenos

# AC
# Runtime: 84 ms, faster than 95.43% of Python3 online submissions for Combinations.
# Memory Usage: 15.2 MB, less than 68.98% of Python3 online submissions for Combinations.
from itertools import combinations
from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return [c for c in combinations(list(range(1, n + 1)), k)]

itertools.product

当有多维度的对象需要迭代笛卡尔积时，可以用 product(iter1, iter2, ...)来生成generator，等价于多重 for 循环。

[lst for lst in product([1, 2, 3], ['a', 'b'])]
[(i, s) for i in [1, 2, 3] for s in ['a', 'b']]

这两种方式都生成了如下结果

[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]

再举一个Leetcode的例子来实战product generator。

Leetcode 17. Letter Combinations of a Phone Number (Medium)

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

举例来说，下面的代码当输入 digits 是 '352' 时，iter_dims 的值是 ['def', 'jkl', 'abc']，再输入给 product 后会产生 'dja', 'djb', 'djc', 'eja', 共 3 x 3 x 3 = 27个组合的值。

{linenos

# AC
# Runtime: 24 ms, faster than 94.50% of Python3 online submissions for Letter Combinations of a Phone Number.
# Memory Usage: 13.7 MB, less than 83.64% of Python3 online submissions for Letter Combinations of a Phone Number.

from itertools import product
from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        mapping = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        iter_dims = [mapping[i] for i in digits]

        result = []
        for lst in product(*iter_dims):
            result.append(''.join(lst))

        return result

yield 示例

Python具有独特的itertools generator，可以花式AC代码，接下来讲解如何进一步构造 generator。Python 定义只要函数中使用了yield关键字，这个函数就是 generator。Generator 在计算机领域的标准名称是 coroutine，即协程，是一种特殊的函数：当返回上层调用时自身能够保存调用栈状态，并在上层函数处理完逻辑后跳入到这个 generator，恢复之前的状态再继续运行下去。Yield语句也举一道经典的Fibonacci 问题。

Leetcode 509. Fibonacci Number (Easy)

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1. Given N, calculate F(N).

Example 1:

Input: 2

Output: 1

Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: 3

Output: 2

Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: 4

Output: 3

Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Fibonacci 的一般标准解法是循环迭代方式，可以以O(n)时间复杂度和O(1) 空间复杂度来AC。下面的 yield 版本中，我们构造了fib_next generator，它保存了最后两个值作为内部迭代状态，外部每调用一次可以得到下一个fib(n)，如此外部只需不断调用直到满足题目给定次数。

{linenos

# AC
# Runtime: 28 ms, faster than 85.56% of Python3 online submissions for Fibonacci Number.
# Memory Usage: 13.8 MB, less than 58.41% of Python3 online submissions for Fibonacci Number.

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        i = 2
        for fib in self.fib_next():
            if i == N:
                return fib
            i += 1
            
    def fib_next(self):
        f_last2, f_last = 0, 1
        while True:
            f = f_last2 + f_last
            f_last2, f_last = f_last, f
            yield f

yield from 示例

上述yield用法之后，再来演示 yield from 的用法。Yield from 始于Python 3.3，用于嵌套generator时的控制转移，一种典型的用法是有多个generator嵌套时，外层的outer_generator 用 yield from 这种方式等价代替如下代码。

def outer_generator():
    for i in inner_generator():
        yield i

用一道算法题目来具体示例。

Leetcode 230. Kth Smallest Element in a BST (Medium)

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Example 1: Input: root = [3,1,4,null,2], k = 1

  3
 / \
1   4
 \
  2

Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3

         5
        / \
       3   6
     /  \
    2    4
  /
1

Output: 3

直觉思路上，我们只要从小到大有序遍历每个节点直至第k个。因为给定的树是Binary Search Tree，有序遍历意味着以左子树、节点本身和右子树的访问顺序递归下去就行。由于ordered_iter是generator，递归调用自己的过程就是嵌套使用generator的过程。下面是yield版本。

{linenos

# AC
# Runtime: 48 ms, faster than 90.31% of Python3 online submissions for Kth Smallest Element in a BST.
# Memory Usage: 17.9 MB, less than 14.91% of Python3 online submissions for Kth Smallest Element in a BST.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def ordered_iter(node):
            if node:
                for sub_node in ordered_iter(node.left):
                    yield sub_node
                yield node
                for sub_node in ordered_iter(node.right):
                    yield sub_node

        for node in ordered_iter(root):
            k -= 1
            if k == 0:
                return node.val

等价于如下 yield from 版本：

{linenos

# AC
# Runtime: 56 ms, faster than 63.74% of Python3 online submissions for Kth Smallest Element in a BST.
# Memory Usage: 17.7 MB, less than 73.33% of Python3 online submissions for Kth Smallest Element in a BST.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def ordered_iter(node):
            if node:
                yield from ordered_iter(node.left)
                yield node
                yield from ordered_iter(node.right)

        for node in ordered_iter(root):
            k -= 1
            if k == 0:
                return node.val

24 点问题之函数式枚举解法

看明白了itertools.permuations，combinations，product，yield以及yield from，我们回到本篇最初的24点游戏问题。

24点游戏的本质是枚举出所有可能运算，如果有一种方式得到24返回True，否则返回Flase。进一步思考所有可能的运算，包括下面三个维度：

1. 4个数字的所有排列，比如给定 [1, 2, 3, 4]，可以用permutations([1, 2, 3, 4]) 生成这个维度的所有可能

2. 三个位置的操作符号的全部可能，可以用 product([+, -, *, /], repeat=3) 生成，具体迭代结果为：[+, +, +]，[+, +, -]，...

3. 给定了前面两个维度后，还有一个比较不容易察觉但必要的维度：运算优先级。比如在给定数字顺序 [1, 2, 3, 4]和符号顺序 [+, *, -]之后可能的四种操作树

四种运算优先级

能否算得24点只需要枚举这三个维度笛卡尔积的运算结果

(维度1：数字组合) x (维度2：符号组合) x (维度3：优先级组合)

{linenos

# AC
# Runtime: 112 ms, faster than 57.59% of Python3 online submissions for 24 Game.
# Memory Usage: 13.7 MB, less than 85.60% of Python3 online submissions for 24 Game.

import math
from itertools import permutations, product
from typing import List

class Solution:

    def iter_trees(self, op1, op2, op3, a, b, c, d):
        yield op1(op2(a, b), op3(c, d))
        yield op1(a, op2(op3(b, c), d))
        yield op1(a, op2(b, op3(c, d)))
        yield op1(op2(a, op3(b, c)), d)

    def judgePoint24(self, nums: List[int]) -> bool:
        mul = lambda x, y: x * y
        plus = lambda x, y: x + y
        div = lambda x, y: x / y if y != 0 else math.inf
        minus = lambda x, y: x - y

        op_lst = [plus, minus, mul, div]

        for ops in product(op_lst, repeat=3):
            for val in permutations(nums):
                for v in self.iter_trees(ops[0], ops[1], ops[2], val[0], val[1], val[2], val[3]):
                    if abs(v - 24) < 0.0001:
                        return True
        return False

24 点问题之 DFS yield from 解法

一种常规的思路是，在四个数组成的集合中先选出任意两个数，枚举所有可能的计算，再将剩余的三个数组成的集合递归调用下去，直到叶子节点只剩一个数，如下图所示。

DFS 调用示例

下面的代码是这种思路的 itertools + yield from 解法，recurse方法是generator，会自我递归调用。当只剩下两个数时，用 yield 返回两个数的所有可能运算得出的值，其他非叶子情况下则自我调用使用yield from，例如4个数任选2个先计算再合成3个数的情况。这种情况下，比较麻烦的是由于4个数可能有相同值，若用 combinations(lst, 2) 先任选两个数，后续要生成剩余两个数加上第三个计算的数的集合代码会繁琐。因此，我们改成任选4个数index中的两个，剩余的indices 可以通过集合操作来完成。

{linenos

# AC
# Runtime: 116 ms, faster than 56.23% of Python3 online submissions for 24 Game.
# Memory Usage: 13.9 MB, less than 44.89% of Python3 online submissions for 24 Game.

import math
from itertools import combinations, product, permutations
from typing import List

class Solution:

    def judgePoint24(self, nums: List[int]) -> bool:
        mul = lambda x, y: x * y
        plus = lambda x, y: x + y
        div = lambda x, y: x / y if y != 0 else math.inf
        minus = lambda x, y: x - y

        op_lst = [plus, minus, mul, div]

        def recurse(lst: List[int]):
            if len(lst) == 2:
                for op, values in product(op_lst, permutations(lst)):
                    yield op(values[0], values[1])
            else:
                # choose 2 indices from lst of length n
                for choosen_idx_lst in combinations(list(range(len(lst))), 2):
                    # remaining indices not choosen (of length n-2)
                    idx_remaining_set = set(list(range(len(lst)))) - set(choosen_idx_lst)

                    # remaining values not choosen (of length n-2)
                    value_remaining_lst = list(map(lambda x: lst[x], idx_remaining_set))
                    for op, idx_lst in product(op_lst, permutations(choosen_idx_lst)):
                        # 2 choosen values are lst[idx_lst[0]], lst[idx_lst[1]
                        value_remaining_lst.append(op(lst[idx_lst[0]], lst[idx_lst[1]]))
                        yield from recurse(value_remaining_lst)
                        value_remaining_lst = value_remaining_lst[:-1]

        for v in recurse(nums):
            if abs(v - 24) < 0.0001:
                return True