[問題解決]プログラマ-ターゲット番号(dfs&bfs)[レベル2]

提问链接

問題の説明

n個の非負の整数.この数字を適当に加算または減算してターゲット番号を作成したいです.たとえば、[1,1,1,1,1,1]で数値3を作成するには、次の5つの方法があります.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.

せいげんじょうけん

与えられた数字の個数は2個または20個以上である.
各数字は1または50以下の自然数です.
ターゲット番号が1または1000以下の自然数です.

I/O例

numberstargetreturn[1, 1, 1, 1, 1]35

せきぶん

bfs、dfs、itertoolsを使用して問題を解決できます.

私の答え

bfsで解決する

ナビゲーション順序はすべての隣接ノードにナビゲートされ,ナビゲートされたノードのサブノードであるため,順序はbfsと考えられるため,問題を解く.

2^n個のブランチの結果値
temp node:現在のノード(要素)の値を加算または減算して答えに格納する値を含む変数.
temp nodeが回転したら答えに保存

def solution(numbers, target):
    # 루트노드에 0 생성
    answer= [0]
    for i in range(len(numbers)):
        temp_node = []
        for j in range(len(answer)):
            temp_node.append(answer[j] - numbers[i])
            temp_node.append(answer[j] + numbers[i])
        answer = temp_node
        #print(answer)
    return answer.count(target)

참고 :   print(answer) 결과

#[-1, 1]
#[-2, 0, 0, 2]
#[-3, -1, -1, 1, -1, 1, 1, 3]
#[-4, -2, -2, 0, -2, 0, 0, 2, -2, 0, 0, 2, 0, 2, 2, 4]
#[-5, -3, -3, -1, -3, -1, -1, 1, -3, -1, -1, 1, -1, 1, 1, 3, -3, -1, -1, 1, -1, 1, 1, 3, -1, 1, 1, 3, 1, 3, 3, 5]

別の解釈

1.キューbfsによる解決

私の解答とほぼ同じで,Qを用いてコードをより直感的に理解することができる.
([値,idx])キューに格納されて解決される戻り点とジャンプ点のコード.

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0], 0])
    queue.append([-1 * numbers[0], 0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp + numbers[idx], idx])
            queue.append([temp - numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

2.再帰的dfsの利用

answer = 0

def dfs(numbers, target, i):
    global answer
    if i == len(numbers):
        if (sum(numbers)) == target:
            answer += 1
            return
    else:
        dfs(numbers, target, i+1)
        numbers[i] *= -1
        dfs(numbers, target, i+1)
    
def solution(numbers, target):
    global answer 
    length = len(numbers)
    dfs(numbers, target, 0)
    return answer
          

3.itertools製品を使用した完全なナビゲーション

# 완전탐색 이용해서 해결
from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    # print(l) # 	[(1, -1), (1, -1), (1, -1), (1, -1), (1, -1)]
    s = list(map(sum, product(*l)))
    # l의 곱집합 구해서(각 튜플에서 한개씩 원소 꺼내), sum구한다
    # s는 2^5 = 32개 나올것
    # print(s)
    return s.count(target) # 값이 target과 동일한거 카운트

feedback

いろいろな解答ができる問題で、簡単そうに見えますが、いろいろ考えなければなりません.
Qやスタックを使うよりも再帰(他解2回)を使う解決法に慣れていないので,他の人の解を参考にして理解した.
第3の解法ではitertools productはデカルトの積で求める方法であり,A×B={(a,b)|a∈A∧b∈B}.コンビネーションとソートだけで製品を再認識しました.
解答した問題の中で、一番難しいレベル2のようです.