Never Settle

题目90. 子集 II 给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。 解题思路1. 回溯12345678910111213141516171819202122232425262728293031323334class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: # 1. 首先对数组排序，使相同的元素相邻 nums.sort() res = [] # 存储最终结果 def backtrack(start: int, path: List[int]): # 2. 将当前路径加入结果集 # path[:] 创建一个新的列表，是当前path的浅拷贝 # 为什么要拷贝？因为path会在后续的回溯过程中被修改 # 如果...

题目实现 pow(x, n)，即计算 x 的 n 次幂。 解题思路使用快速幂（分治）： 若 n 为偶数：x^n = (x^(n/2))^2 若 n 为奇数：x^n = x * x^(n-1) 为了处理负指数，把 x 取倒数并将 n 取相反数。 代码实现（Python）123456789101112131415class Solution: def myPow(self, x: float, n: int) -> float: if n == 0: return 1.0 if n < 0: x = 1 / x n = -n result = 1.0 while n > 0: if n & 1: result *= x x *= x n >>= 1 return result 复杂度分析 时间复杂度：O(l...

题目描述给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，满足： nums[i] == nums[j] abs(i - j) <= k 解题思路1. 滑动窗口 + 集合使用大小为 k 的滑动窗口和集合来解决： 维护一个最大长度为 k 的集合 遍历数组，对于每个元素： 如果当前元素在集合中已存在，返回 true 将当前元素加入集合 如果集合大小超过 k，移除最早加入的元素 2. 代码实现123456789def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: num_set = set() for i in range(len(nums)): if nums[i] in num_set: return True num_set.add(nums[i]) if len(num_set) > k: num_set...

题目描述给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 示例示例 1: 输入: rowIndex = 3 输出: [1,3,3,1] 示例 2: 输入: rowIndex = 0 输出: [1] 示例 3: 输入: rowIndex = 1 输出: [1,1] 提示: 0 <= rowIndex <= 33 解题思路1. 递推解法（空间复杂度 O(k²)） 创建二维数组存储所有行 每个位置的值是上一行相邻两个数的和 边界位置都是1 12345678910111213141516171819202122232425262728293031323334353637#递推解法（空间复杂度O(k^2)）class Solution: def getRow(self, rowIndex: int) -> List[int]: C = [[1] * (i + 1) for i in range(rowIndex + ...

题目描述1. 考虑重复元素的交集给你两个整数数组 nums1 和 nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（取较小值）。 2. 不考虑重复元素的交集给定两个数组，返回它们的交集。输出结果中的每个元素一定是唯一的。 解题思路1. 考虑重复元素（排序 + 双指针）12345678910111213141516def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1.sort() # 先排序 nums2.sort() i, j = 0, 0 # 双指针 res = [] while i < len(nums1) and j < len(nums2): if nums1[i] == nums2[j]: # 相等时添加到结果 res.append(nums1[i]) i += 1 ...

1. 构造函数12345class A {public: A(); ~A();}; 2. 析构函数1234class A {public: ~A();}; 3. 拷贝构造函数1234class A {public: A(const A& other);}; 4. 赋值运算符重载1234class A {public: A& operator=(const A& other);}; 5. 移动构造函数1234class A {public: A(A&& other);}; 6. 移动赋值运算符重载1234class A {public: A& operator=(A&& other);};

深度优先遍历问题问题描述二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 解题思路 基本概念 二叉树的深度是从根节点到最远叶子节点的路径上的节点数 叶子节点是指没有子节点的节点 空节点的深度为 0 递归思路 一个节点的最大深度 = max(左子树深度, 右子树深度) + 1 递归的终止条件：当节点为空时，返回 0 DFS（深度优先搜索）过程 123456对于每个节点：├── 如果节点为空│ └── 返回 0├── 递归计算左子树的深度├── 递归计算右子树的深度└── 返回 max(左子树深度, 右子树深度) + 1 示例分析 1234567891011121314例如对于树： 3 / \ 9 20 / \ 15 7计算过程：1. 节点3的深度 = max(节点9的深度, 节点20的深度) + 12. 节点9的深度 = max(0, 0) + 1 = 13. 节点20的深度 = max(节点15的深度, 节点7的深度) + 14. 节点15和7的深度都是 15. 所以节点20的深度是 26. 最...

给你一个 下标从 1 开始的 整数数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。 水果超市有如下促销活动： 如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。 请你返回获得所有水果所需要的 最少 金币数。 示例 1： 输入：prices = [3,1,2] 输出：4 解释： 用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。免费获得第 3 个水果。请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。 示例 2： 输入：prices = [1,10,1,1] 输出：2 解释： 用 prices[0] = 1 个金币购买第 ...

题目 解题思路这是一个典型的动态规划问题。对于每个房屋，我们有两种选择： 偷这个房子：不能偷相邻的前一个房子，但可以偷前前一个房子。 不偷这个房子：最大金额就是偷到前一个房子为止的最大金额。 定义状态： dp[i] 表示偷窃前 i 个房屋能够获得的最大金额。 状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 含义： 当 dp[i-1] > dp[i-2] + nums[i] 时，选择 dp[i-1]。 否则选择 dp[i-2] + nums[i]。 边界条件： dp[0] = nums[0]：只有一个房子时。 dp[1] = max(nums[0], nums[1])：有两个房子时，选择金额较大的那个。 代码实现1234567891011121314151617class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums) == 1:...

LeetCode 746 - 使用最小花费爬楼梯题目描述给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 1. 问题分析这是爬楼梯问题的变体，主要区别是： 每个台阶都有一个花费 可以从索引0或1开始 目标是到达顶部（数组长度位置）的最小花费 2. 解题思路状态定义dp[i] 表示：到达第i个台阶的最小花费 状态转移方程dp[i] = min(dp[i-1], dp[i-2]) + cost[i] 解释：到达第i个台阶可以从： 第i-1个台阶爬1步上来 第i-2个台阶爬2步上来 选择这两种方式中花费较小的一种 代码实现和详细解释1234567891011121314151617181920212223242526272829303132333435363738class Solution: def minCostClimbingStairs(self, cost...