leetcode 373(bfs + heap), 328(구현), 21(merge two linked list구현)

373 https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

단순히 O(n^2)으로 돌면서 힙에 넣은후 힙에서 k를 빼내는식으로 하면 메모리 초과가 난다. 메모리 초과를 피하기 위해 가장 가능성이 높은 인자들만 저장해두고 그중에 빼와서 답을 낸다.
모두 정렬된 상태이므로 첫번째로 가능한건 인덱스로 0,0이다.(nums1의 인덱스 0, nums2의 인덱스 0) 그리고 그다음으로 가능성 있는건 0,1이나 1,0일거다. 이런식으로 확장해나가면 되는데 항상 현재좌표의 (y,x+1), (y+1, x)처럼 확장하면서 이미 방문한 좌표인지 확인이 필요하다.

from heapq import *

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        heap = [(nums1[0] + nums2[0], 0, 0)]  # 시작은 (0,0)
        visited = set()
        visited.add((0, 0))
        ret = []
        while heap and len(ret) < k:
            _, n1, n2 = heappop(heap)
            ret.append([nums1[n1], nums2[n2]])
            if (n1, n2+1) not in visited and n2+1 < len(nums2):  # 다음좌표는 y, x+1
                visited.add((n1, n2+1))
                heappush(heap, (nums1[n1] + nums2[n2+1], n1, n2+1))
            if (n1+1, n2) not in visited and n1+1 < len(nums1):  # 다음좌표는 y+1, x
                visited.add((n1+1, n2))
                heappush(heap, (nums1[n1+1] + nums2[n2], n1+1, n2))
        return ret

328 https://leetcode.com/problems/odd-even-linked-list/

 

말그대로 구현하면된다.

class Solution(object):
    def oddEvenList(self, head):
        if not head:
            return head
        start_node = odd_node = head
        fist_even_node = even_node = head.next
        while even_node and even_node.next:
            head = even_node.next
            odd_node.next = head
            odd_node = head
            even_node.next = head.next
            even_node = head.next
        odd_node.next = fist_even_node
        return start_node

21 https://leetcode.com/problems/merge-two-sorted-lists/

 

이미 정렬된 리스트이므로 두 리스트를 비교하면서 둘중 작은 값을 빼서 next에 넣는식으로 구현한다. 이후에 list1이나 list2둘중 하나가 남아있을것이므로 그 남아있는걸 끝에 붙여주면 끝난다

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        node = start = ListNode()
        while list1 and list2:
            if list1 and list2 and list1.val < list2.val:
                start.next = list1
                list1 = list1.next
            else:
                start.next = list2
                list2 = list2.next
            start = start.next
        start.next = list1 or list2
        return node.next

discussion에 정말 간단하고 인상적으로 줄여놓은 답들이 있어서 가져온다..

 

https://leetcode.com/problems/merge-two-sorted-lists/discuss/9771/Simple-5-lines-Python

 

감탄이 나오는 깔끔한 답변..

class Solution:
    def mergeTwoLists(self, a, b):
        if a and b:
            if a.val > b.val:
                a, b = b, a
            a.next = self.mergeTwoLists(a.next, b)
        return a or b