动态规划 原理：https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/时间复杂度：O(n)空间复杂度：O(n) import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { // write ...

原理 来自网络，侵删   import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param l1 ListNode类 * @param l2 ListNode类 * @return ListNode类 */ public ListNode mergeTwoLists (ListNode l1, ListNode l2) { // write code here ListNode head = new L...

HashMap import java.util.*; public class Solution { //注意，下标值从 1 开始 public int[] twoSum (int[] numbers, int target) { // write code here HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < numbers.length; i++) { //map 里面放键为每个数的结果，值为下标 //每次放入的时候看是否包含（ target - 当前值） //有的...

快速排序（效果最好） import java.util.*; public class Solution { public int findKth(int[] a, int n, int K) { // write code here quickSort(a, 0, n - 1); return a[n - K]; } public void quickSort(int[] arr, int left, int right) { if (left >= right) return; int i = left; int j = right; int tmp = arr[left]; whi...

方法一：大顶堆 时间复杂度：O(nlongk), 插入容量为k的大根堆时间复杂度为O(longk), 一共遍历n个元素空间复杂度：O(k) public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res = new ArrayList<>(); if (input == null || input.length < k || k <= 0) return res; //降...

简单粗暴 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { private List<TreeNode> preOrder = new ArrayList<>(); private List<TreeNode> inOrder = new ArrayList<>(); private List<TreeNo...

哈希表 + 双向链表 原理：类似力扣 146. LRU 缓存机制推荐看这个讲解：https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/ 代码 import java.util.*; public class Solution { private class Node { Node pre, next; int key, value; private Node(int k, int v) { this.key = k; this.value = v; }...

127 最长公共子串（牛客题霸 ） 方法一：动态规划（此题画出动态变化表更易理解） 原理：类似于力扣：1143. 最长公共子序列时间复杂度O(n * m) n 为A长度，m为B长度空间复杂度O(n * m) 逻辑   public static String LCS (String str1, String str2) { // write code here int dp[][] = new int[str1.length() + 1][str2.length() + 1]; for (int i = 0; i < dp.length; i++) dp[i][0] = 0; for (...