先排序， 再从有序数组中找连续  import java.util.*; public class Solution { public int MLS (int[] arr) { Arrays.sort(arr); int curLen = 0; int maxLen = 0; int last = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] == last) continue; // skip duplicates if (arr[i] == last + 1) { curLen++; maxLen = Math.max(...

栈上存目前未能pair的括号的下标 每遍历一个字符(下标i)，check是否能和栈顶下标对应的字符pair，能pair就pop栈顶。 pop完后i与栈顶的差就是截止到i的valid子串长度。 i.e. 此时栈顶下表对应再往前一个未能pair的字符 举例 0 1 2 3 4 5 6 7 ( ( ) ( ( ) ( ) i stack len 0 0 0 1 0 1 0 2 0 2-0 = 2 3 0 3 0 4 0 3 4 0 5 0 3 5-3 = 2 6 0 3 6 0 7 0 3 7-3 = 4  import java.util.*; public class Solution { pu...

最普通的DFS DFS了几遍就有几个城市群。  import java.util.*; public class Solution { boolean[] visited; int ans = 0; public int citys (ArrayList<ArrayList<Integer>> m) { visited = new boolean[m.size()]; for (int i = 0; i < m.size(); i++) { if (visited[i]) continue; ans++; dfs(i, m); } return ans; } vo...

in-order traversal 时间: O(h) 空间: O(h)  import java.util.*; public class Solution { int visited = 0; int ans = -1; public int KthNode (TreeNode proot, int k) { recurse(proot, k); return ans; } void recurse(TreeNode n, int k) { if (n == null) return; if (ans != -1) return; // already found kth recurse(...

遍历每个字符，记录每个字符最近一次出现的位置。 dp[i]: length of longest substring without duplicates ending at i dp[i] = { dp[i-1] + 1 // if dp[i-1] does not contiain chars[i] i - j // j is the max index of chars[i] in dp[i-1] }  import java.util.*; public class Solution { public int lengthOfLongestSubstring (String s) { ...

连续子数组和的问题 -> 前缀和  import java.util.*; public class Solution { public int maxlenEqualK (int[] arr, int k) { // prefixSumMap: 前缀和 -> 前缀和为sum的最小下标 Map<Integer, Integer> prefixSumMap = new HashMap<>(); prefixSumMap.put(0, -1); int sum_cur = 0; int maxLen = 0; for (int i = 0; i < arr...

正常暴力枚举(递归+回溯) 时间: O(n!) 空间: O(n) import java.util.*; public class Solution { final ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) { Arrays.sort(num); recurse(num, target, 0, new ArrayLis...

首先，两点可以确定一个矩形(i.e. 左上+右下) 设左上+右下两点囊括的矩形为M (M初始为整个mat) 不停的去通过比较x与M的右上和左下角的数值的大小，来缩小M的大小。 x > M右上角, topLeft.row++ x < M右上角, botRight.col-- x > M左下角 topLeft.col++ x < M左下角, botRight.row-- 当M缩成一个点时(i.e. 左上==右下)，这个点就是答案 举例，以下矩形找5： 1 2 6 4 5 10 7 8 11 loop 左上 右下 初始：[0, 0] [2, 2] 1: [0, 0] [1, ...

两个指针分别指向： sentinal: 当前需要反转的k个点的前一个node end: 当前需要反转的k个点的随后一个node e.g.: ans-1-2-3-4-5-6-7-null s e ans-3-2-1-4-5-6-7-null s e 然后对于s->e正常反转链表就行。  import java.util.*; public class Solution { public ListNode reverseKGroup (ListNode head, int k) { ListNode ans = new ListNode(0); ans.next = head; // sen...

public class Solution { public int Fibonacci(int n) { if (n <= 2) return 1; int f_a = 1; int f_b = 1; for (int i = 3; i<=n; ++i) { int tmp = f_a + f_b; f_a = f_b; f_b = tmp; } return f_b; } }

拓扑排序 三个数据存储的内容： infosMap: 还没安排的课(以及该门课的上下游依赖关系) inEdge: 还没上的上游课程的数量 inEdge==0表示这门课不依赖其他课，或者依赖的课已经上过了(i.e. 加入ans了) neis: 下游的课号 queue: 安排了将要上的课。 ans: 已经上过的课。 1. 整理input, 建立infosMap: 2. 遍历infos, 将inEdge==0的课加入queue。 i.e. 该课不依赖其他课，直接安排上。 3. 逐一上掉安排了的课 假设上掉的课是x, x.neis = [y,z], 那么y,z的inEdge减1 如果y,z此时inEdg...

Prim和Kruskal两种方法  // Prim // Time: O(MlogM), each edge is inserted to minHeap once. // Spcae: O(n) import java.util.*; public class Solution { public int miniSpanningTree (int n, int m, int[][] cost) { // u -> [[v1, c1], [v2, c2], ...] List<List<int[]>> graph = new ArrayList<>()...

就标准Dijkstra  import java.util.*; public class Solution { // shortest path from 1 to n. public int findShortestPath (int n, int m, int[][] graph) { // {u: [{v1, w2}, [v2, w2], ...]} Map<Integer, List<int[]>> edges = new HashMap<>(); for(int[] edge : graph) { if (!edges.containsKey(e...

Permutation大部分都能用递归+回溯解决 先build一个charCount把字符串中每个字母的count记下来 recurse的时候从a-z依次选count>0的字母append到输出字符串。 时间: O(n!) 空间: O(n) 栈高  import java.util.*; public class Solution { ArrayList<String> ans = new ArrayList<>(); public ArrayList<String> Permutation(String str) { int[] charCount ...