双指针 主要是去重的逻辑有点麻烦 O(n^2), O(1)  import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { Map<Integer, Set<Integer>> m = new HashMap<>(); ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); int len = num.l...

在第i个数要找左侧窗口内的最大数。所以又可以单调栈套娃  唯一需要变化的就是栈上只保留窗口以内的数，所以栈上存下标以查看栈上最老的数是否还在窗口内。 再来一遍口诀： 找右边的就从右往左，找左边的从左往右 找小的就递增，找大的就递减 这里找左边最大, 那就是从左向右+递减。 import java.util.*; // 找左边最大 -> 从左向右 (非单调)递减 public class Solution { public ArrayList<Integer> maxInWindows(int[] num, int size) { ArrayList<Integer&gt...

import java.util.*; public class Solution { int M; int[] aa; public int findKth(int[] a, int n, int K) { M = n - K; aa = a; quickSortM(0, n-1); return aa[M]; } private void quickSortM(int start, int end) { if (start >= end) return; int pivot = partition(start, end); if (pivot == M) return; if (pi...

左闭右开 public class Solution { public int search (int[] nums, int target) { // search [lo, hi) int lo = 0, hi = nums.length; while (lo < hi) { int mid = lo + ((hi-lo) >> 1); if (nums[mid] == target) { return mid; } else if (nums[mid] >= target) { hi = mid; // search left } else { lo = mid ...

时间: O(nlogn) 空间: O(n) import java.util.*; public class Solution { public int[] MySort (int[] arr) { mergeSort(0, arr.length-1, arr); return arr; } // in-place mergeSort void mergeSort(int lo, int hi, int[] arr) { if (lo >= hi) return; int mid = lo + ((hi-lo)>>1); mergeSort(lo, mid, arr); me...

时间O(NlogN) 空间 avg O(logN), worst O(N), 栈高  import java.util.*; public class Solution { public int[] MySort (int[] arr) { quickSort(0, arr.length-1, arr); return arr; } void quickSort(int start, int end, int[] arr) { if (start < end) { int pivot = partition(start, end, arr); quickSort(start, pivot...

Deque + regex Matcher import java.util.regex.Matcher; import java.util.regex.Pattern; import java.util.*; public class Solution { public String decodeString (String s) { if (s.isEmpty()) return ""; Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { stack.push(c...

单调递增栈 import java.util.*; public class Solution { // 找左边最小: 从左往右 单调递增栈 public String removeKnums (String num, int k) { if (num.length() <= k) return "0"; StringBuilder sb = new StringBuilder(); // stack grows to the right Deque<Character> dq = new ArrayDeque<>(); for (int i = 0; i &lt...

单调栈直接套娃 记口诀就行: 找右边的就从右往左，找左边的从左往右 找小的就单调递增，找大的就单调递减 这题是找右边的大的，那就从右往左loop, 建单调递减栈 O(n), O(n) import java.util.*; public class Solution { public int[] temperatures (int[] temperatures) { int[] ans = new int[temperatures.length]; // stack规则： 从右向左push index，栈单调递减(相对于temp[index]) Deque<Integer> sta...

单调递增栈的解法这个讲的挺清楚的  就贴个java的code。 时间: O(n) 虽然是两层循环，但是每个数最多进/出栈一次 空间: O(n) import java.util.*; public class Solution { public int[][] foundMonotoneStack (int[] nums) { int[][] ans = new int[nums.length][2]; // 找左边最近小数 // stack规则: 从左向右push index，stack保持单调递增(相对于nums[index]) Deque<Integer> stack = n...

1 2 5 5 7 8 global-max 2 0 1 0 0 0 0 1 5 0 0 1 1 0 0 1 7 0 0 0 0 2 0 2 8 0 0 0 0 0 3 3 5 0 0 1 1 0 0 3 dp[i][j]: length of common-sequence ending on A[i] and B[i] dp[i][j] = max { d[i-1][j-1] + 1 ~ A[i] = B[j] 0 ~ A[i] != B[i] }  // No space optimization // Space O(m*n) // Time O(m*n) import java.ut...

完全背包变形 dp[i][v]: 用前i个硬币组合出价值v所需的最少硬币数 dp[0][0]=1, dp[0][v]=0 for v>0. dp[i][v] = Min { (a) dp[i-1][v], // 不用i硬币 (b) dp[i][v-arr[i]] // 用i硬币 } 完全与01背包的核心区别是 - 01背包不能dirty write (一个硬币只能使用0或1次)， i.e. (b)选项为 dp[i-1][v-arr[i]] - 完全背包就是要dirty write (一个硬币可以使用多次) i.e. (b)选项为 dp[i][v-arr[i]]  import java....

完全背包问题的变形。 input: 5,[1,2,4,5] vi dp[0 1 2 3 4 5] 0 1 0 0 0 0 0 1 1 1 1 1 1 1 2 1 1 2 2 3 3 4 1 1 2 2 4 4 5 1 1 2 2 4 5 时间: O(NT) 空间: O(T)  import java.util.*; public class Solution { // dp[i][s]: ways of using fist i coins to sum to s // = dp[i-1][s] + dp[i][s-num[i]] // basecase: dp[0][0] = 1, dp[0...

推荐从头到尾看一遍背包问题九讲 时间: O(n*v) 空间: O(v)  import java.util.*; public class Solution { // dp[i][j]: max weight of picking from first i items, using volume <= j // = Max { // dp[i-1][j] // not use i // dp[i-1][j-vi] + wi // use i public int knapsack (int V, int n, int[][] vw) { int[] dp = new int[V+1]; ...