24点算法()

大家好，我是讯享网，很高兴认识大家。

首发于MyEncyclopedia，微信官方账号，定期发布AI、算法、工程等领域的深度、前沿文章。学习这篇文章最好的方法就是收集起来，发送到桌面浏览器，打开文末，阅读原文，键入代码运行。

24点游戏算法题

先介绍一下21点游戏话题。大家肯定都玩过，就是给定四个卡号，通过加减乘除算出24分。

本文将使用两个Python 3对AC 24游戏部分功能的解决方案。

679.24游戏(硬)

你有4张卡片，每张包含一个从1到9的数字。你需要判断它们是否可以通过*、/、+、-、(、)运算得到24的值。

示例1:

输入:[4，1，8，7]

输出:真

说明:(8-4) * (7-1) = 24

示例2:

输入:[1，2，1，2]

输出:假

itertools.permutations

先介绍一下Python itertools.permutations的用法，仅以Leetcode中的排列问题为例。排列的输入可以是列表，返回的是生成器实例，用于生成所有的排列。简而言之，python的生成器和List一样，可以使用for语句遍历所有生成的值。与List不同，generator的所有值都不必初始化，一般都是按需生成，这样就大大减少了内存占用。下面介绍yield的时候，我们会看到如何合理的构造生成器。

46.排列(中等)

给定一组不同的整数，返回所有可能的排列。

示例:

输入:[1，2，3]

输出:[ [1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]，[3，2，1] ]

置换很简单，只有一行代码。

# AC #运行时:36毫秒，比Permutations的91.78%更快。#MemoryUsage:13.9MB，不到66.52%的pythonlinesubmissionsforpermutations . fromitertoolimportpermutations fromtypingimportlistclasslove:defpermute(self，nums:List[int])-& gt；list[list[int]]:return[pforphinpermutations(nums)]ITER tools .有排列时组合必不可少。Itertools。组合可以生成给定列表的K个元素组合。以一道算法题为例，同一句话可以AC。

77.组合(中等)

给定两个整数n和k，返回1中k个数字的所有可能组合…你可以以任何顺序返回答案。

示例1:

输入:n = 4，k = 2

输出:[ [2，4]、[3，4]、[2，3]、[1，2]、[1，3]、[1，4]，]

示例2:

输入:n = 1，k = 1

输出:[[1]]

# AC #运行时间:84ms，比组合的95.43%的ofPython3onlinesubmissionsforCombinations快。#MemoryUsage:15.2MB，小于68.98%的python 3 online submissions for combinations . fromitertoolimportcombinationsfromtypingimportlistclasslove:def combine(self，n:int，k:int)-& gt；list[list[int]]:return[cforcincombinations(list(range(1，n+1))，k)] ITERTools.product当有多维对象需要迭代笛卡尔积时，可以使用product(iter1，iter2，…)来生成生成器，相当于多个for循环。

[lstforlstinproduct([1，2，3]，[& # 39；一& # 39；,’b & # 39])][(i，s)for in[1，2，3]for sin[& # 39；一& # 39；,’b & # 39]]这两种方法都会产生以下结果

[(1,’一& # 39；),(1,’b & # 39),(2,’一& # 39；),(2,’b & # 39),(3,’一& # 39；),(3,’b & # 39)]再举一个Leetcode的例子来练习产品生成器。

17.电话号码的字母组合(中号)

给定一个包含从2到9的数字的字符串，返回该数字可能代表的所有可能的字母组合。下面给出了数字到字母的映射(就像电话按钮一样)。请注意，1不映射到任何字母。

示例:

输入:& # 34；23″

输出:[& # 34；公元& # 34；, “ae & # 34, “af & # 34, “bd & # 34, “是& # 34；, “bf & # 34, “cd & # 34, “ce & # 34, “cf & # 34].

例如，下面的代码是& # 39；352’，iter_dims的值为[& # 39；def & # 39, ‘jkl & # 39, ‘abc & # 39]，然后输入到产品中就会产生& # 39；dja & # 39, ‘djb & # 39, ‘djc & # 39, ‘eja & # 39，总共3×3×3 = 27个组合值。

# AC #运行时间:24ms，快于94.50%的pythonlinesubmissionsforlettercombinationsophonenumber。#MemoryUsage:13.7MB，小于83.64%的python 3 online submissions for letter combinations of phone number . fromitertoolsimportproductfromtypingimportlistclass solution:defletterCombinations(self，digits:str)-& gt；list[str]:if digits = = & # 34；”:return[]mapping = { & # 39；2′:’abc & # 39,’3′:’def & # 39,’4′:’ghi & # 39,’5′:’jkl & # 39,’6′:’mno & # 39,’7′:’pqrs & # 39,’8′:’tuv & # 39,’9′:’wxyz & # 39} ITER _ dims =[mapping[I]for iin digits]result =[]for lstin product(* ITER _ dims):result . append(& # 39；’。join(lst))returnresultyield示例Python有一个独特的itertools生成器，可以花式AC代码。接下来，解释如何进一步构造生成器。Python定义，只要在函数中使用yield关键字，这个函数就是生成器。生成器在计算机领域的标准名称是协程(coroutine)，即协程，这是一个特殊的函数:它可以在返回到上层调用时保存调用栈状态，然后在上层函数处理完逻辑后跳转到这个生成器中，恢复之前的状态再继续运行。Yield语句也给出了一个经典的斐波那契问题。

509.斐波那契数(简单)

通常表示为F(n)的斐波纳契数列形成了一个序列，称为斐波纳契数列，每个数字都是前面两个数字的和，从0和1开始。即F(0) = 0，F(1) = 1 F(N) = F(N – 1) + F(N – 2)，对于N & gt1.给定N，计算F(N)。

示例1:

输入:2

输出:1

解释:F(2) = F(1) + F(0) = 1 + 0 = 1。

示例2:

输入:3

输出:2

解释:F(3) = F(2) + F(1) = 1 + 1 = 2。

示例3:

输入:4

输出:3

解释:F(4) = F(3) + F(2) = 2 + 1 = 3。

斐波那契的一般标准解法是循环迭代，可以AC，时间复杂度为O(n)，复杂度为O(1) 空复杂度。在下面的yield版本中，我们构造fib_next生成器，它将最后两个值保存为内部迭代状态。每次外部调用，我们都可以得到下一个fib(n)，所以外部只需要一直调用，直到满足给定的次数。

# AC #运行时间:28ms，快于85.56%的python 3 onlinesubmissions for fibonaccinnumber。#MemoryUsage:13.8MB，小于58.41%的python 3 online submissions for fibonaccinnumber . class solution:def fib(self，N:int)-& gt；int:ifN & lt；= 1:return ni = 2 for fibibinyield . fib _ next():ifi = = n:return fibi+= 1 defib _ next(self):f _ last 2，f _ last = 0，1 while true:f = f _ last 2+f _ lastf _ last 2，f _ Yield从Python 3.3开始，嵌套生成器时用于控制转移。一个典型的用法是，当有多个生成器嵌套时，外层的outer_generator使用yield from作为替换下面代码的等价方式。

def outer _ generator():foriinninner _ generator():Yieldi以一个算法题目给出了一个具体的例子。

230.BST中最小的元素(中等)

给定一个二叉查找树，写一个函数kthSmallest，求其中的第k个最小元素。

例1:输入:root = [3，1，4，null，2]，k = 1

3/ 14 2输出:1

示例2:

输入:root = [5，3，6，2，4，null，null，1]，k = 3

5/ 36/ 24/1输出:3

直观上，我们只需要从小到大依次遍历每个节点，直到第k个。因为给定的树是二叉查找树，所以有序遍历意味着以左子树、节点本身和右子树的访问顺序进行递归。因为ordered_iter是一个生成器，所以递归调用自己的过程是一个使用该生成器的嵌套过程。以下是yield版本。

# AC #运行时:48ms，快于90.31%的python 3 online submissionforkthmsmallestelementinabst。#MemoryUsage:17.9MB，小于14.91%的python 3 online submissions forkthmallestelementinabst . class solution:defkthSmallest(self，root:TreeNode，k:int)-& gt；int:defordered _ ITER(node):if node:for sub _ nodeinordered _ ITER(node . left):yield sub _ nodeildnodeforsub _ nodeinordered _ ITER(node . right):yield sub _ nodefornodedeordered _ ITER(root):k-= 1 ifk = = 0:return node . val相当于版本的以下yield:

# AC #运行时:56ms，快于63.74%的python 3 onlinesubmissionforkthmsmallestelementinabst。#MemoryUsage:17.7MB，不到73.33%的python 3 online submissions forkthmallestelementinabst . class solution:defkthSmallest(self，root:TreeNode，k:int)-& gt；int:defordered _ ITER(node):if node:yieldfromsordered _ ITER(node . left)yieldnodeyeldfromsordered _ ITER(node . right)for nodeinordered _ ITER(root):k-= 1 ifk = = 0:return node . val 24点问题的函数枚举解。在理解了itertools包的permuations、combinations、product、yield和yield的关键字之后，我们回到本文中最初的24点游戏问题。

21点游戏的本质是列举所有可能的操作。如果有办法得到24，就返回True否则，它将返回Flase。进一步考虑所有可能的操作，包括以下三个方面:

4个数字的所有排列，比如给定 [1, 2, 3, 4]，可以用permutations([1, 2, 3, 4]) 生成这个维度的所有可能三个位置的操作符号的全部可能，可以用 product([+, -, *, /], repeat=3) 生成，具体迭代结果为：[+, +, +]，[+, +, -]，…给定了前面两个维度后，还有一个比较不容易察觉但必要的维度：运算优先级。比如在给定数字顺序 [1, 2, 3, 4]和符号顺序 [+, *, -]之后可能的四种操作树

四个业务重点

能否算出24个点，只需要列举这三个维度的笛卡尔积的运算结果。

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

# AC #运行时间:112ms，快于24Game的57.59%的python 3 online submissions。#MemoryUsage:13.7MB，不到24 game . importmathfromitertoolsimportpermutations，productfromtypingimportlistclass solution:def ITER _ trees(self，op1，op2，op3，a，b，c，d):yieldop1(op2(a，b)，op3(c，d))yieldop1(a，op2(b，c)，d))yieldop1(a，op2(op3(b，c)，d))yield op1(a，op2(b，op3(bbool:mul=lambdax，y:x*yplus=lambdax，y:x+ydiv=lambdax，y:x/yify！=0elsemath.infminus=lambdax，y:x-yop_lst=[plus，minus，mul，div]foropsinproduct(op_lst，repeat = 3):forvalinpermutations(nums):forvinself . ITER _ trees(ops[0]，ops[1]，ops[2]，val[0]，val[1]，val[2]，val[3]):IFA bs(v-24)& lt；0.0001:returntrue return false 24 DFS yield from Solution of 24-point Problem一个常规的思路是从四个数的集合中选择任意两个数，枚举所有可能的计算，然后递归调用剩下三个数的集合，直到叶子节点只剩下一个数，如下图所示。

DFS调用示例

下面的代码就是这个思路的itertools+yield from solution，recurse方法就是生成器，它会递归地调用自己。当只剩下两个数时，使用yield返回这两个数的所有可能运算的值。在其他非叶情况下，使用yield from进行自呼，比如你从四个数字中选择两个，先计算后合成三个数字。在这种情况下，四个数字可能具有相同的值是很麻烦的。如果通过组合(lst，2)选择了两个数字，那么剩下的两个数字加上第三个计算出来的数字生成集合码就比较麻烦了。因此，我们选择四个索引中的两个，其余的索引可以通过集合操作来完成。

# AC #运行时间:116ms，快于24Game的56.23%的python 3 online submissions。#MemoryUsage:13.9MB，小于24 game . importmathfromitertoolsimportcombinations，product，permutations fromtypingimportlistclassolution:defjudgepoint 24(self，nums:List[int])-& gt；bool:mul=lambdax，y:x*yplus=lambdax，y:x+ydiv=lambdax，y:x/yify！=0elsemath.infminus=lambdax，y:x-yop_lst=[plus，minus，mul，div]defrecurse(lst:List[int]):iflen(lst)= = 2:forop，valuesinproduct(op_lst，permutations(lst)):yieldop(values[0]，values[1])else:# choose 2 indicesfromstoflengthnforchoosen _ idx _ lstincombinations(List(range(len(lst)))，2):# remaininginninginninginproduct0.0001:returnTrue版权归作者所有。商业转载请联系作者授权，非商业转载请注明出处。