【扩展问题】
- 为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
- 快指针一次走3步，走4步，...n步行吗？
10. 环形链表 II（力扣；思路：快慢指针、数学追击问题★★★☆☆）
题目：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路：
代码：
public ListNode detectCycle() { //找到相遇点 ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ break; } } if(fast == null || fast.next == null){ return null; } //slow指针从头走 slow = head; //fast指针从相遇点开始走 //因为X = （N - 1）C + Y while (fast != slow){ fast = fast.next; slow = slow.next; } return fast; }
运行结果：
二、栈的算法题（目前4道）
1. 有效的括号（力扣）
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路：
代码：
public static boolean isValid(String s) { //创建一个栈来存储括号 Stack<Character> stack = new Stack<>(); //用for循环进行拆分String for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); //如果字符是左括号就入栈 if (ch == '(' || ch == '{' || ch == '[') { stack.push(ch); } else { //如果字符是右括号就执行else //如果栈是空的，就意味着右括号之前没有左括号 if (stack.empty()) { return false; } //先看下栈顶元素是不是满足条件的左括号 char ch2 = stack.peek(); //进行匹配 if (ch == ')' && ch2 == '(' || ch == '}' && ch2 == '{' || ch == ']' && ch2 == '['){ //满足条件，栈顶的左括号跳出 stack.pop(); }else{ return false;//如果不满足条件，返回false } } } //假设右括号都匹配完了，还是有左括号加入，也就是栈不为空 if(!stack.empty()){ return false; } return true; }
运行结果：
2. 逆波兰表达式求值（力扣）
题目：给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
思路：
代码：
public int evalRPN(String[] tokens) { //首先创建一个栈 Stack<Integer> stack = new Stack<>(); //遍历数组 for(String x : tokens){ if (!isOperation(x)){ //如果不是操作符就压入栈 stack.push(Integer.parseInt(x));//解析字符串 }else{ //如果遍历到操作符 //弹出两个数 int num2 = stack.pop();//作为右操作数 int num1 = stack.pop();//作为左操作数 switch (x){ case "+": stack.push(num1 + num2); break; case "-": stack.push(num1 - num2); break; case "*": stack.push(num1 * num2); break; case "/": stack.push(num1 / num2); break; } } } //最后弹出最后一个数，就可以得到结果了 return stack.pop(); } //判断传入的字符是不是操作数 private boolean isOperation(String x){ if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")){ return true; } return false; }
运行结果：
3. 栈的压入、弹出序列（牛客网）
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
思路：此题的思路比较简单，就不作图了，代码的注释有写哈哈哈。
代码：
public boolean IsPopOrder (int[] pushV, int[] popV) { //pushV 和 popV 的元素数量都一致 // write code here //首先创建一个栈 Stack<Integer> stack = new Stack<>(); int j = 0; for (int i = 0;i < pushV.length;i++){ stack.push(pushV[i]); //这段代码要注意异常的抛出，得先知道栈不为空，才可以跳出栈顶元素 while(j < popV.length && !stack.empty() && stack.peek().equals(popV[j]) ){ stack.pop(); j++; } } return stack.empty();//如果stack为空了，就是栈内没元素了，都匹配上了 }
运行结果：
4. 最小栈（力扣）
题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
思路：
虽然内部是用了两个栈，但是在外部看就是一个栈！
代码：
public class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack; //初始化两个栈 public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } //压栈 public void push(int val) { //先压入普通栈 stack.push(val); //如果最小栈为空，直接压入最小栈进行维护 if(minStack.empty()){ minStack.push(val); }else{ //如果最小栈有值，那么就看看如今想压入栈的元素与栈顶元素的大小 //栈顶元素是在minStack中最小的元素，也是stack中最小的元素 if (val <= minStack.peek()){ minStack.push(val); } } } //出栈 public void pop() { if(!stack.empty()){ Integer val = stack.pop();//取出stack的栈顶元素 //如果stack的栈顶元素是minStack栈顶元素的，那么minStack的栈顶元素也要取出 if(val.equals(minStack.peek())){//这里必须用equals，因为Integer在元数据区中只有-128~127 minStack.pop(); } } } //查看栈顶元素 public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }
运行结果：
三、队列的算法题（目前3道）
1. 设计循环队列（力扣）
题目：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
思路：
循环队列两个特殊的状态：队空和队满(rear的情况和front类似)。 由图3-5可以看出，循环队列必须损失一个存储空间，如果空白处也存入元素，则队满的条件也成了front==rear,即和队空条件相同，那么就无法区分队空和队满了
(1)三个状态
1)队空状态:qu.rear==qu.front。
2)队满状态:(qu.rear+1)%maxSizequ == front。
3)长度（多少个元素）:(rear-front+maxsize)%maxsize；防止rear-front为负，所以要加maxsize
(2)两个操作
1)元素x进队操作(移动队尾指针)。
qu.rear=(qu.rear+1)%maxSize;qu.data[qu.rear]=x;
2)元素x出队操作(移动队首指针)。
qu.front=(qu.front+1)%maxSize;x=qu.data[qu.front];
队首指针指向的位置不能有数据！！！
代码：
//循环队列 public class MyCircularQueue { private int elem[]; private int front;//表示队列的头 private int rear;//表示队列的尾 //创建循环队列 public MyCircularQueue(int k) { //如果是浪费空间，这里必须多加一个1 this.elem = new int[k + 1]; } //判断队列是否为满 public boolean isFull() { return (rear + 1) % elem.length == front; } //入队列 public boolean enQueue(int value) { //1. 检查是否队列是满的 if (isFull()) { return false; } elem[rear] = value; rear = (rear + 1) % elem.length; return true; } //出队列 public boolean deQueue() { //队列为空 if (isEmpty()) { return false; } front = (front + 1) % elem.length; return true; } //得到队头元素 public int Front() { if (isEmpty()) { return -1; } return elem[front]; } //得到队尾元素 public int Rear() { if(isEmpty()) { return -1; } int index = (rear == 0) ? elem.length - 1 : rear-1; return elem[index]; } //判读队列是否为空 public boolean isEmpty() { return front == rear; } }
运行结果：
2. 用队列实现栈（力扣）
题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
思路：
代码：
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class MyStack2 { //需要两个队列才能模拟栈 private Queue<Integer> qu1; private Queue<Integer> qu2; public MyStack2() { qu1 = new LinkedList<>(); qu2 = new LinkedList<>(); } public void push(int x) { if(!qu1.isEmpty()){ qu1.offer(x); }else if(!qu2.isEmpty()){ qu2.offer(x); }else { qu1.offer(x); } } public int pop() { if(empty()){ return -1;//两个队列都为空，意味着当前的栈为空 } if(!qu1.isEmpty()){ int size = qu1.size(); for(int i = 0;i < size - 1;i++){ int val = qu1.poll(); qu2.offer(val); } return qu1.poll(); }else{ int size = qu2.size(); for(int i = 0;i<size - 1;i++){ int val = qu2.poll(); qu1.offer(val); } return qu2.poll(); } } public int top() { if(empty()){ return -1; } int val = 0; if(!qu1.isEmpty()){ int size = qu1.size(); for(int i = 0;i < size;i++){ val = qu1.poll(); qu2.offer(val); } return val; }else{ int size = qu2.size(); for(int i = 0;i < size;i++){ val = qu2.poll(); qu1.offer(val); } return val; } } public boolean empty() { return qu1.isEmpty() && qu2.isEmpty(); } }
运行结果：
3. 用栈实现队列（力扣）
题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
思路：
代码：
import java.util.Stack; public class MyQueue2 { //创建两个栈 private Stack<Integer> s1; private Stack<Integer> s2; public MyQueue2() { s1 = new Stack<>(); s2 = new Stack<>(); } //入队 public void push(int x) { s1.push(x); } //出队 public int pop() { //栈空判断 if(empty()){ return -1; } if(s2.empty()){ while(!s1.empty()){ s2.push(s1.pop()); } } return s2.pop(); } //返回队头结点 public int peek() { //栈空判断 if(empty()){ return -1; } if(s2.empty()){ while(!s1.empty()){ s2.push(s1.pop()); } } return s2.peek(); } public boolean empty() { return s1.empty() && s2.empty(); } }
运行结果：
四、二叉树的算法题（目前3道）
1. 相同的树（力扣）
题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例1：
输入：p = [1,2,3]，q = [1,2,3]
输出：true
示例2：
输入：p = [1,2]，q = [1,null,2]
输出：false
示例3：
输入：p = [1,2,1]，q = [1,1,2]
输出：false
提示：
- 两棵树上的节点数目都在范围
[0, 100]内 -104 <= Node.val <= 104
思路：
代码：
//判断两棵树是否相同 public boolean isSameTree(TreeNode p, TreeNode q) { //如果p还有结点，q没有结点，证明两棵树的子树就不相同了，反之亦然 if(p != null && q == null || p == null && q != null){ return false; } //要么都为null，要么都不为null if(p == null && q == null){ return true; } //如果两个结点的数值不一样就返回false if(p.val != q.val){ return false; } return isSameTree(q.left,p.left) && isSameTree(q.right,p.right); }
运行结果：
2. 另一棵树的子树（力扣）
题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例1：
输入：root = [3,4,5,1,2]，subRoot = [4,1,2]
输出：true
示例2：
输入：root = [3,4,5,1,2,null,null,null,null,0]，subRoot = [4,1,2]
输出：false
提示：
root树上的节点数量范围是[1, 2000]subRoot树上的节点数量范围是[1, 1000]-104 <= root.val <= 104-104 <= subRoot.val <= 104
思路：
代码：
//判断两棵树是否相同 public boolean isSameTree(TreeNode p, TreeNode q) { //如果p还有结点，q没有结点，证明两棵树的子树就不相同了，反之亦然 if(p == null && q != null || p != null && q == null){ return false; } //要么都为null，要么都不为null if(p == null && q == null){ return true; } //如果两个结点的数值不一样就返回false if(p.val != q.val){ return false; } return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); } public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root == null || subRoot == null){ return false; } if(isSameTree(root,subRoot))//从当前结点开始 return true; if(isSubtree(root.left,subRoot))//从左子树的根结点开始 return true; if(isSubtree(root.right,subRoot))//从右子树的根结点开始 return true; return false; }
运行结果：
3. 翻转二叉树（力扣）
题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
思路：
（1）先将父亲结点交换
（2）再将子树结点交换
（3）然后递归下去
代码：
//翻转二叉树 public TreeNode invertTree(TreeNode root) { //如果为空树，返回null if(root == null){ return null; } //进行交换 TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left);//翻转左子树 invertTree(root.right);//翻转右子树 return root; }
运行结果：
