代码随想录

本笔记为了记录刷代码随想录题的自己的思路，题目去代码随想录找即可。

链表

1.移除链表元素

思路

链表的移除有两个部分，一个是头节点，一个是非头节点，非头节点只需让其前一个节点指向其下一个节点即可。头节点则需要将自己移动到下一个节点。

or

使用虚拟头节点，这样的话，整个链表中每个元素都有前一个节点，写起来代码统一很多。

两种方法大致思路是：

​ 遍历该节点.next，当下一个节点的val值与要求值相同，则将其上一个节点指向其下一个节点。直到下一个节点为null；

​ ==为什么不遍历该节点，而要遍历该节点.next？==

​ 如果遍历该节点，发现该节点需要移除，那么怎么让它的上一个节点指向下一个节点呢？是没有办法的，因为是单项链表，没有办法找到上一个节点的值，没有记录。所以要从该节点.next开始遍历。

2.翻转链表

双指针法

一个链表

​ node1->node2->node3->null

翻转就是将箭头翻转

利用双指针，一个pre=null，一个cur=head

把cur的next一次一次的指向pre，就一次次的把箭头翻转。

递归

跟双指针一样，他同样是翻转箭头。

栈

把节点一个一个存入栈，再来一个虚拟节点一个一个取出来接到后面连成一个翻转后的链表；

3.两两交换链表中的节点

递归

虚拟头节点

虽说移出链表元素时已经解除虚拟头节点，但做这道题时，明显还是不太懂虚拟头节点的作用。

刚做的时候没弄虚拟头节点，两两交换之后，准备返回头节点提交，才发现不知道怎么找到头节点，这时才理解了虚拟头节点还有这个作用，虚拟头节点.next就是头节点。

==通过这道题==

理解到，链表一是搞清楚指向哪，二是搞清楚怎么保存好前面的东西，因为是单向链表，不然的话做完也找不到提交的头节点。

其次就是，一般都要定义新的节点指向该链表中的某个地方，也就是辅助节点。通过辅助节点来进行链表的操作，而不是原节点。

ListNode firstNode;//保存第一个节点
ListNode twoNode;//保存第二个节点
ListNode tmp;//保存第二个节点后面的节点

为什么要保存节点？

dump->1->2->->3->4

交换时要把dump指向2，这时无法找到1，所以提前要把1保存下来。

4.删除链表的倒数第 N 个结点

思路：

第一个自己做出来的链表题。

暴力解法

现在并不清楚一共有几个节点，先用一个while循环判断一下一共几个节点。

然后通过for循环将辅助节点移动到删除节点前一位，然后将它.next指向它.next.next

同时别忘了弄一个虚拟节点以便删除节点。

双指针法

让快的指针比慢的指针多跑n个，然后当快指针为null，慢指针就来对地方了。

5.链表相交

思路：

想到了用双指针遍历寻找。但是不知道怎么遍历下手，因为长度不一样。

后来看了题解，发现如果想要找相交的地方，相交之后两个链表是一样的东西，一样的长度，所以想要相交就必须从长度一样开始找，所以先把长的链表的指针移动到和短的链表一样的地方，然后同样的长度开始遍历寻找从哪个位置开始指针相同。

6. 环形链表 II

两大难点:判断是否为环/找环的起点

判断是否为环

双指针

一个慢指针，一次走一步

一个快指针，一次走两步

当快慢指针可以相遇，就说明是环

万一错过呢？ 快指针相对慢指针每次走一步，所以说一步一步走，不会跳过慢指针。

找环的起点

找代码随想录视频吧，难以描述有点。

把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？ LeetCode：142.环形链表II_哔哩哔哩_bilibili

哈希表

1.基础知识

散列表，也叫哈希表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫散列函数，存放记录的数组叫做散列表。

==哈希表作用==

==一道题==

==思路==

==代码实现==

从上图中看，需要一个蓝框的HashTable是一个数组，用来存放很多链表，然后还要有EMP类。

链表要有增删改查方法，但是最后进行增删改查的是HashTable，因为需要通过散列函数来进行确定id为多少多少的元素在哪个链表。

散列函数有很多方法写，一种是取模法，id%size（size是数组长度）

2. 有效的字母异位词

这道题比较简单，刚学了哈希数组存储的原理。

立马想到把26个字母存到26容量大小的数组里。

但因为学的时候是要用什么哈希函数然后再取模，所以一直不知道怎么取模能分为26个位置。但后来看了题解，这就不需要什么函数什么取模，每个字母的阿斯克码值就能代表他自己，存入对应的位置。遍历s的时候将数组对应位置加1，遍历t的时候减1。如果最后数组中有不是0的位置，那么就说明字符出现次数不相同，则不为字母异位词。

3.两个数组的交集

如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

用set集合。

4.两数之和

再强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里时们就要想到哈希法。

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。

因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

5. 四数相加 II

依然是先想为什么使用哈希法？

该题目是四数组相加，其实有点像前面第二题，有效的字母异位词，是看两个数组中是否是完全相同的字母。

该题目就是先遍历前两个数组，保存前两个数组所能出现的相加组合。然后遍历后两个数组，看是否出现 0-前两个数组合的情况.

说到这里，应该很清楚的能看出，该题目又是要找某个元素之前是否出现过，所以用哈希表。

那么用什么结构呢？

此题目不仅要存相加的结果，还要存其出现的次数，所以用Map。

6. 赎金信

做了上面那么多题，本题我一眼就看出了该用哈希表，并且判断用map做，但做到最后发现内存和时间都很耗用。

回头一看题解才发现自己这次判断对了哈希表，又判断错了用什么结构。

字母字符只有26个，应该用数组来做，而我选择map，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！

7.三数之和

该题目是求数组中三数加起来等于0，受前面两数之和的影响，我起初认为是还是用map哈希法去做，但后续发现改题目要求不重复的三元组，而去重这里我不太会。

看了题解后，说把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。

去重的过程不好处理，有很多小细节，如果在面试中很难想到位。

时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。

因此我学习了该题目的双指针法。

利用for循环遍历，确定第一个数字a。

剩余两个数字使用双指针去找，如果三数大于0，就让前指针减减，如果小于0，就让后指针加加。

其次就是做去重操作：

​ 对于a来说，上来就可以去重，当i和i-1一样，就continue跳过。这里为什么不用i和i+1，因为如果数组内是[0,0,0]，你上来一顿操作把0全跳过了，但没想到这也是一组解。

​ 对于bc来说，是要在找到一组解后开始去重，同理如果是[0,-1,-1,-1,1,1,1], 你要是先去重，把中间的都去了，要先至少找到一组解再去重，这样就不会漏掉。找到一组解后再去重也来得及。

8.四数之和

这道题相对来说比较有思路，因为它与三数之和没有本质区别，就是用双指针法，在三数之和的基础上多加一层for循环。

唯一有问题的是：

在正常思路下进行比较

int sum = nums[i] + nums[j] + nums[left] + nums[right]; //相加与target比较

但这样做超出内存限制了。

看了题解后发现要用long

long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

字符串

1.反转字符串

该题目比较简单，一眼可看出是用双指针。

然后交换字符的话我只想到用临时变量。

还有一种位运算

==异或运算的性质==

1. 运算规则：相同为0，不同为1
2. N ^ 0 = N 如果某一位是0,0和0相同还是0，某一位为1，1和0不同为1，所以每一位都没变化
3. N ^ N = 0 每一位都相同，所以为0
4. a ^ b = b ^ a
5. (a ^ b) ^ c = a ^ (b ^ c)

交换数字

a = a ^ b; => a = a ^ b 
b = a ^ b; => b = (a ^ b) ^ b = a;
a = a ^ b; => a = (a ^ b) ^ a = b;

2.反转字符串 II

做这道题有些乱，随意的思路，没有想好就直接开始做，导致一堆的循环，循环结束条件也很混乱。

看了答案后恍然大悟，与自己一样的思路，简略不少。

1. 固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

我使用了while，和里面的处理反转的while搞得乱七八糟。

3.替换数字

做这个题的前一天大致了解了下思路：

​ 很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

所以这道题知道这些之后就很简单了，先统计数字个数，然后生成新数组（长度是旧+number）

然后就整两个指针，一个指向新数组末尾，一个指向旧数组末尾，当旧数组遇到字母，就给新数组直接转过去，当遇到数字，就给新数组加number。

​

4. 反转字符串中的单词

刚上来对这道题没有什么思路。被去除空格和反转字符串这两个不相干的东西搞蒙了。

先去除空格再反转

该方法进行操作时，可以把题目中传入的字符串用StringBuffer处理，也可以转为char数组处理。

==先利用双指针去除空格==

快慢指针都指向第一个，然后快指针需要全部遍历。

当快指针不为空，慢指针=快指针，同时慢指针移动一位。

每个单词末尾都要加空格，所以当快指针有了要给慢指针的东西时，慢指针先让自己该位置上等于空格，然后移动一位

然后开始接收快指针遍历的单词，直到快指针为空或长度达到。

==反转字符串==

先用基本的反转反转字符串

==反转单词==

把刚才反转字符串搞反的单词进行反转

5.右旋字符串

为了让本题更有意义，提升一下本题难度：不能申请额外空间，只能在本串上操作。 （Java不能在字符串上修改，所以使用java一定要开辟新空间）

我是用java语言做的，因此比较简单。只需要开辟一个新数组然后先把后面的要旋转的放入数组，然后把前面的放入，就实现了反转。

之后想了想怎么在本串实现右旋转。想到昨天做的反转字符串中的单词，先整体反转，但是单词自己的顺序也反转了，再对单词进行反转即可。所以这道题也就是先所有都反转，再对右旋的部分反转和对正常的部分反转

其次看了代码随想录，也可以先局部反转再整体反转。

同时剑指offer中有道题是左反转，也是同样的方法，只不过是区间有所不同。

6.找出字符串中第一个匹配项的下标

自己写的时候没有好的思路，就是一通循环做的。

后来了解到这是KMP算法

然后看了视频

帮你把KMP算法学个通透！B站（理论篇）

KMP算法解决的是字符串匹配的问题

利用前缀表

什么是前缀后缀

例如一个aabaaf

前缀：a aa aab aaba aabaa （包含首字母不包含尾字母）

后缀：f af aaf baaf abaaf （包含尾字母不包含首字母）

最长相等前后缀：

• a 0
• aa 1
• aab 0
• aaba 1
• aabaa 2
• aabaaf 0

得到的这串序列就是前缀表

012345

aabaaf

010120

当在某个位置不匹配时，比如在f不匹配了，就找前一位，是2，也就是从下标为2重新开始匹配。从b字母重新开始匹配。

为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配

012345

aabaaf

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

时间复杂度分析

其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。

帮你把KMP算法学个通透！（求next数组代码篇

next数组，就是存放前缀表的一个的东西，是为了当遇到不匹配的情况时，从该数组找到那个数，去找到从哪开始匹配。

a a b a a b a a f

a a b a a f

0 1 0 1 2 0 （前缀表）

-1 0 1 0 1 2 （前缀表右移，第一位为-1）

-1 0 -1 0 1 -1 （前缀表减一）

不管哪种next数组，其实原理都一样，直接使用前缀表的话，当遇到不匹配就找next数组对应前一位的数字下标。

右移的话是直接找对应的数字下标，减一的话是找前一位并且再加回来一。

求next数组

一共分为4步，初始化，前后缀不相同的情况，前后缀相同的情况，更新next数组的值。

//next数组和要去匹配的字符串
void getNext(int[] next,String s){
	//i指向后缀末尾，j指向前缀末尾
	j=0;//前缀肯定从0开始
	//i是后缀末尾，从1开始遍历
	for(i=1;i<s.size;i++){
		//前后缀不相同
		while(j>0&&s[i]!=s[j]){
			j=next[j-1];//j回退到前一位的数字指向的位置
		}
		//前后缀相同
		if(s[i]==s[j]) j++;
		next[i]=j;
	}
}

7.重复的子字符串

==暴力解法==

会有很多可能子串，比如长度为1的子串，长度为2,3的都有可能。但最多长度也就到字符串的一半，超过一半就不是子串了。

所以要遍历这么多种可能，然后第二层循环是测试每个子串与后面子串每个字母是否相同，判断时就用第一个字串的字母去比较加上子串长度后的字母是否相同。这样就能测出是否能用子串构成。

关于i++和++i的执行效率问题

for循环中 i++的耗时比++i的要长一些。数据量大些时候就比较明显了；

原因：

for循环中 i++ 在处理时，i++实际为i = i+1，执行时先创建临时变量保存 i 值，然后再+1，而++i不需要的，没有这个过程，所以++i的性能高于i++;

工作和学习中，建议尽量使用++i的写法，尽可能提高程序性能；

==KMP算法==

前一道题学了KMP算法，然后自己尝试了一下。

把next数组按照以前方式求了一下，然后没有想全面，单纯的以为第一个子串全是不一样的字母，然后去统计next数组0的数量，然后觉得就是子串的长度，进而对后续子串遍历，第一个子串对应next数组就该是1 2 3 第二个就是4 5 6这种，但忽略了第一个子串不全是一样的字母，总之考虑总是有些少。

看了题解：

最长相等前后缀不包含的地方就是可以重复的子串，所以如果 length %(length - next[size-1]) == 0 就是重复的子字符串

next[size-1]就是最长相等前后缀。

上述是为什么？

步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：，s[0]s[1]与s[2]s[3]相同 。

步骤二： 因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同。

步骤三： 因为 这是相等的前缀和后缀，t[2] 与 k[2]相同 ，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同。

步骤四：循环往复。

所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。

正是因为 最长相等前后缀的规则，当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串。

因此，当字符串长度减去最长相等前后缀的长度能被字符串长度整除，那么他就符合条件

栈和队列

1.有效的括号

这道题依然是老毛病，没有上来好好思考所有情况就开始写，越写越乱。改掉这个习惯。

这道题要考虑有什么情况不匹配：

1. 右不匹配左
2. 有左无右
3. 有右无左

2.删除字符串中的所有相邻重复项

这道题比较简单，在有了上一题的基础下，一眼就知道如何去做。

首先，删除重复项，而且还是反复执行，所以要用栈。

无数据就往里加，有数据就判断是否和要加的相同，相同就弹栈。

3.逆波兰表达式求值

这道题在前面的题目下，很有思路，还是同样用栈存入然后算术，算完继续存入即可。

但是遇到很多问题，首先第一还是不看题，题目给的是String字符串，我定义的栈是Character泛型，导致后面转换来回转，最后还是错的，改为String才ok。

其他的没有什么不会的，很简单。

4.滑动窗口最大值

这道题不太会做 每次要取出的是最大值（单调队列）

大概就是这个图的意思

add进队列时：比加入元素小的元素全部remove，直到加入元素的前一个元素比他大。这样可以保持第一个元素永远是最大的

因此记录元素最大时返回第一个即可。

还有一个因素：万一后面没有比该元素大的，那这样的话每个滑动窗口里最大的都是第一个滑动窗口里最大的。因此要来一个判断，当滑动窗口要不包含该最大元素时，删除该元素（也就是说i=k开始循环，当i-k的值等于队首值，说明再移动的话，滑动窗口的值将不包含该队首值，所以要把他删除）

5.前 K 个高频元素

这道题会做一半吧

能很快想到用Map集合键值对方式存储元素和出现的次数，然后后续要看出现频率最高的k个，只能想到排序，但这样也不好操作，因为是Map集合的value值排序然后要的又是key值。

然后学习了一下视频才知道用小顶堆，大顶堆。

java中用优先级队列实现，PriorityQueue

//构造一个大顶堆		
PriorityQueue<int[]> queue = new PriorityQueue<>((pair1,pair2)->pair2[1]-pair1[1]);
//该堆存入的都是数组，然后后面的是一个lambda表达式，是一个比较函数。意思是比较数组的第二个元素，后减前就是大顶堆，堆最上面是最大的，把元素加入后，最上面的几个就是要的答案。

//这是遍历一个Map集合的方式（如果需要用到）
for(Map.Entry<Integer,Integer> entry:map.entrySet()){//大顶堆需要对所有元素进行排序
            pq.add(new int[]{entry.getKey(),entry.getValue()});
        }

二叉树

1.二叉树基础

点击链接去看

2.二叉树的递归遍历

• 144.二叉树的前序遍历(opens new window)
• 145.二叉树的后序遍历(opens new window)
• 94.二叉树的中序遍历

他们三个问题的唯一区别就是，先进入左右子树的递归还是先保存该节点的值。

前序遍历先保存值，中序遍历则在左右递归中间保存，后序遍历则在左右递归后。

3.二叉树的迭代遍历

前后是一类

前序是中左右，那么我们只需要放入的时候是中右左。每次都取出栈顶元素，然后将栈顶元素存入结果集，然后将该元素的右和左存入栈，下次取栈顶元素时，顺序就是左和右，这样就满足了中左右顺序。

后序时左右中，翻转就是中右左，所以放入时中左右即可，然后弄好结果集后是中右左，翻转一下就是后序遍历。

中序是左右中，你最开始访问的节点是中，但让你保存的是左，所以需要一个节点来保存访问的元素。一直向左访问存入栈，当左孩子为null，就弹栈（此时刚好就是最左面，也就是该弹出的元素），弹栈后保存该元素到结果集，然后看该元素右孩子，同样进行一系列操作，如果右孩子也为null，那就保存该元素到结果集，这样下来的话就是左右中。

4.二叉树的统一迭代法

==用一个null标记该存入的元素==

其实这个办法比较统一

不管是前中后，都在中入栈后加一个null入栈。

前序存入时就右左中，中序就右中左，后序就中右左。

一直弹栈，当弹栈弹出的是null，下一个弹栈的就保存。这样的话就知道什么时候该存入元素了。

以中序为例

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

5.二叉树层序遍历

层序遍历的话也就是按着节点走的顺序去遍历，那就得用到队列。

那怎么知道是否到了下一层呢：每层的数量是确定的，每进入一层就用len保存长度。

遍历每一个节点时，该节点有左右孩子就加入到队尾，然后该节点弹出存到相应的位置。互不影响。然后进行下一个节点同样的操作，直到len等于0说明要进入下一层了。

动态规划