【leetcode】679. 24 Game

题目如下：

解题思路：24点是非常经典的游戏了，因为本题数据量小，可以使用穷举法，把所有的可能结果都算出来。假设nums = [a,b,c,d]，记f(n)表示用nums中n个数字进行运算可以得到的结果集，那么f(4)又可以记为f(4) = U(U(f(1),f(3), U(f(2),f(2))) (U表示合集)，而f(3)又可以记为f(3) = U(f(1),f(2))。可知f(1)的结果集就是参数本身，f(2)的结果集是两个参数a,b进行四则运算的结果，最后判断24是否在结果集中即可。有一点要注意的是，除法运算会有浮点数产生，所以与24比较的时候要有一个浮动的区间。

代码如下：

class Solution(object):

    def union(self,m,n):

        r = []

        for i in range(len(m)):

            for j in range(len(n)):

                r.append(m[i] + n[j])

                r.append(m[i] - n[j])

                r.append(m[i] * n[j])

                if n[j] != 0:

                    r.append(float(m[i]) / float(n[j]))

                if m[i] != 0:

                    r.append(float(n[j]) / float(m[i]))

        return r

    def calc(self,l):

        if len(l) == 1:

            return l

        elif len(l) == 2:

            r =  [l[0] + l[1],l[0] - l[1],l[0] * l[1],l[1] - l[0]]

            if l[1] != 0:

                r.append(float(l[0])/float(l[1]))

            if l[0] != 0:

                r.append(float(l[1])/float(l[0]))

            return r

        elif len(l) == 3:

            return self.union(self.calc([l[0]]) , self.calc([l[1],l[2]])) + \

                   self.union(self.calc([l[1]]) , self.calc([l[0],l[2]])) + \

                   self.union(self.calc([l[2]]) , self.calc([l[0],l[1]]))

    def judgePoint24(self, nums):

        """

        :type nums: List[int]

        :rtype: bool

        """

        r = [([nums[0]], [nums[1], nums[2], nums[3]]), ([nums[1]], [nums[0], nums[2], nums[3]]),

             ([nums[2]], [nums[0], nums[1], nums[3]]),

             ([nums[3]], [nums[0], nums[1], nums[2]]), ([nums[0], nums[1]], [nums[2], nums[3]]),

             ([nums[0], nums[2]], [nums[1], nums[3]]), ([nums[0], nums[3]], [nums[1], nums[2]])]

        for m,n in r:

            m = self.calc(m)

            n = self.calc(n)

            result =  self.union(m,n)

            for res in result:

                if abs(float(24) - float(res)) < 0.00000001:

                    return True

        return False

巴特西

【leetcode】679. 24 Game

最新文章

热门文章