สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกหมายเลขหนึ่งคือ k หากเราเริ่มต้นที่ดัชนี k และที่ดัชนี i ใดๆ เราสามารถไปทางซ้ายหรือขวาด้วยจำนวนขั้นตอนที่ nums[i] ได้พอดี เราต้องเช็คก่อนว่าเราจะไปถึงจุดสิ้นสุดของรายการได้หรือไม่
ดังนั้น หากอินพุตเป็น nums =[0, 0, 2, 1, 3, 3, 1, 1] k =2 ผลลัพธ์จะเป็น True ราวกับว่าเราเริ่มต้นที่ดัชนี 2 แล้วข้ามไปที่ดัชนี 4 แล้วข้ามไปที่ดัชนีสุดท้าย 7.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-
-
n:=ขนาดของ nums
-
เยี่ยมชม :=รายการขนาด n และเติมด้วย 0
-
tovisit :=รายการขนาด 1 และใส่ k เข้าไป
-
ในขณะที่ขนาดของ tovisit <0 ทำ
-
i:=องค์ประกอบสุดท้ายจาก tovisit และลบออกจาก tovisit
-
ถ้าฉันเหมือนกับ n-1 แล้ว
-
คืนค่า True
-
-
ถ้า visit[i] ไม่เหมือนกับ 1 แล้ว
-
เยี่ยมชม[i]:=1
-
ขึ้น:=i + nums[i]
-
ลง:=i - nums[i]
-
ถ้าขึ้น
-
แทรกขึ้นในตอนท้ายของการเยี่ยมชม
-
ถ้าลง>=0 แล้ว
-
ลงท้ายการเยี่ยมชม
-
-
คืนค่าเท็จ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น−
ตัวอย่าง
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
