【leetcode 679】24時ゲーム

タイトル
1から9の数字が書かれたカードが4枚あります.*,/,+,-,(,)の演算で24を得ることができるかどうかを判断する必要があります.
例1:
入力:[4,1,8,7]出力:True解釈:(8-4)*(7-1)=24例2:
入力:[1,2,1,2]出力:False注意:
除算演算子/は、整数除算ではなく実数除算を表します.たとえば、4/(1-2/3)=12です.各演算子は2つの数を演算します.特に-を1元演算子として使用することはできません.例えば、[1,1,1,1]を入力とする場合、式-1-1-1-1は許可されません.数字をつなぐことはできません.例えば、[1,2,1,2]と入力した場合、12+12と書くことはできません.
分析と解題の構想
この問題の最も簡単な考えは間違いなくすべての状況を遍歴することであり、状況は限られているので、遍歴しても特に面倒ではない.まず、いくつかの状況を見てみましょう.

まず、4つの数字の中から任意に2つを選んで、4種類の演算を行うことができて、共にA 4 2∗4 A_があります4^2*4 A 42∗4種選法;

以降、上記の演算の結果を新しい数字として元のリストに代入し、前に選択した2つの数字を置き換えると、リストの数字の個数は3つであるべきである.

三つの中から二つの数字を選んで、4種類の演算を行います.A 3 2∗4 A_があります.3^2*4 A 32∗4種の選法;

同理:最後の2桁の数字の可能性はA 2 1∗4 A_2^1*4 A 21∗4種;

だから共有:A 4 2∗4∗A 3 2∗4∗A 2 1∗4=9216 A_4^2*4*A_3^2*4*A_2^1*4=9216 A42​∗4∗A32​∗4∗A21​∗4=9216

以上の解析の過程から,再帰関数を呼び出すたびに配列が1つの数字を減らすと,1つの数字しか残っていない最後の計算結果になるので,再帰関数の開始時に判断し,配列が1つの数字しかなく,24であれば,説明は24を算出できる.結果resはtrueに割り当てられて返されます.ここで我々の結果resはグローバルな変数であり,すでにtrueであれば演算する必要はないので,最初の行は結果resを判断し,trueのために直接戻ったはずである.任意の2つの数字を巡り,それぞれpとqで取り出し,両者の各種加減乗除の演算を行い,結果を配列一時配列tに保存し,除数がゼロでないと判断することを覚えておく.その後、元の配列numsのpとqを除去し、一時的な配列tの数字を巡り、配列numsに加えて再帰関数を呼び出し、完了したら数字を除去し、状態を回復することが再帰解法の重要な点であることを覚えています.最後にpとqを元の配列numsに戻し,これも還元状態である.
この一節は参考にしたhttps://blog.csdn.net/weixin_33693070/article/details/85968548
リファレンスコード

from operator import truediv, mul, add, sub

class Solution(object):
    def judgePoint24(self, A):
        if not A: return False
        if len(A) == 1: return abs(A[0] - 24) < 1e-6

        for i in range(len(A)):
            for j in range(len(A)):
                if i != j:
                    B = [A[k] for k in range(len(A)) if i != k != j]
                    for op in (truediv, mul, add, sub):
                        if (op is add or op is mul) and j > i: continue
                        if op is not truediv or A[j]:
                            B.append(op(A[i], A[j]))
                            if self.judgePoint24(B): return True
                            B.pop()
        return False