1-刷题记录

数组（need more 15题）

1. 二分查找（前提：数组为有序数组且数组中无重复元素）

   1. 边界->左闭右开、左闭右闭->while()/if后right的赋值、注意mid的计算
   2. 搜索插入位置（要求在数组中找到目标值，并返回其索引，如果目标值不存在于数组中，那么返回他将会被按照顺序插入的位置）：从简到难，先看最容易讨论的情况，即目标值在两边之外和数组为0的情况；再讨论比较常规的情况。

2. 移除元素-双指针法

   1. 快指针：寻找新数组的元素、新数组就是不含有目标元素的数组；
   2. 慢指针：指向更新新数组下标的位置。

3. 有序数组的平方-双指针法

   1. 左指针、右指针：比较平方后的大小，大者加入新的结果数组
   2. 指向结果数组的最右端的指针

4. 长度最小的子数组-滑动窗口（窗口内是什么？如何移动窗口的起始位置？如何移动窗口的结束位置？）

   1. 窗口：满足其和 >=s 的长度最小的连续数组
   2. 窗口的起始位置：如果当前窗口内的值 >=s 了，那么窗口就可以缩小了，即指针可以右移了
   3. 窗口的结束位置：遍历数组的指针，即for循环里的索引
   4. 注意最后return的时候的两种情况

5. 螺旋矩阵-循环不变量原则

   1. 画四条边，每画一条边要坚持一致的原则（左闭右开或者左开右闭），一圈按照统一的原则画下来
   2. 需要考虑的几个数据
      1. 数据填充：1~n^2
      2. 边的长度：联系到for循环的边界，考虑数组本身！
      3. 中间数据的处理（区分奇数偶数）
      4. 需要走几圈：n%2

6. 每日温度（hot100）

   1. 寻找在temperature数组中，对该下标而言，下一个更大数的下标是谁？
      1. 最直接的暴力解法，时间复杂度O(n*n)，最终提交时间超出限制
      2. 相对间接的暴力解法，时间复杂度为O(n*m)
         1. 反向遍历temperature数组，更新next数组，记录每个温度第一次出现的下标
         2. 反向遍历温度列表，对每个元素，在数组next中找到从高于该温度的所有下标，将其中最小下标记为warmerIndex，如果不是无穷大，那么warmerIndex-i即为需要的值
      3. 栈。

链表

1. 移除链表元素

   1. 找到链表中的val，保留前一个节点信息，指向val值的下一个节点
   2. 链表操作的两种情况
      1. 直接使用原来的链表进行操作（存在头结点额外操作问题，因为头结点没有前一个节点信息）
      2. 设置一个虚拟头结点再进行操作（最后返回的时候注意返回dummyHead->next）

2. 设计链表

   1. 单链表
   2. 双链表

3. 反转链表-双指针法

   1. pre: 反转前的前节点，反转后为next节点，注意最后返回的是pre。
   2. cur: 反转前的现节点，反转后为前节点，注意最后cur节点为null。

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

   1. 明确交换的顺序
   2. 明确哪些节点应该暂时储存

5. 删除链表的倒数第N个节点-双指针法

   1. 怎么把倒数第n个节点在一次扫描中定位到
   2. 两个指针一开始都在虚拟头结点处，一个先走n+1步，然后同步走，快指针走到尾结点时，慢指针正好在目标节点的前一个节点处，方便删除目标节点

6. 链表相交（hot100）

   1. 获得两个链表的长度，移动长链表直到剩余节点数目与短链表相同，开始往后比较，直到两个节点相交

7. 环形链表II

   1. 判断链表是否有环-快慢指针法
   2. 如果有环，如何找到这个环的入口

8. 回文链表（hot100）

   1. 扫描成数组，但数据量会很大 - 还是对函数不太熟
   2. 一个指针指向头结点，一个指针指向尾结点，但是尾结点没有办法向前移动，不知道前一个节点的信息，所以不能用
   3. 先反转链表？然后比较两个链表是否相同？但是会面临需要新建链表的问题

   ​ // 解决-3 问题，只反转后半部分链表，前半部分不变，顺序比较前后两部分，比较完后要恢复后半部分链表

   4. 栈。

栈与队列

1. 用栈实现队列

   1. 必须用两个栈来模拟，一个输入栈，一个输出栈。当执行push时，直接把数据压入输入栈；当执行pop或者peek时，先看输出栈是否为空，如果不为空，直接pop或peek输出栈；如果输出栈为空，那么就要先把输入栈的所有数据都导入输出栈，然后再pop或peek输出栈。
   2. 判断队列为空：只需要输出栈和输入栈同时为空，那么队列即为空。

2. 用队列实现栈

   1. 两个队列：主队列和备份队列，当需要执行pop/top操作时，需要把除了最后一个元素外的其他所有元素都移到备份队列中，当最后一个元素出去后，再把备份队列中的其他元素转移回主队列中。
   2. 一个队列：当需要执行pop/top操作时，只需要把除了最后一个元素外的其他元素重新push进该队列中即可。注意在实现pop功能时，需要把该元素重新加入到队列中，否则将会造成下一次pop/top失败。

3. 有效的括号

   1. 想好怎么去利用栈的特点，进行对称匹配
   2. 扫描字符串，扫描左括号，但是对应到相应的右括号入栈，当扫描到右括号时，只需要判断栈顶元素和扫描到的元素是否一致就可以。
      1. 左括号多，栈空但是字符串还没扫描完
      2. 右括号多，扫描完，但是栈未空
      3. 括号不多不少但是不匹配，栈顶元素和扫描到的右括号不一致
   3. 写这个题的时候报错很多，注意细节（分号，方法带括号等）

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

   1. 注意需要对字符串进行重复操作、
   2. 扫描字符串，如果栈为空，直接入栈，否则，比较栈顶元素和扫描到的字符。如果相等，跳过该字符，并把栈顶元素pop；如果不相等，把该元素push进栈。直到扫描完结束。
   3. 下次看看别的方法，试一下非传统的stack

5. 逆波兰表达式求值

   1. 扫描字符串数组，当遇到数字，先压入栈，当遇到运算符，把两个数字从栈中取出（做除法时注意计算顺序），做完计算后，再压入栈。直到扫描结束。中间结果用整数表示
   2. 注意怎么分析各种情况写起来更好看

6. 滑动窗口最大值（得看好几遍、太多bug）

   1. 我一开始的思路是自然而然的暴力解法：就是用一个队列，移动窗口，push/pop向右滑动，然后遍历窗口中的值，得到最大值，但这种方法是O（n*k）的时间复杂度，而不是线性时间复杂度。
   2. key point是怎么解决窗口中最大值的问题，并且我窗口的移动不能把这个最大值给pop出去。
      1. 队列中的元素是一定要排序的，而且要把最大值放在出队口，否则我不知道最大值。
      2. 队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里的最大值元素就可以，同时保证队列里的元素数值是由大到小的。–>自定义数组–单调队列（单调递增或单调递减的队列）
   3. 1-自定义数组-函数设计问题：
      1. pop(value): 如果窗口移动的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。
      2. push(value): 如果push的元素大于入口元素的数组，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。
   4. 2-利用双端队列手动实现单调队列，分清楚队头和队尾
      1. 单调性：队首的下标永远是当前队列中最大的值
      2. 窗口性：队列中只存储当前滑动窗口内的有效下标
      3. 最大的区别：队列中存放的是数组的下标，而不是数组的元素。存放数组的下标可以很容易的判断这个下标对应的元素是否在窗口内，但是存放数组中的元素还要通过特殊的pop来维护。

7. 前K个高频元素

   1. 需要完成：统计元素出现的频率（哈希表）、对频率排序、找出前k个高频元素。

   2. 基于大顶堆实现：频率大的元素优先级高，优先出队，所以要用数组记录下出队的前K个元素

   3. 基于小顶堆实现：频率小的元素优先级高，优先出队，所以留下的K个元素是我们想要的。

      1. 细节：要维护队列内始终只有K个元素（否则没法获取到队列内部K个大频次，只能通过poll获得）
      2. 细节：最后依次弹出队列时，注意先弹出的是前K个中较小的频次。

   4. Comparator的工作机制：

      • 调用提供的 Lambda 函数 (a, b) -> ...，并根据结果来判断：
        • 如果返回负数 (< 0): 表示 a 的优先级 高于 b (a应该排在b前面)。
        • 如果返回正数 (> 0): 表示 b 的优先级 高于 a (b应该排在a前面)。
        • 如果返回零 (= 0): 表示 a 和 b 的优先级相同。
          记住：返回负数，第一个参数 (a) 优先；返回正数，第二个参数 (b) 优先。