Leetcode秋招指路

置顶 发表于 分类于 阅读次数： 本文字数： 33k 阅读时长 ≈ 30 分钟

1. 数组

1.1 哈希表

1
2
3
4
5
6
7
8
class Solution: 
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target-num in hashtable:
                return [hashtable[target-num], i]
            hashtable[num] = i
        return []

1.2 滑动窗口

1.2.1 和大于等于target的最短子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        start, end = 0, 0
        n = len(nums)
        ans = n + 1
        s = 0
        while end < n:
            s += nums[end]
            while s >= target:
                ans = min(ans, end-start+1)
                s -= nums[start]
                start += 1
            end += 1
        return 0 if ans == n+1 else ans
1.2.2 乘积小于K的子数组

1
2
3
4
5
6
7
8
9
10
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans, prob, i = 0, 1, 0
        for j, num in enumerate(nums):
            prob *= nums[j]
            while i<=j and prob>=k:
                prob /= nums[i]
                i += 1
            ans += j-i+1 # [i, j]满足要求，其子串也满足要求，以j为末尾的子串共j-i+1个
        return ans
1.2.3 无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        l, r = 0, 0
        ans, window = 0, set()
        while r < len(s):
            while l<=r and s[r] in window:
                window.remove(s[l])
                l += 1
            window.add(s[r])
            ans = max(ans, r-l+1)
            r += 1
        return ans

1.3 双指针

可用来优化空间复杂度

1.3.1 乘最多水的容器

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r, ans = 0, len(height)-1, 0
        while l < r:
            if height[l] < height[r]:
                ans = max(ans, height[l]*(r-l))
                l += 1
            else:
                ans = max(ans, height[r]*(r-l))
                r -= 1
        return ans
1.3.2 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans, n = [], len(nums)

        for k in range(n-2):
            i, j = k+1, n-1
            if nums[k] > 0: return ans # 第一个数为正数，因此后续不存在零解
            if k > 0 and nums[k] == nums[k-1]: continue # 避免重复解
            while i < j:
                res = nums[k] + nums[i] + nums[j]
                if res < 0:
                    i += 1
                    while i < j and nums[i] == nums[i-1]: i += 1
                elif res > 0:
                    j -= 1
                    while j > i and nums[j] == nums[j+1]: j -= 1
                else:
                    ans.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i-1]: i += 1
                    while j > i and nums[j] == nums[j+1]: j -= 1
        return ans

1.4 二分查找

1.4.1 模板

满足条件的都写l = mid或者r = mid。如果满足条件选择的是l = mid，那么mid写成l + r + 1 >> 1，否则写成l + r >> 1。然后就是else的写法：l = mid对应r = mid - 1，r = mid对应l = mid + 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 找满足条件最左边的索引
while l < r:
    mid = (l+r) // 2
    if nums[mid] >= target:
        r = mid
    else:
        l = mid + 1
# 找满足条件最右边的索引
while l < r:
    mid = (l+r+1) // 2
    if nums[mid] <= target:
        l = mid
    else:
        r = mid - 1
1.4.2 求根号x的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 二分查找
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x + 1
        while abs(r-l) > 1e-12:
            mid = (l + r) / 2
            if mid * mid <= x:
                l = mid
            else:
                r = mid
        return l
      
# 梯度下降
class Solution:
    def mySqrt(self, x: int) -> int:
        # L = (t^2 - x)^2
        t = x
        while (t**2 - x) > 1e-10:
            t = t - 0.001 * 2*(t**2-x)*2*t
        return t
1.4.3 搜索旋转排序数组

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 search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l, r = 0, n-1
        while l <= r:
            mid = (l+r) // 2
            if nums[mid] == target:
                return mid
            if nums[l] <= nums[mid]:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        
        return -1
1.4.4 排序数组中只出现一次的数字

1
2
3
4
5
6
7
8
9
10
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left, right = 0, len(nums)-1
        while left < right:
            mid = (left+right) >> 1
            if nums[mid] == nums[mid^1]:
                left = mid + 1
            else:
                right = mid 
        return nums[left]

1.5 单调栈

1.5.1 模板
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 largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left, right = [-1]*n, [n]*n
		
        # 右侧第一个小于第i个元素的单调栈
        stack = []
        for i in range(n):
            element = heights[i]
            while stack and heights[stack[-1]] > element:
                tmp = stack.pop()
                right[tmp] = i
            stack.append(i)
        
        # 左侧第一个小于第i个元素的单调栈
        stack = []
        for j in range(n-1, -1, -1):
            element = heights[j]
            while stack and heights[stack[-1]] > element:
                tmp = stack.pop()
                left[tmp] = j
            stack.append(j)
1.5.2 每日温度

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        length = len(temperatures)
        ans = [0] * length
        stack = []
        for i in range(length):
            temperature = temperatures[i]
            while stack and temperature > temperatures[stack[-1]]:
                prev_index = stack.pop()
                ans[prev_index] = i - prev_index
            stack.append(i)
        return ans
1.5.3 小行星碰撞

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
    st = []
    for aster in asteroids:
        alive = True
        while alive and aster < 0 and st and st[-1] > 0:
            alive = st[-1] < -aster
            if st[-1] <= -aster:
                st.pop()
        if alive:
            st.append(aster)
    return st
1.5.4 直方图最大矩形面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left, right = [-1]*n, [n]*n

        stack = []
        for i in range(n):
            element = heights[i]
            while stack and heights[stack[-1]] > element:
                tmp = stack.pop()
                right[tmp] = i
            stack.append(i)
        
        stack = []
        for j in range(n-1, -1, -1):
            element = heights[j]
            while stack and heights[stack[-1]] > element:
                tmp = stack.pop()
                left[tmp] = j
            stack.append(j)
        return max(((right[i]-left[i]-1)*heights[i] for i in range(n)))
1.5.5 矩阵中最大的矩形

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
class Solution:
    def maximalRectangle(self, matrix: List[str]) -> int:
        if not matrix: return 0
        m, n = len(matrix), len(matrix[0])
        lengths = [[0 for j in range(n+1)] for i in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                lengths[i][j] = (lengths[i-1][j]+1) if (matrix[i-1][j-1] == '1') else 0

        area = 0
        for i in range(1, m+1):
            gragh = lengths[i][1:]
            left, right = [-1]*n, [n]*n
            
            stack = []
            for j in range(n):
                element = gragh[j]
                while stack and gragh[stack[-1]] > element:
                    right[stack.pop()] = j
                stack.append(j)
            
            stack = []
            for j in range(n-1, -1, -1):
                element = gragh[j]
                while stack and gragh[stack[-1]] > element:
                    left[stack.pop()] = j
                stack.append(j)
            
            area = max(area, max(((right[j]-left[j]-1)*gragh[j] for j in range(n))))
        return area

1.6 模拟

1.6.1 螺旋矩阵
image-20221107235520161 
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
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []

        ans = []
        l, r, t, b = 0, len(matrix[0])-1, 0, len(matrix)-1
        counts = len(matrix) * len(matrix[0])

        while counts >= 1:
            for i in range(l, r+1):
                if counts >= 1:
                    ans.append(matrix[t][i])
                    counts -= 1
            t += 1

            for i in range(t, b+1):
                if counts >= 1:
                    ans.append(matrix[i][r])
                    counts -= 1
            r -= 1

            for i in range(r, l-1, -1):
                if counts >= 1:
                    ans.append(matrix[b][i])
                    counts -= 1
            b -= 1

            for i in range(b, t-1, -1):
                if counts >= 1:
                    ans.append(matrix[i][l])
                    counts -= 1
            l += 1

        return ans
1.6.2 缺失的第一个正数
image-20221107235845751 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n + 1
        
        for i in range(n):
            num = abs(nums[i])
            if num <= n:
                nums[num - 1] = -abs(nums[num - 1])
        
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        
        return n + 1
1.6.3 旋转图像
image-20221107235948338 
1
2
3
4
5
6
7
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range((n + 1) // 2):
                matrix[i][j], matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1] \
                    = matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1], matrix[i][j]
1.6.4 所有子集

1
2
3
4
5
6
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]
        for num in nums:
            ans.extend([x+[num] for x in ans])
        return ans

1.7 前缀和/哈希表

1.7.1 左右两边子数组的和相等

1
2
3
4
5
6
7
8
9
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        s = 0
        for i, v in enumerate(nums):
            if 2*s == total-v:
                return i 
            s += v
        return -1
1.7.2 和为k的子数组

1
2
3
4
5
6
7
8
9
10
11
# 以当前元素为末尾结合前缀和的思想寻找之前有多少个cur-k
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans, cur = 0, 0
        hash = defaultdict(int)
        hash[0] = 1
        for num in nums:
            cur += num
            ans += hash[cur-k]
            hash[cur] += 1
        return ans
1.7.3 0和1个数相同的子数组

1
2
3
4
5
6
7
8
9
10
11
12
# 由于「0 和 1 的数量相同」等价于「1 的数量减去 0 的数量等于 0」，我们可以将数组中的 0 视作 −1，则原问题转换成「求最长的连续子数组，其元素和为 0」。
class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        mp = {0:-1}
        ans, prevSum = 0, 0
        for i, num in enumerate(nums):
            prevSum += 1 if num else -1
            if prevSum in mp:
                ans = max(ans, i-mp[prevSum])
            else:
                mp[prevSum] = i
        return ans
1.7.4 最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums)

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

1.8 排序

1.8.1 快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quicksort(L, l, r):
            if l >= r:
                return L
            i, j, pivot = l, r, L[l]
            while i < j:
                while i < j and L[j] >= pivot: j -= 1
                while i < j and L[i] <= pivot: i += 1
                if i < j: 
                    L[i], L[j] = L[j], L[i]
            L[l] = L[i]
            L[i] = pivot

            quickselect(L, l, i-1)
            quickselect(L, i+1, r)
            return L
        
        return quickselect(nums, 0, len(nums)-1)[-k]
1.8.2 快速选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quickselect(L, l, r, k):
            index = random.randint(l, r)
            L[l], L[index] = L[index], L[l]
            i, j, pivot = l, r, L[index]
            while i < j:
                while i < j and L[j] >= pivot: j -= 1
                while i < j and L[i] <= pivot: i += 1
                if i < j:
                    L[i], L[j] = L[j], L[i]
            L[l] = L[i]
            L[i] = pivot

            return pivot if i == k else (quickselect(L, i+1, r, k) if i < k else quickselect(L, l, i, k))
        
        return quickselect(nums, 0, len(nums)-1, len(nums)-k)
1.8.3 值和下标之差都在给定的范围内

1
2
3
4
5
6
7
8
9
10
11
12
13
# 维护一个大小为k的滑动窗口s1
from sortedcontainers import SortedList
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        sl = SortedList()
        for i in range(len(nums)):
            sl.add(nums[i])
            if i >= k+1:
                sl.remove(nums[i-k-1])
            index = sl.bisect_left(nums[i])
            if index > 0 and sl[index] - sl[index-1] <= t: return True
            if index < len(sl)-1 and sl[index+1]-sl[index] <= t: return True
        return False

2. 链表

2.1 合并K个升序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def mergeTwo(self, list1, list2):
        head = cur = ListNode()
        c1, c2 = list1, list2
        while c1 and c2:
            if c1.val <= c2.val:
                cur.next = c1
                c1 = c1.next
            else:
                cur.next = c2
                c2 = c2.next
            cur = cur.next
        
        cur.next = c1 if c1 else c2
        return head.next

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0: return None
        if len(lists) == 1: return lists[-1]
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])

        return self.mergeTwo(left, right)

2.2 排序的循环链表

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=None, next=None):
        self.val = val
        self.next = next
"""

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        node = Node(insertVal)
        if not head:
            head = node
            head.next = head
            return head
        if head.next == head:
            head.next = node
            node.next = head
            return head
        
        cur, Next = head, head.next
        while Next != head:
            if cur.val <= insertVal <= Next.val:
                break
            if cur.val > Next.val:
                if insertVal > cur.val or insertVal < Next.val:
                    break
            cur = cur.next
            Next = Next.next
        
        cur.next = node
        node.next = Next
        return head

2.3 快慢指针

2.3.1 定位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB: return None
        cura, curb = headA, headB
        while cura != curb:
            cura = headB if not cura else cura.next
            curb = headA if not curb else curb.next
        return cura

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast, slow = head, head
        while n > 0:
            fast = fast.next
            n -= 1
        if not fast:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next
        return head

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 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:
        if not head: return

        def reverse(node):
            cur, ans = node, None
            while cur:
                Next = cur.next
                cur.next = ans
                ans = cur
                cur = Next
            return ans
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        second = reverse(slow.next)
        slow.next = None
        
        first = head
        while first and second:
            f1 = first.next
            s1 = second.next
            
            first.next = second
            first = f1
            second.next = first
            second = s1
2.3.2 判断是否存在环

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next: return None
        fast, slow = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return fast
        return None

3. 字符串

3.1 回文串

3.1.1 中心扩展法
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        for i in range(2*len(s)-1):
            l = i//2
            r = (i+1)//2
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
                ans += 1
        return ans
3.1.2 Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def countSubstrings(self, s: str) -> int:
        t = '$#'
        for c in s:
            t += c
            t += '#'
        t += '!'

        n = len(t)
        lmax, rmax, res = 0, 0, 0
        p = [0 for _ in range(n)]
        for i in range(1, n-1):
            p[i] = 1 if i > rmax else min(rmax-i+1, p[lmax+rmax-i])
        
            while t[i+p[i]] == t[i-p[i]]:
                p[i] += 1
            
            if i+p[i]-1 > rmax:
                rmax = i + p[i] - 1
                lmax = i - p[i] + 1
            
            res += p[i] // 2
        return res
3.1.3 动态规划

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 partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[True for j in range(n)] for i in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                dp[i][j] = (s[i]==s[j] and dp[i+1][j-1])

        def dfs(i):
            if i == n:
                ans.append(cur[:])
                return
            
            for j in range(i, n):
                if dp[i][j]:
                    cur.append(s[i:j+1])
                    dfs(j+1)
                    cur.pop()

        ans, cur = [], []
        dfs(0)
        return ans

3.2 子串匹配

3.2.1 KMP算法

暂略

3.3 模拟

3.3.1 电话号码的字母组合
image-20221108000451646 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        hashT = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        counts = functools.reduce(lambda x,y:x*y, [len(hashT[k]) for k in digits])
        ans = []
        for i in range(counts):
            last, ss = i, ""
            for j in range(len(digits)-1, -1, -1):
                c = digits[j]
                pos = last % len(hashT[c])
                ss += hashT[c][pos]
                last //= len(hashT[c])
            ans.append(ss[::-1])

        return ans

3.4 滑动窗口

3.4.1 不含重复字符的最长子字符串

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
# Solution 1
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        dct = {s[0] : 0}
        l, r, ans = 0, 1, 1
        while r < len(s):
            if s[r] not in dct:
                dct[s[r]] = r
            else:
                if l <= dct[s[r]]:
                    l = dct[s[r]] + 1

                dct[s[r]] = r
            
            ans = max(ans, r-l+1)
            r += 1
        return ans

# Solution 2
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格，移除一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

4. 堆

heapq.heappush(heap, item)

heapq.heappop(heap)

heapq.heapify(x)

heapq.nlargest(n, iterable, key=None)

heapq.nsmallest(n, iterable, key=None)

4.1 最小堆

4.1.1 寻找两个正序数组的中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1, n2 = len(nums1), len(nums2)
        n = tmp = (n1+n2+1)//2
        h = []
        while tmp:
            if (nums1 and nums2 and nums1[-1] >= nums2[-1]) or not nums2:
                heapq.heappush(h, nums1[-1])
                nums1.pop()
            else:
                heapq.heappush(h, nums2[-1])
                nums2.pop()
            tmp -= 1
        
        if (n1+n2) & 1:
            return h[0]
        else:
            return (h[0]+nums1[-1])/2 if ((nums1 and nums2 and nums1[-1] >= nums2[-1]) or not nums2) else (h[0]+nums2[-1])/2
4.1.2 和最小的k个数对

1
2
3
4
5
6
7
8
9
10
11
12
from itertools import product
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        p = product(nums1[:k], nums2[:k])
        p = [(-_[0]-_[1], _[0], _[1]) for _ in p]
        ans = []
        for item in p:
            if len(ans) == k and item[0] > ans[0][0]:
                heapq.heappushpop(ans, item)
            if len(ans) < k:
                heapq.heappush(ans, item)
        return [(pair[1], pair[2]) for pair in heapq.nlargest(k, ans)]

5. 树

5.1 字典树/前缀树

5.1.1 模板
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
class Trie:
    def __init__(self):
        self.trie = {}

    def insert(self, word: str) -> None:
        curr = self.trie
        for w in word:
            if w not in curr:
                curr[w] = {}
            curr = curr[w]
        curr["#"] = '#'

    def search(self, word: str) -> bool:
        curr = self.trie
        for w in word:
            if w not in curr.keys():
                return False
            curr = curr[w]
        return '#' in curr.keys()

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curr = self.trie
        for w in prefix:
            if w not in curr.keys():
                return False
            curr = curr[w]
        return len(curr)!=0
5.1.2 替换单词

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 replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = {}
        for d in dictionary:
            cur = trie
            for ch in d:
                if ch not in cur:
                    cur[ch] = {}
                cur = cur[ch]
            cur['#'] = {}
        
        words = sentence.split(' ')
        for i, word in enumerate(words):
            cur = trie
            for j, ch in enumerate(word):
                if '#' in cur:
                    words[i] = word[:j]
                    break
                if ch not in cur:
                    break
                cur = cur[ch]
        return ' '.join(words)
5.1.3 最短的单词编码

1
2
3
4
5
6
7
8
9
10
# 存储后缀
class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        s = set(words)

        for word in words:
            for j in range(1, len(word)):
                s.discard(word[j:])

        return sum(len(word) + 1 for word in s)
5.1.4 神奇的字典

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 Trie:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class MagicDictionary:
    def __init__(self):
        self.root = Trie()
    def buildDict(self, dictionary: List[str]) -> None:
        for word in dictionary:
            cur = self.root
            for ch in word:
                if ch not in cur.children:
                    cur.children[ch] = Trie()
                cur = cur.children[ch]
            cur.isEnd = True
    def search(self, searchWord: str) -> bool:
        def dfs(node, pos, modify):
            if pos == len(searchWord):
                return node.isEnd and modify
            ch = searchWord[pos]
            if ch in node.children:
                if dfs(node.children[ch], pos+1, modify):
                    return True
            
            if not modify:
                for k in node.children.keys():
                    if ch != k:
                        if dfs(node.children[k], pos+1, True):
                                return True
            return False 
                
        return dfs(self.root, 0, False)
5.1.5 最大的异或

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
class Trie():
    def __init__(self):
        self.left = None
        self.right = None

class Solution:
    def __init__(self):
        self.root = Trie()
        self.ans = 0
    def findMaximumXOR(self, nums: List[int]) -> int:
        def add(num):
            cur = self.root
            for bit in range(30, -1, -1):
                curbit = (num >> bit) & 1
                if not curbit:
                    if not cur.left:
                        cur.left = Trie()
                    cur = cur.left
                else:
                    if not cur.right:
                        cur.right = Trie()
                    cur = cur.right
    
        def check(num):
            ans = 0
            cur = self.root
            for bit in range(30, -1, -1):
                curbit = (num >> bit) & 1
                if curbit == 1:
                    if cur.left:
                        cur = cur.left
                        ans = ans*2+1
                    else:
                        cur = cur.right
                        ans = ans*2
                else:
                    if cur.right:
                        cur = cur.right
                        ans = ans*2+1
                    else:
                        cur = cur.left
                        ans = ans * 2
            return ans

        for i in range(1, len(nums)):
            add(nums[i-1])
            self.ans = max(self.ans, check(nums[i]))
        return self.ans

5.2 深度优先搜索DFS

5.2.1 从根节点到叶节点的路径数字之和

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 sumNumbers(self, root: TreeNode) -> int:
        self.s = 0
        def dfs(node, num):
            if not node: return
            num = 10*num+node.val
            if not node.left and not node.right:
                self.s += num
            
            dfs(node.left, num)
            dfs(node.right, num)
                
        dfs(root, 0)
        return self.s
5.2.2 所有大于等于节点的值之和

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 convertBST(self, root: TreeNode) -> TreeNode:
        self.total = 0
        def dfs(node):
            if not node: return
            dfs(node.right)
            self.total += node.val
            node.val = self.total
            dfs(node.left)
        dfs(root)
        return root
5.2.3 节点之和的最大路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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 maxPathSum(self, root: TreeNode) -> int:
        self.max = float("-inf")
        def dfs(node):
            if not node: return 0
            # 计算左右子树分别能提供的最大值，如果小于0，可以直接丢掉一边的路径
            l = max(dfs(node.left), 0)
            r = max(dfs(node.right), 0)
            # 以该节点为父节点的子树的最大路径和
            val = node.val + l + r
            self.max = max(self.max, val)
            # 该节点往上只能提供半边的贡献，否则不构成路径
            return max(node.val+l, node.val+r)
        
        dfs(root)
        return self.max

5.3 广度优先搜索BFS

5.3.1 二叉树的层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def BFS(self, root):
        nodeQueue, result = [], []
        if not root: return result
        nodeQueue.append(root)
        while nodeQueue:
            # 这个表示单层节点所有的值
            singleLevel = []            
            queueLength = len(nodeQueue)
            for i in range(0, queueLength):
                currentNode = nodeQueue.pop(0)
                if currentNode.left:
                    nodeQueue.append(currentNode.left)
                if currentNode.right:
                    nodeQueue.append(currentNode.right)
                singleLevel.append(currentNode.val)
            result.append(singleLevel)
        return result

5.4 前缀和

5.4.1 向下的路径节点之和

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
# Solution 1 DFS
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        def rootSum(root, targetSum):
            if root is None:
                return 0

            ret = 0
            if root.val == targetSum:
                ret += 1

            ret += rootSum(root.left, targetSum - root.val)
            ret += rootSum(root.right, targetSum - root.val)
            return ret
        
        if root is None:
            return 0
            
        ret = rootSum(root, targetSum)
        ret += self.pathSum(root.left, targetSum)
        ret += self.pathSum(root.right, targetSum)
        return ret

# Solution 2 前缀和
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        self.ret = 0
        prefix = collections.defaultdict(int)
        prefix[0] = 1

        def dfs(root, curr):
            if not root:
                return 0
            curr += root.val
            self.ret += prefix[curr - targetSum]
            prefix[curr] += 1
            dfs(root.left, curr)
            dfs(root.right, curr)
            prefix[curr] -= 1

        dfs(root, 0)
        return self.ret

6. 深度优先搜索DFS

6.1 模板题

6.1.1 括号生成

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(s, left, right):
            if left > n or right > left: return
            if left + right == 2*n:
                ans.append(s)
                return
            dfs(s+'(', left+1, right)
            dfs(s+')', left, right+1)
        dfs('', 0, 0)
        return ans
6.1.2 岛屿的最大面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(x, y):
            if x < 0 or y < 0 or x == n or y == m or grid[x][y] == 0:
                return 0
            grid[x][y] = 0
            direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            ans = 1
            for (ix, iy) in direction:
                ans += dfs(x+ix, y+iy)
            return ans

        n, m, ans = len(grid), len(grid[0]), 0
        for i, l in enumerate(grid):
            for j, e in enumerate(l):
                ans = max(dfs(i, j), ans)
        return ans

6.2 回溯

6.2.1 允许重复选择元素的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.ans = []
        def dfs(target, idx):
            if target == 0:
                self.ans.append(cur[:])
            elif target < 0:
                return
            else: 
                for i in range(idx, len(candidates)):
                    cur.append(candidates[i])
                    dfs(target-candidates[i], i)
                    cur.pop()
            
        cur = []
        dfs(target, 0)
        return self.ans
6.2.2 含有重复元素集合的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        def dfs(index, target):
            if target < 0:
                return 
            elif target == 0:
                    ans.append(cur[:])
            else:
                for i in range(index, len(candidates)):
                    if i != index and candidates[i] == candidates[i-1]:
                        continue
                    num = candidates[i]
                    cur.append(num)
                    dfs(i+1, target-num)
                    cur.pop()
        ans, cur = [], []
        dfs(0, target)
        return ans

6.2.3 没有重复元素集合的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs():
            if len(cur) == n:
                ans.append(cur[:])
                return

            for i in range(0, n):
                if vis[i]: continue
                cur.append(nums[i])
                vis[i] = 1
                dfs()
                vis[i] = 0
                cur.pop()
            
        
        ans, cur = [], []
        n = len(nums)
        vis = [0] * n
        dfs()
        return ans
6.2.4 含有重复元素集合的全排列

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 permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs():
            if len(cur) == n:
                ans.append(cur[:])
                return

            for i in range(0, n):
                if vis[i] or (not vis[i] and i>0 and nums[i] == nums[i-1] and not vis[i-1]):
                    continue
                cur.append(nums[i])
                vis[i] = 1
                dfs()
                vis[i] = 0
                cur.pop()
        
        nums.sort()
        ans, cur = [], []
        n = len(nums)
        vis = [0] * n
        dfs()
        return ans
6.2.5 分割回文子字符串

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 partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[True for j in range(n)] for i in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                dp[i][j] = (s[i]==s[j] and dp[i+1][j-1])

        def dfs(i):
            if i == n:
                ans.append(cur[:])
                return
            
            for j in range(i, n):
                if dp[i][j]:
                    cur.append(s[i:j+1])
                    dfs(j+1)
                    cur.pop()

        ans, cur = [], []
        dfs(0)
        return ans
6.2.6 复原IP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        n = len(s)
        ans, cur = [], []
        def dfs(i):
            if len(cur) > 4: return 
            if i==len(s) and len(cur) == 4:
                ans.append('.'.join(cur))
                return
            
            for j in range(i+1, min(i+4, len(s)+1)):
                ss = s[i:j]
                if int(ss) > 255 or (len(ss) > 1 and ss[0] == '0'):
                    break
                cur.append(ss)
                dfs(j)
                cur.pop()

        dfs(0)
        return ans

6.3 二分图

6.3.1 模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:

        UNCOLOR, RED, GREEN = 0, 1, 2
        colors = [UNCOLOR for _ in range(len(graph))]
        def dfs(idx, color):
            colors[idx] = color
            cNei = GREEN if color == RED else RED
            for j in graph[idx]:
                if colors[j] == UNCOLOR:
                    dfs(j, cNei)
                    if not self.valid:
                        return
                elif colors[j] == color:
                    self.valid = False
                    return

        self.valid = True
        for i, e in enumerate(colors):
            if colors[i] == UNCOLOR:
                dfs(i, RED)
                if not self.valid:
                    break
        return self.valid

7. 广度优先搜索BFS

7.1 模板题

7.1.1 矩阵中的距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        dist = [[0] * n for _ in range(m)]
        zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
        # 将所有的 0 添加进初始队列中
        q = collections.deque(zeroes_pos)
        seen = set(zeroes_pos)

        # 广度优先搜索
        while q:
            i, j = q.popleft()
            for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni, nj))
                    seen.add((ni, nj))
        
        return dist
7.2.2 所有路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        def bfs():
            d = collections.deque([[0]])
            ans = []
            while d:
                tmp = d.popleft()

                if tmp[-1] == n-1:
                    ans.append(tmp)
                    continue

                for next_ in graph[tmp[-1]]:
                    d.append(tmp+[next_])
            return ans
        
        return bfs()

7.2 拓扑排序

7.2.1 课程顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        ans = []
        indegree = [0] * numCourses
        graph = collections.defaultdict(list)

        for (t, f) in prerequisites:
            graph[f] += [t]
            indegree[t] += 1
        
        d = collections.deque([idx for idx in range(numCourses) if indegree[idx]==0])
        while d:
            element = d.popleft()
            ans.append(element)

            for to in graph[element]:
                indegree[to] -= 1
                if indegree[to] == 0:
                    d.append(to)
        
        return ans if len(ans) == numCourses else []
7.2.2 外星文字典

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
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = collections.defaultdict(list)
        indegree = {c: 0 for c in words[0]}
        for s, t in itertools.pairwise(words):
            for c in t:
                indegree.setdefault(c, 0)
            for i, (f, d) in enumerate(zip(s, t)):
                if f != d:
                    graph[f].append(d)
                    indegree[d] += 1
                    break
                elif i == min(len(s), len(t))-1 and len(s) > len(t):
                    return ""

        
        d = collections.deque([c for c in indegree if indegree[c]==0])
        ans = ''
        while d:
            first = d.popleft()
            ans += first
            for ch in graph[first]:
                indegree[ch] -= 1
                if indegree[ch] == 0:
                    d.append(ch)
        return ans if len(ans) == len(indegree) else ""
7.2.3 重建序列

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 sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        indegree = [0] * (len(nums)+1)

        for i, l in enumerate(sequences):
            for f, t in itertools.pairwise(l):
                graph[f].append(t)
                indegree[t] += 1

        d = collections.deque([x for x in range(1, (len(nums)+1)) if indegree[x]==0])
        if len(d) > 1 or len(d) == 0: return False

        while d:
            if len(d) > 1: return False
            top = d.popleft()
            for i in graph[top]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    d.append(i)
        
        return True

8. 动态规划

8.1 例题

8.1.1 最大子数组和

1
2
3
4
5
6
7
8
9
10
11
# 状态：以i结尾的最大子数组和
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) > 1:
            dp = [0]*len(nums)
            dp[0] = nums[0]
            for i in range(len(nums)):
                dp[i] = max(dp[i-1]+nums[i], nums[i])
            return max(dp)
        else:
            return nums[0]
8.1.2 接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        l, r = 0, n-1
        # 当前列左边和右边最高列的高度
        dp_left, dp_right = [0]*n, [0]*n
        for i in range(1, n):
            dp_left[i] = max(dp_left[i-1], height[i-1])
        for i in range(n-2, -1, -1):
            dp_right[i] = max(dp_right[i+1], height[i+1])
        
        ans = 0
        for i in range(n):
            minh = min(dp_left[i], dp_right[i])
            if height[i] < minh:
                ans += minh - height[i]
        return ans
8.1.3 通配符匹配
image-20221107134201453 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)

        dp = [[False]*(m+1) for i in range(n+1)]
        dp[0][0] = True
        for i in range(1, m+1):
            if p[i-1] == '*':
                dp[0][i] = True
            else:
                break

        for i in range(1, n+1):
            for j in range(1, m+1):
                if s[i-1] == p[j-1] or p[j-1] == '?':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1] == '*':
                    # 不使用 或 使用 *号
                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
        return dp[n][m]
8.1.4 翻转字符

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        dp0, dp1 = 0, 0
        for c in s:
            dp0, dp1 = dp0, min(dp0, dp1)
            if c == '0':
                dp1 += 1
            else:
                dp0 += 1
        return min(dp0, dp1)
8.1.5 最长斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        d = {x:i for i, x in enumerate(arr)}
        dp = [[2 for _ in range(n)] for _ in range(n)]
        for i in range(1, n-1):
            for j in range(i+1, n):
                e2, e3 = arr[i], arr[j]
                e1 = e3 - e2
                if e1 in d and (k:=d[e1]) < i:
                    dp[i][j] = dp[k][i] + 1
                    ans = max(ans, dp[i][j])
        return ans
8.1.6 最少回文分割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        dp = [float('inf') for _ in range(n)]

        g = [[True]*n for _ in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                g[i][j] = (s[i] == s[j]) and g[i+1][j-1]

        for i in range(n):
            if g[0][i]:
                dp[i] = 0
            else:
                for j in range(i):
                    if g[j+1][i]:
                        dp[i] = min(dp[j]+1, dp[i])
        return dp[-1]
8.1.7 字符串交织

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n, k = len(s1), len(s2), len(s3)
        if m+n !=k: return False

        dp = [[False]*(n+1) for _ in range(m+1)]
        dp[0][0] = True
        for i in range(m+1):
            for j in range(n+1):
                if i > 0:
                    dp[i][j] |= s1[i-1] == s3[i+j-1] and dp[i-1][j]
                if j > 0:
                    dp[i][j] |= s2[j-1] == s3[i+j-1] and dp[i][j-1]
        return dp[-1][-1]
8.1.8 最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        return dp[-1][-1]
8.1.9 最长递增子序列
1
2
3
4
5
6
7
8
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1 for _ in range(len(nums))]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)
8.1.10 分割等和子集

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
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2:
            return False
        
        total = sum(nums)
        maxNum = max(nums)
        if total & 1:
            return False
        
        target = total // 2
        if maxNum > target:
            return False
        
        dp = [[False] * (target + 1) for _ in range(n)]
        for i in range(n):
            dp[i][0] = True
        
        dp[0][nums[0]] = True
        for i in range(1, n):
            num = nums[i]
            for j in range(1, target + 1):
                if j >= num:
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]
                else:
                    dp[i][j] = dp[i - 1][j]
        
        return dp[n - 1][target]
8.1.12 加减的目标值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n, Sum = len(nums), sum(nums)
        neg = Sum - target
        if neg < 0 or neg & 1:
            return 0
        neg = neg // 2
        dp = [0] * (neg+1)
        dp[0] = 1
        for i in range(1, n+1):
            num = nums[i-1]
            for j in range(neg, num-1, -1):
                dp[j] += dp[j-num]
        return dp[neg]
8.1.13 最少的硬币数目

1
2
3
4
5
6
7
8
9
10
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

        for coin in coins:
            for x in range(coin, amount+1):
                dp[x] = min(dp[x], dp[x-coin]+1)
        
        return dp[amount] if dp[amount] != float('inf') else -1
8.1.14 排列的数目

1
2
3
4
5
6
7
8
9
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [1] + [0] * target
        for i in range(1, target + 1):
            for num in nums:
                if num <= i:
                    dp[i] += dp[i - num]
        
        return dp[target]

9. 图

9.1 并查集

9.1.1 省份数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def find(index):
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1, index2):
            parent[find(index1)] = find(index2)
        
        cities = len(isConnected)
        parent = list(range(cities))

        for i in range(cities):
            for j in range(i+1, cities):
                if isConnected[i][j] == 1:
                    union(i, j)
        
        return sum(parent[x]==x for x in range(cities))
9.1.2 相似的字符串

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
class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        def find(idx):
            if idx != parents[idx]:
                parents[idx] = find(parents[idx])
            return parents[idx]
        
        def check(i, j):
            nums = 0
            for a, b in zip(strs[i], strs[j]):
                if a != b:
                    nums += 1
                if nums >2: return False
            return True

        n = len(strs)
        parents = list(range(n))
        for i in range(n):
            for j in range(i+1, n):
                fi, fj = find(i), find(j)
                if fi == fj:
                    continue
                if check(i, j):
                    parents[fi] = fj
        
        return sum(i==parents[i] for i in range(n))
9.1.3 多余的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parents = list(range(n+1))


        def find(idx):
            if idx != parents[idx]:
                parents[idx] = find(parents[idx])
            return parents[idx]
        
        def union(i, j):
            parents[find(i)] = find(j)
        
        for i, j in edges:
            if find(i) != find(j):
                union(i, j)
            else:
                return [i, j]
        return []

10. 位运算

10.1 快速幂

1
2
3
4
5
6
7
8
9
10
class Solution:
    def myPow(self, x: float, n: int) -> float:
        m = abs(n)
        ans = 1
        while m:
            if m & 1:
                ans *= x
            x *= x
            m >>= 1
        return ans if n > 0 else 1/ans

10.2 快速幂取余

1
2
3
4
5
6
7
8
9
10
class Solution:
    def myPow(self, x: float, n: int, M: int) -> float:
        m = abs(n)
        ans = 1
        while m:
            if m & 1:
                ans = ans * x % M
            x = x * x % M
            m >>= 1
        return ans if n > 0 else 1/ans

附录（Python Trick）

a. int/bin

1
2
# 将一个字符串类型的x视其为base进制，返回十进制结果
class int(x, base=10)
1
2
3
# 返回x的二进制表示
# 如 bin(10) -> '0b1010'
bin(x)

b. any

1
2
3
# any() 函数用于判断给定的可迭代参数 iterable 是否全部为 False，则返回 False，如果有一个为 True，则返回 True
# False：0/空/False
any(iterable)

c. product

1
2
# 返回A，B的笛卡尔积
itertools.product(A, B)

d. reduce

1
functools.reduce(function, iterable[, initializer])

e. ord/chr

1
2
3
4
5
6
# ord 返回ASCII数值
# ord('a') -> 97
ord(c) 
# chr 返回对应字符
# chr(97) -> 'a'
chr(i)

f. find/rfind

1
2
3
# find() 从头查找子串位置，找到返回索引，找不到返回-1
# rfind() 从字符串末尾开始查找
"abc".find('a')

g. bisect_left/bisect_right

1
2
3
4
# 若存在x，返回最左侧的索引；若不存在x，返回合适的插入位置使列表有序
bisect.bisect_left(list, x)
# 若存在x，返回最右侧的索引；若不存在x，返回合适的插入位置使列表有序
bisect.bisect_right(list, x)

h. combinations/permutations

1
2
3
4
# [('a', 'b'), ('a', 'c'), ('b', 'c')]
list(itertools.combinations("abc", 2))
# [(1,2,3),(1,3,2),...]
list(itertools.permutations([1,2,3], 3))

i. Counter

1
2
3
4
5
6
7
8
9
10
11
12
from collections import Counter
c = Counter()                           # a new, empty counter
c = Counter('gallahad')                 # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
c = Counter(cats=4, dogs=8)             # a new counter from keyword args

c = Counter(a=4, b=2, c=0, d=-2)
sorted(c.elements())
# ['a', 'a', 'a', 'a', 'b', 'b']

Counter('abracadabra').most_common(3)
# [('a', 5), ('b', 2), ('r', 2)]

j. SortedList

1
2
3
4
5
6
from sortedcontainers import SortedList
sl = SortedList(['e', 'a', 'c', 'd', 'b'])
>>> sl
SortedList(['a', 'b', 'c', 'd', 'e'])
>>> s1.add('h')
>>> s1.remove('a')