Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 몇 가지 공통 노드가 있는 두 개의 정렬된 연결 목록에서 최대 합 연결 목록을 구성합니다.

<시간/>

두 개의 정렬된 연결 목록이 있다고 가정하면 시작 노드에서 끝 노드까지의 최대 합 경로로 구성된 연결 목록을 만들어야 합니다. 최종 목록은 두 입력 목록의 노드로 구성될 수 있습니다.

결과 목록을 생성할 때 교차점(목록에서 동일한 값을 갖는 두 노드)에 대해서만 다른 입력 목록으로 전환할 수 있습니다. 일정한 양의 추가 공간을 사용하여 해결해야 합니다.

따라서 입력이 [6,8,35,95,115,125], [5,8,17,37,95,105,125,135]와 같으면 출력은 [6,8,17,37,95,115,125,135]

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 결과 :=없음

  • 이전1 :=a, 현재1 :=a

  • 이전2 :=b, 현재2 :=b

  • current1이 None과 같지 않거나 current2가 None과 같지 않은 동안 do

    • res1 :=0, res2 :=0

    • current1 및 current2가 null이 아니고 current1의 데이터가 current2의 데이터와 같지 않은 동안 do

      • 현재1의 데이터 <현재2의 데이터인 경우

        • res1 :=res1 + current1 데이터

        • current1 :=current1의 다음

      • 그렇지 않으면

        • res2 :=res2 + current2 데이터

        • current2 :=current2의 다음

    • current1이 null이면

      • current2가 null이 아닌 동안 수행

        • res2 :=res2 + current2 데이터

        • current2 :=current2의 다음

    • current2가 null이면

      • current1이 null이 아닌 동안 수행

        • res1 :=res1 + current1 데이터

        • current1 :=current1의 다음

    • 이전1이 b와 같고 이전2가 b와 같으면

      • 결과 :=이전1 일 때 (res1> res2) 그렇지 않으면 이전2

    • 그렇지 않으면

      • res1> res2인 경우

        • 이전2의 다음 :=이전1의 다음

      • 그렇지 않으면

        • 이전1의 다음 :=이전2의 다음

    • 이전1 :=현재1

    • 이전2 :=현재2

    • current1이 null이 아니면

      • current1 :=current1의 다음

    • current2가 null이 아니면

      • current2 :=current2의 다음

  • 결과의 내용을 표시합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class LinkedList(object):
   def __init__(self, data_set = []):
      self.head = None
      if len(data_set) > 0:
         for item in data_set:
            self.insert_node(item)
   class ListNode(object):
      def __init__(self, d):
         self.data = d
         self.next = None
   def insert_node(self, new_data):
      new_node = self.ListNode(new_data)
      new_node.next = self.head
      self.head = new_node
   def find_max_sum_list(self, a, b):
      result = None
      previous1 = a
      current1 = a
      previous2 = b
      current2 = b
      while current1 != None or current2 != None:
         res1 = 0
         res2 = 0
         while current1 != None and current2 != None and current1.data != current2.data:
            if current1.data < current2.data:
               res1 += current1.data
               current1 = current1.next
            else:
               res2 += current2.data
               current2 = current2.next
         if current1 == None:
            while current2 != None:
               res2 += current2.data
               current2 = current2.next
         if current2 == None:
            while current1 != None:
               res1 += current1.data
               current1 = current1.next
         if previous1 == a and previous2 == b:
            result = previous1 if (res1 > res2) else previous2
         else:
            if res1 > res2:
               previous2.next = previous1.next
            else:
               previous1.next = previous2.next
         previous1 = current1
         previous2 = current2
         if current1 != None:
            current1 = current1.next
         if current2 != None:
            current2 = current2.next
      while result != None:
         print(result.data, end = ' ')
         result = result.next
my_list1 = LinkedList([125,115,95,35,8,6])
my_list2 = LinkedList([135,125,105,95,37,17,8,5])
my_list1.find_max_sum_list(my_list1.head, my_list2.head)

입력

[125,115,95,35,8,6], [135,125,105,95,37,17,8,5]

출력

6 8 17 37 95 115 125 135