[コードテスト/プログラマ]ターゲット番号

3897 ワード
コーディングテスト プログラマ python テキストリンク

💡の意見を打診

  • DFSよりもBFSの実行時間が早いので、BFSとBFSを使用しているのでDequeライブラリを使用するべきだと思います.
  • +数字であれば、和-数字であれば、すべての数字を分類して目標値の個数を計算してから戻るべきだと思います.
  • dequeで実現する方法が全く思いつかず、時間がかかりすぎて、他の人のコードを見ることにしました.

    • 他人のコード


    再帰を用いて問題を解決する人が多いが,再帰よりもdequeを用いて問題を解決したいのでdequedを用いて解答を探す.
    🔗コメント
    「Programmers」-ターゲット番号を尋ねるを参照してください.
    rom collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0, 0)]) # sum, level
    while queue:
        s, l = queue.popleft()
        if l > len(numbers):
            break
        elif l == len(numbers) and s == target:
            answer += 1
        queue.append((s+numbers[l-1], l+1))
        queue.append((s-numbers[l-1], l+1))

    return answer
  • 合計とlevelが加わるdeque.
  • dequeの左側から1つずつポップアップし、合計をs、levelをlとして指定します.
  • lが数値配列の長さより大きい場合、重複文を終了します.
  • lが数値配列の長さに等しく、sがtargetに等しい場合、答えは1を加算する.
  • dequeにsとnubers配列のl-1数字の値とlevel(l+1)を追加し、sとnubers配列のl-1数字の値とlevel(l+1)も追加します.
  • Deque祈願まで繰り返します.
    • 答えの値を返します.🔗プログラマ-ターゲット番号
    https://programmers.co.kr/learn/courses/30/lessons/43165
    [アンドロイド]Jetpack Component試食-5編:簡易実施品リスト
    🔄 サイクルを通してTmuxセッションズ