树

1.二叉树前序遍历

非递归

用一个栈维护节点，插入顺序为右左根，那么弹出顺序为根左右，正好是前序顺序。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> st = new Stack<>();List<Integer> ans = new ArrayList<>();if(root == null) return ans;st.push(root);while(!st.isEmpty()){TreeNode node = st.pop();if(node.right != null){st.push(node.right);}if(node.left != null){st.push(node.left);}ans.add(node.val);}return ans;}
}

递归

class Solution {List<Integer> ans = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {dfs(root);return ans;}public void dfs(TreeNode root){if(root == null) return;ans.add(root.val);dfs(root.left);dfs(root.right);}
}

2.二叉树中序遍历

非递归

维护一个栈用于记录回溯序列。通过root是否为空判断是否到达叶子，到达了就取出栈顶元素，这个元素就是最后一个节点。

入栈顺序总是先左，左边为空了那就弹栈，此时弹出的就是根，接下去遍历右节点

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();Stack<TreeNode> st = new Stack<>();if(root == null) return ans;while(root != null || !st.isEmpty()){if(root != null){ st.push(root);root = root.left;}else{ root = st.pop(); //返回上个叶子ans.add(root.val);root = root.right;}}return ans;}
}

递归

class Solution {List<Integer> ans = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {dfs(root);return ans;}public void dfs(TreeNode root){if(root == null) return;dfs(root.left);ans.add(root.val);dfs(root.right);}
}

3.二叉树后序遍历

非递归

取巧。

前序非递归写法是维护栈，入栈顺序右左根，那么后序我们就维护左右根的顺序，出栈顺序就是根右左，然后再反转就变成左右根，刚好是后序的遍历顺序。

如果不取巧的话，就要一直向左遍历，然后要维护一个父节点，通过父节点找右节点，会比较麻烦。

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> st = new Stack<>();List<Integer> ans = new ArrayList<>();if(root == null) return ans;st.push(root);while(!st.isEmpty()){TreeNode node = st.pop();if(node.left != null){st.push(node.left);}if(node.right != null){st.push(node.right);}ans.add(node.val);}Collections.reverse(ans);return ans;}
}

递归

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {dfs(root);return list;}public void dfs(TreeNode root){if(root == null){return;}dfs(root.left);dfs(root.right);list.add(root.val);}
}

4.二叉树层序遍历

非递归

BFS 思想，维护一个队列，由于队列是先入先出的，因此每次循环队列的大小就是当层的节点个数，直接取就ok。

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {   List<List<Integer>> ans = new ArrayList<>();if(root == null) return ans;Queue<TreeNode> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){int num = q.size();List<Integer> list = new ArrayList<>();while(num > 0){TreeNode node = q.poll();list.add(node.val);if(node.left != null){q.add(node.left);}if(node.right != null){q.add(node.right);}num--;}ans.add(list);}return ans;}
}

递归

用深度 dep判断第几层，第一次遍历到 dep >= ans.size()，说明当前第一次遍历到第 dep层，那么就对ans扩容，

然后添加答案，正常递归。

class Solution {List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {   if(root == null) return ans;dfs(0,root);return ans;}public void dfs(int dep,TreeNode root){if(root == null) return;if(dep >= ans.size()){List<Integer> list = new ArrayList<>();//list.add(root.val);ans.add(list);}ans.get(dep).add(root.val);dfs(dep+1,root.left);dfs(dep+1,root.right);}
}

之字型

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/comments/

用的非递归版，开个变量记录奇偶。

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if(root == null) return ans;queue.add(root);int i = 0;while(!queue.isEmpty()){List<Integer> list = new ArrayList<>();int size = queue.size();while(size > 0){TreeNode node = queue.poll();if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);list.add(node.val);size--;}if((i&1) == 1) Collections.reverse(list);i++;ans.add(list);}return ans;}
}

5.树的子结构

https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

判断B是不是A的子树

暴力 dfs A树和B树

class Solution {private boolean flag = false; //记录答案True or falsepublic boolean isSubStructure(TreeNode A, TreeNode B) {dfs1(A,B);return flag; }public void dfs1(TreeNode rt, TreeNode B){ //遍历A树节点if(B == null || rt == null) return;if(flag == true) return;if(dfs2(rt,B)){flag = true;return;}dfs1(rt.left,B);dfs1(rt.right,B);}public boolean dfs2(TreeNode rt, TreeNode B){ //遍历B树节点if(B == null) return true;  //B已经遍历到叶子了，说明前面的节点都能在A中找到对应，说明是A的子树if(rt == null) return false;  if(rt.val != B.val) return false;  //值不同直接falsereturn dfs2(rt.left, B.left) & dfs2(rt.right, B.right);  }
}

6.二叉树镜像

https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/

左变右，右变左，相当于交换节点

class Solution {public TreeNode mirrorTree(TreeNode root) {if(root == null) return null;TreeNode tmp = root.left;root.left = mirrorTree(root.right);root.right = mirrorTree(tmp);return root;}
}

7.对称二叉树

递归

左子树递归顺序和右子树相反就好了

class Solution {public boolean isSymmetric(TreeNode root) {if(root == null) return true;;return dfs(root.left, root.right);}public boolean dfs(TreeNode A, TreeNode B){if(A == null && B == null) return true;if(A == null || B == null) return false;if(A.val != B.val) return false;return dfs(A.left,B.right)&dfs(A.right,B.left);}
}

非递归

//版本一，使用层序遍历的方法
class Solution {public boolean isSymmetric(TreeNode root) {List<Integer> list = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if(root == null) return true;queue.add(root);while(!queue.isEmpty()){int size = queue.size();while(size > 0){size--;TreeNode node = queue.poll();if(node == null){list.add(-1);continue;}list.add(node.val);queue.add(node.left);queue.add(node.right);}for(int i = 0; i < list.size(); i++){if(list.get(i) != list.get(list.size()-1-i)) return false;}list.clear();}return true;}
}

//版本二，使用双队列模拟
class Solution {public boolean isSymmetric(TreeNode root) {Queue<TreeNode> q1 = new LinkedList<>();Queue<TreeNode> q2 = new LinkedList<>();if(root == null) return true;q1.add(root.left);q2.add(root.right);while(!q1.isEmpty() && !q2.isEmpty()){TreeNode node1 = q1.poll();TreeNode node2 = q2.poll();if(node1 == null && node2 == null) continue;if(node1 == null || node2 == null) return false;if(node1.val != node2.val) return false;q1.add(node1.left);q1.add(node1.right);q2.add(node2.right);q2.add(node2.left);}return true;}
}

8.二叉树右视图

https://leetcode-cn.com/problems/binary-tree-right-side-view/

非递归

类似层序遍历，找到当前队列中最右的元素

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> rightSideView(TreeNode root) {Queue<TreeNode> q = new LinkedList<>();if(root == null) return list;q.add(root);while(!q.isEmpty()){int size = q.size();while(size > 0){TreeNode node = q.poll();if(size == 1){list.add(node.val);}if(node.left != null)q.add(node.left);if(node.right != null)q.add(node.right);size--;}}return list;} 
}

递归

每次都往右子树递归，记录一个深度，通过答案$list$的大小来判断当前的深度是不是第一次遍历到，如果是，说明此时的结点一定是最靠右的，记录答案。

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> rightSideView(TreeNode root) {DFS(root, 0);return list;} public void DFS(TreeNode root, int dep){if(root == null) return;if(dep >= list.size()){list.add(root.val);}DFS(root.right,dep+1);DFS(root.left,dep+1);}
}

9.前序和中序还原二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

前序序列序列头必定是子树树根，那么遍历中序序列找到树根，树根前面的就是左子树，后面的就是右子树。

Arrays.copyOfRange是左闭右开

class Solution{public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length == 0) return null;int rt = preorder[0];int index = 0;for(int i = 0; i < inorder.length; i++){if(inorder[i] == rt){index = i;break;}}TreeNode node = new TreeNode(rt);node.left = buildTree(Arrays.copyOfRange(preorder, 1, 1+index), Arrays.copyOfRange(inorder, 0, index));node.right = buildTree(Arrays.copyOfRange(preorder, index+1, preorder.length), Arrays.copyOfRange(inorder, index+1, inorder.length));return node;}
}

10.中序和后序还原二叉树

和上面思路类似

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/comments/

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(postorder.length == 0 || inorder.length == 0) return null;int rt = postorder[postorder.length-1];int index = 0;for(int i = 0; i < inorder.length; i++){if(inorder[i] == rt){index = i;break;}}TreeNode node = new TreeNode(rt);node.left = buildTree(Arrays.copyOfRange(inorder, 0, index),Arrays.copyOfRange(postorder,0,index));node.right = buildTree(Arrays.copyOfRange(inorder, index+1, inorder.length),Arrays.copyOfRange(postorder,index,postorder.length-1));return node;}
}

排序算法

稳定性：

① 定义：能保证两个相等的数，经过排序之后，其在序列的前后位置顺序不变。（A1=A2，排序前A1在A2前面，排序后A1还在A2前面）

② 意义：稳定性本质是维持具有相同属性的数据的插入顺序，如果后面需要使用该插入顺序排序，则稳定性排序可以避免这次排序。

比如，公司想根据“能力”和“资历”（以进入公司先后顺序为标准）作为本次提拔的参考，假设A和B能力相当，如果是稳定性排序，则第一次根据“能力”排序之后，就不需要第二次根据“”资历

排序了，因为“资历”排序就是员工插入员工表的顺序。如果是不稳定排序，则需要第二次排序，会增加系统开销。

1.快排

时间复杂度

最好情况：pivot每次选择都在中值位置，左右区间元素个数相同，那么递归树高度为logn，每层遍历次数不超过n，所以总的比较次数是nlogn，时间复杂度为$O(logn)$

最坏情况：pivot每次都选在边界位置（值最大或最小），那么一边区间元素为空，一边为n，导致递归树高度为n,每次比较都要进行n-1次，所以总的比较次数是nlogn,时间复杂度为$O(n^2)$，这种情况一般是序列本身基本有序。

空间复杂度

最好情况：辅助栈空间$O(logn)$

最坏情况：辅助栈空间$O(n)$

取决于递归树高度

稳定性

每次partition都会进行元素位置交换，因此不稳定

递归

// l = 0, r = nums.length()-1
public static int partition(int l,int r){int pivot = num[l]; //这个值不确定，因此复杂度不稳定int L = l, R = r;while(L < R){while(L < R && num[R] >= pivot) R--;num[L] = num[R];while(L < R && num[L] <= pivot) L++;num[R] = num[L];}num[L] = pivot;return L;
}public static void quickSort(int l,int r){if(l < r){int mid = partition(l,r);quickSort(l,mid);quickSort(mid+1,r);}
}

非递归

使用栈来模拟递归过程

// l = 0, r = nums.length()-1
public static int partition(int start,int end){LinkedList<Integer> stack = new LinkedList<Integer>();  //用栈模拟if(start < end) {stack.push(end);stack.push(start);while(!stack.isEmpty()) {int l = stack.pop();int r = stack.pop();int index = partition(a, l, r);if(l < index - 1) {stack.push(index-1);stack.push(l);}if(r > index + 1) {stack.push(r);stack.push(index+1);}}}
}public static void quickSort(int l,int r){if(l < r){int mid = partition(l,r);quickSort(l,mid);quickSort(mid+1,r);}
}

2.堆排序

过程：

• build_heap： 建立一个初始堆，从最后一个非叶子结点开始调整堆
• 堆顶编号为0，每调整一次堆，可调整的元素个数减一，因此逆序插入
• 交换堆顶元素与 i 元素，逆序插入堆中，调整，heapify

时间复杂度

初始化堆：$O(n)$

调整一次堆：$O(logn)$

排序：$O(nlogn)$

排序的比较次数和序列的初始状态有关，如果序列初始就是一个堆，那么比较次数较少，否则的话并没有明显改变。所以堆排序的

时间复杂度为$O(nlogn)$

空间复杂度

无辅助栈空间，$heapify$的递归过程实际上就是原地排序的过程，因此空间复杂度为$O(1)$

稳定性

不稳定

//最大堆
public static void build_heap(int len){int parent = len-1;parent = (parent-1)/2; //第一个非叶子节点for(int i = parent; i >= 0; i--){heapify(i, len);}
}/*** 调整堆* @param index 当前最大值位置* @param len  数组长度*/
public static void heapify(int index, int len){if(index >= len) return;  //n 数组长度int c1 = index*2+1;  //左孩子int c2 = index*2+2;  //右孩子int max = index;     //目前最大值下标if(c1 < len && num[c1] > num[max]){ //左孩子的值大于当前最大值max = c1;   //调整最大值为左孩子}if(c2 < len && num[c2] > num[max]){ //右孩子的值大于当前最大值max = c2;  //调整最大值为右孩子}if(max != index){  //最大值不是原来的值，就要交换swap(index,max);heapify(max,len);  //往上递归}
}public static void swap(int index, int max) {int tmp = num[index];num[index] = num[max];num[max] = tmp;
}public static void HeapSort(){build_heap(num.length);for(int i = num.length-1; i >= 0; i--){swap(i,0);heapify(0,i);}
}

3.选择排序

每次都选择当前序列中 $0-i$ 最大的数，将它与末尾的数 $i$ 交换，这样就保证了大的数在后面

时间复杂度

$O(n^2)$

空间复杂度

$O(1)$

稳定性

不稳定，因为两个相等的数可能经过交换，位置发生变化。

public static void selectSort(){for(int i = num.length-1; i >= 0; i--){int max = 0;for(int j = 0; j <= i; j++){if(num[j] >= num[max]){max = j;}}swap(i,max);}
}

4.归并排序

思想就是将数组分成左右两部分，对两部分分别排序，知道两边都有序后进行合并。

时间复杂度

每次取半，复杂度$O(logn)$

每次合并都需要遍历两边数组，平均复杂度为$O(n)$

所以总平均复杂度为 $O(nlogn)$

空间复杂度

辅助数组用于合并

$O(n)$

稳定性

稳定

public static void mergeSort(int l, int r){if(l == r) return;int mid = (l+r)>>1;mergeSort(l,mid);mergeSort(mid+1,r);merge(l,mid+1,r);
}public static void merge(int l,int m,int r){int lsize = m-l;  //左半部数组大小int rsize = r-m+1; //右半部数组大小int[] left = new int[lsize];  int[] right = new int[rsize];for(int i = l; i < m; i++){left[i-l] = num[i];}for(int i = m; i <= r; i++){right[i-m] = num[i];}//对l，r进行合并int i = 0, j = 0, k = l;while(i < lsize && j < rsize){if(left[i] < right[j]){num[k++] = left[i++];}else{num[k++] = right[j++];}}while(i<lsize){num[k++] = left[i++];}while(j<rsize){num[k++] = right[j++];}
}

5.冒泡排序

动态规划

1.经典股票

买卖一次

找差值最大的一组数，$dp[i]$ 表示到 $i$ 为止的最小股票价格

答案就是 第 $i$ 天股票减去 $dp[i]$

class Solution {public int maxProfit(int[] prices) {int n = prices.length;if(n == 0) return 0;int[] dp = new int[n];dp[0] = prices[0];for(int i = 1; i < n; i++){dp[i] = Math.min(dp[i-1],prices[i]);}int ans = 0;for(int i = 1; i < n; i++){ans = Math.max(ans, prices[i]-dp[i]);}return ans;}
}

买卖多次，买之前必须卖掉之前手里有的

对于第 $i$ 天的股票，不一定要买，也不一定要卖，那就相当于可以作为一个中介。买了 $i$ 在 $j$ 卖掉，买入 $j$，在 $k$ 卖掉，相当于买入 $i$ 在

$k$ 卖掉， $j-i+k-j = k-j$ , 因此不管何时买入卖出，只要保证每次买卖利润为正，就能保证最大的总利润

class Solution {public int maxProfit(int[] prices) {int ans = 0;for(int i = 1; i < prices.length; i++){if(prices[i] > prices[i-1]) ans += prices[i]-prices[i-1];}return ans;}
}

2.剪绳子

dp 解法

$dp[n]$表示长度为 $n$ 能获得的最大价值。这里的 $dp$可以表示不进行分割的最大值。比如 n = 3，不进行分割最大就是 3， 这样设置是为了后面递推的方便。

那么 $dp[i] = max(dp[i], dp[j]*dp[i-j])$，意思是将 $i 拆解成长度为 j 和长度为 i-j 的两段$

class Solution {public int cuttingRope(int n) {int[] dp = new int[100];if(n == 2) return 1;if(n == 3) return 2;dp[1] = 1;dp[2] = 2;dp[3] = 3;for(int i = 4; i <= n; i++){for(int j = 1; j <= i/2; j++){dp[i] = Math.max(dp[i], dp[j]*dp[i-j]);}}return dp[n];}
}

数学(贪心)解法

贪心可证：当 $n$ 分成 $3*3*3*...*2*2..$ 时答案是最大的，也就是说尽量分最多的 3 能使得答案最优，但是要注意 如果最后剩下4就不要分成3*1了，这样反正答案变小。

class Solution {public int cuttingRope(int n) {if(n == 2) return 1;if(n == 3) return 2;if(n%3==0){return (int)Math.pow(3,n/3);}else if(n%3==1){ //相当于分成了 3*3*3*....*4 ，最后的4不要分成3和1return 4*(int)Math.pow(3,n/3-1); }else{  // 3*3*3*....*2 return 2*(int)Math.pow(3,n/3);}}
}

3.把数字翻译成字符串

class Solution {public int translateNum(int num) {if(num <= 9) return 1;char[] s = (num + "").toCharArray();int len = s.length;int[] dp = new int[len];dp[0] = 1;if(s[0] <= '1' || (s[0] == '2' && s[1] <= '5')) dp[1] = 2;else dp[1] = 1;for(int i = 2; i < len; i++){if(s[i-1] == '1' || (s[i-1] == '2' && s[i] <= '5')) dp[i] += dp[i-2];dp[i] += dp[i-1];}return dp[len-1];}
}

链表

1.奇偶链表

https://leetcode-cn.com/problems/odd-even-linked-list/

$O(1)$空间$O(n)$时间，实现将编号为奇数的链表放在前面，偶数放在后面

用一个奇链表头和偶链表头记录两条链表，然后间隔遍历，最后相连。

class Solution {public ListNode oddEvenList(ListNode head) {if(head == null || head.next == null) return head;ListNode p1 = head;ListNode p2 = head.next;ListNode p = p2;while(p1.next != null && p2.next != null){p1.next = p2.next;p1 = p1.next;p2.next = p1.next;p2 = p2.next;}p1.next = p;return head;}
}

2.合并两有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode cur = dummy;while(l1 != null && l2 != null){if(l1.val <= l2.val){cur.next = l1;l1 = l1.next;}else{cur.next = l2;l2 = l2.next;}cur = cur.next;}if(l1 != null) cur.next = l1;if(l2 != null) cur.next = l2;return dummy.next;}
}

数组、思维

1.和为s的连续正数序列

class Solution {public int[][] findContinuousSequence(int target) {List<int[]> ans = new ArrayList<>();for(int i = 1; target-i>0; i++){target -= i;int a[] = new int[i+1];if(target%(i+1)==0){int res = target/(i+1);int k = 0;for(int j = 1; j <= i+1; j++){a[k++] = res++;}ans.add(a);}}Collections.reverse(ans);return ans.toArray(new int[ans.size()][]);}
}

2.删除排序数组中的重复项

class Solution {public int removeDuplicates(int[] nums) {int k = 0;for(int i = 0; i < nums.length; i++){if(nums[i] != nums[k]){nums[++k] = nums[i];}}return k+1;}
}

3.圆圈中最后剩下的数字

4. 接雨水

class Solution {public int trap(int[] height) {int[] left = new int[height.length];int[] right = new int[height.length];if(height.length == 0) return 0;left[0] = height[0];for(int i = 1; i < height.length; i++){left[i] = Math.max(left[i-1], height[i]);}right[height.length-1] = height[height.length-1];for(int i = height.length-2; i >= 0; i--){right[i] = Math.max(right[i+1], height[i]);}int ans = 0;for(int i = 0; i < height.length; i++){int minn = Math.min(left[i], right[i]);if(height[i] < minn){ans += minn-height[i];}}return ans;}
}