Leetcode 算法感悟¶

统计信息：字数 4093 阅读9分钟

多种思路解题¶

同一个题目，可能有不同的思路解决。之前都是选择思路简单，性能更高的方法，没有把一道题完全钻研，把全部的解法都做出来。这样只学会了一种解决方法。

实际上，尽量追求性能的极致（这样在数据量较大的时候，代码的性能更高）同时，有一些问题，可能无法使用简单的思路，这时就使用复杂的思路解决。

刚开始为了数量，直接刷题做出来即可。后期为了质量，要把主流的方法都掌握了，这个对自己才是提高。做10000道两数之和，还没有1道N皇后问题提高的更多。

不同的类别题目的答题模式¶

现在题目已经做了不少，可以说基本初级的题目和一部分中级的题目没问题了。有时间总结一下做题的方法，什么类型的题用什么类型的方法，算法的复杂度和优缺点是什么。

两数之和¶

考点：数组线性搜索，转换成对象的索引查找。普通的思路：双重循环，性能较差。较好的思路：使用字典存储已经遍历的数，一层循环即可完成（不足是内存消耗增加）。

排列组合¶

考点：回溯算法思路：遍历当前数组，依次把项放到子数组中，判断子数组是否满足条件；如果小于条件，继续循环；如果等于条件，放在结果数组中。如果大于条件，退出当前循环。然后回溯，把这个项从子数组中拿出来，放入下一个项判断。注意：排列组合中是否允许重复；数组是否排序等。

查找数组¶

考点：二分查找思路：默认线性查找的复杂度是 N；排序数组直接使用二分查找 logN（获取首尾元素和中间元素，然后比较中间元素和目标值的差别，改变首尾元素继续计算，直到找到目标元素）注意：数组是否已经排序（如果没有排序，优先使用 arr.sort 排序），数组是否有重复项等（new Set 去重）

数组排序¶

考点：快速排序思路：二分的思路：选择一个数作为基准数，把剩下的数字循环一次进行比较，获取大数数组和小数数组，然后分别对大数数组和小数数组递归排序。最后把基准数，大数数组，小数数组 concat 就是结果。时间复杂度是 N * logN。传统的冒泡排序法，选择排序法是 N * N，这个是浏览器内置排序的方法。也可以使用指针实现，节省空间。注意：不是所有的数组最佳方案都是快速排序。如果一个数组重复数字很多，范围较小，桶排序更适合。

选择算法¶

选择算法，需要从实际数据量（数组长度，字符串长度等）考虑，总计算量不超过 10^8 1、如果数组长度大于 10^8，最好选择 O(1) 或者 logN 最差选择 O(n) 2、如果数组长度是 10000，可以选择 n * logN 到 N ^ N 的算法 3、如果数组长度是 100，可以选择 N ^ 3 的算法每次计算仅仅是四则运算，避免循环内部操作 DOM，减少数组复杂操作，避免数组对象的查找

滑动窗口¶

题目：求一个数组中固定长度的子序列的和的最大值（或最小值）考点：滑动窗口（双指针）子序列是连续的思路： 1、设置 tmp 存储临时变量，使用 max min 存储最值 2、设置开始节点是窗口的长度 length，设置结束节点是0，获取第一个窗口的和，存储到 tmp 中，max = tmp 3、循环数组，窗口移动，获取加入窗口的元素和去掉窗口的元素，重新计算 tmp，重新计算 max min 4、循环结束，返回 max min 时间复杂度是 O(n)