【Leetcode】随笔

🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

题目一：二叉树的直径（LeetCode 543）

题目分析：

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个节点路径长度中的最大值。这条路径可能穿过也可能不穿过根节点。例如：输入root = [1,2,3,4,5]，输出3（路径为4→2→1→3或5→2→1→3，长度为3）。

解题思路：

深度优先搜索（DFS）：计算每个节点的左右子树深度之和，最大值即为直径。
递归逻辑：

• 定义辅助函数计算节点的深度，同时在计算过程中更新直径最大值。
• 节点深度为左右子树深度的最大值加1。
• 对于每个节点，其左右子树深度之和可能是直径的候选值，与当前最大值比较并更新。
  终止条件：空节点的深度为0。

示例代码：

# 二叉树节点定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameterOfBinaryTree(root):
    max_diameter = 0  # 存储最大直径
    
    def depth(node):
        nonlocal max_diameter
        if not node:
            return 0
        # 计算左右子树深度
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        # 更新最大直径（左右子树深度之和）
        max_diameter = max(max_diameter, left_depth + right_depth)
        # 返回当前节点的深度
        return max(left_depth, right_depth) + 1
    
    depth(root)
    return max_diameter

# 辅助函数：构建二叉树（同前）
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# 测试示例
if __name__ == "__main__":
    # 构建示例树：[1,2,3,4,5]
    root = build_tree([1,2,3,4,5])
    print("二叉树的直径：", diameterOfBinaryTree(root))  # 输出：3

代码解析：

depth函数递归计算节点深度，同时在每个节点处计算左右子树深度之和，与max_diameter比较并更新。
max_diameter通过nonlocal关键字在嵌套函数中修改，记录整个树中的最大直径。
直径是路径上的边数，等于两个节点之间的节点数减1，因此左右子树深度之和（节点数差）即为路径边数。
时间复杂度为O(n)（n为节点数，每个节点访问一次），空间复杂度为O(n)（递归栈深度）。

题目二：格雷编码（LeetCode 89）

题目分析：

n 位格雷码序列 是一个由 2ⁿ 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2ⁿ - 1] 内（含 0 和 2ⁿ - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同
  给定一个整数 n，返回任一有效的 n 位格雷码序列。例如：输入n = 2，输出[0,1,3,2]（二进制为00→01→11→10，满足相邻差异）。

解题思路：

递归法：n位格雷码可由n-1位格雷码生成。
生成规则：

• n=0时，格雷码序列为[0]。
• 对于n>0，先获取n-1位的格雷码序列，记为prev。
• 则n位格雷码序列为：prev + [x + 2^(n-1) for x in reversed(prev)]。
• 即前半部分为n-1位格雷码，后半部分为反转的n-1位格雷码每位加2^(n-1)，确保相邻元素只有一位不同。

示例代码：

def grayCode(n):
    if n == 0:
        return [0]
    # 递归获取n-1位格雷码
    prev = grayCode(n - 1)
    # 计算2^(n-1)
    add = 1 << (n - 1)
    # 生成n位格雷码：前半部分为prev，后半部分为反转的prev每位加add
    return prev + [x + add for x in reversed(prev)]

# 测试示例
if __name__ == "__main__":
    n = 2
    print(f"{n}位格雷码序列：", grayCode(n))  # 输出：[0, 1, 3, 2]
    
    n = 3
    print(f"{n}位格雷码序列：", grayCode(n))  # 输出：[0,1,3,2,6,7,5,4]

代码解析：

利用格雷码的递归生成特性，n位格雷码可通过n-1位格雷码构造，避免了复杂的位运算逻辑。
反转prev并每位加2^(n-1)，确保后半部分与前半部分的最后一个元素只有一位不同（最高位），且后半部分内部相邻元素也满足条件。
时间复杂度为O(2ⁿ)（序列长度为2ⁿ），空间复杂度为O(2ⁿ)（存储结果及递归栈）。

题目三：删除排序链表中的重复元素 II（LeetCode 82）

题目分析：

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。例如：输入head = [1,2,3,3,4,4,5]，输出[1,2,5]；输入head = [1,1,1,2,3]，输出[2,3]。

解题思路：

双指针+虚拟头节点：

• 虚拟头节点：简化头节点可能被删除的情况，指向原头节点。
• 前驱指针（prev）：指向当前已确认无重复的节点。
• 当前指针（curr）：遍历链表，查找重复节点。
  遍历逻辑：
• 若curr与curr.next的值相等，说明存在重复，移动curr直到找到不重复的节点，然后将prev.next指向该节点（删除中间重复节点）。
• 若curr与curr.next的值不相等，prev和curr同时后移。
• 注意处理链表末尾的重复节点。

示例代码：

# 链表节点定义
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteDuplicates(head):
    # 创建虚拟头节点
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy  # 前驱指针
    curr = head   # 当前指针
    
    while curr and curr.next:
        if curr.val == curr.next.val:
            # 记录重复值，移动curr到最后一个重复节点
            duplicate_val = curr.val
            while curr and curr.val == duplicate_val:
                curr = curr.next
            # 删除重复节点
            prev.next = curr
        else:
            # 无重复，两指针同时后移
            prev = curr
            curr = curr.next
    
    return dummy.next

# 辅助函数：将列表转换为链表
def list_to_linkedlist(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 辅助函数：将链表转换为列表
def linkedlist_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# 测试示例
if __name__ == "__main__":
    head1 = list_to_linkedlist([1,2,3,3,4,4,5])
    new_head1 = deleteDuplicates(head1)
    print("删除重复后链表1：", linkedlist_to_list(new_head1))  # 输出：[1,2,5]
    
    head2 = list_to_linkedlist([1,1,1,2,3])
    new_head2 = deleteDuplicates(head2)
    print("删除重复后链表2：", linkedlist_to_list(new_head2))  # 输出：[2,3]

代码解析：

通过虚拟头节点dummy避免单独处理头节点被删除的情况，prev始终指向已确认无重复的节点。
当发现curr与curr.next值相等时，先记录重复值，将curr移动到最后一个重复节点的下一个位置，再通过prev.next = curr删除所有重复节点。
若不存在重复，则prev和curr正常后移。
时间复杂度为O(n)（n为链表长度，仅遍历一次），空间复杂度为O(1)（使用常数变量）。

✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍