โปรแกรมค้นหาจำนวนขั้นตอนขั้นต่ำในการเข้าถึงดัชนีสุดท้ายใน Python

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

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[4, 8, 8, 5, 4, 6, 5] ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถข้ามจากดัชนี 0 ไปเป็นดัชนี 4 ได้ เนื่องจากค่าของมันคือ 4 และ จากนั้นเราข้ามกลับไปที่ดัชนี 3 สุดท้ายเราสามารถข้ามจากดัชนี 3 เป็น 6 เนื่องจากค่าทั้งสองเป็น 5.

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

• pos :=แผนที่ว่างเปล่า
• สำหรับแต่ละดัชนี i และค่า n เป็น nums ทำ
  • ใส่ i ต่อท้าย pos[n]
• n :=ขนาดของ nums
• เข้าชมแล้ว :=ทำรายการขนาด n และกรอกเป็นเท็จ
• เข้าชมแล้ว[0] :=จริง
• ในขณะที่ q ไม่ว่างเปล่า ให้ทำ
  • (u, d) :=องค์ประกอบด้านซ้ายของ q และลบองค์ประกอบด้านซ้าย
  • ถ้าคุณเหมือนกับ n - 1 แล้ว
    • คืนสินค้า
  • สำหรับแต่ละ v ในรายการ pos[nums[u]] และ [u - 1, u + 1], do
    • ถ้า 0 <=v
    • เยี่ยมชม[v] :=True
    • ใส่คู่ (v, d + 1) ที่ส่วนท้ายของ q
• ลบ pos[nums[u]]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, nums):
      from collections import defaultdict, deque
      pos = defaultdict(list)
      for i, n in enumerate(nums):
         pos[n].append(i)
      q = deque([(0, 0)])
      n = len(nums)
      visited = [False] * n
      visited[0] = True
      while q:
         u, d = q.popleft()
         if u == n - 1:
            return d
         for v in pos[nums[u]] + [u - 1, u + 1]:
            if 0 <= v < n and not visited[v]:
               visited[v] = True
               q.append((v, d + 1))
         del pos[nums[u]]
ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))

อินพุต

[4, 8, 8, 5, 4, 6, 5]

ผลลัพธ์

3