我的学习记录

待总结

数组涉及到的题目其实非常广泛，有很多经典的比如双指针法的几个分支、贪心、回溯和动态规划都有相对应的题目，另外也有一些模拟题，比如螺旋矩阵，另外还有一些算是非常规的做法的题目，主要体现在可能并不是主流的算法思想，更多是针对某一道题的做法，遇到这种一般也没有什么好办法，只好多复习

所以数组是非常繁杂的，也很难用几个固定的套路去定义它，只好常刷常新啦

链表的题目一般是自成一派的，并不会牵扯到过多其他的东西，并且由于它遍历方式的独特性，一般来说我们都会使用双指针法的快慢指针来解决大部分问题

常用的套路是用一个虚拟头节点 dummy，也叫哨兵，它的下一个节点会指向真正的头节点，但只有修改链表可能要动到头节点时才会使用，初始化方式可以是空；如果不会涉及到修改头节点，那一般就不太需要 dummy，例如反转和环形

另外就是四步的反转链表，这也是非常常见的，以及一些常用的结论，在面对特定题目时要通过重复来熟悉记忆

只要涉及到排序时，链表一般使用的就是归并排序，但要注意归并排序本身是要求两条链表是有序的，所以有些时候遇到无序的可能需要使用递归（如果要使用，就要注意退出条件，要提前剪枝），然后如果是单条链表的话就需要先用快慢指针把单条拆成两条才行

很多时候做链表的题目时并不一定要怀疑自己，并且感觉链表是得多写才能熟练的，光看可能导致实际写代码时造成很大混乱

主要涉及双指针法、滑动窗口和 KMP 算法

KMP 主要解决的是寻找重复子串问题，用来优化滑动窗口的时间复杂度

双指针法主要被应用于数组、链表和字符串的一些题目，其核心思想是维护两个变量，这两个变量是对某个数据结构不同位置的索引，来方便我们遍历整个数据结构的元素

一般来说都会涉及到指针的移动，来满足不同题目的特定要求

左右指针是双指针法的具体应用之一，目前我接触到的主要被分为二分查找和头尾遍历，前者是一个经典的算法思想，后者则是从头和尾同时开始遍历，以优化时间复杂度

二分查找一般来说我比较喜欢左闭右闭区间的写法，具体是指维护 l, r := 0, len(nums) - 1 这两个变量，然后以 l <= r 作为循环条件，通过在循环内求 mid := l + (r - l) / 2 来让这个位置的元素和目标比较

大部分情况下需要二分的数据结构都是一维的，然后只需要索引一个位置，但有些题目会比如出现了重复的目标元素，需要找到左边界和右边界，或者是给一个二维 / 旋转数组来要求你进行二分，也有可能比如包装一下要用二分来求平方根

变形有很多种，需要多加复习

至于头尾遍历的话，一般是用于比如三数之和这种题目，通过遍历有序的元素来找出特定元素；或者也可以用来实现比如说数组的反转，go 的反转实现 nums[l], nums[r] = nums[r], nums[l] 非常方便

左右指针一般用于有序数组

快慢指针一般常见于链表的题目中，通过 cur、pre、dummy、tail 等指针来方便我们遍历链表、进行特定操作或返回头节点

当它被应用于链表中时，需要格外注意指针何时前进、要前进多少步、链表的索引是否从零开始等问题，以及如何进行交换和赋值也是非常容易绕晕的

LRU 算法也叫最近最少使用算法，常见于缓存设计中，面试时被考到的频率非常高，所以要熟练掌握

一般来说是使用双向链表和哈希表来实现，具体思路是哈希表定位，双向链表维护最近使用顺序，每次命中或插入，都把该节点挪到链表头；超容量时，就从尾部把最久未用的删掉，也就是尾部默认是最久没被用到的

哈希表主要是存储键到节点的映射，要注意节点是要维护键这个字段的，这样在淘汰节点时才能把其从哈希表中删除，在新建节点时也要把键写进去

只要按照这个思路来就可以很轻松地实现