Hi there 👋

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 71 https://leetcode.cn/problems/simplify-path/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用一个栈存储目录，如果当前字符不是 ‘/’，那么更新 dir，直到遇到 ‘/’。如果 dir 是 “.."，把栈顶目录弹出。如果 dir 不是”."、"..“和空串，添加到栈中。最后使用 ‘/’ 连接目录作为答案。为方便处理，首先在 path 最后添加 ‘/’。 时间复杂度：O(n)，其中 n 是字符串 path 的长度。 空间复杂度：O(n)。我们需要 O(n) 的空间存储 names 中的所有字符串。 ...

LeetCode 面试题 02.05 https://leetcode.cn/problems/sum-lists-lcci/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 两数之和。 时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们需要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。 空间复杂度：O(1)。注意返回值不计入空间复杂度。 ...

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 316 https://leetcode.cn/problems/remove-duplicate-letters/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 单调栈。 统计每个字母的出现次数，记到一个哈希表或者数组 left 中。 遍历 s，先把 left[s[i]] 减一。 如果 s[i] 在 ans 中，直接 continue。为了快速判断 s[i] 是否在 ans 中，可以用一个哈希表或者布尔数组 inAns 辅助判断。 如果 s[i] 不在 ans 中，那么判断 s[i] 是否小于 ans 的最后一个字母（记作 x），如果 s[i]<x 且 left[x]>0，那么可以把 x 从 ans 中去掉，同时标记 inAns[x]=false。 反复执行第 4 步，直到 ans 为空，或者 s[i]>x，或者 left[x]=0。 把 s[i] 添加到 ans 末尾，同时标记 inAns[s[i]]=true。然后继续遍历 s 的下一个字母。 遍历完 s 后，返回 ans。 时间复杂度：O(n)，其中 n 为 s 的长度。我们写了一个二重循环，看上去是 O(n^2) 的，但是考虑到每个 s[i] 加到 ans 中至多一次，从 ans 中去掉也至多一次。所以整体上看，算法的时间复杂度是 O(n) 的。 空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集的大小，本题中字符均为小写字母，所以 ∣Σ∣=26。注意 ans 的长度不会超过 ∣Σ∣。 ...

Nowcoder 340 https://www.nowcoder.com/practice/6eec992558164276a51d86d71678b300 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题数据范围为小于 10 亿，需要先把数字拆分为亿，万，个三级。对于每个部分，转换一个四位数为中文读法。 时间复杂度：O(1) 空间复杂度：O(1) ...