ให้ลิสต์ nums จากดัชนี i กระโดดไป i + nums[i] หรือ i - nums[i] ได้ หาจำนวนกระโดดน้อยที่สุดจากแต่ละดัชนี เพื่อถึงค่าที่ parity (คู่/คี่) ต่างจากจุดเริ่มต้น หากไม่ถึงได้ให้ -1
ตัวอย่าง: [7, 3, 4, 5, 6, 9, 6, 7] → [-1, 1, 2, -1, -1, -1, 1, -1]
อัลกอริธึม BFS จากแต่ละดัชนี
- สำหรับแต่ละดัชนี เริ่ม BFS หาเป้าหมายที่ parity ต่างกัน
- ใช้ queue เก็บ (index, distance) และ set
seenป้องกันวนซ้ำ - ถ้าหาไม่เจอคืนค่าสูงมาก แล้วแปลงเป็น -1
การนำไปใช้
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)):
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])) # [-1, 1, 2, -1, -1, -1, 1, -1]
