算法篇

算法

数组

• 二分法
• 双指针法(快慢指针)
• 滑动窗口
• 模拟行为（做旋转矩形）
• 前缀和

链表

链表数据结构代码

public class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){ this.val = val;}
    ListNode(int val; ListNode next){this.val = val;this.next = next;}
}

常见题型方法

• 虚拟头节点：先设定一个虚拟的头结点，头结点.next指向head，这样方便处理头结点相关的操作。
• 链表的基本操作
• 反转链表：两种方法。一是：前后指针；二是：递归，从后往前。
• 删除倒数第N个结点 用快慢指针相差为N
• 链表相交 快慢指针
• 环形链表找入口 先判断相交；再根据公式头结点往环的入口走的节点数=快指针与慢指针相交的结点往入口走的节点数，找到入口节点。

哈希表

• 有效的字母异位词

  利用哈希表的特性，如果题目限定字符，就用数组代替哈希表。

• 两个数组的交集
  通过哈希表来检查是否含有set.contains(value)

• 两数之和
  利用HashMap来储存[数值，坐标]。因为HashMap的Key查询速率(map.containsKey())是O(1)很快，所以将数值作为key值。因为题目要返回坐标，所以用map结构存储坐标值。

• 四数相加
  将两个数组的数加上作为set,再用两层循环看另外的两个数组的数。

• 三数之和/四数之和
  先用Arrays.sort排序数组，再用分层的思想。
  多数之和解法：先固定一个节点，再固定下一个节点..直到剩下两个节点，利用双指针，减少一层时间复杂度。
  要注意进行排重。
  首层和次层需要检测nums[i]==nums[i-1]去重。
  双指针层left right，去重。

字符串

• KMP算法：找到一个字符串的子串最大长度的相等前后缀。
  

• 反转字符串 , 双指针法，头尾调换。reverse，O(n )

• 反转字符串II， 局部反转字符串，i += 2*k ，跳指针，再按条件调换。

• 替换数字。提前检测数字长度，扩充字符空间，再前后指针双指针替换。

• 反转字符串里的单词。
  方法一：双指针，右指针跳过尾空格，然后找到下一个空格坐标，定位左指针，左右指针的单词复制到字符数组里。依次类推。

  方法二：将整个字符串反转，跳过字符串头的空格，检测到单词下一个空格，将单词反转。这是头找法。

  方法三：先去多余空格，头和尾，和中间空格。再将每个单词一一反转。

• 实现strStr()。相当于contains。
  方法：利用KMP算法。

• 重复的子字符串：
  方法一：如果一个子串s是由重复子串组成，那么由两个这样的子串s组成的子串t = s + s里，去掉头和尾，存在子串==s。
  方法二：KMP算法，如果存在重复子串。子串最大前后缀相等值n %(n - next[s.length-1]) ==0.

栈与队列

栈的操作Stack

• pop
• push
• peek

队列的操作 deque LinkedList

• offer():队尾插入元素
• poll():队首弹出元素
• peek():返回队首元素

• 栈实现队列
  通过两个栈实现，一个输入栈，一个输出栈。