Python程式檢查是否可以透過單詞列表拼寫出目標

假設我們有一個名為 nums 的數字列表和另一個數字 k。如果我們從索引 k 開始，並且在任何索引 i 處，我們都可以向左或向右移動正好 nums[i] 步。我們必須檢查我們是否可以到達列表的末尾。

因此，如果輸入類似於 nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2，則輸出將為 True，因為如果我們從索引 2 開始，然後跳到索引 4，然後跳到最後一個索引 7。

為了解決這個問題，我們將遵循以下步驟：

  • n := nums 的大小

  • visited := 一個大小為 n 的列表，並填充 0

  • tovisit := 一個大小為 1 的列表，並將 k 插入其中

  • 當 tovisit 的大小 < 0 時，執行以下操作

    • i := tovisit 中的最後一個元素，並將其從 tovisit 中刪除

    • 如果 i 與 n-1 相同，則

    • 返回 True

  • 如果 visited[i] 與 1 不相同，則

    • visited[i] := 1

    • up := i + nums[i]

    • down := i - nums[i]

    • 如果 up < n，則

    • 將 up 插入 tovisit 的末尾

    • 如果 down >= 0，則

    • 將 down 插入 tovisit 的末尾

  • 返回 False

讓我們看看以下實現以獲得更好的理解：

示例

 線上演示

class Solution:
   def solve(self, nums, k):
   n=len(nums)
   visited = [0]*n
   tovisit = [k]
   while len(tovisit)>0:
         i=tovisit.pop()
      if i==n-1:
         return True
      if visited[i]!=1:
         visited[i]=1
         up=i+nums[i]
         dn=i-nums[i]
      if up=0:
         tovisit.append(dn)
   return False
ob = Solution()
nums = [0, 0, 2, 1, 3, 3, 1, 1]
k = 2
print(ob.solve(nums, k))

輸入

[0, 0, 2, 1, 3, 3, 1, 1], 2

輸出

True

更新於: 2020年10月5日

146 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告