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 detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 初始化快慢指针，都指向链表头部
        fast, slow = head, head 
        
        # 使用快慢指针遍历链表
        while fast and fast.next:
            fast = fast.next.next  # 快指针每次走两步
            slow = slow.next        # 慢指针每次走一步
            
            # 如果快慢指针相遇，说明链表中有环
            if fast == slow:
                # 将慢指针重新指向链表头部
                slow = head 
                
                # 快慢指针每次各走一步，直到它们再次相遇
                while fast != slow:
                    fast = fast.next  # 快指针每次走一步
                    slow = slow.next  # 慢指针每次走一步
                
                # 相遇的节点就是环的入口节点
                return slow 
        
        # 如果遍历结束都没有相遇，说明链表中没有环，返回None
        return None

 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 minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        # 初始化 dp 表，dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # 正确的初始化方式
        
        # 初始化第一列：将 word1 的前 i 个字符转换为空字符串需要 i 次删除操作
        for i in range(m + 1):
            dp[i][0] = i
        
        # 初始化第一行：将空字符串转换为 word2 的前 j 个字符需要 j 次插入操作
        for j in range(n + 1):
            dp[0][j] = j
        
        # 填充 dp 表
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    # 如果当前字符相等，则不需要操作，直接继承 dp[i-1][j-1]
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    # 如果当前字符不相等，则取以下三种操作的最小值：
                    # 1. 删除：dp[i-1][j] + 1
                    # 2. 插入：dp[i][j-1] + 1
                    # 3. 替换：dp[i-1][j-1] + 1
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        
        # 返回 dp[m][n]，即将 word1 转换为 word2 所需的最小操作数
        return dp[m][n]

 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 __init__(self):
        # 初始化结果变量，用于记录最大路径和
        # 初始值设为负无穷，确保任何路径和都比它大
        self.res = -float('inf')

    def pathSum(self, root):
        """
        递归计算以当前节点为根节点的子树的最大路径和
        :param root: 当前节点
        :return: 返回以当前节点为起点的最大路径和
        """
        # 如果当前节点为空，返回0（空节点对路径和无贡献）
        if not root:
            return 0

        # 递归计算左子树的最大路径和，如果为负则取0（舍弃负数路径）
        left = max(0, self.pathSum(root.left))
        # 递归计算右子树的最大路径和，如果为负则取0（舍弃负数路径）
        right = max(0, self.pathSum(root.right))

        # 更新全局最大路径和：当前节点值 + 左子树最大路径和 + 右子树最大路径和
        self.res = max(self.res, left + right + root.val)

        # 返回以当前节点为起点的最大路径和：当前节点值 + 左子树或右子树中的最大值
        return max(left, right) + root.val

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        """
        计算二叉树中的最大路径和
        :param root: 二叉树的根节点
        :return: 返回最大路径和
        """
        # 调用递归函数计算最大路径和
        self.pathSum(root)
        # 返回全局最大路径和
        return self.res

 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

class Solution:
    def __init__(self):
        # 初始化结果列表，用于存储所有合法的IP地址
        self.res = []

    def backtrack(self, word, ip, idx, step):
        """
        回溯函数，用于生成所有可能的IP地址
        :param word: 原始字符串
        :param ip: 当前生成的IP地址部分
        :param idx: 当前处理的字符索引
        :param step: 当前已经生成的IP段数（0到4）
        """
        # 如果已经处理完所有字符，并且生成了4段IP地址
        if idx == len(word) and step == 4:
            self.res.append(ip[:-1])  # 去掉最后一个点号，添加到结果列表
            return
        # 如果已经处理完所有字符，但未生成4段IP地址，或者已经生成4段IP地址，但未处理完所有字符，直接返回
        elif idx == len(word) or step == 4:
            return
        # 如果当前字符是 "0"，则当前段只能是 "0"，不能有前导零
        elif word[idx] == "0":
            self.backtrack(word, ip + "0.", idx + 1, step + 1)  # 递归处理下一段
            return
        else:
            # 初始化当前段的数值
            sum = 0
            # 尝试在当前段中取1到3个字符
            for i in range(idx, len(word)):
                sum = sum * 10 + int(word[i])  # 计算当前段的数值
                # 如果当前段的数值超过255，直接退出循环
                if sum > 255:
                    break
                # 递归处理下一段
                self.backtrack(word, ip + str(sum) + ".", i + 1, step + 1)

    def restoreIpAddresses(self, s: str) -> List[str]:
        """
        主函数，调用回溯函数生成所有合法的IP地址
        :param s: 原始字符串
        :return: 所有合法的IP地址列表
        """
        self.backtrack(s, "", 0, 0)  # 从第0个字符开始回溯
        return self.res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        # 初始化 (m+1) x (n+1) 的动态规划表，dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # 遍历 text1 和 text2 的每个字符
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    # 如果当前字符相等，则 LCS 长度增加1
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    # 如果当前字符不等，则取上方或左方的最大值
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        # 返回 text1 和 text2 的最长公共子序列长度
        return dp[m][n]

 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 removeNthFromEnd(self, head, n) -> Optional[ListNode]:
        # 创建一个虚拟头节点，简化边界情况处理（如删除的是第一个节点）
        dummy = ListNode(next=head)
        # 初始化两个指针 slow 和 fast，都指向虚拟头节点
        slow, fast = dummy, dummy
        
        # 让 fast 指针先向前移动 n 步
        for i in range(n):
            fast = fast.next
        
        # 同时移动 slow 和 fast 指针，直到 fast 指针到达链表末尾
        while fast.next:
            slow = slow.next
            fast = fast.next
        
        # 此时 slow 指针指向待删除节点的前一个节点
        # 将 slow.next 指向 slow.next.next，跳过待删除节点
        slow.next = slow.next.next
        
        # 返回链表的新头节点（即 dummy.next）
        return dummy.next

 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 deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 创建一个哑节点（dummy node），其 next 指向链表头节点
        # 哑节点的作用是简化边界条件的处理（例如删除头节点的情况）
        dummy = ListNode(next=head)
        
        # 初始化两个指针：
        # - slow：指向哑节点，用于构建新链表
        # - fast：指向链表头节点，用于遍历链表
        slow, fast = dummy, head
        
        # 遍历链表
        while fast:
            # 如果当前 fast 节点与 slow 的下一个节点值相等，说明存在重复节点
            # 继续移动 fast 指针，直到找到不重复的节点或链表末尾
            while fast and fast.val == slow.next.val:
                fast = fast.next
            
            # 如果 fast 指针移动后，fast == slow.next.next
            # 说明 slow.next 节点没有重复，直接将 slow 移动到下一个节点
            if fast == slow.next.next:
                slow = slow.next
            else:
                # 否则，说明 slow.next 节点有重复，直接跳过所有重复节点
                slow.next = fast
        
        # 返回新链表的头节点
        return dummy.next

 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

def findKthNumber(self, nums1, nums2, i, j, k):
    """
    用来找到两个数组的第k个元素(从1开始)
    :param nums1: 第一个有序数组
    :param nums2: 第二个有序数组
    :param i: nums1 尚未遍历的坐标起始，包含i
    :param j: nums2 尚未遍历的坐标起始，包含j
    :param k: 目标找的第k个元素，从1开始
    """
    # 保证 nums1 的剩余长度最小，这样可以减少递归的次数
    if len(nums1) - i > len(nums2) - j:
        return self.findKthNumber(nums2, nums1, j, i, k)

    # 如果 nums1 的剩余长度为 0，直接在 nums2 中找第k个元素
    elif len(nums1) == i:
        return nums2[j + k - 1]

    # 如果 k == 1，直接返回两个数组当前起始元素的最小值
    elif k == 1:
        return min(nums1[i], nums2[j])

    # 计算 nums1 和 nums2 中要比较的位置
    # ii 和 jj 分别是 nums1 和 nums2 中可能的第 k//2 个元素
    ii = min(len(nums1), i + k // 2)  # 保证 ii 不超过 nums1 的长度
    jj = min(len(nums2), j + k // 2)  # 保证 jj 不超过 nums2 的长度

    # 比较 nums1[ii-1] 和 nums2[jj-1]
    if nums1[ii - 1] < nums2[jj - 1]:
        # 如果 nums1[ii-1] 比 nums2[jj-1] 小
        # 说明 nums1 的前半部分不可能是第k个元素
        # 因此，我们可以在 nums1 的剩余部分 (从 ii 开始)
        # 和 nums2 中找第 k - (ii - i) 个元素
        return self.findKthNumber(nums1, nums2, ii, j, k - (ii - i))
    else:
        # 如果 nums2[jj-1] 比 nums1[ii-1] 小
        # 说明 nums2 的前半部分不可能是第k个元素
        # 因此，我们可以在 nums2 的剩余部分 (从 jj 开始) 
        # 和 nums1 中找第 k - (jj - j) 个元素
        return self.findKthNumber(nums1, nums2, i, jj, k - (jj - j))

 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

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        """
        返回二叉树的右视图
        :param root: 二叉树的根节点
        :return: 右视图的节点值列表
        """
        # 如果根节点为空，直接返回空列表
        if not root:
            return []

        # 结果列表：存储右视图的节点值
        res = []
        
        # 使用队列进行层次遍历（BFS）
        q = deque([root])
        
        # 进行层次遍历
        while q:
            # 当前层的节点数量
            size = len(q)
            
            # 遍历当前层的所有节点
            for i in range(size):
                # 从队列左侧取出节点
                node = q.popleft()
                
                # 如果当前节点是当前层的最后一个节点，将其值加入结果列表
                if i + 1 == size:
                    res.append(node.val)
                
                # 将当前节点的左孩子加入队列
                if node.left:
                    q.append(node.left)
                
                # 将当前节点的右孩子加入队列
                if node.right:
                    q.append(node.right)
        
        # 返回结果列表
        return res

 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

class Solution:

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        返回二叉树的中序遍历结果
        :param root: 二叉树的根节点
        :return: 中序遍历的节点值列表
        """
        # 初始化结果列表
        self.res = []

        # 定义递归函数进行中序遍历
        def dfs(root):
            # 如果当前节点为空，直接返回
            if not root:
                return

            # 递归遍历左子树
            dfs(root.left)
            
            # 将当前节点的值加入结果列表
            self.res.append(root.val)
            
            # 递归遍历右子树
            dfs(root.right)

        # 从根节点开始递归遍历
        dfs(root)

        # 返回结果列表
        return self.res