前言

代码能力是计算机专业学生的基础能力，求职技术方向的同学，无论是测试、开发或算法，互联网公司在这一块的考察都是重中之重。一般而言，大厂在每一轮的技术面中，至少会出一道编程题，多的会直接上三道编程题，难度主要集中在easy和medium，少数丧心病狂（褒义词）的面试官会出hard题。而考察范围已是圈内公开的秘密，就在《剑指offer》和Leetcode上，因此刷题成为了大家求职路上必须要迈过的一道坎，这个坎没有人可以帮到你，只有靠你自己。

本笔记记录自己在刷题过程中的总结，包括数据结构和算法两个方面。

常用函数

# c to num
ord(c)
# num to c
chr(97)

链表

https://leetcode.cn/tag/linked-list/problemset/

反转链表

设置前置节点，且值为None

def reverse(head):
    pre = None
    cur = head
    while cur:
        cur_next = cur.next
        cur.next = pre 
        pre, cur = cur, cur_next
    return pre

def get_the_k_node(self, head, k):
    p = head
    count = 0
    while p:
        count += 1
        if count == k:
            return p 
        p = p.next
    return None

快慢指针

141. 环形链表

142. 环形链表II

def hasCycle(head):
    slow, fast = head, head 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    if not (fast and fast.next):
        return None 
    fast = head 
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

287. 寻找重复数

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = 0
        fast = 0
        slow = nums[slow]
        fast = nums[nums[fast]]
        while slow != fast:
            slow = nums[slow]
            fast =  nums[nums[fast]]
        fast = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow

234. 回文链表

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # O(1)空间复杂度
        first_half = self.end_of_first_half(head)
        second_half_reverse = self.reverse_list(first_half.next)
        is_same = self.check_is_same(head, second_half_reverse)
        first_half.next = self.reverse_list(second_half_reverse)
        return is_same
    
    def end_of_first_half(self, head):
        fast, slow = head, head
        while fast and fast.next and fast.next.next:
            fast = fast.next.next 
            slow = slow.next 
        return slow
    
    def reverse_list(self, head):
        pre = None
        cur = head
        while cur:
            cur_next = cur.next 
            cur.next = pre 
            pre, cur = cur, cur_next
        return pre 
    
    def check_is_same(self, head1, head2):
        p, q = head1, head2
        while q:
            if p.val != q.val:
                return False
            p, q = p.next, q.next 
        return True

160. 相交链表

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # head A 走到头
        p,q = headA, headB
        while p != q:
            p = headB if p is None else p.next
            q = headA if q is None else q.next
        return p

有序链表合并

新增前置节点，且值为最小值，简化边界

def merge(l1, l2):
    pre_head = ListNode('-inf')
    pre = pre_head
    while l1 and l2:
        if l1.val <= l2.val:
            pre.next = l1 
            l1 = l1.next
        else:
            pre.next = l2
            l2 = l2.next 
        pre = pre.next 
    pre.next = l1 if l1 else l2
    return pre_head.next

21. 合并两个有序链表

双向链表

146. LRU 缓存

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.pre = None


class LRUCache:

    def __init__(self, capacity):
        self.head = Node(-1,-1)
        self.tail = Node(-1,-1)
        self.head.next = self.tail
        self.tail.pre = self.head
        self.key_to_node = dict()
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]
        self.remove_from_link(node)
        self.insert_into_top(node)
        return node.val 
    

    def put(self, key, val):
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = val
            self.remove_from_link(node)
        else:
            node = Node(key, val)
            self.key_to_node[key] = node
            if len(self.key_to_node) > self.capacity:
                last_node = self.tail.pre
                self.remove_from_link(last_node)
                del self.key_to_node[last_node.key]
        self.insert_into_top(node)
    
    def insert_into_top(self, node):
        old_top = self.head.next 
        self.head.next = node
        node.pre = self.head
        node.next = old_top
        old_top.pre = node 

    def remove_from_link(self, node):
        pre_node = node.pre 
        next_node = node.next 
        pre_node.next = next_node
        next_node.pre = pre_node

哈希表

https://leetcode.cn/tag/hash-table/problemset/

Python中的数据结构为set(), dict()

是否包含某个元素

1. 两数之和: 存下整个数组
128. 最长连续序列: 存下整个数组
36. 有效的数独: 存下行/列/子块的数字
73. 矩阵置零: 存下含0的行和列

560. 和为 K 的子数组
$$\sum_{p}^{q} n_{i} = \sum_{0}^{q} n_{i} - \sum_{0}^{p} n_{i} $$

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        sum_until = 0
        count = 0
        sum_to_count = defaultdict(int)
        sum_to_count[0] = 1
        for i in range(len(nums)):
            sum_until += nums[i]
            count += sum_to_count[sum_until-k]
            sum_to_count[sum_until] += 1
        return count

数字与符号的映射

12. 整数转罗马数字

13. 罗马数字转整数

class Solution:
    def romanToInt(self, s: str) -> int:
        c_to_num = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        ans = 0
        pre_num = c_to_num[s[0]]
        for c in s[1:]:
            cur_num = c_to_num[c]
            if cur_num > pre_num:
                ans -= pre_num
            else:
                ans += pre_num
            pre_num = cur_num
        ans += pre_num
        return ans

17. 电话号码的字母组合

字符串的特征

不同排列特征相同

def hash_eng_string(s):
    counts = [0 for _ in range(26)]
    for c in s:
        counts[ord(c) - ord('a')] += 1
    return tuple(counts)

tokenize, 判断两个排列的one-hot表示是否相同

290. 单词规律

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        s_tokenized = self.tokenize(s.split())
        pattern_tokenized = self.tokenize(list(pattern))
        return tuple(s_tokenized) == tuple(pattern_tokenized)
    
    def tokenize(self, word_list):
        word_to_index = {}
        for word in word_list:
            if word not in word_to_index:
                word_to_index[word] = len(word_to_index)
        tokenized = []
        for word in word_list:
            tokenized.append(word_to_index[word])
        return tokenized

205. 同构字符串

滑动窗口

https://leetcode.cn/tag/sliding-window/problemset/

先固定左节点，移动右节点找到符合条件的窗口，然后固定右节点，尽可能地收缩左节点

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        ans = None
        window_sum = 0
        right = 0
        while right < len(nums):
            window_sum += nums[right]
            while window_sum >= target and left <= right:
                ans = min(right - left + 1, ans) if ans else right - left + 1
                window_sum -= nums[left]
                left += 1
            right += 1
        return ans if ans else 0

239. 滑动窗口最大值

构造一个单调递减的双端队列

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = deque()
        for i in range(k):
            while q and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
        ans = [nums[q[0]]]
        for i in range(k, len(nums)):
            while q and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
            while i - q[0] + 1 > k:
                q.popleft()
            ans.append(nums[q[0]])
        return ans

栈

https://leetcode.cn/tag/stack/problemset/

括号匹配

20. 有效的括号

计算器

队列

import queue
q = queue.Queue()
q.put(val)
val = q.get()
q.empty()
q.qsize()

BFS遍历

102. 二叉树的层序遍历

双端队列

import collections
q = collections.deque()
q.append()
q.appendleft()
q.pop()
q.popleft()
list(q)

优先队列

from queue import PriorityQueue

q = PriorityQueue()
q.put(val)
val = q.get()
q.empty()
q.qsize()

264. 丑数 II

import queue

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        factors = {2,3,5}
        seen = {1}
        q = queue.PriorityQueue()
        q.put(1)

        for i in range(n-1):
            cur = q.get()
            for factor in factors:
                n = cur * factor
                if n not in seen:
                    seen.add(n)
                    q.put(n)
        
        return q.get()

from queue import PriorityQueue

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m,n = len(heightMap), len(heightMap[0])
        q = PriorityQueue()
        visited = set()
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0 or i == m-1 or j == n-1:
                    q.put((heightMap[i][j], i, j))
                    visited.add((i,j))
        ret = 0
        while not q.empty():
            h,i,j = q.get()
            ds = [(0,1),(0,-1),(-1,0),(1,0)]
            for d in ds:
                next_i, next_j = i + d[0], j + d[1]
                if not ( 0 <= next_i < m and 0 <= next_j < n):
                    continue
                if (next_i, next_j) in visited:
                    continue
                if heightMap[next_i][next_j] < h:
                    ret += (h - heightMap[next_i][next_j])
                q.put((max(h, heightMap[next_i][next_j]), next_i, next_j))
                visited.add((next_i,next_j))
        return ret

二叉树

98. 验证二叉搜索树

二叉搜索树的中序遍历为单调递增

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        is_valid = True
        pre_node = None

        def dfs(node):
            nonlocal is_valid,pre_node
            if not is_valid:
                return 
            if not node:
                return 
            dfs(node.left)
            if pre_node and pre_node.val >= node.val:
                is_valid = False
                return      
            pre_node = node 
            dfs(node.right)
        
        dfs(root)
        return is_valid

99. 恢复二叉搜索树

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        nodes = []

        def inorder(node):
            if not node:
                return 
            inorder(node.left)
            nodes.append(node)
            inorder(node.right)
        
        inorder(root)

        x = None
        y = None 

        pre = nodes[0]

        for i in range(1, len(nodes)):
            if pre.val > nodes[i].val:
                y = nodes[i]
                if not x:
                    x = pre 
            pre = nodes[i]
        
        if x and y:
            x.val, y.val = y.val, x.val

有序数组转二叉搜索树

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        if len(nums) == 1:
            return TreeNode(nums[0])
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

是否为平衡二叉树

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        node_to_height = {None:0}
        is_balance = True
        
        def dfs(node):
            nonlocal is_balance

            if not is_balance:
                return 
            
            if not node:
                return 

            dfs(node.left)
            dfs(node.right)

            if not is_balance:
                return 

            if abs(node_to_height[node.left] - node_to_height[node.right]) > 1:
                is_balance = False
                return 
                
            node_to_height[node] = max(node_to_height[node.left], node_to_height[node.right]) + 1
        
        dfs(root)
        return is_balance

102. 二叉树的层序遍历

import queue
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        ret = []
        q = queue.Queue()
        q.put(root)

        while not q.empty():
            tmp = []
            size = q.qsize()

            for _ in range(size):
                node = q.get()
                tmp.append(node.val)
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            ret.append(tmp)
        
        return ret

字典树

class Trie:

    def __init__(self):
        self.children = dict()
        self.is_leaf = False
    
    def insert(self, word):
        node = self 
        for c in word:
            if c not in node.children:
                node.children[c] = Trie()
            node = node.children[c]
        node.is_leaf = True
    
    def search_prefix_node(self, word):
        node = self
        for c in word:
            if c not in node.children:
                return None
            node = node.children[c]
        return node
    
    def search(self, word):
        node = self.search_prefix_node(word)
        return node is not None and node.is_leaf
    
    def startsWith(self, word):
        node = self.search_prefix_node(word)
        return node is not None

排序

快速排序

912. 排序数组

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        pivot = random.choice(nums)
        left = self.sortArray([x for x in nums if x < pivot])
        right = self.sortArray([x for x in nums if x > pivot])
        mid = [x for x in nums if x == pivot]
        return left + mid + right

215. 数组中的第K个最大元素

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_select(nums, k):
            # 随机选择基准数
            pivot = random.choice(nums)
            big, equal, small = [], [], []
            # 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
            for num in nums:
                if num > pivot:
                    big.append(num)
                elif num < pivot:
                    small.append(num)
                else:
                    equal.append(num)
            if k <= len(big):
                # 第 k 大元素在 big 中，递归划分
                return quick_select(big, k)
            if len(nums) - len(small) < k:
                # 第 k 大元素在 small 中，递归划分
                return quick_select(small, k - len(nums) + len(small))
            # 第 k 大元素在 equal 中，直接返回 pivot
            return pivot
        
        return quick_select(nums, k)

56. 合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        ret = []
        start, end = intervals[0]
        for i in range(1, len(intervals)):
            a, b = intervals[i]
            if a > end:
                # 无法合并
                ret.append([start, end])
                start, end = a, b
            elif a <= end:
                # 合并
                end = max(end, b)
        
        ret.append([start, end])

        return ret

自定义排序

1	`key = functools.cmp_to_key`

179. 最大数

class Solution:
    def largestNumber(self, nums: List[int]) -> str:

        def compare(num1, num2):
            num1_str = str(num1)
            num2_str = str(num2)
            return int(num1_str + num2_str) - int(num2_str + num1_str)

        nums.sort(key=functools.cmp_to_key(compare))
        ret = "".join([str(num) for num in nums[::-1]])
        return ret[:-1].lstrip('0') + ret[-1]

拓扑排序

https://leetcode.cn/tag/topological-sort/problemset/

BFS搜索

from queue import Queue

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 检查图中是否有环
        edges = defaultdict(list)
        in_dgree = [0] * numCourses

        for course,pre_course in prerequisites:
            edges[pre_course].append(course)
            in_dgree[course] += 1
        
        q = Queue()

        for i in range(numCourses):
            if in_dgree[i] == 0:
                q.put(i)
        
        visited = 0

        while not q.empty():
            visited += 1
            index = q.get()
            for unlock_course in edges[index]:
                in_dgree[unlock_course] -= 1
                if in_dgree[unlock_course] == 0:
                    q.put(unlock_course)
        
        return visited == numCourses

329. 矩阵中的最长递增路径

class Solution:

    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        
        rows, columns = len(matrix), len(matrix[0])
        outdegrees = [[0] * columns for _ in range(rows)]
        queue = collections.deque()
        for i in range(rows):
            for j in range(columns):
                for dx, dy in Solution.DIRS:
                    newRow, newColumn = i + dx, j + dy
                    if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[i][j]:
                        outdegrees[i][j] += 1
                if outdegrees[i][j] == 0:
                    queue.append((i, j))

        ans = 0
        while queue:
            ans += 1
            size = len(queue)
            for _ in range(size):
                row, column = queue.popleft()
                for dx, dy in Solution.DIRS:
                    newRow, newColumn = row + dx, column + dy
                    if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] < matrix[row][column]:
                        outdegrees[newRow][newColumn] -= 1
                        if outdegrees[newRow][newColumn] == 0:
                            queue.append((newRow, newColumn))
        
        return ans

802. 找到最终的安全状态

找出不在环中的节点

from queue import Queue

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # 找出成环节点
        n = len(graph)
        edges = defaultdict(list)
        out_degree = [0] * n

        for i in range(n):
            for index in graph[i]:
                edges[index].append(i)
                out_degree[i] += 1
        
        q = Queue()
        for i in range(n):
            if out_degree[i] == 0:
                q.put(i)
        
        safety_index = []

        while not q.empty():
            i = q.get()
            safety_index.append(i)
            for j in edges[i]:
                out_degree[j] -= 1
                if out_degree[j] == 0:
                    q.put(j)
        
        safety_index.sort()

        return safety_index

其他排序

274. H 指数

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse=True)
        h = 0
        for i in range(len(citations)):
            # citations[i] > 0 and citation[i] >= h+1 and i + 1 >= h+1
            if citations[i] > h:
                h += 1
            else:
                break
        return h

二分查找

返回nums大于等于target的数字(最接近/插入的)

def binary_search(nums, target):
    left = 0
    right = len(nums)

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] > target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            return mid 
    
    return left

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        return [
            self.search_left_index(nums, target),
            self.search_right_index(nums, target)
        ]
    
    def search_left_index(self, nums, target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                if mid == 0 or nums[mid - 1] < target:
                    return mid 
                right = mid - 1 
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
        return -1
    

    def search_right_index(self, nums, target):
        left = 0
        right = len(nums) -1 

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                if mid ==len(nums) - 1 or nums[mid + 1] > target:
                    return mid 
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
        
        return -1

33. 搜索旋转排序数组

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 二分查找
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            
            if nums[mid] >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

153. 寻找旋转排序数组中的最小值

假设最右边元素为x,最小值右边的元素一定都小于x，最小值左边的元素一定都大于x

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1
        return nums[right]

162. 寻找峰值
不断朝向坡峰行走

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)

        def get(i: int) -> int:
            if i == -1 or i == n:
                return float('-inf')
            return nums[i]

        left, right, ans = 0, n - 1, -1
        while left <= right:
            mid = (left + right) // 2
            if get(mid - 1) < get(mid) > get(mid + 1):
                ans = mid
                break
            if get(mid) < get(mid + 1):
                left = mid + 1
            else:
                right = mid - 1
        
        return ans

贪心

动态规划

198. 打家劫舍

dp[i]是打劫0-i家能获得的最大值，$dp[i] = max(dp[i-1], dp[i-2] + nums[i])$

279. 完全平方数

dp[i]表示数字i最少的完全平方数，$dp[i] = min{dp[i - j*j]} + 1$

322. 零钱兑换

dp[i]表示零钱i所需要最少的个数，$dp[i] = min{dp[i-j]} + 1$

139. 单词拆分

dp[i]表示s[:i]能否用给定的单词拼出，$dp[i] = dp[j] & w[j:i] \in D $

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for end_index in range(1, len(s)+1):
            for word in wordDict:
                if len(word) > end_index:
                    continue
                if dp[end_index - len(word)] and s[end_index-len(word):end_index] == word:
                    dp[end_index] = True
                    break
        return dp[-1]

300. 最长递增子序列

dp[i]表示以i为终点的严格递增子序列的长度, $dp[i] = max(dp[j])+1, nums[i]>nums[j], j<i$

152. 乘积最大子数组

需要同时记录最大值和最小值

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # dp_min[i], [j, i] 乘积最小结果
        # dp_max[i], [i, i] 乘积最大结果
        ret = float('-inf')
        dp_min,dp_max = [], []
        for i in range(len(nums)):
            dp_min.append(nums[i])
            dp_max.append(nums[i])
            if i > 0:
                temp = [
                    nums[i],
                    dp_max[i-1] * nums[i],
                    dp_min[i-1] * nums[i]
                ]
                dp_min[-1] = min(temp)
                dp_max[-1] = max(temp)
            ret = max(ret, dp_max[-1])
        return ret

416. 分割等和子集

dp[i][j]表示从nums[0:i]中能否选择一些数使得和为j，$ dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]] $

边界情况，dp[i][0] = 1, dp[0][nums[0]] = 1

32. 最长有效括号

dp[i][j]为有效括号

dp[i][j-2]是有效括号，且s[j-1]=”(“, s[j]=”)”

dp[i+1][j-1]是有效括号，且s[i]=”(“, s[j]=”)”

22. 括号生成

dp[i]表示全部的括号

dp[i] = ‘(‘ + dp[p] + ‘)’ + dp[q]

62. 不同路径

dp[i][j]表示到达位置i,j的路径数量

dp[i][j] = dp[i-1][j] + dp[i][j-1]

dp[i][j] = 1, if i==0 or j ==0

64. 最小路径和

dp[i][j]表示到达位置i,j的最小路径和

dp[0][0] = grid[0][0]

dp[i][0] = dp[i-1][0] + grid[i][0]

dp[0][j] = dp[0][j-1] + grid[0][j]

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

5. 最长回文子串

dp[i][j]表示s[i:j]是否为一个回文子串

dp[i][j] = dp[i+1][j-1] & s[i] == s[j]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = s[0]
        n = len(s)
        dp = [[False for j in range(n)] for i in range(n)]

        for l in range(1, n+1):
            for i in range(n):
                j = i + l - 1
                if j >= n:
                    break
                if l == 1:
                    dp[i][j] = True
                elif l == 2 and s[i] == s[j]:
                    dp[i][j] = True 
                elif i+1 <= j-1 and dp[i+1][j-1] and s[i] == s[j]:
                    dp[i][j] = True
                
                if dp[i][j] and l > len(ans):
                    ans = s[i:j+1]
        
        return ans

1143. 最长公共子序列

dp[i][j]表示text1[0:i]和text2[0:j]的最长公共序列

dp[i][j] = dp[i-1][j-1] + 1, if text1[i] == text2[j]

dp[i][j] = max(dp[i-1][j], dp[i][j-1]), if text1[i] != text2[j]

72. 编辑距离

dp[i][j]表示word1[0:i)转换成word2[0:j)的编辑距离

dp[i][j] = dp[i-1][j-1], if word1[i-1] == word2[j-1]

dp[i][j] = dp[i-1][j], dp[i-1][j-1], dp[i][j-1], if word1[i-1] != word2[j-1]

dp[0][j] = j

dp[i][0] = i

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m,n = len(word1), len(word2)

        dp =[ [0 for j in range(n+1)] for i in range(m+1)]

        for i in range(m+1):
            for j in range(n+1):
                if i == 0:
                    dp[i][j] = j
                elif j == 0:
                    dp[i][j] = i 
                elif word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min([
                        dp[i-1][j-1],
                        dp[i-1][j],
                        dp[i][j-1]
                    ]) + 1

        return dp[m][n]

96. 不同的二叉搜索树
$ dp[i] = \sum_{j=1}^{j=i} dp[j-1]*dp[i-j] $
139. 单词拆分

dp[i] = any(dp[j] and s[i:j] in WordDict)

深度优先搜索

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        
        @lru_cache(None)
        def dfs(row: int, column: int) -> int:
            best = 1
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                newRow, newColumn = row + dx, column + dy
                if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:
                    best = max(best, dfs(newRow, newColumn) + 1)
            return best

        ans = 0
        rows, columns = len(matrix), len(matrix[0])
        for i in range(rows):
            for j in range(columns):
                ans = max(ans, dfs(i, j))
        return ans

递归

50. Pow(x, n)
快速幂

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            return 1.0 / self.myPow(x, -1 * n)
        if n == 0:
            return 1.0
        y = self.myPow(x, n//2)
        if n % 2 == 1:
            return x * y * y
        else:
            return y * y

数学

2967. 使数组成为等数数组的最小代价

生成10**9以内的全部回文数

self.valid_nums = []
base = 1
while base <= 10000:
    # 生成奇数长度
    for i in range(base, base * 10):
        x = i 
        t = i // 10
        while t:
            x = x * 10 + t % 10
            t = t // 10
        self.valid_nums.append(x)
    if base <= 1000:
        # 生成偶数长度
        for i in range(base, base * 10):
            x = i 
            t = i 
            while t:
                x = x * 10 + t % 10
                t = t // 10
            self.valid_nums.append(x)
    base *= 10

最短路径

2976. 转换字符串的最小成本 I

Floyd算法

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        nodes = set(original + changed)
        nodes = list(nodes)
        
        path = {
            nodes[i]:
            {
                nodes[j] :float('inf') if i != j else 0
                for j in range(len(nodes))
            }
            for i in range(len(nodes))
        }
        
        for a,b,c in zip(original, changed, cost):
            path[a][b] = min(path[a][b], c)
        
        for a in nodes:
            for b in nodes:
                for c in nodes:
                    path[b][c] = min(path[b][c], path[b][a] + path[a][c])
        
        cost_sum = 0
        for i in range(len(source)):
            if source[i] == target[i]:
                continue
            if source[i] not in path or target[i] not in path[source[i]] or path[source[i]][target[i]] == float('inf'):
                return -1
            cost_sum += path[source[i]][target[i]]
        return cost_sum

-1514. 概率最大的路径

from queue import PriorityQueue

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        
        graph = defaultdict(list)

        for i,(x,y) in enumerate(edges):
            graph[x].append((succProb[i], y))
            graph[y].append((succProb[i], x))
        
        prob = [0.0] * n
        prob[start_node] = 1.0
        q = PriorityQueue()
        q.put((-1.0, start_node))

        while not q.empty():
            p, node = q.get()
            p = -1.0 * p 
            if p < prob[node]:
                continue
            for pro_next, node_next in graph[node]:
                if prob[node_next] < prob[node] * pro_next:
                    prob[node_next] = prob[node] * pro_next
                    q.put((-1.0 * prob[node_next], node_next))
        
        return prob[end_node]

计算机基础

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Docker使用笔记上一篇

Leetcode刷题笔记

前言