二叉树的中序遍历
具体做法
step 1：优先判断树是否为空，空树不遍历。
step 2：准备辅助栈，当二叉树节点为空了且栈中没有节点了，我们就停止访问。
step 3：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
step 4：到达最左后，可以开始访问，如果它还有右节点，则将右边也加入栈中，之后右子树的访问也是优先到最左。
/* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ import java.util.*; public class Solution { public int[] inorderTraversal (TreeNode root) { //添加遍历结果的数组 List<Integer> list = new ArrayList(); Stack<TreeNode> s = new Stack<TreeNode>(); //空树返回空数组 if (root == null) return new int[0]; //当树节点不为空或栈中有节点时 while (root != null || !s.isEmpty()) { //每次找到最左节点 while (root != null) { s.push(root); root = root.left; } //访问该节点 TreeNode node = s.pop(); list.add(node.val); //进入右节点 root = node.right; } //返回的结果 int[] res = new int[list.size()]; for (int i = 0; i < list.size(); i++) res[i] = list.get(i); return res; } }
*二叉树的后序遍历
具体做法
step 1：开辟一个辅助栈，用于记录要访问的子节点，开辟一个前序指针pre。
step 2：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
step 3：弹出一个栈元素，看成该子树的根，判断这个根的右边有没有节点或是有没有被访问过，如果没有右节点或是被访问过了，可以访问这个根，并将前序节点标记为这个根。
step 4：如果没有被访问，那这个根必须入栈，进入右子树继续访问，只有右子树结束了回到这里才能继续访问根。
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ import java.util.*; public class Solution { public int[] postorderTraversal (TreeNode root) { //添加遍历结果的数组 List<Integer> list = new ArrayList(); Stack<TreeNode> s = new Stack<TreeNode>(); TreeNode pre = null; while (root != null || !s.isEmpty()) { //每次先找到最左边的节点 while (root != null) { s.push(root); root = root.left; } //弹出栈顶 TreeNode node = s.pop(); //如果该元素的右边没有或是已经访问过 if (node.right == null || node.right == pre) { //访问中间的节点 list.add(node.val); //且记录为访问过了 pre = node; } else { //该节点入栈 s.push(node); //先访问右边 root = node.right; } } //返回的结果 int[] res = new int[list.size()]; for (int i = 0; i < list.size(); i++) res[i] = list.get(i); return res; } }
堆/栈/队列
用两个栈实现队列
思路：
元素进栈以后，只能优先弹出末尾元素，但是队列每次弹出的却是最先进去的元素，如果能够将栈中元素全部取出来，才能访问到最前面的元素，此时，可以用另一个栈来辅助取出。
import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() { //将第一个栈中内容弹出放入第二个栈中 while (!stack1.isEmpty()) stack2.push(stack1.pop()); //第二个栈栈顶就是最先进来的元素，即队首 int res = stack2.pop(); //再将第二个栈的元素放回第一个栈 while (!stack2.isEmpty()) stack1.push(stack2.pop()); return res; } }
包含min函数的栈
import java.util.Stack; public class Solution { //用于栈的push 与 pop Stack<Integer> s1 = new Stack<Integer>(); //用于存储最小min Stack<Integer> s2 = new Stack<Integer>(); public void push(int node) { s1.push(node); //空或者新元素较小，则入栈 if (s2.isEmpty() || s2.peek() > node) s2.push(node); else //重复加入栈顶 s2.push(s2.peek()); } //这里注意要同时pop两个栈来保证元素同步，因为第二个栈是有重复的 public void pop() { s1.pop(); s2.pop(); } public int top() { return s1.peek(); } public int min() { return s2.peek(); } }
有效括号序列
思路
括号的匹配规则应该符合先进后出原理：最外层的括号即最早出现的左括号，也对应最晚出现的右括号，即先进后出，因此可以使用同样先进后出的栈：遇到左括号就将相应匹配的右括号加入栈中，后续如果是合法的，右括号来的顺序就是栈中弹出的顺序。
具体做法
step 1：创建辅助栈，遍历字符串。
step 2：每次遇到小括号的左括号、中括号的左括号、大括号的左括号，就将其对应的呦括号加入栈中，期待在后续遇到。
step 3：如果没有遇到左括号但是栈为空，说明直接遇到了右括号，不合法。
step 4：其他情况下，如果遇到右括号，刚好会与栈顶元素相同，弹出栈顶元素继续遍历。
step 5：理论上，只要括号是匹配的，栈中元素最后是为空的，因此检查栈是否为空即可最后判断是否合法。
import java.util.*; public class Solution { public boolean isValid (String s) { //辅助栈 Stack<Character> st = new Stack<Character>(); //遍历字符串 for (int i = 0; i < s.length(); i++) { //遇到左小括号 if (s.charAt(i) == '(') //期待遇到右小括号 st.push(')'); //遇到左中括号 else if (s.charAt(i) == '[') //期待遇到右中括号 st.push(']'); //遇到左打括号 else if (s.charAt(i) == '{') //期待遇到右打括号 st.push('}'); //st.isEmpty() 如果没有遇到左括号但是栈为空，说明直接遇到了右括号 //st.pop() != s.charAt(i)如果遇到右括号，刚好会与栈顶元素相同 else if (st.isEmpty() || st.pop() != s.charAt(i)) return false; } //栈中是否还有元素，没有元素说明都匹配成功了，有元素说明还有的没有匹配成功 return st.isEmpty(); } }
最小的K个数
具体做法
step 1：利用input数组中前k个元素，构建一个大小为k的大顶堆，堆顶为这k个元素的最大值。
step 2：对于后续的元素，依次比较其与堆顶的大小，若是比堆顶小，则堆顶弹出，再将新数加入堆中，直至数组结束，保证堆中的k个最小。
step 3：最后将堆顶依次弹出即是最小的k个数。
import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res = new ArrayList<Integer>(); //排除特殊情况 if (k == 0 || input.length == 0) return res; //大根堆 PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo(o1)); //构建一个k个大小的堆 //（只需要加数据，它自己会构建一个大顶堆，注意这里是先把input数组的前四个元素加到堆中） for (int i = 0; i < k; i++) q.offer(input[i]); //然后把input数组的第5个元素开始一个个与第堆顶元素（也就是最大的值）比较 //小的值加入堆，大的值弹出不要了，所以最后堆中就剩下来最小的四个值 for (int i = k; i < input.length; i++) { //较小元素入堆 if (q.peek() > input[i]) { //大的值弹出不要了（也就是堆顶元素） q.poll(); //小的值加入堆 q.offer(input[i]); } } //堆中元素取出入数组 for (int i = 0; i < k; i++) res.add(q.poll()); return res; } }
寻找第K大
具体做法
step 1：进行一次快排，大元素在左，小元素在右，得到的标杆j点.在此之前要使用随机数获取标杆元素，防止数据分布导致每次划分不能均衡。
step 2：如果 j + 1 = k ，那么j点就是第K大。
step 3：如果 j + 1 > k，则第k大的元素在左半段，更新high = j - 1，执行step 1。
step 4：如果 j + 1 < k，则第k大的元素在右半段，更新low = j + 1, 再执行step 1.
import java.util.*; public class Solution { //交换函数 Random r = new Random(); public static void swap(int arr[], int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } public int partition(int[] a, int low, int high, int k){ //随机快排划分 int x = Math.abs(r.nextInt()) % (high - low + 1) + low; swap(a, low, x); int v = a[low]; int i = low + 1; int j = high; while(true){ //小于标杆的在右 while(j >= low + 1 && a[j] < v) j--; //大于标杆的在左 while(i <= high && a[i] > v) i++; if(i > j) break; swap(a, i, j); i++; j--; } swap(a, low, j); //从0开始，所以为第j+1大 if(j + 1 == k) return a[j]; //继续划分 else if(j + 1 < k) return partition(a, j + 1, high, k); else return partition(a, low, j - 1, k); } public int findKth(int[] a, int n, int K) { return partition(a, 0, n - 1, K); } }
import java.util.*; public class Solution { public int findKth(int[] a, int n, int K) { // 暂存K个较大的值，优先队列默认是自然排序（升序），队头元素（根）是堆内的最小元素，也就是小根堆 PriorityQueue<Integer> queue = new PriorityQueue<>(K); // 遍历每一个元素，调整小根堆 for (int num : a) { // 对于小根堆来说，只要没满就可以加入（不需要比较）；如果满了，才判断是否需要替换第一个元素 if (queue.size() < K) { queue.add(num); } else { // 在小根堆内，存储着K个较大的元素，根是这K个中最小的，如果出现比根还要大的元素，说明可以替换根 if (num > queue.peek()) { queue.poll(); // 高个中挑矮个，矮个淘汰 queue.add(num); } } } return queue.isEmpty() ? 0 : queue.peek(); } }
数据流中的中位数
具体做法
step 1：用一数组存储输入的数据流。
step 2：Insert函数在插入的同时，遍历之前存储在数组中的数据，按照递增顺序依次插入，如此一来，加入的数据流便是有序的。
step 3：GetMedian函数可以根据下标直接访问中位数，分为数组为奇数个元素和偶数个元素两种情况。记得需要类型转换为double。
import java.util.*; public class Solution { private ArrayList<Integer> val = new ArrayList<Integer>(); public void Insert(Integer num) { if (val.isEmpty()) //val中没有数据，直接加入 val.add(num); //val中有数据，需要插入排序 else { int i = 0; //遍历找到插入点 for (; i < val.size(); i++) { if (num <= val.get(i)) break; } //插入相应位置 val.add(i, num); } } public Double GetMedian() { int n = val.size(); //奇数个数字 if (n % 2 == 1) //类型转换 return (double)val.get(n / 2); //偶数个数字 else { double a = val.get(n / 2); double b = val.get(n / 2 - 1); return (a + b) / 2; } } }
表达式求值
思路
对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。
处理优先级问题，那必定是乘号有着优先运算的权利，加号减号先一边看，我们甚至可以把减号看成加一个数的相反数，则这里只有乘法和加法，那我们优先处理乘法，遇到乘法，把前一个数和后一个数乘起来，遇到加法就把这些数字都暂时存起来，最后乘法处理完了，就剩余加法，把之前存起来的数字都相加就好了。
处理括号的问题，我们可以将括号中的部分看成一个新的表达式，即一个子问题，因此可以将新的表达式递归地求解，得到一个数字，再运算：
终止条件： 每次遇到左括号意味着进入括号子问题进行计算，那么遇到右括号代表这个递归结束。
返回值： 将括号内部的计算结果值返回。
本级任务： 遍历括号里面的字符，进行计算。
具体做法
step 1：使用栈辅助处理优先级，默认符号为加号。
step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。
step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
step 5：最后将栈中剩余的所有元素，进行一次全部相加。
import java.util.*; public class Solution { public ArrayList<Integer> function(String s, int index) { Stack<Integer> stack = new Stack<Integer>(); int num = 0; char op = '+'; int i; for (i = index; i < s.length(); i++) { //数字转换成int数字 //判断是否为数字 if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { num = num * 10 + s.charAt(i) - '0'; if (i != s.length() - 1) continue; } //碰到'('时，把整个括号内的当成一个数字处理 if (s.charAt(i) == '(') { //递归处理括号 ArrayList<Integer> res = function(s, i + 1); num = res.get(0); i = res.get(1); if (i != s.length() - 1) continue; } switch (op) { //加减号先入栈 case '+': stack.push(num); break; case '-': //相反数 stack.push(-num); break; //优先计算乘号 case '*': int temp = stack.pop(); stack.push(temp * num); break; } num = 0; //右括号结束递归 if (s.charAt(i) == ')') break; else op = s.charAt(i); } int sum = 0; //栈中元素相加 while (!stack.isEmpty()) sum += stack.pop(); ArrayList<Integer> temp = new ArrayList<Integer>(); temp.add(sum); temp.add(i); return temp; } public int solve (String s) { ArrayList<Integer> res = function(s, 0); return res.get(0); } }
哈希
两数之和
知识点：哈希表
哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在O(1)时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。
思路
我们能想到最直观的解法，可能就是两层遍历，将数组所有的二元组合枚举一遍，看看是否是和为目标值，但是这样太费时间了，既然加法这么复杂，我们是不是可以尝试一下减法：对于数组中出现的一个数a，如果目标值减去a的值已经出现过了，那这不就是我们要找的一对元组吗？这种时候，快速找到已经出现过的某个值，可以考虑使用哈希表快速检验某个元素是否出现过这一功能。
具体做法
step 1：构建一个哈希表，其中key值为遍历数组过程中出现过的值，value值为其相应的下标，因为我们最终要返回的是下标。
step 2：遍历数组每个元素，如果目标值减去该元素的结果在哈希表中存在，说明我们先前遍历的时候它出现过，根据记录的下标，就可以得到结果。
step 3：如果相减后的结果没有在哈希表中，说明先前遍历的元素中没有它对应的另一个值，那我们将它加入哈希表，等待后续它匹配的那个值出现即可。
step 4：需要注意最后的结果是下标值加1.
import java.util.*; public class Solution { public int[] twoSum (int[] numbers, int target) { int[] res = new int[0]; //创建哈希表,两元组分别表示值、下标 HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); //在哈希表中查找target-numbers[i] for (int i = 0; i < numbers.length; i++) { int temp = target - numbers[i]; //若是没找到，将此信息计入哈希表 if (!hash.containsKey(temp)) hash.put(numbers[i], i); //否则返回两个下标+1 else return new int[] {hash.get(temp) + 1, i + 1}; } return res; } }
数组中出现次数超过一半的数字
思路
首先我们分析一下，数组某个元素出现次数超过了数组长度的一半，那它肯定出现最多，而且只要超过了一半，其他数字不可能超过一半了，必定是它。
如果给定的数组是有序的，那我们在连续的相同数字中找到出现次数最多即可，但是题目没有要求有序，一种方法是对数组排序后解决，但是时间复杂度就上去了。那我们可以考虑遍历一次数组统计各个元素出现的次数，找到出现次数大于数组长度一半的那个数字。
具体做法
step 1：构建一个哈希表，统计数组元素各自出现了多少次，即key值为数组元素，value值为其出现次数。
step 2：遍历数组，每遇到一个元素就把哈希表中相应key值的value值加1，用来统计出现次数。
step 3：本来可以统计完了之后统一遍历哈希表找到频次大于数组长度一半的key值，但是根据我们上面加粗的点，只要它出现超过了一半，不管后面还有没有，必定就是这个元素了，因此每次统计后，我们都可以检查value值是否大于数组长度的一半，如果大于则找到了。
import java.util.*; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { //哈希表统计每个数字出现的次数 HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); //遍历数组 for (int i = 0; i < array.length; i++) { //统计频率 if (!mp.containsKey(array[i])) mp.put(array[i], 1); else mp.put(array[i], mp.get(array[i]) + 1); //一旦有个数大于长度一半的情况即可返回 if (mp.get(array[i]) > array.length / 2) return array[i]; } return 0; } }
数组中只出现一次的两个数字
思路
既然有两个数字只出现了一次，我们就统计每个数字的出现次数，利用哈希表的快速根据key值访问其频率值。
具体做法
step 1：遍历数组，用哈希表统计每个数字出现的频率。
step 2：然后再遍历一次数组，对比哈希表，找到出现频率为1的两个数字。
step 3：最后整理次序输出。
import java.util.*; public class Solution { public int[] FindNumsAppearOnce (int[] array) { HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); ArrayList<Integer> res = new ArrayList<Integer>(); //遍历数组 for(int i = 0; i < array.length; i++) //统计每个数出现的频率 if(!mp.containsKey(array[i])) mp.put(array[i], 1); else mp.put(array[i], mp.get(array[i]) + 1); //再次遍历数组 for(int i = 0; i < array.length; i++) //找到频率为1的两个数 if(mp.get(array[i]) == 1) res.add(array[i]); //整理次序 if(res.get(0) < res.get(1)) return new int[] {res.get(0), res.get(1)}; else return new int[] {res.get(1), res.get(0)}; } }
