โปรแกรมค้นหาการกระโดดขั้นต่ำที่จำเป็นในการเข้าถึงมูลค่าด้วยพาริตีที่แตกต่างกันใน Python

สมมติว่าเราได้รับรายการหมายเลขที่เรียกว่า nums ที่นี่เราสามารถข้ามไปที่ดัชนี i + ตัวเลข[i] หรือ ไปที่ i − หมายเลข[i] จากดัชนี i หากมีค่าอยู่ในรายการ ดังนั้นเราจึงต้องหาจำนวนการกระโดดที่จำเป็นอย่างน้อยเพื่อให้ได้ค่าอื่นที่มีความเท่าเทียมกันต่างกันโดยรักษาลำดับในอินพุตไม่เปลี่ยนแปลง หากเราไม่สามารถหาจำนวนอื่นที่มีความเท่าเทียมกันต่างกันได้ มันจะถูกตั้งค่าเป็น -1

ดังนั้น ถ้าอินพุตเหมือนกับตัวเลข =[7, 3, 4, 5, 6, 9, 6, 7] ผลลัพธ์จะเป็น [-1, 1, 2, -1, -1, −1, 1 , −1].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน bfs() นี่จะใช้เวลาฉัน

  • q :=คิวคู่ใหม่ที่มีคู่ (i, 0)

  • เห็นแล้ว :=ชุดใหม่

  • ในขณะที่ q ไม่ว่างให้ทำ

    • (j, d) :=ออกจากองค์ประกอบส่วนใหญ่ของ q และลบรายการซ้ายสุดจาก q

    • เพิ่ม j เข้าไป

    • ถ้า (nums[i] + nums[j]) mod 2 ไม่ใช่ศูนย์ ดังนั้น

      • กลับ d

    • สำหรับแต่ละ k ใน [j + nums[j], j − nums[j]] ทำ

      • ถ้า 0 <=k <ขนาดของ nums และ k ไม่เห็น ดังนั้น

        • แทรก (k, d + 1) ที่ด้านขวาสุดของ q

  • กลับ 10^10

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• ans :=รายการใหม่

• สำหรับฉันในช่วง 0 ถึงขนาดของ nums ทำ

  • เห็นแล้ว :=ชุดใหม่

  • x :=bfs(i)

  • ต่อท้าย x ใน ans เมื่อ x <10^10 ไม่เช่นนั้น ให้ต่อท้าย -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)):
         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]))

อินพุต

numbers = [7, 3, 4, 5, 6, 9, 6, 7]

ผลลัพธ์

[−1, 1, 2, −1, −1, −1, 1, −1]