LeetCode练习（自用）

第一章数组part01

AC/WA等等缩写的含义

关于二分查找

最重要的就是分类讨论好二分，二分看着好写边界 case 还是需要测试的哈
什么是区间不变量？比如区间取左闭右闭的话那么每次区间二分范围都是新区间的左闭右闭后面做判断时要一直基于这个左闭右闭的区间
其实区间定义成开或者闭都没有什么关系只是要明确每次收缩范围后范围内的元素是哪些注意会不会漏掉边界就好
大家需要注意二分的几种情况

- 当l = 0, r = n的时候因为r这个值我们在数组中无法取到,while(l < r) 是正确写法
- 当l = 0, r = n - 1的时候因为r这个值我们在数组中可以取到,while(l <= r) 是正确写法主要看能不能取到这个值

二分法有多种写法，末尾是开区间闭区间都可以解出寻找单个元素和寻找边界的题目，只需要注意相应的是l < r还是l <= r,每次取mid还是取mid加减一即可。建议理解后背熟一套模板，不要搞混。
其实二分还有很多应用场景，有着许多变体，比如说查找第一个大于target的元素或者第一个满足条件的元素，都是一样的，根据是否满足题目的条件来缩小答案所在的区间，这个就是二分的本质。另外需要注意，二分的使用前提：有序数组
二分的最大优势是在于其时间复杂度是O(logn)，因此看到有序数组都要第一时间反问自己是否可以使用二分。
关于二分mid溢出问题解答：

- mid = (l + r) / 2时，如果l + r 大于 INT_MAX(C++内，就是int整型的上限)，那么就会产生溢出问题（int类型无法表示该数）
- 所以写成 mid = l + (r - l) / 2或者 mid = l + ((r - l) >> 1) 可以避免溢出问题

对于二进制的正数来说，右移x位相当于除以2的x几次方，所以右移一位等于➗2，用位运算的好处是比直接相除的操作快

关于移除元素

快指针可以理解成在旧数组中找非目标元素，然后赋值给慢指针指向的新数组，虽然都指向一个数组
关于二分法和移除元素的共性思考
这两题之间有点类似的，他们都是在不断缩小 left 和 right 之间的距离，每次需要判断的都是 left 和 right 之间的数是否满足特定条件。对于「移除元素」这个写法本质上还可以理解为，我们拿 right 的元素也就是右边的元素，去填补 left 元素也就是左边的元素的坑，坑就是 left 从左到右遍历过程中遇到的需要删除的数，因为题目最后说超过数组长度的右边的数可以不用理，所以其实我们的视角是以 left 为主，这样想可能更直观一点。用填补的思想的话可能会修改元素相对位置，这个也是题目所允许的。
fast < nums.size() 和 fast <= nums.size()-1 没什么区别，那为什么第二个会在空数组时报数组越界的错误？
vector的size()函数返回值是无符号整数，空数组时返回了0，再减个一会溢出

第二章数组part02

关于长度最小的子数组

滑动窗口：本质是满足了单调性,即左右指针只会往一个方向走且不会回头。收缩的本质即去掉不再需要的元素。也就是做题我们可以先固定移动右指针，判断条件是否可以收缩左指针算范围。大家可以好好理解一下。
加入滑动窗口中有负数怎么办？
如果有负数的话感觉也不能用滑动窗口了，因为有负数的话无论你收缩还是扩张窗口，你里面的值的总和都可能增加或减少，就不像之前收缩一定变小，扩张一定变大，一切就变得不可控了。如果要 cover 所有的情况，那每次 left 都要缩到 right，那就退化为暴力了哈哈。
在滑动窗口类型题目里有没有去DEBUG的什么小技巧呢？
一般是怀疑哪里有问题就打印哪里像今天的滑动窗口就可以把窗口首尾的下标变化过程打印出来能很清楚的看到窗口是怎样移动的

关于螺旋矩阵II

关于offset不太好理解：offset的意义在于结束一圈后起始位置向后移结束位置向前移。可以画和n=4或者n=5的矩阵，会比较好理解。offset就是由于要去更向内的一圈，内圈元素更少的地方循环，所以循环的次数变少了

第二章链表part01

关于移除链表元素

要把哪个元素排除出链表只需要使得没有指向它的指针如果cur指向2那么只能更改2的next指针对删除它本身没有作用
注意点：指针问题, 大家今天写删除链表题的时候经常少了else判断, 链表首要想好指针是怎么移动的，是否会移动会访问null即可
大家遇到问题的时候对于链表问题可以多用笔画画图,这样会加深你对指针和节点实体的理解,代码的鲁棒性如何通常可以利用边界case尝试,今天很多人都是因为空指针的错误其实大多是一些if,while中不小心取到了空和循环次数和条件有关这种可以设计简单case比如1-2-3-null这种手动画图走一遍自己的代码就解决了。
是否要添加虚拟头结点 ：
虚拟头结点的主要目的是为了避免对头结点的特殊处理；这个处理就指的是修改操作。所以可以这样：涉及到对链表修改(如插入，删除，移动)的，都加个dummy，只是遍历取点就可以不用加
大家空针异常优先在节点前debug判断一下是否为null来定位！
关于递归来做这道题可以看看这边博客的思维三道题套路解决递归问题 | lyl's blog

关于设计链表

设计链表因为调用了很多函数，一旦出错可能不知道调试从何下手，因此建议把代码放到本地IDE上，一个一个函数去测试看出错在什么地方
很多同学对于第index个有所混淆，做题目前一定要理解题目的意思哈，这里的index是从0开始的
addAtIndex 方法中描述的“如果 index 等于链表的长度，则该节点将附加到链表的末尾” 这句话中链表长度这里是指 size而不是size - 1，如果是size-1的话那就会和在最后一个元素前插入冲突了

关于反转链表

链表一定要分清节点和指针的概念。 new ListNode()是真实存在的一个节点, head = new ListNode() 相当于 head指针指向了一个真实的节点, node = head, 相当于node和head同时指向了这个真实的节点
大家尽量不要去动虚拟头节点,因为虚拟头节点本来就是个工具节点,操作后面的节点本身就好了哦
有同学问：为什么有时候需要判定cur->next !=nullptr 有时候又不需要只用判断cur!=nullptr呢？其实这个要看场景，一般就是看你如果不判断的话会不会导致空指针异常，因为如果你的指针遍历到null还调用它的属性或方法肯定就会报错的，但是有时候的情况不会遍历到cur->next，所以要看具体情况。

第二章链表part02

关于两两交换链表中的节点

while (prev.next != nu11 && prev.next.next != nu11) 这边为什么是&& 不是|| 一个是对于偶数个结点的判断一个是奇数个结点那不应该是||的关系吗？
奇数节点就不需要交换了，所以只有满足后面有偶数个节点的时候才会进入循环
循环条件，什么情况应该判断指针本身为空呢?
可以看这个这个遍历的指针最后需要走到哪里需不需要对最后一个节点做操作
三道题套路解决递归问题 | lyl's blog里面有递归的题解很好的博客

关于删除链表的倒数第N个节点

链表问题的debug：可以在循环中逻辑执行前打一次输出语句,执行后打一次输出节点值val, 符合你的预期在增加打输出node.next.val(如果你需要知道后面连接是啥),空针就代表你断链了或者其他错误了, 然后这样慢慢增加找, 还有一种就是利用手动画图debug,记得自己学链表的时候经常画图设计简单case边界case来调试,现在写链表的题都是可以脑子有链表图debug了哈哈,可以尝试一下哈各位

关于链表相交

大家在遇到无法定位头节点,头节点可能被移动删除导致定位失效的时候可以考虑用虚拟头节点,并不是每道题都要用的！！！！
指针存的地址，指针一样，指向一个位置，本题要比较的是结点指针不是值
不要把值和节点的概念混淆起来节点是一个实例占用一块空间值只是它的成员变量值怎样和节点本身没有任何关系一个实例只由它的地址唯一确定!
寻找链表相交节点的题，有提到了一种两个指针分别依次走两个链表的思路，其本质上是链表拼接，详情可以参考题解
相交链表的数学证明过程

关于环形链表

今天的题目的环形链表大家有一些人不会数学方法的话，这边提供一种只需要数环节点个数的方法哈, 因为保证了fast节点比slow节点间距X个节点(环的节点个数),所以相遇一定会在链表头哈

很多同学在 node.next.next空指针,主要原因就是 next可能为null 在用这个之前优先考虑
找环形链表的入口时，为什么 n 可以直接取 1 呢？
我是这样理解的，就是如果相遇前快指针在环中转了不止一圈，比如说转了 5 圈，导致转多圈的原因就是 x 比较长，而环的周长可能比较短。所以最后我们在找入口的时候，两个指针分别从起点和环相遇点开始移动，如果是多圈的情况，那在这个移动过程中从相遇点开始移动的指针也会转多圈，就像公式里写的，x是包含n-1个周长加上 z 的，所以我们可以将这部分在 x 抵消，也就是假设 n 为 1，此时从相遇点开始走的指针也还是在原位出发（省去了转多圈的操作），最后结果还是一样的。

第三章哈希表part01

关于有效的字母异位词

为什么遍历第二个字符串时只考虑碰到计数小于0的情况返回false而不考虑大于0的情况（即s字符串出现了t字符串中没有的字符）？
最开始会判断两个字符串长度是否相等，在两个字符串长度相同的情况下，如果有大于0的情况，一定对应地会出现其他字符小于0。
python中 record = [0] *26 为什么不能写成record=[ ]*26？
要初始化为0或者其他任何数字也行，不填的话编译器应该不知道原来的数字是多少

关于快乐数

sum重复出现，就肯定不是快乐数，为什么呢？
因为只要重复出现一次就说明会无限循环，就像之前链表那个环，假设a1算完等于a2,a2算完等于a3，a3算完等于a1，那么下一次a1算完必定等于a2，再下一次a2算完必定是a3，形成了一个循环，而这个循环中不可能有1，因为1平方的结果永远是1,所以肯定有循环就肯定不是快乐数，是快乐数就肯定没有循环
本题的代码随想录中的 js 示例代码用的map，其实效果和set都是一样的，都是标识某个数是否出现过，map的键也是唯一的。正如Java中，HashSet 和 LinkedHashSet 是基于 HashMap 实现的，而 TreeSet 是基于TreeMap实现的。这些map类都是用散列表或者红黑树来存储键值对的数据结构。
关于本题的时间复杂度，计算方式与一般题目略有不同: