Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm độ dài của thanh dài nhất có thể trong Python?

Giả sử chúng ta có một danh sách các số nguyên que. Ở đây mỗi phần tử trong danh sách đại diện cho một thanh có hai đầu, các giá trị này nằm trong khoảng từ 1 đến 6. Chúng đại diện cho mỗi đầu. Chúng ta có thể kết nối hai que với nhau nếu bất kỳ đầu nào của chúng giống nhau. Các đầu của que kết quả sẽ là các đầu còn lại và chiều dài của nó được tăng lên. Chúng ta phải tìm chiều dài của cây gậy dài nhất có thể.

Vì vậy, nếu đầu vào giống như stick =[[2, 3], [2, 4], [3, 5], [6, 6]], thì đầu ra sẽ là 3, vì chúng ta có thể kết nối [2, 3 ] và [2, 4] để lấy [3, 4], chúng ta có thể kết nối nó với [3, 5] để lấy [4, 5].

Để 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 dfs (). Thao tác này sẽ đưa nút, edge_idx và một tập hợp được truy cập

  • nếu edge_idx không phải là null, thì

    • nếu edge_idx được truy cập, thì

      • trả về 0

    • đánh dấu edge_idx là đã truy cập

    • res:=0

    • đối với mỗi e_idx trong g [node], hãy thực hiện

      • n_node:=stick [e_idx, 0] khi stick [e_idx, 1] giống với nút nếu không thì stick [e_idx, 1]

      • res:=tối đa res và 1 + dfs (n_node, e_idx, đã truy cập)

    • nếu edge_idx khác 0 thì

      • xóa edge_idx khỏi đã truy cập

    • trả lại res

  • Từ phương thức chính, thực hiện như sau:

  • stick:=danh sách cho tất cả các s trong que tính (s [0], s [1])

  • đỉnh:=một tập hợp mới

  • g:=một bản đồ trống

  • đối với mỗi chỉ số i và cạnh trong que tính, thực hiện

    • chèn tôi vào g [edge [0]]

    • chèn tôi vào g [edge [1]]

    • chèn cạnh [0] và cạnh [1] vào các đỉnh

  • res:=0

  • đối với mỗi v trong các đỉnh, thực hiện

    • res:=tối đa của res và dfs (v, null và rỗng)

  • trả về res - 1

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 defaultdict

class Solution:
   def solve(self, sticks):
      def dfs(node, edge_idx, visited):
         if edge_idx is not None:
            if edge_idx in visited:
               return 0
            visited.add(edge_idx)
         res = 0
         for e_idx in g[node]:
            n_node = sticks[e_idx][0] if sticks[e_idx][1] == node else sticks[e_idx][1]
            res = max(res, 1 + dfs(n_node, e_idx, visited))
         if edge_idx:
            visited.remove(edge_idx)
         return res

      sticks = [(s[0], s[1]) for s in sticks]
      vertices = set()
      g = defaultdict(set)
      for i, edge in enumerate(sticks):
         g[edge[0]].add(i)
         g[edge[1]].add(i)
         vertices.add(edge[0])
         vertices.add(edge[1])
      res = 0
      for v in vertices:
         res = max(res, dfs(v, None, set()))
      return res - 1

ob = Solution()
sticks = [
   [2, 3],
   [2, 4],
   [3, 5],
   [6, 6]
]
print(ob.solve(sticks))

Đầu vào 

sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ]

Đầu ra 

3