(Leetcode) Python中的24游戏

Question

这是一个Leetcode问题 -

您有4张卡片，每张卡都包含一个从1到9__的数字。您需要判断它们是否可以通过*__、/__、+__、- (,__)来获得24__的值。Note - 1。除法运算符/表示实际除法，而不是整数除法。例如，4 / (1 - 2/3) = 12__。2.每个操作都是在两个数字之间进行的。特别是，我们不能使用-作为一元运算符。例如，以[1, 1, 1, 1]作为输入，-1 - 1 - 1 - 1表达式是不允许的。3.你不能把数字连在一起。例如，如果输入是[1, 2, 1, 2]__，则不能将其写入12 + 12__。

这是我对这个挑战的解决方案-

类解决方案(对象)：def judge_point_24(self，)：“”：“”：类型名称:列表:rtype：== 1:返回num == 24或abs(nums 24.0) <= 0.1表示i in范围(len(Num))：for j in range(<=(Num))：if i == j：连续索引= set() indexes.remove(i) indexes.remove(j)操作= [] operations.append(浮点数)+浮点数(Num))operations.append(浮点数)-浮点数(Num)operations.append(浮点数(Num)))-operations.append(浮点数)如果operations.append=0(浮点数/浮点数( nums ))，如果operations.append=0(浮点数/浮点数( nums ) next_items =[索引中索引的num]在操作中的x: if self.judge_point_24(next_items +) == True:返回True返回False

解释-我的解决方案是缩小nums大小，直到它变成一个大小。一旦它是一个大小，检查我们是否已经到达24或足够近。基本上，我尝试从数组中选择两个元素，并应用所有可能的计算，然后递归地调用具有计算结果的数组和其余的数组。当我从调用中看到True时，我也会返回True。

下面是一些示例输出-

#output = Solution()

#print(output.judge_point_24([4, 1, 8, 7]))

>>> True

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

#output = Solution()

#print(output.judge_point_24([1, 2, 1, 2]))

>>> False

以下是这些产出所需的时间-

%timeit output.judge_point_24([4, 1, 8, 7])
2.16 ms ± 46 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit output.judge_point_24([1, 2, 1, 2])
43 ms ± 902 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

这是我的电子编码结果-

所以，我想知道我是否能使这个程序更短、更高效。

任何帮助都将不胜感激。

Answer 1

Docstring

nums真的是List[int]类型吗？也许这是第一次，但在第一步之后，它将变成一个List[float]。

效率

假设nums是一个数字列表(int或float)，您就不需要对任何一个值调用float()。如果您希望从竞赛输入中获得一个由4个字符串组成的列表("1"，通过"9")，则使用int(_)将它们转换为数字，然后将List[int]传递给您的评判函数。

可以将测试nums[0] == 24 or abs(nums[0] - 24.0) <= 0.1简化为abs(nums[0] - 24.0) <= 0.1。

你做的工作比你想象的要多。这段代码在列表中循环，查找值对：

    for i in range(len(nums)):
        for j in range(len(nums)):
            if i == j:
                continue

对于每一对I& j，计算这些值的所有可能组合，包括反向减法和反向除法。

稍后，您只会遇到与j& i相同的一对！第二次计算这些值的所有可能组合。

如果您的内循环是在当前外部循环索引之后的一个索引处开始的，那么您就不会用i > j生成一对索引.甚至i == j，所以您也可以省略该测试。最后，由于内循环从外循环上的1索引开始，外部循环应该提前结束一个索引：

    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):

您还可以使用enumerate( )同时循环这些值及其索引。

    for i, a in enumerate(nums[:-1]):
        for j, b in enumerate(nums[i+1:], i+1):

然后可以引用a代替nums[i]，引用b代替nums[j]，这将防止对nums[]数组进行重复索引，这将导致性能下降。

剩余价值的管理：

            indexes = set([x for x in range(len(nums))])
            indexes.remove(i)
            indexes.remove(j)
            next_items = [nums[index] for index in indexes]

首先，set([x for x in range(len(nums))])可以简单地称为set(range(len(nums)))。不需要理解列表。

但这仍然是很多额外的工作。只需将数字复制到一个新列表中，然后删除i-th和j-th条目。由于保证了i < j，所以删除‘th元素首先不会更改i'th元素的位置：

            next_items = nums[:]
            del next_items[j]
            del next_items[i]

或者，通过省略i-th和j-th元素，使用您想要的元素构建新的列表：

            next_items = nums[:i] + nums[i+1:j] + nums[j+1:]

2+2 == 2*2和1*1 == 1/1 == reverse_div(1,1).这是一个小的优化，但是与其列出所有可能的operations值，不如对这些值创建一个set()，这将消除一些冗余的递归步骤。

如果您不需要将它作为leetcode自动判断的要求，则可以通过不始终传递额外的class参数来获得一些效率。这可以只是一个函数。

重编代码

def judge_point_24(nums):

    for i, a in enumerate(nums[:-1]):
        for j, b in enumerate(nums[i+1:], i+1):
            operations = {a+b, a*b, a-b, b-a}
            if a:
                operations.add(b/a)
            if b:
                operations.add(a/b)

            if len(nums) > 2:
                next_items = nums[:i] + nums[i+1:j] + nums[j+1:]
                for x in operations:
                    if judge_point_24(next_items + [x]) == True:
                        return True
            else:
                return any(abs(x-24) < 0.1 for x in operations)

    return False

if __name__ == '__main__':

    def test(expected, nums):
        print(nums, judge_point_24(nums))
        assert judge_point_24(nums) == expected

    test(True, [4, 1, 8, 7])
    test(False, [1, 2, 1, 2])