Top1：LeetCode 70爬楼梯
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
一、滚动数组优化动态规划。动态规划，x位置的可能是从x-1一步过来的，也可能是从x-2两步过来的，这两种可能，所以f(x) = f(x-1) + f(x-2)
滚动数组优化只要让f(x=1)=1,f(x=2) = 2就可以往前递推了
- 时间复杂度：O（n）
- 空间复杂度：O（1）
可通过完整代码：
public static int climbStairs(int n) {
int f1 = 0, f2 = 0, f3 = 1; // 0 0 1 前移一步得到 0 1 0+1=1，第三个下标为f(1)的值；再往前移一步，1 1 1+1=2，第三个下标为f(2)的值
// 再后面也一直都是后两个数相加，所以满足条件
for (int i = 1; i <= n; i++) {
f1 = f2;
f2 = f3;
f3 = f1 + f2; // 也就是移动之前的f2和f3
}
return f3;
}
Top2：Leetcode 199二叉树的右视图
官方题解：深度优先
题目描述：
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
一、定义两个Stack一个存深度，一个存节点。定义一个map，key存深度，value存对应右视图的值
- 时间复杂度：O（n）。深度优先搜索最多访问每个结点一次，因此是线性复杂度。
- 空间复杂度：O（n）。最坏情况下，栈内会包含接近树高度的结点数量，占用 O(n) 的空间。
可通过完整代码：
public List<Integer> rightSideView(TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Integer> depthStack = new Stack<>();
nodeStack.add(root);
int maxDepth = -1;
depthStack.add(0);
while (!nodeStack.isEmpty()) { // 通过深度栈和结点栈来进行遍历，每次每个depth只添加一个
int depth = depthStack.pop();
TreeNode node = nodeStack.pop();
if (node != null) {
maxDepth = Math.max(maxDepth, depth);
if (!map.containsKey(depth)) {
map.put(depth, node.val);
}
nodeStack.add(node.left);
nodeStack.add(node.right);
depthStack.add(depth + 1);
depthStack.add(depth + 1);
}
}
List<Integer> ans = new ArrayList<>();
for (int depth = 0; depth <= maxDepth; depth++) {
ans.add(map.get(depth));
}
return ans;
}
Top3：Leetcode 232用栈实现队列
题目描述：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。
一、push()函数直接push到s1中，并用front存参数int x的值。pop()函数先判断s2是否为空，如果是判断s1非空将s2.push(s1.pop())再弹出s2；否则直接弹出s2：s2.pop()【肯定先push元素的，所以这里s1和s2不会都为空】
二、peek()函数如果s2非空返回s2.peek()，s2为空返回front。`empty()函数return s1.isEmpty && s2.isEmpty
可通过完整代码：
class MyQueue {
private Stack<Integer> s1 = new Stack<>();
private Stack<Integer> s2 = new Stack<>();
private int front;
public MyQueue() {
}
public void push(int x) {
if (s1.isEmpty()) {
front = x;
}
s1.push(x);
}
public int pop() {
if (s2.isEmpty()) { // s2为空，需要弹入s1的元素，再s2.pop()
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop(); // s1和s2都为空，或者s2不为空，直接弹出s2就可以了
}
public int peek() { // 返回最先入队的那个元素【队列开头的元素】
if (!s2.isEmpty()) return s2.peek();
return front;
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
Top4：Leetcode 143重排链表
官方题解：https://leetcode.cn/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/
题目描述：
找到链表中间节点+反转链表+合并链表
一、先找到中点（奇数中间元素下标，偶数firstEnd下标），再取右半边反转链表，最后将右半边【偶数另一半，或者奇数去掉中间的另一半】合并链表
- 时间复杂度：O（n）。
- 空间复杂度：O（1）。三个函数都只使用了常数级的空间
可通过完整代码：
public void reorderList(ListNode head) {
if (head == null) return;
ListNode mid = middleNode(head);
ListNode l1 = head;
ListNode l2 = mid.next; // 用到了右半边【示例：长度为4用倒数2个，长度为5用倒数2】
mid.next = null; // 因为是单向-->连接，所以.next就可以直接切断
l2 = reverseList(l2);
mergeList(l1, l2);
}
private void mergeList(ListNode l1, ListNode l2) {
ListNode l1Next;
ListNode l2Next;
while (l1 != null && l2 != null) { // 奇偶都可以，当合出来的长为2、3的时候都只经过一次while循环【此处也用&&，必须都不为null，有一个为null表示已经结束】
l1Next = l1.next;
l2Next = l2.next;
l1.next = l2;
l1 = l1Next;
l2.next = l1;
l2 = l2Next;
}
}
private ListNode reverseList(ListNode l2) { // 反转链表：单向连接-->，先存下curr.next接着改变next指向：curr.next=prev；再移动prev和curr
ListNode prev = null;
ListNode curr = l2;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
private ListNode middleNode(ListNode head) { // 奇数长返回中间Node引用，偶数返回firstEnd
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) { // 偶数2个不经过循环直接返回slow；奇数循环一次就返回slow指向中间【此处用&&】
slow = slow.next; // 移动slow引用
fast = fast.next.next; // 移动fast引用
}
return slow;
}
