LeetCode(4)

Posted on Edited on In Views:
Symbols count in article: 16k Reading time ≈ 15 mins.

题目库: [94, 144, 145, 226, 110, 105, 107, 543, 113, 116, 129, 108, 617, 404, 222, 'jz40', 912, 1046, 451, 703, 206, 2 , 21, 19, 692, 24, 83, 82, 876, 328, 143, 86, 61, 92, 160]

Trees

94 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        out = []

        def inorder(root):
            if not root:
                return 

            inorder(root.left)
            out.append(root.val)
            inorder(root.right)
        
        inorder(root)
        return out

144 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        out = []
        def preorder(node):
            if not node:
                return
            
            out.append(node.val)
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return out

145 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        out = []
        def postorder(node):
            if not node:
                return
            
            postorder(node.left)
            postorder(node.right)
            out.append(node.val)
        
        postorder(root)
        return out

226 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:

        def invert(node):
            if not node:
                return
            
            node.left, node.right = node.right, node.left
            invert(node.left)
            invert(node.right)
        
        invert(root)
        return root

110 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(node):
            if not node:
                return [0, True]
            
            left_height = height(node.left)
            right_height = height(node.right)

            if not left_height[1] or not right_height[1]:
                return [0, False]

            if (left_height[0] - right_height[0]) > 1 or (left_height[0] - right_height[0]) < -1:
                return [0, False]
            
            return [max(right_height[0], left_height[0]) + 1, True]
        
        return height(root)[-1]

105 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            
            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]
            
            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n - 1, 0, n - 1)

107 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        q = [root]
        out = [[root.val]]
        next_level = []
        while q:
            curr_node = q.pop(0)
            if curr_node.left:
                next_level.append(curr_node.left)
            
            if curr_node.right:
                next_level.append(curr_node.right)
            
            if not q:
                if next_level:
                    temp = []
                    for i in range(len(next_level)):
                        temp.append(next_level[i].val)
                    out.insert(0, temp)

                q = next_level
                next_level = []
        
        return out

543 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def diameter(node):
            if not node:
                return [0, 0]
            
            left_depth = diameter(node.left)
            right_depth = diameter(node.right)

            total_diameter = left_depth[0] + right_depth[0]

            return [max(left_depth[0], right_depth[0]) + 1, max(left_depth[1], right_depth[1], total_diameter)]
        
        return diameter(root)[-1]

113 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        paths = []

        def find_path(node, path, path_sum):
            if not node:
                return

            if not node.left and not node.right and (node.val + path_sum) == targetSum:
                paths.append(path + [node.val])
                return

            find_path(node.left, path + [node.val], path_sum + node.val)
            find_path(node.right, path + [node.val], path_sum + node.val)

        
        find_path(root, [], 0)

        return paths

116 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root

        q = [root]
        curr_level = []
        while q:     
            curr_node = q.pop(0)
            if curr_node.left:
                curr_level.append(curr_node.left)
            
            if curr_node.right:
                curr_level.append(curr_node.right)
            
            if not q:
                for i in range(len(curr_level) - 1):
                    curr_level[i].next = curr_level[i + 1]
                
                q = curr_level
                curr_level = []
            
        return root

129 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        out = 0

        def find_sums(node, num):
            nonlocal out
            
            if not node:
                return
            
            if not node.left and not node.right:
                out += int(num + str(node.val))
            
            find_sums(node.left, num + str(node.val))
            find_sums(node.right, num + str(node.val))
        
        find_sums(root, '')

        return out

108 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def build_tree(subset):
            if not subset:
                return 
            l, r = 0, len(subset) - 1
            mid = l + (l + r) // 2
            curr_node = TreeNode(val=subset[mid], left=build_tree(subset[:mid]), right=build_tree(subset[mid+1:]))
            return curr_node

        return build_tree(nums)

617 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1 or not root2:
            return root1 if not root2 else root2

        def merge(node_1, node_2):
            if not node_1:
                return node_2
            
            if not node_2:
                return node_1
            
            node_1.val = node_1.val + node_2.val
            node_1.left = merge(node_1.left, node_2.left)
            node_1.right = merge(node_1.right, node_2.right)

            return node_1
        
        merge(root1, root2)
        return root1

404 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        left_sum = 0
        
        def find_sum(node, left):
            nonlocal left_sum

            if not node:
                return

            if left and not node.left and not node.right:
                left_sum += node.val
                return
            
            find_sum(node.left, left=True)
            find_sum(node.right, left=False)
        
        find_sum(root, False)
        return left_sum

222 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    # 1.dfs
    def countNodes(self, root: TreeNode) -> int:
        return self.dfs(root, 1)

    def dfs(self, root, k):
        if root==None:
            return 0
        if root.left==None and root.right==None:
            return k
        
        max1 = self.dfs(root.left, 2*k)
        max2 = self.dfs(root.right, 2*k+1)
        return max(max1, max2)

Heap

剑指 Offer 40 Easy

1
2
3
4
5
6
7
8
9
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        import heapq
        heapq.heapify(arr)
        out_lst = []
        for i in range(k):
            out_lst.append(heapq.heappop(arr))
        
        return out_lst

912 Medium

1
2
3
4
5
6
7
8
9
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        import heapq
        heapq.heapify(nums)
        sorted_lst = []
        for i in range(len(nums)):
            sorted_lst.append(heapq.heappop(nums))
        
        return sorted_lst

1046 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        import heapq
        for i in range(len(stones)):
            stones[i] = -stones[i]
        
        heapq.heapify(stones)
        while len(stones) > 1:
            biggest = heapq.heappop(stones)
            s_biggest = heapq.heappop(stones)
            diff = biggest - s_biggest
            if diff:
                heapq.heappush(stones, diff)
            
        if stones:
            return -stones[-1]
        else:
            return 0

451 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def frequencySort(self, s: str) -> str:
        count_dict = {}
        for i in s:
            if i not in count_dict.keys():
                count_dict[i] = -1
            else:
                count_dict[i] -= 1
        
        temp_lst = []
        for i in s:
            temp_lst.append((count_dict[i], i))
        
        import heapq
        heapq.heapify(temp_lst)
        out_str = ''
        for i in range(len(s)):
            out_str += heapq.heappop(temp_lst)[-1]

        return out_str

692 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        from collections import Counter
        from functools import cmp_to_key
        counter = Counter(words)
        words = [(v, k) for k, v in counter.items()]
        def key_sort(x, y):
            if x[0] == y[0]:
                l_x = len(x[1])
                l_y = len(y[1])
                i = 0
                while i < min(l_x, l_y):
                    if x[1][i] < y[1][i]:
                        return 1
                    elif x[1][i] > y[1][i]:
                        return -1
                    
                    i += 1
                
                if l_x < l_y:
                    return 1
                else:
                    return -1

            elif x[0] > y[0]:
                return 1
            else:
                return -1

        words.sort(key=cmp_to_key(key_sort), reverse=True)
        for i in range(k):
            words[i] = words[i][-1]
        return words[:k]

703 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class KthLargest:
    import heapq
    def __init__(self, k: int, nums: List[int]):
        heapq.heapify(nums)
        self.k = k
        self.nums = nums
        while len(self.nums) > k:
            heapq.heappop(self.nums)

    def add(self, val: int) -> int:
        if len(self.nums) < self.k:
            heapq.heappush(self.nums, val)

        elif val > self.nums[0]:
            heapq.heappop(self.nums)
            heapq.heappush(self.nums, val)
        
        return self.nums[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

LinkedList

206 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def reverse(node):
            if not node.next:
                return node
            
            next_node = reverse(node.next)
            next_node.next = node
            return node

        if not head:
            return head
        else:
            last_node = head
            while last_node.next:
                last_node = last_node.next

            reverse(head)
            head.next = None
            return last_node

2 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        l1_num = ''
        l2_num = ''

        while l1:
            l1_num += str(l1.val)
            l1 = l1.next
        
        while l2:
            l2_num += str(l2.val)
            l2 = l2.next
        
        result_num = str(int(l1_num[::-1]) + int(l2_num[::-1]))
        new_head = ListNode(val=int(result_num[-1]))
        curr_head = new_head
        for i in range(len(result_num) - 2, -1, -1):
            curr_node = ListNode(val=int(result_num[i]))
            curr_head.next = curr_node
            curr_head = curr_node
        
        return new_head

21 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 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, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        
        if not l2:
            return l1
        
        if l1.val < l2.val:
            out_head = l1
            l1 = l1.next
        else:
            out_head = l2
            l2 = l2.next

        temp_head = out_head
        while l1 and l2:
            if l1.val < l2.val:
                temp_head.next = l1
                l1 = l1.next
            else:
                temp_head.next = l2
                l2 = l2.next

            temp_head = temp_head.next
        
        if not l1:
            temp_head.next = l2

        if not l2:
            temp_head.next = l1
        
        return out_head

19 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        def remove(node):
            if not node:
                return 0

            curr_level = remove(node.next) + 1

            if curr_level == (n + 1):
                node.next = node.next.next
            
            return curr_level

        curr_level = remove(head)

        if curr_level == n:
            return head.next

        return head

24 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
	def swapPairs(self, head):
		# 递归的终止条件
		if not (head and head.next):
			return head
		# 假设链表是 1->2->3->4
		# 这句就先保存节点2
		tmp = head.next
		# 继续递归，处理节点3->4
		# 当递归结束返回后，就变成了4->3
		# 于是head节点就指向了4，变成1->4->3
		head.next = self.swapPairs(tmp.next)
		# 将2节点指向1
		tmp.next = head
		return tmp

83 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:

        def del_dup(head):
            if not head:
                return head, []
            
            if not head.next:
                return head, [head.val]
            
            curr_node, val_lst = del_dup(head.next)
            if head.val in val_lst:
                return curr_node, val_lst
            else:
                head.next = curr_node
                return head, val_lst + [head.val]
        
        out, _ = del_dup(head)
        return out

82 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:

        def del_dup(head):
            if not head or not head.next:
                return head
            
            next_node = del_dup(head.next)
            if not next_node:
                if head.val == head.next.val:
                    return next_node
                else:
                    head.next = next_node
                    return head

            if head.val == next_node.val:
                return next_node.next
            elif head.val == head.next.val:
                return next_node
            else:
                head.next = next_node
                return head

        out = del_dup(head)
        return out

876 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        def find_mid(head, curr_count=1):
            if not head.next:
                return head, curr_count // 2 + 1

            node, count = find_mid(head.next, curr_count + 1)
            if count == curr_count:
                return head, count
            else:
                return node, count
        
        out, count = find_mid(head)
        return out

328 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        i = 3
        if not head or not head.next:
            return head

        double_head, double_curr = head.next, head.next
        single_head = head
        curr_node = head.next.next
        while curr_node:
            if i % 2 == 0:
                double_curr.next = curr_node
                double_curr = double_curr.next
            else:
                single_head.next = curr_node
                single_head = single_head.next
            
            curr_node = curr_node.next
            i += 1
        
        double_curr.next = None
        single_head.next = double_head

        return head

143 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        stack = []
        second_lst = slow.next
        slow.next = None
        while second_lst:
            stack.append(second_lst)
            second_lst = second_lst.next        

        temp = head
        while stack:
            curr_node = stack.pop()
            temp.next, curr_node.next = curr_node, temp.next
            temp = curr_node.next

86 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        small_head = ListNode()
        large_head = ListNode()
        curr_node, curr_small, curr_large = head, small_head, large_head
        while curr_node:
            if curr_node.val < x:
                curr_small.next = curr_node
                curr_small = curr_small.next
            else:
                curr_large.next = curr_node
                curr_large = curr_large.next
            
            curr_node = curr_node.next
            
        curr_small.next = large_head.next
        curr_large.next = None

        return small_head.next

61 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k == 0 or not head or not head.next:
            return head
        
        n = 1
        cur = head
        while cur.next:
            cur = cur.next
            n += 1
        
        if (add := n - k % n) == n:
            return head
        
        cur.next = head
        while add:
            cur = cur.next
            add -= 1
        
        ret = cur.next
        cur.next = None
        return ret

92 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        stack = []
        new_head = ListNode()
        new_head.next = head
        curr_node = new_head
        i = 1
        left += 1
        right += 1
        while curr_node:
            if i + 1 == left:
                start_node = curr_node
                curr_node = curr_node.next
                i = i + 1
                while i <= right:
                    stack.append(curr_node)
                    curr_node = curr_node.next
                    i += 1

                end_node = curr_node
                
                while stack:
                    start_node.next = stack.pop()
                    start_node = start_node.next
                
                start_node.next = end_node

                break
            
            curr_node = curr_node.next
            i += 1
            
        out = new_head.next
        return out

160 Easy

1
2
3
4
5
6
7
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A
Related Posts