Giả sử, chúng ta được cung cấp một danh sách các số được gọi là nums. Ở đây chúng ta có thể chuyển đến chỉ mục i + số [i] hoặc đến i - số [i] từ chỉ mục i nếu các giá trị tồn tại trong danh sách. Vì vậy, chúng ta phải tìm số bước nhảy cần thiết ít nhất để đạt đến một giá trị khác với độ chẵn lẻ khác nhau giữ cho thứ tự trong đầu vào không thay đổi. Nếu chúng ta không thể đạt đến một số khác có độ chẵn lẻ khác, nó được đặt thành −1.
Vì vậy, nếu đầu vào là các số =[7, 3, 4, 5, 6, 9, 6, 7], thì đầu ra sẽ là [−1, 1, 2, −1, −1, −1, 1 , −1].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm bfs (). Điều này sẽ mất tôi
-
q:=một hàng đợi kép mới kết thúc bằng một cặp (i, 0)
-
đã thấy:=một tập hợp mới
-
trong khi q không trống, thực hiện
-
(j, d):=phần tử bên trái nhất của q và xóa phần tử ngoài cùng bên trái khỏi q
-
thêm j vào đã thấy
-
if (nums [i] + nums [j]) mod 2 khác 0, thì
-
trở lại d
-
-
với mỗi k trong [j + nums [j], j - nums [j]], thực hiện
-
nếu 0 <=k
-
chèn (k, d + 1) vào cuối bên phải của q
-
-
-
-
trả về 10 ^ 10
-
-
Từ phương thức chính, hãy làm như sau -
-
ans:=một danh sách mới
-
đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện
-
đã thấy:=một tập hợp mới
-
x:=bfs (i)
-
nối x trong ans khi x <10 ^ 10 nếu không thì nối thêm −1
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)): 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]))
Đầu vào
numbers = [7, 3, 4, 5, 6, 9, 6, 7]
Đầu ra
[−1, 1, 2, −1, −1, −1, 1, −1]