week1_复盘

day1

第一道题

第一道题是二分搜索，几个关键点是，二分搜索得是有序数组，通过数学的二分法实现。
代码细节，一个是左闭右开，目标值小于mid，调整右指针到mid，注意右边是开的，因此mid=right，如果目标值大于mid，调整左指针到mid+1，注意左边是闭的，因此left=mid+1。
当然如果是左闭右闭，代码细节就会有一些变化，目标值小于mid，调整右指针到mid-1，注意右边是闭的，因此right=mid-1，如果目标值大于mid，调整左指针到mid+1，注意左边是闭的，因此left=mid+1。

第二题

是移除元素，设置快慢指针，快指针用来遍历数组，慢指针用来指向新数组的位置。然后和目标值比较，如果不相等，慢指针加一，然后赋值为快指针的值。如果相等，快指针加一，继续遍历。

第三题

然后是有序数组的平方，因为数组是有序的，所以平方后的最大值一定在数组的两端，所以可以设置双指针，一个指向数组的头，一个指向数组的尾。然后比较两个指针指向的元素的平方，将较大的那个放到新数组的末尾，然后对应的指针向中间移动。
当然也可以用python的推导式加上sort函数，实现有序数组的平方。

day2

第一题长度最小的子数组

这道题是滑动窗口，设置左右指针，初始都指向数组的头，然后右指针向右移动，直到窗口内的元素和大于等于目标值，然后记录下窗口的长度，然后左指针向右移动，直到窗口内的元素和小于目标值，然后继续移动右指针满足条件后继续记录下窗口的长度，直到右指针到达数组的尾。

第二题螺旋矩阵II

这道题的关键是边界判定，四条边都用左闭右开的方式，最后一个点给下一条边，还有是循环条件是n//2，转一圈掉两层，然后是偏移量，最开始是0 0 然后每次循环偏移量加一，然后是n为奇数时，最后一个点单独处理等于n。

你看看果然不能托现在才想起来附加题没做

day3

第一题 移除链表元素

这道题主要是考虑头节点被删除的情况，所以可以设置一个虚拟头节点，指向头节点，然后设置一个指针指向虚拟头节点，然后遍历链表，如果下一个节点的值等于目标值，就删除下一个节点，否则指针后移。最后返回虚拟头节点的下一个节点。

第二题 设计链表

这道题主要是考虑链表的基本操作，比如添加节点，删除节点，获取节点的值等。主要是index的处理，哦对链表没法用下标的方式来访问节点，所以需要遍历链表来找到目标节点。

第三题 反转链表

这道题是双指针一个cur节点加一个pre节点以及临时节点temp，初始时pre指向None，cur指向头节点，然后遍历链表，每次将cur的next指向pre，然后pre移动到cur，cur移动到temp，最后返回pre。
然后递归，还是不会写

day4

第一题 两两交换链表中的节点

这道题主要是找到前置节点，然后交换两个节点，然后移动指针到下一个位置，注意判断条件的先后，防止空指针异常。设置了两个temp节点，一个用来保存下一个节点，一个用来保存下下下一个节点。可以用画图帮助理解。

第二题 删除链表的倒数第N个节点

这道题是快慢指针，先让快指针移动n+1步，然后快慢指针同时移动，直到快指针到达链表尾部，然后删除慢指针的下一个节点。

第三题 链表相交

这道题是双指针法，设置两个指针分别指向两个链表的头节点，然后同时移动两个指针，当一个指针到达链表尾部时，移动到另一个链表的头节点，继续移动，直到两个指针相等或者都为None。这样就能找到链表的交点。然后我自己想的是用梯形的感觉。

第四题 环形链表II

这道题是快慢指针，快指针每次移动两步，慢指针每次移动一步，直到快指针追上慢指针，或者快指针到达链表尾部。如果追上了，说明链表有环，然后快指针从链表头开始，慢指针从相遇点开始，每次移动一步，直到再次相遇，相遇点就是环的入口。如果快指针到达链表尾部，说明链表没有环。
然后在起点的相遇的位置两个快慢节点改成速度相同，再次相遇的位置就是环的入口。

我自己的杂谈

这一周要准备期末考，又要坚持学代码，压力挺大的其实。虽然感觉期末成绩对我没啥用，但是总害怕大家觉得我天天不在宿舍一定天天读书的那种压力，尽管生活没有那么多的观众就是了，但是这种自我暗示也算是让我进行期末准备了，其实我还有很多自己想做的是，想看鱼书，想学数学，当然ctf也是落下好久了，确实娱乐比以前少了，但是效率总是很低，欸，可能也是天赋的缘故吧。其实我本来有很多想说的，但是这个blog公开了，也是怪不好意思的，那就这样吧