知识点

LeetCode算法题

1. LeetCode算法题

   1. 复习

      1. 25.【K 个一组翻转链表】

         时间复杂度：O(n)

         空间复杂度：O(1)

      2. 61.【旋转链表】

         时间复杂度：O(n)

         空间复杂度：O(1)

      3. 82.【删除排序链表中的重复元素 II】

         解题思路：

         用一个哑巴节点作为头，连接整个链表。通过curr.next.val == curr.next.next.val找到重复元素，然后删除所有val是curr.next.val的节点。

         时间复杂度：O(n)

         空间复杂度：O(1)

      4. 148.【排序链表】

         时间复杂度：O(nlogn)

      5. 124.【二叉树中的最大路径和】

   2. 学习

      1. 264.【丑数 II】

         解题思路：

         最简单思路，优先级队列+HashSet

         更好些的，就是动态规划优化后的丑数计算。

      2. 4.【寻找两个正序数组的中位数】

         解题思路：

         思路1：双指针+双元素。由于是数组，因此中位数的索引肯定是确定的。使用双指针，分别指向两个数组的第一个元素，然后每次让元素小的那个指针后移，就可以不用物理上合并两个数组，找到中位数了。该算法时间复杂度O(m+n)，空间复杂度O(1)。详细请看代码。

         思路2：使用二分查找。该算法时间复杂度O(log(m+n))，空间复杂度O(1)。

      3. 15.【三数之和】