LeetCode Notes 之 一句话题解

1. 两数之和。

   使用哈希表。遍历数组， 并不断的将遍历到的元素加入表中，key为元素值，value为元素下标。如果遇到一个元素，其构成目标和的另一半在哈希表中，则结束。

   • 时间复杂度 O(n)，空间复杂度O(n)。

2. 无重复字符的最长子串

   滑动窗口。从左到右滑动窗口，每次右边界右移一位。如果此时窗口中有重复元素，则左边界右移一位直至无重复元素，并计算和更新最大长度。

   • 时间复杂度 O(n)，空间复杂度O(n)。
   • 可以使用哈希表存储窗口中的元素，此时空间复杂度可以优化到O(Σ)，Σ为可能出现字符的字符集的大小。

3. 最长回文子串

   中心扩散法。每个回文串的中心可能在中间的一个或两个字符，遍历字符串，并不断判断以当前位置为中心的回文串最大长度，并更新。

   • 时间复杂度 O(n²)，空间复杂度O(1)。
   • 可以用Manacher 算法，将时间复杂度降到 O(n)，类似kmp算法。

4. Z字形变换

   找规律。按每行找出字符和索引的对应关系。

   • 时间复杂度 O(n)，空间复杂度O(n)。

5. 字符串转换整数

   有限自动机。将可能扫到的字符归纳成状态，并将状态转换枚举出来，形成有限状态自动机，从开头扫描直至结束。

   • 时间复杂度 O(n)，空间复杂度O(1)。

6. 有效的括号

   栈。依次扫描，如果是左括号则进栈（此题好像不需要判断优先级），右括号则判断栈顶元素是否能匹配，并出栈。最后看栈是否空。

   • 时间复杂度 O(n)，空间复杂度O(n)。

7. 合并K个排序链表

   最大堆。先将这K个链表的头结点调整为最小堆，每次取出堆顶结点，拉链，并将其下一个结点入堆（空则不入），调整堆。

   • 时间复杂度 O(nlogk) ，空间复杂度O(k)。

8. 搜索插入位置

   二分查找。查找有序数组中第一个大于等于目标值的元素的下标。

   • 时间复杂度 O(logn) ，空间复杂度O(1)。

9. 解数独

   回溯法。回溯主函数参数包括：当前行、列、数独板。选择为0-9。要求返回一个解，所以填完直接返回即可。

   • 时间复杂度 （9！）⁹ ，空间复杂度 81。

10. 跳跃游戏II

    贪心算法。每次计算当前位置到能跳到的最远位置之间（初始为0），每个点能到达的最远位置，并跳到能到达该位置的那个点，步数加一。能跳到终点直接返回。

    • 时间复杂度 O(n) ，空间复杂度O(1)。

11. N皇后

    回溯法。回溯主函数参数包括：当前行、棋盘、结果。选择为在该行的某列中放皇后。要求返回全部解，所以回溯主函数参数要额外包括一个结果，每次到最后一行且合理则加入解，最后返回。

    • 时间复杂度 O(n！) ，空间复杂度O(n)。

12. N皇后II

    回溯法。回溯主函数参数包括：当前行、棋盘、当前解的数量。选择为在该行的某列中放皇后。要求返回解的数量，所以每次到最后一行且合理，则解数加一，最后返回。

    • 时间复杂度 O(n！) ，空间复杂度O(n)。

13. 跳跃游戏

    贪心算法。每次计算当前位置到能跳到的最远位置之间（初始为0），每个点能到达的最远位置，并跳到能到达该位置的那个点，步数加一。如果某两次跳跃，能到达的最远位置没变，且不能到终点，就说明跳不到最后一个位置。

    • 时间复杂度 O(n) ，空间复杂度O(1)。

14. 合并区间

    排序 + 分类讨论。先对区间进行快速排序。初始化结果列表，并开始遍历，分三种情况。

    • 如果下个区间被当前区间包裹，则当前区间不变，下个区间右移再判断。
    • 如果下个区间被当前区间的右端点分割，则当前区间的右端点扩展到下个区间的右端点。
    • 如果下个区间与当前区间无交集，则将当前区间加入结果列表，双区间右移。
    • 时间复杂度 O(nlogn) ，空间复杂度O(logn)。

15. 插入区间

    一次遍历。从左到右。如果当前区间右端点小于目标左端点，继续，否则准备合并。

    • 如果目标区间左端点比当前区间左端点小，则扩展当前区间左端点至目标区间左端点。
    • 如果目标区间右端点比当前区间右端点大，则扩展当前区间右端点至目标区间右端点，冰箱后依次判断是否需要合并区间。
    • 时间复杂度 O(n) ，空间复杂度O(1)。

16. x的平方根

    二分查找。

    • 时间复杂度 O(x) ，空间复杂度O(1)。

17. 爬楼梯

    动态规划最低配。斐波那契，dp[n]为爬n阶的方法，状态转移：dp[n] = dp[n-1] + dp[n-2]

    • 时间复杂度 O(n) ，空间复杂度O(1)。

18. 颜色分类

    双指针。指针a永远指向下一个应该放0的位置，初始化为0；指针b永远指向下一个应该放2的位置，初始化为n - 1。使用一个当前指针从左到右遍历数组，遇到0与a交换，遇到2与b交换，直至与b相遇。