foolish fly fox's blog

--Stay hungry, stay foolish.
--Forever young, forever weep.

679. 24 Game

https://leetcode.com/problems/24-game/description/
知识点：普通全排列的实现、指数全排列的实现、小数比较、Python异常

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

Note:

• The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
  Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
  You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

solution

solution 1

My solution:

class Solution:
    def judgePoint24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # 普通全排列
        def full_permutate(a):
            if len(a)<=1:
                return [a]
            ret_seq = []
            for i in range(len(a)):
                if i==0 or a[0]!=a[i]:
                    a[0],a[i] = a[i],a[0]
                else:continue
                for sub_seq in full_permutate(a[1:]):
                    ret_seq.append([a[0]]+sub_seq)
            return ret_seq
        #指数全排列
        def exp_permutate(a, l):
            diff_a = set(a)
            pre_permutate = [[]]
            for i in range(l):
                tmp_seq = []
                for sub_seq in pre_permutate:
                    for k in diff_a:
                        tmp_seq.append(sub_seq + [k])
                pre_permutate = tmp_seq
            return pre_permutate
            
        opt_permutation = exp_permutate(list("+-*/"),3)
        calc_template = [
            "(({0}{4}{1}){5}{2}){6}{3}",
            "({0}{4}{1}){5}({2}{6}{3})",
            "({0}{4}({1}{5}{2})){6}{3}",
            "{0}{4}(({1}{5}{2}){6}{3})",
            "{0}{4}({1}{5}({2}{6}{3}))"
        ]
        for nums_seq in full_permutate(nums):
            for opt in opt_permutation:
                for calc_t in calc_template:
                    calc_str = calc_t.format(*nums_seq, *opt)
                    try:
                        if math.isclose(eval(calc_str),24):
                            print(calc_str)
                            return True
                    except ZeroDivisionError:
                        continue
        return False

solution 2

一种更简洁的实现：

import itertools
import math
def judgePoint24(nums):
    if len(nums) == 1:
        return math.isclose(nums[0], 24)
    return any(judgePoint24([x] + rest)
            for a,b,*rest in itertools.permutations(nums)
                for x in {a+b, a-b, a*b, b and a/b})

Analysis

和我自己写的程序长度相差不是一点啊。也正是由于一次次看到代码的不足，才慢慢成长起来的！

首先，功能上，我的程序比下面的程序好的一点是：可以显示出构成计算出24的表达式。

要明白 solution 2 的编程思路，需要知道以下几个知识点：

math.isclose

当两个float类型进行比较，或者是float和int进行相等比较时，通常会出现未预期的效果：

print(3==1/(1-2/3))
print(3<=1/(1-2/3))
print(3.0==1/(1-2/3))
print(3.0<=1/(1-2/3))

False
False
False
False

所以，如果有小数参与，一定不要比较是否相等，尽量不要使用 ==、 >=、 <=。

可以使用math.isclose进行有小数参与的比较：

import math
print(math.isclose(3,1/(1-2/3)))
print(math.isclose(3,1/(1-2/3)) or 3<1/(1-2/3))
print(math.isclose(3.0,1/(1-2/3)))
print(math.isclose(3.0,1/(1-2/3)) or 3.0<1/3*3)

True
True
True
True

星号的作用

• 当对多个变量进行赋值时，在等号的左边最靠近等号的位置，可以接受没被接收的值，并存放于list中：

a, b, *c = 1,2,3,4,5
print(c)
a, b, *c = 1,2
print(c)

[3, 4, 5]
[]

• 当定义于函数的形参时，和上面的功能类似，接受没被接收的传入参数，不过其类型为tuple：

def f1(v1, v2, *vs):
    print(vs)
f1(1,2,3,4,5)
f1(1,2)

(3, 4, 5)
()

• 当实参传入时带信号，表示将list或tuple解开后一个一个传入函数：

def f(a,b):
    print(a,b)
x = (1,2)
y = 3
f(x, y)
f(*x)

(1, 2) 3
1 2

• 双星在形参处，接受所有未被接收的含关键字参数，类型为dict

def f(a,**k):
    print(a,k)
f(1,c=3,d=4,f=5)

1 {'c': 3, 'd': 4, 'f': 5}

• 双星在实参处，将dict类型数据解包后，作为带键参数传入函数：

def f(a,b,c):
    print(a,b,c)
k = {'a':1,'b':2,'c':3}
f(k,10,20)
f(**k)

{'a': 1, 'b': 2, 'c': 3} 10 20
1 2 3

除0异常的处理

如果遇到除0，通常会发生除0异常：

a = 5
b = 0
print(a/b)

Traceback (most recent call last):
  File "/Users/fenghuabin/Code/Year2018/CsLearnNote/LeetCode/lviv2gnev_code_chunk.py", line 3, in 
    print(a/b)
ZeroDivisionError: division by zero

解决办法：

1. 使用异常处理

a = 5
b = 0
try:
    print(a/b)
except ZeroDivisionError:
    print(b)
b = 2
try:
    print(a/b)
except ZeroDivisionError:
    print(0)

0
2.5

2. 添加判断

a = 5
b = 0
if b:print(a/b)
else:print(b)
b = 2
if b:print(a/b)
else:print(b)

0
2.5

3. 使用and

a = 5
b = 0
print(b and a/b)
b = 2
print(b and a/b)

0
2.5

itertools创建全排列

itertools.permutations可以获取一个可遍历对象的所有组合的迭代器：

import itertools
for pn in itertools.permutations("abc"):
    print(pn)

('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

其中也是可能包含重复元素的：

import itertools
for pn in itertools.permutations("abb"):
    print(pn)

('a', 'b', 'b')
('a', 'b', 'b')
('b', 'a', 'b')
('b', 'b', 'a')
('b', 'a', 'b')
('b', 'b', 'a')

也可以指定组合长度：

import itertools
for pn in itertools.permutations("abc", 2):
    print(pn)

('a', 'b')
('a', 'c')
('b', 'a')
('b', 'c')
('c', 'a')
('c', 'b')

总结

个人觉得，虽然 solution 的代码量非常少，可读性还是较差的，不是非常推荐。