Posts

LeetCode 443 https://leetcode.cn/problems/string-compression/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 为了实现原地压缩，我们可以使用双指针分别标志我们在字符串中读和写的位置。每次当读指针 read 移动到某一段连续相同子串的最右侧，我们就在写指针 write 处依次写入该子串对应的字符和子串长度即可。 在实际代码中，当读指针 read 位于字符串的末尾，或读指针 read 指向的字符不同于下一个字符时，我们就认为读指针 read 位于某一段连续相同子串的最右侧。该子串对应的字符即为读指针 read 指向的字符串。我们使用变量 left 记录该子串的最左侧的位置，这样子串长度即为 read−left+1。 特别地，为了达到 O(1) 空间复杂度，我们需要自行实现将数字转化为字符串写入到原字符串的功能。这里我们采用短除法将子串长度倒序写入原字符串中，然后再将其反转即可。 时间复杂度：O(n)，其中 n 为字符串长度，我们只需要遍历该字符串一次。 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。 ...

LeetCode 416 https://leetcode.cn/problems/partition-equal-subset-sum/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题相当于能否从 nums 中选出一个子序列，其元素和恰好等于 s/2。这是 0-1 背包的恰好装满型问题。 dfs(i, j)=dfs(i−1, j−nums[i]) || dfs(i−1, j) ​ 时间复杂度：O(ns)，其中 n 是 nums 的长度，s 是 nums 的元素和（的一半）。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(ns)，单个状态的计算时间为 O(1)，所以动态规划的时间复杂度为 O(ns)。 空间复杂度：O(ns)。保存多少状态，就需要多少空间。 ...

LeetCode 344 https://leetcode.cn/problems/reverse-string/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 由于 left+right=n−1 恒成立，所以只需要用一个变量 i 表示 left，n−1−i 就是 right。 根据上面的讨论，循环直到 i=⌊n / 2⌋ 时停止。 时间复杂度：O(n)，其中 n 为 s 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...

LeetCode 难度： 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...

LeetCode 难度： 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...

LeetCode 673 https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是 LC 300 最长递增子序列的升级版。 定义 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度，cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数。设 nums 的最长上升子序列的长度为 maxLen，那么答案为所有满足 dp[i]=maxLen 的 i 所对应的 cnt[i] 之和。 对于 cnt[i]，其等于所有满足 dp[j]+1=dp[i] 的 cnt[j] 之和。在代码实现时，我们可以在计算 dp[i] 的同时统计 cnt[i] 的值。 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。 空间复杂度：O(n)。 ...

LeetCode 51 https://leetcode.cn/problems/n-queens/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 放置皇后有四个要求，本行(row)，本列(col)，与主对角线平行的斜线(row - col)和与副对角线平行的斜线(row + col)。为了避免 row - col 出现负数，使用 row - col + n - 1。 时间复杂度：O(n^2 n!)。 空间复杂度：O(n)。返回值的空间不计入。 ...

LeetCode 349 https://leetcode.cn/problems/intersection-of-two-arrays/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 把 nums1​ 中的元素都加到哈希集合 st 中，这样可以 O(1) 判断 nums2[i] 在不在 nums1 中。 为了保证答案列表中没有重复元素，在 nums2[i] 加入答案列表的同时，把 nums2[i] 从哈希集合 st 中去掉，这样后面遍历到相同的元素时，由于其不在 st 中，所以不会加入答案列表。 时间复杂度：O(n+m)，其中 n 是 nums1 的长度，m 是 nums2 的长度。 空间复杂度：O(n)。注：可以把长度小的数组转成哈希集合，这样可以做到 O(min(n,m)) 的空间复杂度。 ...

LeetCode 难度： 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...

LeetCode 难度： 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...