# Leetcode刷题总结

### 1. 原因

为什么最近开始刷算法题呢？其实原因也比较简单的：

* 我想去市场上看看，去感受一下真实的行情；最近几年整体环境的确很差，公司也在不断的裁员的；我本身倒对公司裁员没有太多的看法，毕竟都是为了活下去的，只要你按照法律要求给钱即可；
* 刷题可能是面试中的门槛，过了这个门槛才能聊后面的事情，也是不得不的事情吧;

### 2. 我是如何刷题的

其实本身没有太多的经验，以前面试的时候我都是从第一个题目不断的往后刷，每次就没坚持多久就刷不动了；这次我改变了一下策略，我在极客时间上买了一个课，叫做"[算法面试通关 40 讲](https://time.geekbang.org/course/detail/100019701-41561)" , 这不是广告，只不过自己刚好看到了就买了下来看看；和我之前的策略不一样的是，他分类来介绍不同的算法题，对类似的面试题会统一聊一下；我想想自己也没什么策略就先按照这么来做题;

### 3. 总结

因为才开始，所以后面会慢慢的补充自己在刷题过程中的经验的，所以慢慢会连载下去; 

#### 3.1 Array&List

数组优点在于访问速度快，缺点在于修改的性能比较差；List优点在于随机访问性能比较差，因为要遍历，好处是修改性能好，因为只需要关心节点前后的指针即可;

1. [反转List](https://leetcode.com/problems/reverse-linked-list/)

    这个题目我自己用了两种方式，一种是比较暴力的解法，一种是比较好的解法；暴力解法就是遍历List将每个node的地址保存在数组中，然后在反着遍历数组修改每一个节点的对应的next节点; 还有一种方式关键在于: 同时维持两个指针`current` 和 `next`指针，每一次修改`next`指针指向current，不断的迭代来反转List

2. [如何判断List有环](https://leetcode.com/problems/linked-list-cycle)

    这个题据说面试比较常见；也有两种解法，第一种就是用map来维持遍历过节点的信息，如果第二次遍历到同一个节点的时候能知道，好处简单坏处就是耗内存； 第二种解法其实比较诡异，叫做快慢指针法；原理是fast的指针一定会在某一个时刻和slow指针相遇，这样就能知道是否有环；其实我有一个优化的思路，就是快和慢指针在遍历的时候顺便给节点加上编号，当慢节点遍历到一个节点的时候发现当前节点有编号并且和自己不一样，必然就会有环，好处就是不用去判断相遇的问题了;

3. [成对反转](https://leetcode.com/problems/swap-nodes-in-pairs)

    题目的意思List成对反转，不是整体反转；其实这个题目的难点在于成对反转涉及到了多少个节点; 
    ![image-20230119170329615](https://cdn.nomoshen.com/typora_img/image-20230119170329615.png)

    其实涉及到了3个节点，因为当紫色两个节点进行互换的时候其实会影响到白色节点的`Next`指针，所以你需要同时保持3个节点，然后进行替换；然后进行成对遍历;

    

4. [list是否有环2](https://leetcode.com/problems/linked-list-cycle-ii) 

    其实这个题目一开始我是真不知道如何做，相比于第二题，主要的难点在于需要知道哪个节点是环的起点；后面看了leetcode上面的一个人的解释的时候我突然就明白了, [WilmerKrisp](https://leetcode.com/problems/linked-list-cycle-ii/discussion/) 这个用户的解释就非常的好；其实这是一个数学问题；里面有一幅图就非常好的解释这个问题，有兴趣的可以点击链接看一下；大概意思是: 假如slow节点与fast节点相遇的时候离起点的距离是X，那么fast行进的距离是2X; 那么从相遇节点开始一步一步进行，和从头开始一步一步行进的过程，这两个节点相遇的节点就是环的起点；
    <img src="https://cdn.nomoshen.com/typora_img/773c5aef-3d67-4052-b4ea-4f17f6fe5a8f_1638443854.8036969.png" alt="WilmerKrisp画的图" style="zoom:50%;" />

5. [按组进行反转List](https://leetcode.com/problems/reverse-nodes-in-k-group/)

    关于这题主要是反转那题的升级版本，主要注意的点在于按照组进行反转之后，这个组前面的那个节点的指针需要保存下来，用来变换一下它的next的节点；

#### 3.2 Stack&Queue

关于Stack和Queue知识点有几个:

* Stack: FILO
* Queue: FIFO; 
* Priority Queue: 主要是大小堆;

1.[用queue来实现stack](https://leetcode.com/problems/implement-queue-using-stacks/solution/)

​	比较简单的，queue可以用数组来模拟;

2.[用stack来实现Queue](https://leetcode.com/problems/implement-stack-using-queues/description/)

3.[判断表达式是否有效](https://leetcode.com/problems/valid-parentheses/description/)

​	是stack的一个应用，比较简单;

4. [stream 获得最大的K个数字](https://leetcode.com/problems/kth-largest-element-in-a-stream/solutions/149050/Java-Priority-Queue/)

    本质上用小根堆的方式维护一个K大小的堆，如果出现比最小值要大的数据就进行替换+调整，这样遍历玩一遍的时候就可以获得正确的数据；不过我写的代码3次之后才被accept,原因在于heap的调整上面出现了错误；这个数据结构比想象中要难写一些；

5. [输出滑动窗口中最大的数据](https://leetcode.com/problems/sliding-window-maximum/)

    这题目前我的accept的方案性能貌似还不是很好，还需要优化；解法目前我想到的有两种：

    1. 维护一个大根堆，在遍历的过程中不断的去剔除不在滑动窗口中的值；这个解法我最为纠结的其实是如何快速的从heap中把要剔除的数据剔除，后来看到有人解释就是创建索引，每一个下标在heap中的位置进行索引；这个的时间复杂度为`O(n * logk)`

    2. 另外一种方式比较需要思考一下；维持一个窗口，如果进来的数据比最大值要大，那就可以将这个数值前面的数据都剔除，原因是只要我在，你们这些比我来的找并且比较小的数据是没有机会输出的，所以就可以排掉；如果后面进来的数据比最大值要小，那么依然要保存；原因是最大值比这些数值来的早，可能后期会被淘汰，一旦淘汰这些数字不就有机会了；主要的点在于两个:

        1. 队列第一个位置就是当前最大值；
        2. 当最大值被剔除之后，通过不断的让队列的第一个位置的数据和插入的数据进行比较，如果比插入的数据要小的话就提出，从而维护第一条特征；

        最终这个算法的复杂度是`O(N)`