数据结构

stack(栈)

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

  1.     //用一个map去存储，右边的符号做对比，用栈结构去判断，每次有开有合
  2.     public boolean isValid(String s) {
  3.         int n = s.length();
  4.         //奇数一定是没有闭合的
  5.         if (n % 2 == 1) {
  6.             return false;
  7.         }
  8.         HashMap<Character, Character> pairs = new HashMap<Character, Character>() {
  9.             {
  10.                 put(')', '(');
  11.                 put('}', '{');
  12.                 put(']', '[');
  13.             }
  14.         };
  15.         Deque<Character> stack = new LinkedList<>();
  16.         for (int i = 0; i < n; i++) {
  17.             //取出字符串中的字符
  18.             char ch = s.charAt(i);
  19.             if (pairs.containsKey(ch)) {
  20.                 //如果有右边的符号，就去栈里面去取出来对比，没有就是false
  21.                 if (stack.isEmpty() || !stack.peek().equals(pairs.get(ch))) {
  22.                     return false;
  23.                 }
  24.                 //出栈
  25.                 stack.pop();
  26.             } else {
  27.                 //入栈
  28.                 stack.push(ch);
  29.             }
  30.         }
  31.         return stack.isEmpty();
  32.     }

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

  1.     public List<Integer> preorderTraversal(TreeNode root) {
  2.         List<Integer> res = new ArrayList<>();
  3.         //为空直接返回
  4.         if (root == null) {
  5.             return res;
  6.         }
  7.         Deque<TreeNode> stack = new LinkedList<>();
  8.         TreeNode node = root;
  9.         //栈不为空或者二叉树不为空就开始循环
  10.         while (!stack.isEmpty() || node != null) {
  11.             //二叉树不为空就开始循环
  12.             while (node != null) {
  13.                 //结果集加上当前的
  14.                 res.add(node.val);
  15.                 //入栈
  16.                 stack.push(node);
  17.                 //取左节点
  18.                 node = node.left;
  19.             }
  20.             //出栈
  21.             node = stack.pop();
  22.             //取右节点
  23.             node = node.right;
  24.         }
  25.         return res;
  26.     }

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 注意 两个整数之间的除法只保留整数部分。 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1： 输入：tokens = [“2”,”1”,”+”,”3”,”“] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9 示例 2： 输入：tokens = [“4”,”13”,”5”,”/“,”+”] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6 示例 3： 输入：tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”“,”/“,”“,”17”,”+”,”5”,”+”] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((10 (6 / ((9 + 3) -11))) + 17) + 5 = ((10 (6 / (12 -11))) + 17) + 5 = ((10 (6 / -132)) + 17) + 5 = ((10 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

  1.     public int evalRPN(String[] tokens) {
  2.         Stack<Integer> stack = new Stack<>();
  3.         for (String token : tokens) {
  4.             if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
  5.                 Integer pop1 = stack.pop();
  6.                 Integer pop2 = stack.pop();
  7.                 switch (token) {
  8.                     case "+":
  9.                         stack.push(pop2 + pop1);
  10.                         break;
  11.                     case "-":
  12.                         stack.push(pop2 - pop1);
  13.                         break;
  14.                     case "*":
  15.                         stack.push(pop2 * pop1);
  16.                         break;
  17.                     case "/":
  18.                         stack.push(pop2 / pop1);
  19.                         break;
  20.                     default:
  21.                 }
  22.             } else {
  23.                 stack.push(Integer.valueOf(token));
  24.             }
  26.         }
  27.         return stack.peek();
  28.     }

42. 接雨水（Trapping Rain Water）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 输入：height = [4,2,0,3,2,5] 输出：9

  1.     public int trap(int[] height){
  2.         int ans = 0;
  3.         Deque<Integer> stack = new LinkedList<Integer>();
  4.         int n = height.length;
  5.         for (int i = 0; i < n; i++) {
  6.             while (!stack.isEmpty() && height[i] > height[stack.peek()]){
  7.                 Integer pop = stack.pop();
  8.                 if (stack.isEmpty()){
  9.                     break;
  10.                 }
  11.                 int left =  stack.peek();
  12.                 int currWidth = i - left -1;
  13.                 int currhight =  Math.min(height[left],height[i]) - height[pop];
  14.                 ans += currhight * currWidth;
  16.             }
  17.             stack.push(i);
  19.         }
  20.         return ans;
  22.     }

queue(队列)

347. Top K Frequent Elements(前 K 个高频元素)

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

示例 2: 输入: nums = [1], k = 1 输出: [1]

  1.     public int[] topKFrequent(int[] nums, int k) {
  2.         Map<Integer, Integer> occurrences = new HashMap<>();
  3.         for (int num : nums) {
  4.             occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
  5.         }
  6.         //构建一个最小堆去最对比，由于堆的大小至多为 k
  7.         PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
  8.         for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
  9.             int num = entry.getKey();
  10.             int count = entry.getValue();
  11.             if (queue.size() == k) {
  12.                 if (queue.peek()[1] < count) {
  13.                     queue.poll();
  14.                     queue.offer(new int[]{num, count});
  15.                 }
  17.             } else {
  18.                 queue.offer(new int[]{num, count});
  19.             }
  20.         }
  21.         int[] ret = new int[k];
  22.         for (int i = 0; i < k; i++) {
  23.             ret[i] = Objects.requireNonNull(queue.poll())[0];
  24.         }
  25.         return ret;
  26.     }

102. Binary Tree Level Order Traversal(二叉树的层序遍历)

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点） 示例 1： 输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]] 示例 2： 输入：root = [1] 输出：[[1]] 示例 3： 输入：root = [] 输出：[]

a091f4dd2d7e56a6cd2a8b0a97e1711.jpg

  1.     public List<List<Integer>> levelOrder(TreeNode root) {
  2.         List<List<Integer>> res = new ArrayList<>();
  3.         Queue<TreeNode> queue = new ArrayDeque<>();
  4.         if (root != null) {
  5.             queue.add(root);
  6.         }
  7.         while (!queue.isEmpty()) {
  8.             int n = queue.size();
  9.             List<Integer> level = new ArrayList<>();
  10.             for (int i = 0; i < n; i++) {
  11.                 TreeNode node = queue.poll();
  12.                 level.add(node.val);
  13.                 if (node.left != null) {
  14.                     queue.add(node.left);
  15.                 }
  16.                 if (node.right != null) {
  17.                     queue.add(node.right);
  18.                 }
  19.             }
  20.             res.add(level);
  21.         }
  22.         return res;
  23.     }

linkedList(链表)

206. Reverse Linked List（反转链表）

203. 移除链表元素

24. Swap Nodes in Pairs

237. Delete Node in a Linked List

19. Remove Nth Node From End of List

160. Intersection of Two Linked Lists

234. Palindrome Linked List

binaryTree(二叉树)

104. Maximum Depth of Binary Tree

111. Minimum Depth of Binary Tree

226. Invert Binary Tree

112. Path Sum

collection(查找表)

算法思想

cursor(游标)

partition(分治)

pointers(双指针)

Window(滑动窗口)

dp(动态规划)

greedy(贪心)

backtracking(回溯)

math(数学)