Pythonで異なるパリティを持つ値に到達するために必要な最小ジャンプを見つけるためのプログラム

numsと呼ばれる番号のリストが提供されているとします。ここで、値がリストに存在する場合は、インデックスi+数値[i]またはインデックスiからi-数値[i]にジャンプできます。したがって、少なくとも入力の順序を変更せずに、パリティが異なる別の値に到達するために必要なジャンプの数を見つける必要があります。パリティが異なる別の番号に到達できない場合は、-1に設定されます。

したがって、入力が数値=[7、3、4、5、6、9、6、7]のような場合、出力は[-1、1、2、-1、-1、-1、1 、-1]。

これを解決するには、次の手順に従います-

• 関数bfs（）を定義します。これには私がかかります

  • q：=ペア（i、0）を持つ新しい両端キュー

  • 見た：=新しいセット

  • qが空でない間、実行します

    • （j、d）：=qの左端の要素を残し、qから左端のアイテムを削除します

    • 見たものにjを追加する

    • （nums [i] + nums [j]）mod 2がゼロ以外の場合、

      • dを返す

    • [j + nums [j]、j − nums [j]]のkごとに、実行

      • 0 <=k

        • qの右端に（k、d + 1）を挿入します

  • 10^10を返す

• メインの方法から、次のようにします-

• ans：=新しいリスト

• 0からnumsのサイズの範囲のiの場合、実行します

  • 見た：=新しいセット

  • x：=bfs（i）

  • x <10 ^ 10の場合はansにxを追加し、それ以外の場合は-1を追加します

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

from collections import deque
class Solution:
   def solve(self, nums):
      def bfs(i):
         q = deque([(i, 0)])
         seen = set()
         while q:
            j, d = q.popleft()
            seen.add(j)
            if (nums[i] + nums[j]) % 2:
               return d
            for k in [j + nums[j], j − nums[j]]:
               if 0 <= k < len(nums) and k not in seen:
                  q.append((k, d + 1))
         return 10 ** 10
      ans = []
      for i in range(len(nums)):
         seen = set()
         x = bfs(i)
         ans.append(x if x < 10 ** 10 else −1)
      return ans
ob = Solution()
print(ob.solve([7, 3, 4, 5, 6, 9, 6, 7]))

入力

numbers = [7, 3, 4, 5, 6, 9, 6, 7]

出力

[−1, 1, 2, −1, −1, −1, 1, −1]