Cho mảng nums. Từ chỉ số i có thể nhảy đến i + nums[i] hoặc i - nums[i] (nếu trong mảng). Tìm số bước nhảy ít nhất để đến giá trị có chẵn/lẻ khác với nums[i]. Không đạt được thì -1.
Ví dụ: numbers = [7, 3, 4, 5, 6, 9, 6, 7] -> [-1, 1, 2, -1, -1, -1, 1, -1].
Chạy BFS từ mỗi chỉ số i, trạng thái (vị trí, bước). Kiểm tra parity khi thăm.
Ví dụ
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]))
Đầu vào
[7, 3, 4, 5, 6, 9, 6, 7]
Đầu ra
[-1, 1, 2, -1, -1, -1, 1, -1]