数组-链表

感谢代码随想录

1. 数组

1.1. 滑动窗口

不断调整起始位置和终止位置，处理一块区间内的数据。

在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。确定好移动的情况，并处理需要优先移动窗口还是先处理窗口中的数据。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

1.2. 螺旋数组

确定边界处理的不变量，确保每个子问题的结构都是相同的

然后按照不变量写出每次循环的次数

2. 链表

2.1. 删除链表

删除倒数第n值

删除列表时，最好增加dummy_head节点，删掉头节点更方便

增加dummy-head

2.2. 链表相交

返回相交链表节点

img

1. 求A，B的长度l_A, l_B
2. 为方便起见，将A始终未较长链表，否则将A，B交换
3. 根据l_A, l_B 的差值，将长端链表对齐
4. 依次比较

2.3. 环形链表

20220925103433

$$ slow = x+y \\ fast = x+y+n(y+z) \\ fast = 2*slow $$ 计算得到 x = (n − 1)(y + z) + z 代表，从头节点走向环形入口 = 从相遇点出发走n个节点

// 先向前走再进行验证，否则第一个就相等了

2.4. 交换链表

2.4.1. 交换相邻连个元素链表

交换两个元素

链表中，没有头指针，增加一个虚拟头指针dummyhead

1. 获得cur->next, 因断链，保存cur->next
2. 获得cur->next->next, 因断链，保存cur->next->next->next
3. 获得cur->next->next->next

2.4.2. 反转链表

回文链表

1. 使用快慢指针，找到链表中间节点

   slow 与 fast 同时指向 head 节点开始

   1. 偶数链表， slow节点在中间靠后节点

   

   2. 奇数链表，slow节点在中间节点

   

2. 后半段链表翻转

   1. 需使用pre节点存放前一节点
   2. 断开链表后，需要存放后一节点

   

3. 前后两端比较，不同则返回错误

2.5. 前缀和

将之间计算的结果累加保存在数据中，之后使用时使用结算完成的数组

需要更具题目要求，选择计算什么样的前缀数组

while (~scanf("%d%d", &a, &b))//按位取反，如果结果是eof=-1,取反之后结果为0

3. 双指针

3.1. 双指针指向头尾

有效的山脉数量

1. left 与 right分别从前后遍历
2. 如果二者相遇，则是有效的山脉

3.2. 移出元素

移出0

1. slow 指向新的指针
2. fast 指向旧的指针
3. 将旧指针的元素放在新指针的位置

3.3. 右移元素

右移数组元素

依旧可以使用移动元素 的思想

1. slow 指向 新的指针
2. fast 指向旧的指针

需要注意：

1. 移动数据，会对数据进行覆盖，应复制一个元素
2. fast指针不能越界，需进行 fast = (fast+1) % nums.size()

3.4. 左右元素相同

1. left, right 分别代替i左右元素之和
2. right = sum - left - num[i]

3.5. 排除重复元素

长键盘按入

情况较多，需列出可能的情况

比较name[i] 与 type[j] 由两种情况

1. 相同，则i, j 同时向后移动

2. 不相同， j与 i-1比较，相同，则j向后移动

   因为 i = 0 时，不能向前比较，如果结果不同，直接返回错误

比较完成后，name与 typed有可能有剩余

1. name有剩余 《=》 i< name.size()
2. typed有剩余， typed需要与name[end] 作比较

4. 感谢

代码随想录