LeetCode 21 - 25 记录

21

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

from typing import Optional, List

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 == None:
            return list2
        if list2 == None:
            return list1
        res_head = ListNode()
        res_head_backup = res_head
        while list1 != None and list2 != None:
            if list1.val <= list2.val:
                res_head.next = list1
                res_head = res_head.next
                list1 = list1.next
            else:
                res_head.next = list2
                res_head = res_head.next
                list2 = list2.next
        if list1 != None:
            res_head.next = list1
        elif list2 != None:
            res_head.next = list2
        return res_head_backup.next

# 将一个 List 转换成单向链表
def generate_linked_list(data:List):
    nodelist = []
    for d in data:
        nodelist.append(ListNode(d))
    for i in range(len(nodelist) - 1):
        nodelist[i].next = nodelist[i + 1]
    return nodelist[0]

# 打印单向链表
def print_linked_list(head:ListNode):
    cursor = head
    print('Linked List: ', end='')
    while cursor != None:
        print(cursor.val, end=' ')
        cursor = cursor.next
    # print('head: ', head.val)
    print()

if __name__ == '__main__':
    solu = Solution()
    list1 = generate_linked_list([1, 2, 4])
    list2 = generate_linked_list([1, 3, 4])
    Output = solu.mergeTwoLists(list1, list2)
    print_linked_list(Output)

简单的题目，和归并排序算法中的合并的那一步比较类似。

22

https://leetcode.com/problems/generate-parentheses/

解法一

繁琐的解法

from typing import List

from leet15_20.leet19 import print_linked_list
class Solution:
    def generateParenthesis(self, n: int) -> List[int]: # temporary modify, then change to str back
        self.num = n
        self.res = []
        nodevalue = 1
        nodesum = 1
        onePath = [1]
        self.findOnePath(-1, nodesum, onePath.copy())
        # print('onePath -->', onePath)
        self.findOnePath(1, nodesum, onePath.copy())
        # print('test')
        result = []
        for each in self.res:
            tmp_str = ''
            for _ in each:
                if _ == 1:
                    tmp_str += '('
                else:
                    tmp_str += ')'
            result.append(tmp_str)
            # print(each)
        # print('test')
        return result

    def findOnePath(self, nodevalue: int, nodesum: int, onePath: List[int]) -> None:
        if len(onePath) == self.num * 2:
            tmp = 0
            for i in onePath:
                tmp = tmp + i
            if tmp == 0:
                self.res.append(onePath)
            return None
        nodesum = nodesum + nodevalue
        onePath.append(nodevalue)
        if nodesum > 0 and nodesum < self.num:
            self.findOnePath(1, nodesum, onePath.copy())
            self.findOnePath(-1, nodesum, onePath.copy())
        elif nodesum == 0:
            self.findOnePath(1, nodesum, onePath.copy())
        else:
            self.findOnePath(-1, nodesum, onePath.copy())

if __name__ == '__main__':
    solu = Solution()
    n = 4
    Output = solu.generateParenthesis(n)
    print(Output)
    print('length of Output:', len(Output))
    for each in Output:
        print(each)

解法二

动态规划，如果理解了，就十分简单。

实现起来，如果手熟的话，就比较简单。

from typing import List

from leet15_20.leet19 import print_linked_list

# 使用动态规划
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return None
        parenthesis_list = []
        parenthesis_list.append(None) # 0 --> None
        parenthesis_list.append(['()']) # 1 --> ['()']
        for i in range(2, n + 1):
            cur_list = []
            for j in range(1, i + 1):
                if j == 1:
                    for each in parenthesis_list[i - j]:
                        tmp = '(' + ')' + each
                        cur_list.append(tmp)
                elif j == i:
                    for each in parenthesis_list[j - 1]:
                        tmp = '(' + each + ')'
                        cur_list.append(tmp)
                else:
                    for left in parenthesis_list[j - 1]:
                        for right in parenthesis_list[i - j]:
                            tmp = '(' + left + ')' + right
                            cur_list.append(tmp)
            parenthesis_list.append(cur_list)
        return parenthesis_list[n]

if __name__ == '__main__':
    solu = Solution()
    Input = 4
    Output = solu.generateParenthesis(Input)
    print(Output)

23

https://leetcode.com/problems/merge-k-sorted-lists/submissions/

利用优先队列来解题。

from typing import List, Optional
from queue import PriorityQueue

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        n = len(lists)
        q = PriorityQueue(n)
        res = ListNode()
        cursor = res
        for i in range(n):
            # print('test-->')
            # print(lists[i].val)
            if lists[i] != None:
                q.put((lists[i].val, i, lists[i]))
        while q.empty() == False:
            key, index, value = q.get()
            # print(key)
            cursor.next = value
            cursor = value
            value = value.next
            if value != None:
                q.put((value.val, index, value))

        return res.next

def generate_linked_list(data:List):
    nodelist = []
    for d in data:
        nodelist.append(ListNode(d))
    for i in range(len(nodelist) - 1):
        nodelist[i].next = nodelist[i + 1]
    return nodelist[0]

def print_linked_list(head:ListNode):
    cursor = head
    print('Linked List: ', end='')
    while cursor != None:
        print(cursor.val, end=' ')
        cursor = cursor.next
    # print('head: ', head.val)
    print()

if __name__ == '__main__':
    solu = Solution()
    lists = [[1,4,5],[1,3,4],[2,6]]
    Input = []
    for each_list in lists:
        tmp_node = generate_linked_list(each_list)
        Input.append(tmp_node)
    # for each_node in Input:
    #    print_linked_list(each_node)
    Output = solu.mergeKLists(Input)
    print_linked_list(Output)

24

https://leetcode.com/problems/swap-nodes-in-pairs/

这道题对照着链表的图，写起来的话，思路还是十分清晰的。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

from typing import Optional

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None or head.next == None:
            return head
        cursor = head
        new_head = head.next
        pre_tail_node = None
        while cursor != None and cursor.next != None:
            first_node = cursor
            second_node = cursor.next
            third_node = cursor.next.next
            second_node.next = cursor
            cursor.next = third_node
            cursor = third_node
            if pre_tail_node == None:
                pass
            else:
                pre_tail_node.next = second_node
            pre_tail_node = first_node
        return new_head

if __name__ == '__main__':
    solu = Solution()
    from singly_list_utils import generate_linked_list, print_linked_list
    Input = generate_linked_list([1, 2, 3, 4, 5])
    Output = solu.swapPairs(Input)
    print_linked_list(Output)

25

https://leetcode.com/problems/reverse-nodes-in-k-group/

from typing import List, Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k == 1:
            return head
        def reverse_head(head:Optional[ListNode]) -> Optional[ListNode]:
            cursor = head
            pre_node = None
            next_node = None
            while cursor.next != None:
                next_node = cursor.next
                cursor.next = pre_node
                pre_node = cursor
                cursor = next_node
            cursor.next = pre_node
            return cursor
        count = 0
        part_head = None
        cursor = head
        flag = 1
        new_head = None
        pre_raw_head = None
        while cursor != None:
            # print('test-->', cursor.val)
            count = count + 1
            if count == 1:
                part_head = cursor
            if count == k:
                if pre_raw_head != None:
                    cur_pre_raw_head = pre_raw_head
                pre_raw_head = part_head
                next_part_head = cursor.next # save the next k nodes's head
                cursor.next = None
                cur_reversed_part_head = reverse_head(part_head)
                part_head.next = next_part_head
                count = 0
                cursor = next_part_head # update cursor
                if flag == 1:
                    new_head = cur_reversed_part_head
                    flag = 0
                else:
                    cur_pre_raw_head.next = cur_reversed_part_head
                continue
            cursor = cursor.next # update cursor
        return new_head


def generate_linked_list(data:List):
    nodelist = []
    for d in data:
        nodelist.append(ListNode(d))
    for i in range(len(nodelist) - 1):
        nodelist[i].next = nodelist[i + 1]
    return nodelist[0]

def print_linked_list(head:ListNode):
    cursor = head
    print('Linked List: ', end='')
    while cursor != None:
        print(cursor.val, end=' ')
        cursor = cursor.next
    # print('head: ', head.val)
    print()

if __name__ == '__main__':
    solu = Solution()
    data_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
    Input_head = generate_linked_list(data_list)
    Input_k = 3
    Output = solu.reverseKGroup(Input_head, Input_k)
    print_linked_list(Output)

我这个代码写得真的有点乱啊。思路是清晰的，但是实现起来，总归是不利落。

也有可能是上课时候偷偷写的缘故，上课写 leetcode，总归是没有在宿舍里面写要更加能够集中精力。