【Leetcode】随笔

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

题目一：子集 II（LeetCode 90，困难）

题目分析

给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。例如：输入 nums = [1,2,2]，输出 [[],[1],[1,2],[1,2,2],[2],[2,2]]；输入 nums = [0]，输出 [[],[0]]。

解题思路

采用回溯法+排序去重，核心是通过排序让重复元素相邻，再在回溯过程中跳过重复元素，避免生成重复子集。具体步骤如下：

1. 排序预处理：将数组 nums 升序排序，确保相同元素相邻，为去重做准备。
2. 回溯函数设计：
   • 函数参数：start（当前递归的起始索引，避免子集重复）、path（当前子集）；
   • 终止条件：无显式终止，每次递归都将 path 加入结果列表（子集长度可从 0 到 n）；
   • 回溯逻辑：
     • 从 start 开始遍历数组元素；
     • 若当前元素与前一个元素相同且 i > start（跳过重复元素，确保同一层递归不选相同元素），跳过；
     • 选择当前元素：将 nums[i] 加入 path；
     • 递归调用：backtrack(i+1, path)（下一层递归从 i+1 开始，避免重复选同一元素）；
     • 回溯：从 path 中删除 nums[i]，撤销选择。
3. 初始化与执行：初始化结果列表，调用 backtrack(0, [])，最终返回结果列表。

示例代码

def subsetsWithDup(nums):
    nums.sort()  # 排序，让重复元素相邻
    result = []
    
    def backtrack(start, path):
        # 每次递归都将当前子集加入结果
        result.append(path.copy())
        # 从start开始遍历，避免子集重复
        for i in range(start, len(nums)):
            # 跳过重复元素（同一层递归不选相同元素）
            if i > start and nums[i] == nums[i-1]:
                continue
            # 选择当前元素
            path.append(nums[i])
            # 递归下一层，起始索引+1
            backtrack(i+1, path)
            # 回溯，撤销选择
            path.pop()
    
    backtrack(0, [])
    return result

# 测试示例
nums1 = [1,2,2]
print("子集II结果1：", subsetsWithDup(nums1))  # 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

nums2 = [0]
print("子集II结果2：", subsetsWithDup(nums2))  # 输出：[[],[0]]

nums3 = [1,1,2,3]
print("子集II结果3：", subsetsWithDup(nums3))  # 输出：[[],[1],[1,1],[1,1,2],[1,1,2,3],[1,1,3],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

代码解析

• 排序去重的关键：排序后重复元素相邻，通过 i > start and nums[i] == nums[i-1] 确保“同一层递归不选相同元素”，例如 nums = [1,2,2] 中，第一层递归选第一个 2 后，第二层递归可选第二个 2；但第一层递归若跳过第一个 2 直接选第二个 2，会导致重复子集 [2]，故需跳过。
• start参数的作用：限制下一层递归的起始索引为 i+1，避免子集包含重复元素的不同排列（如 [1,2] 和 [2,1]），确保子集按数组顺序生成。
• 复杂度分析：时间复杂度 O(n×2ⁿ)（排序 O(n log n)，回溯生成 2ⁿ 个子集，每个子集复制 O(n)）；空间复杂度 O(n)（递归栈深度和 path 长度均为 n）。

题目二：目标和（LeetCode 494，困难）

题目分析

给你一个非负整数数组 nums 和一个整数 target。向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数，可以构造一个表达式。返回可以使表达式结果等于 target 的不同表达式的数目。例如：输入 nums = [1,1,1,1,1], target = 3，输出 5（5 种表达式：-1+1+1+1+1、+1-1+1+1+1、+1+1-1+1+1、+1+1+1-1+1、+1+1+1+1-1）；输入 nums = [1], target = 1，输出 1。

解题思路

采用动态规划法（转化为子集和问题），核心是通过数学转化减少问题复杂度：

1. 数学转化：设添加 '+' 的元素和为 sum_pos，添加 '-' 的元素和为 sum_neg，则：
   • sum_pos - sum_neg = target；
   • sum_pos + sum_neg = sum_total（数组总和）；
   • 两式相加得 2sum_pos = target + sum_total → sum_pos = (target + sum_total) / 2。
   • 问题转化为：寻找数组中元素和为 sum_pos 的子集数目（子集对应添加 '+' 的元素）。
2. 边界条件：
   • 若 target + sum_total 为奇数或 target > sum_total，无可行解，返回 0；
   • 若 sum_pos 为负数，返回 0（元素非负，子集和不可能为负）。
3. 动态规划设计：
   • 状态定义：dp[j] 表示“和为 j 的子集数目”；
   • 初始化：dp[0] = 1（和为 0 的子集有 1 个：空子集）；
   • 状态转移：遍历每个元素 num，从 sum_pos 倒序遍历到 num，dp[j] += dp[j - num]（选当前元素时，子集数目累加和为 j - num 的子集数目）；
4. 返回结果：dp[sum_pos] 即为可行表达式的数目。

示例代码

def findTargetSumWays(nums, target):
    sum_total = sum(nums)
    # 边界条件：无可行解
    if (target + sum_total) % 2 != 0 or target > sum_total:
        return 0
    sum_pos = (target + sum_total) // 2
    if sum_pos < 0:
        return 0
    
    # 动态规划：dp[j]表示和为j的子集数目
    dp = [0] * (sum_pos + 1)
    dp[0] = 1  # 初始化：和为0的子集有1个（空子集）
    
    for num in nums:
        # 倒序遍历，避免重复使用同一元素
        for j in range(sum_pos, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[sum_pos]

# 测试示例
nums1 = [1,1,1,1,1]
target1 = 3
print("目标和数目1：", findTargetSumWays(nums1, target1))  # 输出：5

nums2 = [1]
target2 = 1
print("目标和数目2：", findTargetSumWays(nums2, target2))  # 输出：1

nums3 = [1,2,3]
target3 = 0
print("目标和数目3：", findTargetSumWays(nums3, target3))  # 输出：2（1+2-3、-1-2+3）

代码解析

• 转化的优势：将“目标和”这一正负号问题转化为“子集和”问题，减少了状态维度，从 O(n×target) 降至 O(n×sum_pos)，效率大幅提升。
• 倒序遍历原因：0-1 背包问题中，倒序遍历避免同一元素被多次选择（若正序遍历，dp[j - num] 已被更新，会导致重复累加）。
• 复杂度分析：时间复杂度 O(n×sum_pos)（n 为数组长度，sum_pos 最大为 sum_total）；空间复杂度 O(sum_pos)（dp 数组长度为 sum_pos + 1），是最优解法。

题目三：LRU 缓存（LeetCode 146，困难）

题目分析

设计一个 LRU（最近最少使用）缓存结构，使它支持以下操作：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存；
• int get(int key) 如果关键字 key 存在于缓存中，则获取关键字的值，否则返回 -1；
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。

要求：get 和 put 操作的时间复杂度均为 O(1)。

解题思路

采用哈希表+双向链表实现，核心是用双向链表维护缓存的使用顺序，用哈希表快速定位节点：

1. 数据结构设计：
   • 双向链表：节点存储 key 和 value，维护缓存的使用顺序——最近使用的节点移到链表头部，最久未使用的节点在链表尾部；
   • 哈希表：键为缓存的 key，值为双向链表的节点，实现 O(1) 时间定位节点。
2. 核心操作：
   • 添加节点到头部：新插入或刚访问的节点移到链表头部；
   • 删除节点：从链表中删除指定节点（用于缓存满时删除尾部节点，或更新已有节点时先删除原节点）；
   • 删除尾部节点：缓存满时，删除链表尾部节点（最久未使用），并从哈希表中移除对应键。
3. 操作实现：
   • get 操作：若 key 在哈希表中，找到节点，删除后移到头部，返回 value；否则返回 -1；
   • put 操作：
     • 若 key 已存在：删除原节点，更新 value 后移到头部；
     • 若 key 不存在：创建新节点，加入哈希表和链表头部；若缓存满，删除尾部节点及哈希表对应键。

示例代码

class DLinkedNode:
    """双向链表节点"""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()  # 哈希表：key→DLinkedNode
        self.capacity = capacity
        self.size = 0
        
        # 虚拟头节点和尾节点，简化边界操作
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_to_head(self, node):
        """将节点添加到双向链表头部"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        """从双向链表中删除指定节点"""
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _move_to_head(self, node):
        """将节点移到双向链表头部（先删除再添加）"""
        self._remove_node(node)
        self._add_to_head(node)
    
    def _remove_tail(self):
        """删除双向链表尾部节点（最久未使用）"""
        node = self.tail.prev
        self._remove_node(node)
        return node
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 找到节点，移到头部
        node = self.cache[key]
        self._move_to_head(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 新建节点，添加到缓存和链表头部
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            self.size += 1
            # 缓存满，删除尾部节点
            if self.size > self.capacity:
                removed_node = self._remove_tail()
                del self.cache[removed_node.key]
                self.size -= 1
        else:
            # 节点已存在，更新值并移到头部
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)

# 测试示例
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print("get(1)：", lru.get(1))  # 输出：1（访问后1移到头部）
lru.put(3, 3)  # 缓存满，删除最久未使用的2
print("get(2)：", lru.get(2))  # 输出：-1
lru.put(4, 4)  # 缓存满，删除最久未使用的1
print("get(1)：", lru.get(1))  # 输出：-1
print("get(3)：", lru.get(3))  # 输出：3
print("get(4)：", lru.get(4))  # 输出：4

代码解析

• 虚拟节点的优势：添加虚拟头和尾节点，避免处理“链表为空”或“删除头/尾节点”时的边界条件（如无需判断节点是否为头/尾），简化代码逻辑。
• O(1) 时间复杂度保证：哈希表实现 key 到节点的 O(1) 定位，双向链表实现节点的 O(1) 插入、删除和移动，确保 get 和 put 操作均为 O(1)。
• 复杂度分析：时间复杂度 O(1)（所有操作均为常数时间）；空间复杂度 O(capacity)（缓存最多存储 capacity 个节点），完全满足题目要求。

✨ 本次分享的3道题覆盖“回溯去重（子集II）”“动态规划转化（目标和）”“数据结构设计（LRU缓存）”，核心是灵活运用算法思想和数据结构解决复杂问题。若对某题的优化思路、拓展场景（如 LRU 缓存的进阶实现）或其他困难题有需求，随时告诉我！😊
🏠 更多算法解析欢迎到CSDN主页交流：山顶风景独好😍