就是递归去暴力枚举. 后选的数必须比之前选的大(之前选的数用last记录, last初始为0), 以保证不会有重复(i.e. 不会出现同时输出[1,2]和[2,1])。 用回溯去避免不必要的array copy. i.e 回溯是basecase输出的时候才copy 不回溯是每一次recurse都要copy, 输出时不用copy.  import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); public ArrayList...

分治 递归 每次递归： 统计每个字符的出现次数 存入freq[] 遍历每一个字符，遇到freq < k的就把字符串拆分成左右两边分别求解，取max 比如 aaabbbcdddefff 对于c拆分 -> aaabbb, dddefff aaabbb会直接return 6， dddefff继续对e拆分 -> ddd, fff ... ...  import java.util.*; public class Solution { public int longestSubstring (String s, int k) { return lss(s, k); } int lss(...

对于i，如果满足i左侧所有数都小于i，并且i右侧所有数都大于i，那么i的位置不用变 两个条件中任意一个条件不满足，那么i就要挪位置 (充分必要)。 那不就是找出需要挪位置的最小和最大下标，求个差就行了 从左向右走一遍 判断是不是i左侧所有数都小于i 从右向左走一遍 判断是不是i右侧所有数都大于i 然后记录不满足条件的最小和最大下标。 时间: O(n) 空间: O(1)  import java.util.*; public class Solution { public int findUnsortedSubarray (int[] nums) { int minInvalidId = Int...

熟悉的味道, 跟这道题一摸一样的解法。 对于每个i: 找i左右两侧离i最近的比i低的柱子j和k, j<i<k, h[j]<h[i]>h[k] 以height[i]为高的矩形的最大宽度为(k-j-1) 时间: O(n) 空间: O(n)  import java.util.*; public class Solution { public int largestRectangleArea (int[] heights) { // mem[i][0] = j, mem[i][1] = k int[][] mem = new int[heights.length][2]; /...

import java.util.*; public class Solution { public int maxProfit (int[] prices) { int min = Integer.MAX_VALUE; int maxProfit = 0; for (int p : prices) { maxProfit = Math.max(maxProfit, p - min); min = Math.min(p, min); } return maxProfit; } }

给每个leaf(包括null)编号 A / \ B C / \ / \ D E F # 00 01 10 11 编号对应从root走到这个leaf的路径 e.g. 00 表示左->左， 01表示左->右 编号的二进制位数为树高(h), 最大id为2^h-1 e.g. 树高2 -> leafId in range [0 - 11], i.e. [0 - 2^2-1] 树高3 -> leafId in range [0 - 111], i.e. [0 - 2^3-1] 然后就对leaf进行二分查找，找到id最大的non-null-leaf(上图中的F) 二分查找(左闭右闭)...

跟(一)一样的。 搞清楚插入/删除分别对应的是dp[][]里的哪个位置就行 // dp[i][j]: min # edit to transform str1[0, i] to str2[0, j] // NOTE：因为dp[0][j]对应空字符串str1，dp[i][0]对应空字符串str2, // 所以其实dp[i][j]对应的是str1[0, i-1] to str2[0, j-1] // // if str1[i-1] == str2[j-1] // dp[i][j] = dp[i-1][j-1] 啥都不变 // else // dp[i][j] = // MIN(dp[i-1][j]...

// dp[i][j]: min # edit to transform str1[0, i-1] to str2[0, j-1] // // e.g. str1=abc str2=abd // // if str1[i-1] == str2[j-1] // dp[i][j] = dp[i-1][j-1] 啥都不变 // else // dp[i][j] = // MIN(dp[i-1][j] + 1, 删除 ab=>abd + 删除c // dp[i][j-1] + 1, 插入 abc=>ab + 插入d // dp[i-1][j-1]) + 1， 替换 ab=>ab + ...

双指针 1. 计算当前左右指针所夹面积 2. 如果lH <= rH, 移动左指针，直到指针所指的高度比之前lH高 (宽变短了, 所以高必须变高才可能面积更大) 3. 如果lH > rH同理。 移动右指针，直到指针所指的高度比之前rH高  import java.util.*; public class Solution { public int maxArea (int[] height) { if (height.length < 2) return 0; int l = 0, r = height.length-1; int maxV = 0; while (l <...

HashMap + PriorityQueue的时间O(N)解 NOTE: 题目要求O(logN), 还是得双向链表 https://blog.nowcoder.net/n/0c72ed84c3f54959b346cf54273ccfaf 每个elem保存freqeuncy和seq#. seq#为最近一次对该elem操作的步数id。 PriorityQueue中根据存入elem的[freqeuncy, sequence#] 每次对一个elem进行get或set时跟新该elem的[freqeuncy, sequence#] 并重新插入PQ set O(N) (i.e. PQ的remove时间为O...

import java.util.*; public class Solution { public ArrayList<Interval> merge(ArrayList<Interval> intervals) { if (intervals.size() <= 1) return intervals; Collections.sort(intervals, (a,b)->a.start - b.start); ArrayList<Interval> ans = new ArrayList<>(); ans.add(interva...

lastP记录目前为止看到的最低开仓价格 只要第i天的价格比lastP高，就获利了结  import java.util.*; public class Solution { public int maxProfit (int[] prices) { if (prices.length <= 1) return 0; int lastP = Integer.MAX_VALUE; int profit = 0; for (int p : prices) { if (p > lastP) profit += p - lastP; lastP = p; } return profit; ...

时间: O(NlogN) heap operation is O(logN) 空间: O(N) import java.util.*; public class Solution { public int minmumNumberOfHost (int n, int[][] startEnd) { // sort startEnd by start, then end. Comparator<int[]> comparator = (a, b) -> { // return a[1]-b[1]会int overflow。。。 是真TM无聊 if (a[0] == b[0]) ...

对于括号的题，核心基本都是: "一个字符串是合法的括号组合"的*充分必要*条件是: 1. 字符串中开口数等于闭口数 (这是废话) 2. 字符串的所有prefix都满足: 开口数>=闭口数 举个栗子，比如 "()(())": prefix: "(", "()", "()(", "()((", "()(()", "()(())". 那么对与这道题，为满足1,2, 每一个位置可以有的permutation就是: 1. 如果有多余的开口 -> 可以选开口 2. 如果有多余未闭合的开口 -> 可以选闭口 剩下的就是正常的递归+回溯了 时间: O(2^n), 每一位最多2个permuta...