LeetCode (2)

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

题目库: [242, 205, 215, 347, 349, 148, 1122, 973, "jz45", 147, 56, 57, 922, 104, 100, 101, 17, 102, 200, 98, 111, 112 103, 199, 994, 114]

Strings

242 Easy

先排序再比较就行，或者我们可以统计每个字母出现次数，关键是要明白字符数量不同就不相同

1
2
3
4
5
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s = sorted(s)
        t = sorted(t)
        return s == t

205 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        mapping_s = {}
        mapping_t = {}
        for i, j in zip(s, t):
            if i not in mapping_s.keys():
                mapping_s[i] = j
                if j in mapping_t.keys():
                    return False
                mapping_t[j] = i

            else:
                if mapping_s[i] != j:
                    return False

        return True

Sort

215 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution_1:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # selection sort
        n = len(nums)
        def find_max(start):
            max_num = nums[start]
            idx = start
            for i in range(start + 1, n):
                if max_num < nums[i]:
                    max_num = nums[i]
                    idx = i

            return idx

        j = 0
        while j < k:
            max_idx = find_max(j)
            val = nums[j]
            nums[j] = nums[max_idx]
            nums[max_idx] = val

            j += 1
        
        return nums[j - 1]
    
class Solution_2:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(nums, l, r):
            first_small = l
            for j in range(l, r):
                if nums[j] > nums[r]:
                    swap(nums, first_small, j)
                    first_small += 1

            swap(nums, first_small, r)
            return first_small
        
        def swap(nums, i, j):
            temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp

        import random
        random.shuffle(nums)
        # random shuffle 不然quick selection会慢
        l, r = 0, len(nums) - 1
        k = k - 1
        while l < r:
            q = partition(nums, l, r)
            if q == k:
                return nums[q]
            elif q > k: 
                r = q - 1
            else:
                l = q + 1
        
        return nums[l]

347 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 topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq_dict = {}
        for i in nums:
            if i in freq_dict.keys():
                freq_dict[i] += 1
            else:
                freq_dict[i] = 1
        
        nums = []
        for i, v in freq_dict.items():
            nums.append((v, i))

        nums.sort(key=lambda x: x[0], reverse=True)

        out = []
        for counts, idx in nums:
            if len(out) == k:
                break
            out.append(idx)

        return out

349 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
39
40
41
42
43
44
45
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # merge sort
        def merge_sort(nums):
            if len(nums) <= 1:
                return nums
            else:
                mid = len(nums) // 2
                left_lst = merge_sort(nums[:mid])
                right_lst = merge_sort(nums[mid:])
                out_lst = []
                while left_lst or right_lst:
                    if not left_lst:
                        out_lst.extend(right_lst)
                        break
                    elif not right_lst:
                        out_lst.extend(left_lst)
                        break
                    elif left_lst[0] > right_lst[0]:
                        out_lst.append(right_lst.pop(0))
                    else:
                        out_lst.append(left_lst.pop(0))
                
                return out_lst
        # binary search
        def binary_search(sort_lst, target_lst):
            out_lst = []
            for target in target_lst:
                l, r = 0, len(sort_lst) - 1
                if target not in out_lst:
                    while l <= r:
                        mid = l + (r - l) // 2
                        if target == sort_lst[mid]:
                            out_lst.append(target)
                            break
                        elif sort_lst[mid] > target:
                            r = mid - 1
                        else:
                            l = mid + 1

            return out_lst


        nums2 = merge_sort(nums2)
        return binary_search(nums2, nums1)

148 Medium

十分丑陋的merge sort

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

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

        def traverse(lst, t):
            if t == 0:
                return None, lst

            curr_node = lst
            while t > 0:
                if t == 1:
                    right = curr_node.next
                    curr_node.next = None
                
                curr_node = curr_node.next
                t -= 1

            return lst, right

        def merge_sort(lst, length):
            if length <= 1 :
                return lst
            else:
                mid = length // 2
                left, right = traverse(lst, mid)
                left_lst = merge_sort(left, mid)
                right_lst = merge_sort(right, length - mid)
                
                if not left_lst:
                    return right_lst
                elif not right_lst:
                    return left_lst
                elif left_lst.val > right_lst.val:
                    out_lst = right_lst
                    curr_out_node = right_lst
                    right_lst = right_lst.next
                else:
                    out_lst = left_lst
                    curr_out_node = left_lst
                    left_lst = left_lst.next

                while True:
                    if not left_lst:
                        curr_out_node.next = right_lst
                        break
                    elif not right_lst:
                        curr_out_node.next = left_lst
                        break
                    elif left_lst.val > right_lst.val:
                        curr_out_node.next = right_lst
                        right_lst = right_lst.next
                    else:
                        curr_out_node.next = left_lst
                        left_lst = left_lst.next
                    
                    curr_out_node = curr_out_node.next
                
                return out_lst

        length = 0
        curr_pos = head
        while curr_pos:
            curr_pos = curr_pos.next
            length += 1
        
        return merge_sort(head, length)

75 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
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution_1:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # quick sort
        def partition(nums, l, r):
            large_start = l
            for i in range(l, r):
                if nums[i] <= nums[r]:
                    swap(nums, large_start, i)
                    large_start += 1
                    
            swap(nums, large_start, r)
            return large_start

        def swap(nums, i, j):
            temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp
            
        def quick_sort(nums, l, r):
            if (r - l) <= 0:
                return nums
            else:
                mid = partition(nums, l, r)
                left_lst = quick_sort(nums, l, mid - 1)
                right_lst = quick_sort(nums, mid + 1, r)

                return left_lst + [nums[mid]] + right_lst
                
        quick_sort(nums, 0, len(nums) - 1)

class Solution_2:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # insertion sort

        def swap(nums, i, j):
            temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp

        for i in range(len(nums)):
            j = i
            while j > 0:
                if nums[j] < nums[j - 1]:
                    swap(nums, j, j - 1)
                    j -= 1
                else:
                    break

1122 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:

        start = 0
        for v in arr2:
            while (v in arr1[start:]):
                idx = arr1[start:].index(v) + start
                temp = arr1[start]
                arr1[start] = arr1[idx]
                arr1[idx] = temp
                start += 1
        

        out = arr1[:start]
        out.extend(sorted(arr1[start:]))

        return  out

973 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
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:

        def cal_dist(point):
            return point[0]**2 + point[1]**2

        def partition(nums, l, r):
            large_start = l
            pivot = cal_dist(nums[r])
            for i in range(l, r):
                if cal_dist(nums[i]) <= pivot:
                    swap(nums, large_start, i)
                    large_start += 1
                    
            swap(nums, large_start, r)
            return large_start

        def swap(nums, i, j):
            temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp
            
        def quick_sort(nums, l, r, k):
            if (r - l) <= 0:
                pass
            else:
                mid = partition(nums, l, r)
                diff = k - mid - 1

                if diff < 0:
                    quick_sort(nums, l, mid - 1, k)
                elif diff > 0:
                    quick_sort(nums, mid + 1, r, k)

        quick_sort(points, 0, len(points) - 1, k)

        return points[:k]

剑指 Offer 45. 把数组排成最小的数 Medium

1
2
3
4
5
6
7
8
class Key(str):
    def __lt__(self, other):
        return self + other < other + self

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        nums = sorted([str(i) for i in nums], key=Key)
        return "".join(nums)

147 Medium

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

            prev_node, curr_node = curr_node, curr_node.next
        
        return head

56 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: (x[0], x[1]))
        i = 0
        while i < (len(intervals) - 1):
            if intervals[i + 1][0] <= intervals[i][1]:
                r = max(intervals[i][1], intervals[i + 1][1])
                intervals[i] = [intervals[i][0], r]
                intervals.pop(i + 1)
            else:
                i += 1
        
        return intervals

57 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        def merge(intervals: List[List[int]]) -> List[List[int]]:
            intervals.sort(key=lambda x: (x[0], x[1]))
            i = 0
            while i < (len(intervals) - 1):
                if intervals[i + 1][0] <= intervals[i][1]:
                    r = max(intervals[i][1], intervals[i + 1][1])
                    intervals[i] = [intervals[i][0], r]
                    intervals.pop(i + 1)
                else:
                    i += 1
            
            return intervals
            
        intervals.append(newInterval)
        return merge(intervals)

922 Easy

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        nums.sort()
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if (i % 2) == (nums[j] % 2):
                    temp = nums[i]
                    nums[i] = nums[j]
                    nums[j] = temp
                    break

        return nums

Search

104 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 maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        elif not root.left and not root.right:
            return 1
        else:
            l = self.maxDepth(root.left) + 1
            r = self.maxDepth(root.right) + 1

            return max(l, r)

101 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 isSymmetric(self, root: TreeNode) -> bool:

        def symmetric(root_1, root_2):
            if not root_1 and not root_2:
                return True
            else:
                if (not root_1 and root_2) or (root_1 and not root_2):
                    return False
                elif root_1.val != root_2.val:
                    return False
                else:
                    check_left = symmetric(root_1.left, root_2.right)
                    check_right = symmetric(root_1.right, root_2.left)
                    return check_left and check_right

        return symmetric(root.left, root.right)

100 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def check_same(root_1, root_2):
            if not root_1 and not root_2:
                return True
            elif (not root_1 and root_2) or (root_1 and not root_2):
                return False
            elif root_1.val != root_2.val:
                return False
            else:
                left = check_same(root_1.left, root_2.left)
                right = check_same(root_1.right, root_2.right)
                return left and right
        
        return check_same(p, q)

17 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
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        dig_map = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']
        }

        q = dig_map[digits[0]][:]

        for i in range(1, len(digits)):
            for _ in range(len(q)):
                head = q.pop(0)
                for k in dig_map[digits[i]]:
                    q.append(''.join([head, k]))
        
        return q

102 Meidum

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
# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        q = [[root]]
        levels = []
        while q:
            head = q.pop()
            next_nodes = []
            curr_level = []
            for i in head:
                if i.left:
                    next_nodes.append(i.left)

                if i.right:
                    next_nodes.append(i.right)
                
                curr_level.append(i.val)

            if next_nodes:
                q.append(next_nodes)

            levels.append(curr_level)

        return levels

200 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
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        def clear_island(i, j):
            if grid[i][j] == '0':
                return 
            else:
                grid[i][j] = '0'
                if (i + 1) < m:
                    clear_island(i + 1, j)

                if (i - 1) >= 0:
                    clear_island(i - 1, j)
                
                if (j - 1) >= 0:
                    clear_island(i, j - 1)
                
                if (j + 1) < n:
                    clear_island(i, j + 1)
        
        counts = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    counts += 1
                    clear_island(i, j)

        return counts

98 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
# 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_1:
    def isValidBST(self, root: TreeNode) -> bool:

        def is_valid(root, lower=float('-inf'), upper=float('inf')):
            if not root:
                return True
            elif root.val >= upper or root.val <= lower:
                return False
            else:
                left = is_valid(root.left, lower, root.val)
                right = is_valid(root.right, root.val, upper)

                return left and right
        
        return is_valid(root)

class Solution_2:
    def isValidBST(self, root: TreeNode) -> bool:
        def tree(node):
            if not node:
                return
            tree(node.left)
            ls.append(node.val)
            tree(node.right)
        
        ls = []
        tree(root)
        for i in range(len(ls)-1):
            if ls[i] >= ls[i+1]:
                return False
        return True

111 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        if not root.left and not root.right:
            return 1
        
        min_depth = 10**9
        if root.left:
            min_depth = min(self.minDepth(root.left), min_depth)
        if root.right:
            min_depth = min(self.minDepth(root.right), min_depth)
        
        return min_depth + 1

112 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        def cal_sum(root, num):
            if not root:
                return False
            
            if not root.left and not root.right and root.val == num:
                return True

            left = cal_sum(root.right, num - root.val)
            right = cal_sum(root.left, num - root.val)
        
            return left or right
        
        return cal_sum(root, targetSum)

103 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
41

# 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 zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        q = [[root]]
        i = 0
        out_lst = [[root.val]]
        while True:
            nodes = q.pop(0)
            temp_lst = []
            for j in range(len(nodes) - 1, -1, -1):
                if i % 2 == 0:
                    if nodes[j].right:
                        temp_lst.append(nodes[j].right)

                    if nodes[j].left:
                        temp_lst.append(nodes[j].left)
                
                else:
                    if nodes[j].left:
                        temp_lst.append(nodes[j].left)
                    
                    if nodes[j].right:
                        temp_lst.append(nodes[j].right)

            if not temp_lst:
                break

            i += 1
            q.append(temp_lst)
            out_lst.append([k.val for k in temp_lst])
        
        return out_lst

199 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 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 rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        q = [[root]]
        out = [root.val]
        while True:
            nodes = q.pop(0)
            temp_lst = []
            for node in nodes:
                if node.left:
                    temp_lst.append(node.left)
                
                if node.right:
                    temp_lst.append(node.right)
            
            if not temp_lst:
                break
            
            out.append(temp_lst[-1].val)
            q.append(temp_lst)

        return out

994 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n, d = len(grid), len(grid[0])
        q = []
        counts = 0
        for i in range(n):
            for j in range(d):
                if grid[i][j] == 1:
                    counts += 1

                if grid[i][j] == 2:
                    q.append((i, j))

        rounds = 0
        while q and (counts > 0):
            for _ in range(len(q)):
                i, j = q.pop(0)
                # check up
                if i != 0:
                    if grid[i - 1][j] == 1:
                        grid[i - 1][j] = 2
                        q.append((i - 1, j))
                        counts -= 1

                # check down
                if i != (n - 1):
                    if grid[i + 1][j] == 1:
                        grid[i + 1][j] = 2
                        q.append((i + 1, j))
                        counts -= 1

                # check left
                if j != 0:
                    if grid[i][j - 1] == 1:
                        grid[i][j - 1] = 2
                        q.append((i, j - 1))
                        counts -= 1

                # check right
                if j != (d - 1):
                    if grid[i][j + 1] == 1:
                        grid[i][j + 1] = 2
                        q.append((i, j + 1))
                        counts -= 1

            

            rounds += 1
        
        for i in range(n):
            for j in range(d):
                if grid[i][j] == 1:
                    return -1

        return rounds


114 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
# 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 flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        def linked_lst_tree(root):
            if not root:
                return None

            if not root.left and not root.right:
                return root

            left = linked_lst_tree(root.left)
            right = linked_lst_tree(root.right)
            
            if left:
                temp = left
                while temp.right:
                    temp = temp.right

                temp.right = right
                root.right = left
                root.left = None

            return root
        
        linked_lst_tree(root)
Related Posts