leetcode双指针经典练习题
通过 LeetCode 80、88、977 三道题,继续记录双指针算法的应用。从有序数组去重入手,比较不同的快慢指针写法,再利用倒序填充解决原地合并数组和有序数组平方的问题,附 Python 实现。
通过 LeetCode 80、88、977 三道题,继续记录双指针算法的应用。从有序数组去重入手,比较不同的快慢指针写法,再利用倒序填充解决原地合并数组和有序数组平方的问题,附 Python 实现。
记录 LeetCode 1438「绝对差不超过限制的最长连续子数组」的解题思路。在滑动窗口中使用两个单调队列,分别维护最大值和最小值,当差值超过 limit 时不断收缩窗口,将整体时间复杂度优化到 O(n),并与 LeetCode 239 的定长窗口进行对比。
记录 LeetCode 179「最大数」的解题思路。从普通数值排序和字典序排序的局限出发,通过比较两个数字不同拼接顺序的大小,推导出自定义排序规则,并使用 Python 的 cmp_to_key 实现排序,最后处理全零的特殊情况。
记录 LeetCode 239「滑动窗口最大值」的解题思路。利用单调队列维护窗口最大值,通过队尾删除较小元素、队头移除过期索引,避免重复遍历窗口,将时间复杂度优化到 O(n),附 Python 实现。
记录 LeetCode 136「只出现一次的数字」的解题过程。从哈希表统计出现次数入手,再利用异或运算的性质,让成对出现的数字相互抵消,将额外空间复杂度从 O(n) 优化到 O(1),附 Python 实现。
通过 LeetCode 509「斐波那契数」和 322「零钱兑换」两道题,记录动态规划的基本思路。从朴素递归出发,利用备忘录解决重复计算问题,再改为自底向上的迭代实现,理解状态定义、状态转移和空间优化,附 Python 代码。