301. remove-invalid-parentheses
- 给一个字符串，其中包含小括号和其他一些字符，这些括号可能并不匹配，移除尽可能少的括号使得字符串中的括号能valid，返回所有可能的结果。
- ME：这和前面这个求最长匹配的括号子字符串长度有那么一点点相似。回头看了一下求长度，可以用Stack也可以用DP，但是换到这题就陷入了江局。。。
- TA：首先看了百事哥的DFS方法，思路是先从左到右根据count判断右括号有没有多，一旦多了（count为负数）就开始尝试删除右括号，尝试的起点是last_j，即上一次删除的索引，重点是当前开始多出来的索引i。从前往后找非连续出现的右括号或者连续的右括号中的第一个，这样就可以保证得到的结果不会重复。但是对于左括号怎么办？那就从右往左再判断一波左括号，答主的做法是直接反转字符串，这样就可以重复使用代码了，当这一波也结束了，就可以把结果反转回来，加入结果List了。模仿了一波写出来是这样。此外还有BFS的方法，从完整的s开始入队，每次poll队首出来，判断是否valid，不valid就用循环尝试删除每一位的括号，并将生成的这些子字符串入队。为了防止重复，用到了Set来存放每一个出现的字符串，如果在Set中出现过就不再入队了。一旦出现了一个合法的，它就是删除最少的括号使之合法的，那么当前这一个level的所有字符串都验证完之后该存的存完之后，就不用继续了。12345678910111213141516171819202122232425262728293031323334353637383940class Solution {private Set<String> validExpressions = new HashSet<>();public List<String> removeInvalidParentheses(String s) {int leftToRemove = 0, rightToRemove = 0;for (char c : s.toCharArray()) {if (c == '(') {leftToRemove++;} else if (c == ')') {// 在没有多余的左括号的情况下才需要删除当前的右括号rightToRemove = leftToRemove == 0 ? rightToRemove + 1 : rightToRemove;// 与之前的「多余」左括号相抵消leftToRemove = leftToRemove > 0 ? leftToRemove - 1 : leftToRemove;}}dfs(s, 0, 0, 0, leftToRemove, rightToRemove, new StringBuilder());return new ArrayList<>(validExpressions);}private void dfs(String s, int index, int leftCount, int rightCount, int leftRem, int rightRem, StringBuilder curr) {if (index == s.length()) {if (leftRem == 0 && rightRem == 0) {validExpressions.add(curr.toString());}} else {char c = s.charAt(index);int len = curr.length();if ((c == '(' && leftRem > 0) || (c == ')' && rightRem > 0)) {dfs(s, index + 1, leftCount, rightCount, leftRem - (c == '(' ? 1 : 0), rightRem - (c == ')' ? 1 : 0), curr);}curr.append(c);if (c != '(' && c != ')') {dfs(s, index + 1, leftCount, rightCount, leftRem, rightRem, curr);} else if (c == '(') {dfs(s, index + 1, leftCount + 1, rightCount, leftRem, rightRem, curr);} else if (leftCount > rightCount) { // 拼接了右括号且目前左括号较多，则可以继续dfs(s, index + 1, leftCount, rightCount + 1, leftRem, rightRem, curr);}curr.deleteCharAt(len);}}}
303. range-sum-query-immutable
- 给一个int数组，系统会调用rangeSum求两个索引之间的数字和（inclusive）。
- ME：用一个cache存从第一个到当前索引的和，要用的时候减一下呗。写出来是这样。
- TA：没啥。
304. range-sum-query-2d-immutable
- 给一个棋盘，求
(row1, col1)和(row2, col2)所夹矩形的数字之和。 - ME：和上题差不多吧，维护的变成了二维的棋盘，每一格寸的是从左上角到当前位置的元素之和。要求局部之和的时候就减去左边、上面再加回左上角的即可。写出来是这样。
- TA：都差不多吧。
306. additive-number
- 给一个纯数字组成的字符串，判断它是否是additive number字符串，即前后相邻的两个数相加得到下一个数，一路直到最后都符合这种相加的关系。
- ME：自己没搞出来。。。
- TA：我没有搞清楚的是，只要前两个数确定了，后续数字就都确定了，要做的只是去验证一遍。所以只需要来一波双重循环确定前两个数即可。首先看的是这个方法，两个for的变量分别表示前两个数的长度，于是就确定了前两个数，继续往后check是否符合加法即可。check的时候一旦发现，当前这两个数之和的字符串不是后续字符串的开头（使用startsWith），就不用再检查了，跳出回到双重循环继续穷举前两个数吧。而为了防止越界问题，可以引入
import java.math.BigInteger类。另外还有一个挺简洁的recursive方法。
待307. range-sum-query-mutable
- 相比303，多了一个update(index, value)函数，可以更新原本输入的数组。
- ME：一开始就想着直接每次更新的时候O(N)更新对应的sum数组呗，结果超时。毕竟update调用次数和sumRange差不多的话，你这么更新相当于每次都是O(N)的sumRange，那和咸鱼有什么区别？陷入江局。。。感觉进入300题之后基本每题都会陷入江局啊=_=
- TA：
309. best-time-to-buy-and-sell-stock-with-cooldown
- 又是这个股票的，相比121那几题多了一天的缓冲期，即出售后必须至少隔一天才能再买。同样是求无限次交易的最大收益。
- ME：不会！很气！！连续发烧，状态全无。
- TA：看了百事哥的解答终于懂了状态转换是个啥意思。答主给了三种状态，buy, sell和rest，buy就是消耗资金、sell是获得收益。buy[i]要么是继续保持前一天buy[i-1]买入的状态，要么是从两天前卖出sell[i-2]之后再减去当天购买股票要消耗的资金；sell[i]要么是保持前一天sell[i-1]卖出的状态，要么是前一天买入的资金加上今天出手时的价格。这个状态转换还是很清晰的。
310. minimum-height-trees
- 给一个整数n表示有n个点，再给n-1条边，将其中一个点作为根节点可以变成一个树的样子，求最小高度的树可以以哪些点为根。
- ME：不会。。。。。。。。。
- TA：又看了百事哥的解答，和大神差距还是很大。思路是，这一坨东西中肯定有至少两个是叶子节点，即只有一个邻接边，每次把这些叶子节点都从它相邻的点的邻接列表中给抹去，相当于把level最低的这些节点从图中删除，然后会形成新的最低层叶子节点，一路遍历一路删，删到最顶上剩余节点一个或两个的时候，就可以输出结果了。邻接表这里用的是ArrayList + Set的形式存放，每次看看List中各个Set的size就知道它是不是叶子节点了。写出来是这样。
311. sparse-matrix-multiplication
- 给两个二维数组表示的sparse矩阵A和B，其中含有较多的0 element，实现矩阵乘法。
- 根据矩阵乘法的规律，只有
A[i][j]不为0时才去B[j][列数]调取元素相乘并累加到结果矩阵中。123456789101112131415161718192021class Solution {public int[][] multiply(int[][] A, int[][] B) {if (A == null || B == null || A.length == 0 || B.length == 0) {return new int[0][0];}int m = A.length, n = A[0].length, nB = B[0].length;int[][] AB = new int[m][nB];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (A[i][j] != 0) {for (int k = 0; k < nB; k++) {if (B[j][k] != 0) {AB[i][k] += A[i][j] * B[j][k];}}}}}return AB;}}
312. burst-balloons
- 给一个整数数组表示一系列bonus，吹一个气球就能获得当前bonus乘以左、右相邻的bonus之积，同时该气球就从数组中取走了，然后继续。求最优的顺序使获得的总bonus最多。
- ME：不会。。。。。。。。。。
- TA：这题又是看百事哥的帖子，毕竟这些题好像还都是他添加的。这个问题首先要考虑哪一步的结果是确定的，因为你抽走了中间的一个数字之后，其左、右元素会并过来，所以不能简单地拆分成左、右两个子问题来做。但是你走到最后，只剩下一个元素的时候，乘积一定就直接是这个bonus了。所以可以用类似于回溯法的思路来思考，给定区间(left, right)，其中left和right位置的bonus不能够被选择/清除，那么中间的某个元素i如果留到最后，它的bonus就是
num[left] * num[i] * num[right]，至于剩下其他位置的就需要交给递归(left, i)和(i, right)来做。写出来是这样，用memo二维数组来节省不必要的递归。也可以改写成三重循环的DP，第一重循环从2开始到n，表示区间长度；第二重循环从0开始到n-k，表示起始位置，结束位置直接在循环入口由left + k确定；第三重循环从其实位置的下一位开始，这就是真正更新dp数组的位置了，dp[left][right] = dp[left][i] + dp[i][right] + bonus[i]。写出来是这样的。
313. super-ugly-number
- 和前面264非常像，只不过把固定的2、3、5改成了一个可自定义的Prime数组。
- ME：参考前面的做法搞出来了。定义candidate数组，对应存放prime中每个数可能的倍数形式。而所乘的这个倍数需要来自ugly数组，每一个candidate当前的倍数在ugly中的索引也需要用一个index数组存起来。总的来说执行步骤是，来一波循环找出candidate中最小的那个放入ugly数组，然后在遍历一遍candidate数组找到符合这个最小值的项，根据index去更新。
- TA：毕竟我这样每次都来一波循环求最小值并不划算，这个使用PriorityQueue的方法深得我心，自定义了一个Number类，为了让PriorityQueue能排序，需要override一下compareTo函数。这样每次poll出来之后只需要再更新下一个倍数值，直接插入PriorityQueue，之后就可以直接取了。
314. binary-tree-vertical-order-traversal
- 给一个二叉树，要求进行vertical level traversal， 如果垂直方向是平级的，则从上到下输出。
- 用Queue + Map解决。要判断垂直方向平级，就利用相对往左、往右移动的步数来判断，对应存到map中。不过事实上可以先走一波求出index的range，然后就可以直接往List里加了，不用额外的map。12345678910111213141516171819202122232425262728293031323334class Solution {int minIndex = 0, maxIndex = 0;public List<List<Integer>> verticalOrder(TreeNode root) {if (root == null) {return new ArrayList<>();}Map<Integer, List<Integer>> map = new HashMap<>();Queue<TreeNode> nodeQueue = new LinkedList<>();Queue<Integer> indexQueue = new LinkedList<>();nodeQueue.offer(root);indexQueue.offer(0);while (!nodeQueue.isEmpty()) {TreeNode currNode = nodeQueue.poll();int currIndex = indexQueue.poll();maxIndex = Math.max(maxIndex, currIndex);minIndex = Math.min(minIndex, currIndex);map.putIfAbsent(currIndex, new ArrayList<>());map.get(currIndex).add(currNode.val);if (currNode.left != null) {nodeQueue.offer(currNode.left);indexQueue.offer(currIndex - 1);}if (currNode.right != null) {nodeQueue.offer(currNode.right);indexQueue.offer(currIndex + 1);}}List<List<Integer>> ans = new ArrayList<>();for (int i = minIndex; i <= maxIndex; i++) {ans.add(i - minIndex, map.get(i));}return ans;}}
316. remove-duplicate-letters
- 给一个只含有小写字母的字符串，要求删除其中重复的字母，且删除后的结果必须lexicographical升序。
- ME：不会。。。。。。。。。
- TA：看了这个greedy方法感觉怎么这么简单= =。先来一波统计各个字母的出现频数，然后从头往后找当前最小的字母，把它作为第一个并删除后续字符串中的该字母，然后递归继续处理后续字符串。需要注意的是，如果在找最小字母的过程中发现某一个字母已经耗尽了，那么就不能再正常往后找了，因为耗尽的这个字母在后面不会再出现，因此必须以当前找到的最小字母为开头，这样就保证这个耗尽的字母不会被舍弃掉。写出来是这样。还可以使用Stack来存放字母，像这样，若当前字母比栈顶字母小就弹出弹出，直到当前字母能放进去而不比栈顶的大，若栈中已有当前字母（用另一个数组标记）就直接跳过了。此外还有纯iterative的方法，思路是找到每个字母最后一个出现的位置，存入Map。然后遍历Map找到这些索引中的最小值，然后从0到这个最小值之间找最小的字母，并把这个字母从Map中删去，然后从该字母最后一次出现的下一位开始往后，到剩下那些字母中的最小索引位置。123456789101112131415161718192021222324252627282930313233class Solution {public String removeDuplicateLetters(String s) {if (s == null || s.length() == 0) {return s;}Stack<Character> stack = new Stack<>();Map<Character, Integer> lastIndex = new HashMap<>();Set<Character> inStack = new HashSet<>();char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {lastIndex.put(chars[i], i);}for (int i = 0; i < chars.length; i++) {if (inStack.contains(chars[i])) {continue;}while (!stack.isEmpty() &&chars[i] < stack.peek() &&lastIndex.get(stack.peek()) > i) {inStack.remove(stack.pop()); // 若栈顶字母更大且后续还有，就丢出来}stack.push(chars[i]);inStack.add(chars[i]);}StringBuilder sb = new StringBuilder(stack.size());for (char c : stack) {sb.append(c);}return sb.toString();}}
317. shortest-distance-from-all-buildings
- 给一个grid，1表示楼房、2表示障碍物、0表示空地。求在哪个空地上可以到所有其他的楼房、且总路程最短，返回这个最小总路程。
- 近似于暴力的做法。维护一个distance二维数组，表示该空地到其他楼房的距离之和，同时维护一个reach二维数组，表示该空地可到达的楼房数量。从每个
1出发进行BFS更新distance和reach，BFS时对于同一批的节点累积相同的steps。最后再走一波所有的空地，根据distance和reach来更新retVal，取最小值。时间复杂度为O(NM*NM). 这里最开始的这部统计1的个数只是为了在BFS中进行pruning，防止一个绝不可达的1.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172class Solution {public int shortestDistance(int[][] grid) {if (grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}// 求所有1的个数int rows = grid.length, cols = grid[0].length, buildingNum = 0;for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {if (grid[row][col] == 1) {buildingNum++;}}}// 从1出发，累计每个1到每个0处的距离，同时统计0能到达的1的个数int[][] distance = new int[rows][cols], reachCount = new int[rows][cols];for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {if (grid[row][col] == 1 && !bfs(grid, distance, reachCount, row, col, buildingNum)) {return -1; // 如果该1处并不能到达所有的其他的1，则这个1是孤立的、不可达的，直接返回-1}}}// 遍历所有0处，找到能到达所有1的最小距离int retVal = Integer.MAX_VALUE;for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {if (grid[row][col] == 0 && reachCount[row][col] == buildingNum) {retVal = Math.min(retVal, distance[row][col]);}}}return retVal == Integer.MAX_VALUE ? -1 : retVal; // 最后有可能没有0可以到达所有1}private int[] dir = new int[] {0, 1, 0, -1, 0};private boolean bfs(int[][] grid, int[][] distance, int[][] reachCount, int row, int col, int buildingNum) {int rows = grid.length, cols = grid[0].length;boolean[][] visited = new boolean[rows][cols];Queue<int[]> q = new LinkedList<>();visited[row][col] = true;q.offer(new int[] {row, col});int steps = 1, reached = 1;while (!q.isEmpty()) {int size = q.size();while (size-- > 0) {int[] curr = q.poll();for (int i = 0; i < 4; i++) {int rowNext = curr[0] + dir[i];int colNext = curr[1] + dir[i + 1];if (rowNext < 0 || rowNext >= rows ||colNext < 0 || colNext >= cols ||visited[rowNext][colNext] ||grid[rowNext][colNext] == 2) {continue;}visited[rowNext][colNext] = true;if (grid[rowNext][colNext] == 1) {reached++;} else {distance[rowNext][colNext] += steps;reachCount[rowNext][colNext]++;q.offer(new int[] {rowNext, colNext});}}}steps++;}return reached == buildingNum;}}
318. maximum-product-of-word-lengths
- 给一个String的数组，求其中没有重复字母的两个字符串长度之积的最大值。
- ME：利用位运算，每一个字母出现则对应位置的bit置为1，然后两两作与运算，如果结果是0说明二者没有重复的字母，把他俩的长度乘一下即可。双重循环求出最大值。写出来是这样。
- TA：差不多吧，位运算是最快最方便的了。
319. bulb-switcher
- 给一个整数n表示灯泡数，按照每一个、每两个…每n个的间隔反转灯泡状态，一开始全关，然后全开，然后隔一个关一个，然后隔两个toggle。。。
- ME：一开始老老实实地按题意来做，超时。。。
- TA: 没想到这么无聊。因为灯泡最后要能亮着，它经历的操作一定是奇数次，一个数有奇数个因数，那它一定是平方数，所以问题就转换成求n中含有多少个平方数了。写出来就这样。
320. generalized-abbreviation
- 给一个字符串，求它的所有用数字代替字母个数后可能的缩写形式。例如
abc可以缩写成["3","2c","1b1","1bc","a2","a1c","ab1","abc"]. - 对于一个字母只有两种情况，要么将它缩写成数字，要么保留字母本身，因此最直接的想法就是递归解法。从前往后逐个字母走，若替换成数字则继续加上前面的数字，若保留字母本身则需要看看它前面是数字则需要先append上数字、再append上当前字母、清零字母计数。我觉得时间复杂度是O(2^N)，其中N是单词的长度，因为一共就是2^N种可能性，都需要访问一次。1234567891011121314151617181920212223242526class Solution {public List<String> generateAbbreviations(String word) {List<String> ans = new ArrayList<>();generate(ans, word.toCharArray(), 0, new StringBuilder(), 0);return ans;}private void generate(List<String> ans, char[] wordChar, int index, StringBuilder sb, int charCount) {if (index == wordChar.length) {if (charCount > 0) {sb.append(charCount);}ans.add(sb.toString());} else {int originalLen = sb.length();generate(ans, wordChar, index + 1, sb, charCount + 1);sb.setLength(originalLen);if (charCount > 0) {sb.append(charCount);}sb.append(wordChar[index]);generate(ans, wordChar, index + 1, sb, 0);sb.setLength(originalLen);}}}
321. create-maximum-number
- 给两个一位整数的数组，给一个整数k，要求从两个数组中选取数字组成k位数，使它尽可能大。
- ME：不会。。。。。。
- TA：又是看了百事哥的解答，思路是根据长度
i确定第一个数组能得到的最大数组，然后根据k - i确定第二个数组能得到的最大数组，然后把他俩合并成一个长度为k的数组。主要分成了三个辅助函数。一个是greater，用于比较两个数组组成的数字谁更大，需要找出第一个不同的位置，然后直接判断首个不同的数字谁大。而是maxArray，根据传入的数组和所需的长度，找出最大的一个结果，在外层循环中从第一位遍历到最后一位，在内层取数字时需要与上一位结果进行比较，如果结果还比现在这位数字还小，那把当前数字覆盖掉之前的数字结果就能尽可能大，因此需要回退一波，再继续判断（因此要用while而不能简单地if），当然也不能太贪心一直要取最大的，免得到最后剩下的数字还不够填进去的，因此需要用一个判断n - i + j > k来判断，i为循环变量表示已经从原数组中取到了多少位，j表示结果索引，n为原数组的数字个数，显然剩余数字加上已经取的数字应当大于k才能进行取舍，否则是没得挑的。写出来是这样的。
322. coin-change
- 给一个数组表示有哪些面值的硬币，然后给一个目标值，求最少用多少枚硬币能达到的这个目标值。
- ME：这个很明显的DP，所以我会做，写出来是这样。思路是从前往后更新DP数组，一开始全部初始化为-1表示不可达，dp[i]表示面值为i需要多少枚硬币，显然dp[0]应为0。对coin面值数组排序保证从小到大排列，然后开始从1更新。若
i - coin[j] >= 0说明可以从该状态加一枚coin[j]的硬币到达状态i，更新之，否则就可以直接跳出内层循环了，因为再往后看其他面值的coin只会负得更多。最后取dp[amount]即得。 - TA：我的是Bottom-up的DP，从无到有累积到目标值。还有一种Top-down的思路，利用递归来直接从目标值往回减。递归的结束条件有两种，一个是target减完成了负数，则不存在，返回0；若target恰好是0，那么直接返回0表示不需要额外添加硬币；还有就是如果在之前的结果中已经计算出了DP的值，直接返回即可。否则就逐个取出coin面值，然后用当前target减去这个面值递归到下一层去看需要多少枚硬币，该结果如果存在，则加一即为当前target所需的硬币数。需要尝试所有面值的硬币来找到最小值。模仿出来是这样。
323. number-of-connected-components-in-an-undirected-graph
- 给一个n和由0~n-1组成的边，求这些node和edge组成多少个独立的components。
方法一：并查集，指定每一组的祖先，最后再一波遍历看看有多少个root即可。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354class Solution {public int countComponents(int n, int[][] edges) {if (edges == null || edges.length == 0 || edges[0].length == 0) {return n;}int[] id = new int[n];Arrays.fill(id, -1);for (int i = 0; i < edges.length; i++) {int fromRoot = find(id, edges[i][0]);int toRoot = find(id, edges[i][1]);if (fromRoot != toRoot) {id[fromRoot] = toRoot;}}int ans = 0;for (int i = 0; i < n; i++) {if (id[i] == -1) {ans++;}}return ans;}private int find(int[] id, int p) {while (id[p] != -1) {if (id[id[p]] != -1) id[p] = id[id[p]];p = id[p];}return p;}}// 更标准的并查集：以每个index作为label判定是否是root，而不是-1；而且最后也不用一波统计了。public int countComponents(int n, int[][] edges) {int[] roots = new int[n];for(int i = 0; i < n; i++) roots[i] = i;for(int[] e : edges) {int root1 = find(roots, e[0]);int root2 = find(roots, e[1]);if(root1 != root2) {roots[root1] = root2; // unionn--;}}return n;}public int find(int[] roots, int id) {while(roots[id] != id) {roots[id] = roots[roots[id]]; // optional: path compressionid = roots[id];}return id;}方法二：先把图建起来，然后用BFS／DFS来count。
324. wiggle-sort-ii
325. maximum-size-subarray-sum-equals-k
- 给一个int数组和一个target sum k，求subarray whose sum等于k中的最长长度。
- 这种根据sum在数组中找xxx的问题，通常都用map。既然我是要通过sum找在数组中的位置，map中存的就是sum-index pair。如果当前累计的sum减去targetSum在map中出现过，说明该index到当前处这部分的和就是targetSum，更新一下maxLen即可。12345678910111213141516171819202122class Solution {public int maxSubArrayLen(int[] nums, int k) {if (nums == null || nums.length == 0) {return 0;}int sum = 0, maxLen = 0;// 记录从开头到当前index的sum// 需要sum -> index保证通过sum访问index是O(1)时间Map<Integer, Integer> sum2Index = new HashMap<>();for (int i = 0; i < nums.length; i++) {sum += nums[i];if (sum == k) {maxLen = i + 1;} else if (sum2Index.containsKey(sum - k)) { // 若有说明index~i这段的和就是kmaxLen = Math.max(maxLen, i - sum2Index.get(sum - k));}sum2Index.putIfAbsent(sum, i);}return maxLen;}}
326. power-of-three
- 给一个int，判断它是否3的幂。
- ME：前面231是判断是否2的幂，用while不断乘3判断，写出来是这样。但是题目问能不能不要用循环或递归，在之前的2的幂用的是bit的特点，n & (n - 1)这样搞的，这个我就不知所措了。。
- TA：没想到是这样的，直接用int范围内最大的一个3的幂模n，为0就说明n也是3的幂。
328. odd-even-linked-list
- 给一个链表，要求将奇数位置的节点挪到链表前半部分、偶数的节点放到后半部分。要求in-place且时间复杂度为O(N)。
- ME：从前往后遍历一波找到链表最后一个节点作为边界，然后再从头开始处理，把当前节点的后两个节点作为下一个节点，而原本的下一个节点直接丢到链表末尾拼接上去，一直处理直到碰到边界。写出来是这样。
- TA：额，你需要先遍历一波找末尾元素这个不太优雅，这个直接新建一个even一个odd然后逐步往后拼的方法更优雅。
329. longest-increasing-path-in-a-matrix
- 给一个矩阵，求从某一点开始沿上下左右的最长的完美升序路径的长度。
- ME：带memory的DFS咯，如果已经访问过该点就直接返回从该点出发的最长升序路径长度，否则就沿上下左右拓展，若大于等于该方向的数直接返回1，否则就返回DFS该方向的结果加1。写出来是这样。
- TA：思路差不多，别人的写得更优雅。
330. patching-array
- 给一个排好序的数组，给一个目标值n，要求通过数组中的这些数字任意组合之和能够覆盖[1, n]这个范围内（含边界的所有数字），若不满足则可以往里加数字，求最少加多少个数字能满足要求。
- ME：一开始想到Set的方法，将当前Set中的数字导入Queue之后，逐个取出并加上后续的数字，然后塞进Set中。然后从前往后遍历，如果Set的规模已经达到n就结束，否则找到第一个Set中缺乏的元素，然后加入进去，然后对应再更新Set即通过这个数字加上Set中原本的数字能够得到哪些新的数字。写出来是这样，但是如果n非常大就爆内存了。
- TA：又看了这个眼熟大神的方法才恍然大悟。假设给定范围是
[1, n]，假设缺的数字为miss，从1开始，从nums数组中取出数字nums[i]，若不大于miss，则[1, miss + nums[i] - 1]范围内都能取到了，下一个缺的数字就更新为miss + nums[i]；但如果nums[i]超过了miss，说明仅凭这些数字没有办法凑出miss，因此就补一个miss，因此可达范围就更新为[1, miss + miss - 1]，下一个缺乏的数字就变成了miss + miss。写出来是这样。
331. verify-preorder-serialization-of-a-binary-tree
- 给一个二叉树的前序遍历serialize的字符串，判断这个字符串能否还原出一棵二叉树（但不能真的去还原）。
- ME：用Stack搞定。将原字符串以逗号分隔，为数字则push(0)，为
#则对栈顶数字加一，若达到了2则弹出，并对前一个数字加一。在这个过程中如果栈已经弹空了而节点还没有遍历完成，说明数字有多，不合法。一直到最后如果栈恰好弹空，则完美。写出来是这样。 - TA：百事哥还是6。思路是，每一个节点分为两种边，一定有一个in边，若不是空节点则还有两个out边。初始化计数为diff，从第一个节点开始遍历，默认会因为in边减1，再根据
#决定是否加上两个out边。
332. reconstruct-itinerary
- 给一系列机票出发地/目的地的字符串数组，求一条字典序最小的路径能用遍这些机票。
- ME：一开始只想到如何取字典序最小，就是HashMap + PriorityQueue的组合，每次给定一个出发机场就能够拿到目的地中的最小者，但是没留意到可能最小的这条路是个死胡同，去了就回不来了、没法遍历全部目的地。没办法，只能老老实实地DFS。为了保证字典序最小，必须先对这些机场排个序再对应赋索引值，这样按顺序从左到右遍历目的地的时候一定是按照字典序从小到大遍历的，那先达到的答案就一定是字典序最小的了。我一开始提交还没有注意到机票可能有重复的，因此直接用了二维boolean作为邻接矩阵，最后改成这样才过了。
- TA：卧槽，没想到我一开始的想法确实是可以的，百事哥就是这么搞出来的。在DFS的时候，对于每个起始点都获取它能到达的目的地的PriorityQueue，按顺序取出来就是字典序最小的，poll出来后DFS它。当它所有的目的地都已遍历结束，就把当前的这个字符串addFirst到结果List中，表示是从我出发前往的。只能说，很强。
333. largest-bst-subtree
- 给一个二叉树跟节点，求其中能够形成BST的最大子树的size。
- 构建一个类保存当前子树的size、最小值和最大值，当size小于0就表示当前子树不是合法的BST。用一个全局变量维护最大的BST子树size。123456789101112131415161718192021222324252627282930313233343536373839class Solution {class Result {int size;int min;int max;public Result(int size, int min, int max) {this.size = size;this.min = min;this.max = max;}}public int largestBSTSubtree(TreeNode root) {traverse(root);return maxSize;}int maxSize = 0;private Result traverse(TreeNode root) {Result retVal = new Result(0, Integer.MAX_VALUE, Integer.MIN_VALUE);if (root != null) {Result leftResult = traverse(root.left);Result rightResult = traverse(root.right);if (leftResult.size < 0 || rightResult.size < 0 ||root.val <= leftResult.max || root.val >= rightResult.min) {retVal = new Result(-1, Integer.MAX_VALUE, Integer.MIN_VALUE);} else {// 最小值出现在左子树，最大值出现在右子树retVal = new Result(leftResult.size + rightResult.size + 1,Math.min(leftResult.min, root.val),Math.max(rightResult.max, root.val));}}maxSize = Math.max(retVal.size, maxSize);return retVal;}}
334. increasing-triplet-subsequence
- 给一个数组，判断它是否包含长度为3的升序子序列（可以不连续）。要求O(N)的时间复杂度，O(1)的空间。
- ME：一波流遍历。每次需要更新最小值min，若当前值大于min，说明这是一个长度为2的升序，接下来只需要找到比结尾数字更大的就是一个长度为3的升序了。但可能往后找的过程中会出现新的min，或者出现比min大同时又比结尾数字小的，都需要更新。写出来是这样。
- TA：别人写得更清晰简洁，只需要维护第一个元素small和第二个元素big即可。
335. self-crossing
- 给一个含有正整数的数组，表示从原点出发，依次沿上下左右走的长度，判断路径是否会交叉。
- ME：不会。。。
- TA：这题似乎没什么意思，就是找规律。比如这个。
336. palindrome-pairs
- 给一个字符串数组，求索引对的List使得word[i]和word[j]拼接而成的字符串自对称。
- ME：第一反应和前面的214. shortest-palindrome有点像，但那个是在前面拼接最短的字符串使之自对称，但这里不论长短、前后，能使它自对称就OK。然而不会啊。。。
- TA：我擦，没想到这样直接暴力破解也可以，写出来是这样。先一波流把每个字符串放到Map中形成字符串袄索引的映射，然后取每个字符串，用内层循环截成前后两个部分，判断是否对称，然后再适当反转后查找是否存在于Map中，对应添加即可。需要注意的是防止重复，可能需要根据长度判断取还是不取。不过其实这题考察的是Trie结构，所以不提倡前面的暴力法，得看这个。
- 方法一: 一个字符串能和另一个组成palidrome分三种情况，一是自身和对方长度长度相等且互为reverse；二是自身前半部分是pali，只需要后半部分能找到对应的reverse即可，将reverse拼在前方；三是自身的后半部分是pali，只需要前半部分找到对应reverse即可，reverse拼在后方。假设最长的字符串长度为k，时间复杂度为
O(k^2 * N)，其中的k^2消耗在找所有的prefix/suffix上。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566class Solution {public List<List<Integer>> palindromePairs(String[] words) {List<List<Integer>> retVal = new ArrayList<>();if (words == null || words.length == 0) {return retVal;}Map<String, Integer> word2Index = new HashMap<>();for (int i = 0; i < words.length; i++) {word2Index.put(words[i], i);}for (String word : words) {int currIndex = word2Index.get(word);// word + reverse的形式String rev = new StringBuilder(word).reverse().toString();if (!word.equals(rev) && word2Index.containsKey(rev)) {retVal.add(Arrays.asList(currIndex, word2Index.get(rev)));}// [prefix + pali] + prefixReverse的形式List<String> prefixes = getPrefixesBeforePali(word);for (String prefix : prefixes) {String prefixReverse = new StringBuilder(prefix).reverse().toString();if (word2Index.containsKey(prefixReverse)) {retVal.add(Arrays.asList(currIndex, word2Index.get(prefixReverse)));}}// suffixReverse + [pali + suffix]的形式List<String> suffixes = getSuffixesAfterPali(word);for (String suffix : suffixes) {String suffixReverse = new StringBuilder(suffix).reverse().toString();if (word2Index.containsKey(suffixReverse)) {retVal.add(Arrays.asList(word2Index.get(suffixReverse), currIndex));}}}return retVal;}private List<String> getPrefixesBeforePali(String word) {List<String> retVal = new ArrayList<>();for (int i = 0; i < word.length(); i++) {if (isValidPali(word, i, word.length() - 1)) {retVal.add(word.substring(0, i));}}return retVal;}private List<String> getSuffixesAfterPali(String word) {List<String> retVal = new ArrayList<>();for (int i = 0; i < word.length(); i++) {if (isValidPali(word, 0, i)) {retVal.add(word.substring(i + 1, word.length()));}}return retVal;}private boolean isValidPali(String str, int left, int right) {while (left < right) {if (str.charAt(left++) != str.charAt(right--)) {return false;}}return true;}}
337. house-robber-iii
- 给一个二叉树，每个节点表示所能抢到的钱财，强盗不能同时抢具有直接父子关系的两个节点。求最大收益。
- ME：偷看了这个写出了个最慢最low的无脑递归方法，写出来是这样。反正就是取当前节点加上后左节点的两个孩子和右节点的两个孩子（可能为空），然后与左右孩子递归结果之和做比较，取较大者。不过似乎有重复计算的节点，比较浪费时间，可以用
HashMap<TreeNode, Integer>记录下来，不过也不算特别快？ - TA：最后的那个方法是记录状态的，有点DP的意思，写出来是这样。利用一个辅助函数，返回数组int[2]，索引0表示不取当前节点的时候的最大收益、1则表示取，对应地就可以求左节点和右节点取和不取的值，对应加一下，最后返回取或不取root的最大值。
338. counting-bits
- 给一个正整数num，返回size为num + 1的数组，每个位置对应存放该索引的bit形式含有的1的数量。
- ME：最naive的方法，遍历一遍，每个都求一次1有多少个，写出来是这样。但是题目问能不能做到one-pass，不要每个都重新求。我就观察出了规律，把2的幂作为分界，后面都依赖于前面（减去这个幂）的结果，写出来是这样，不过速度好慢。。。
- TA：原来还可以这么简洁，规律是直接利用除2的索引和是否为奇数来求，写出来是这样.后来还看到了一个用了循环的方法，也是挺6。
339. nested-list-weight-sum
- 给一个nested的list，根据nested的深度赋予weight，深度深一层weight就加1，求weighted sum。
- 递归解决。1234567891011121314151617181920212223242526272829303132333435363738394041424344454647/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* public interface NestedInteger {* // Constructor initializes an empty nested list.* public NestedInteger();** // Constructor initializes a single integer.* public NestedInteger(int value);** // @return true if this NestedInteger holds a single integer, rather than a nested list.* public boolean isInteger();** // @return the single integer that this NestedInteger holds, if it holds a single integer* // Return null if this NestedInteger holds a nested list* public Integer getInteger();** // Set this NestedInteger to hold a single integer.* public void setInteger(int value);** // Set this NestedInteger to hold a nested list and adds a nested integer to it.* public void add(NestedInteger ni);** // @return the nested list that this NestedInteger holds, if it holds a nested list* // Return null if this NestedInteger holds a single integer* public List<NestedInteger> getList();* }*/class Solution {public int depthSum(List<NestedInteger> nestedList) {if (nestedList == null || nestedList.size() == 0) {return 0;}return getSum(nestedList, 1);}private int getSum(List<NestedInteger> nestedList, int level) {int sum = 0;for (NestedInteger i : nestedList) {if (i.isInteger()) {sum += level * i.getInteger();} else {sum += getSum(i.getList(), level + 1);}}return sum;}}
341. flatten-nested-list-iterator
- 设计题，一个NestedInteger类List的遍历，即List中元素可能为List也可能为Integer，转化成纯Integer的List。
- ME：递归把数字都存起来呗，写出来是这样。
- TA：这个告诉你还可以用Stack改写成Iterative的，写出来是这样。
342. power-of-four
- 给一个int，判断它是否4的幂。
- ME：这题都不想自己写循环/递归的了，但还是想不出一行的解法。
- TA：没想到就只是比2的幂多了一步判断而已，比如这个是利用num - 1一定是3的倍数来搞的，另外就是利用
0x55555555来确认bit中的1是否出现在奇数位。
343. integer-break
- 给一个正整数，将它拆分成至少两个正整数之和，使得这些小正整数之积最大，求这个积。
- ME：用了DP，近似于O(N^2)的复杂度，写出来是这样。
- TA：没想到还能这样直接找规律，所有这些小整数，只要尽可能多一些3就能使积最大了。
344. reverse-string
- 反转字符串。
- ME：没啥，就这样
- TA：没啥。
345. reverse-vowels-of-a-string
- 反转字符串中的元音字母。
- ME：用个set放元音字母，然后一前一后俩指针对换呗，写出来是这样。
- TA：没啥。
- Set的初始化方法：
Set<Character> vowels = new HashSet<>(Arrays.asList(new Character[]{'a','e','i','o','u','A','E','I','O','U'}));，而不用一个个add。
346. moving-average-from-data-stream
- 求moving average。其实就是维护一个sum，初一下就好了。skip.
347. top-k-frequent-elements
- 给一个乱序的int数组，给一个k，求这个数组中出现频数前k高的数，要求时间复杂度优于O( N*logN )。
- ME：其实不是自己做出来的，看了这个O(N)木桶法，真的叼，写出来是这样。先扫一遍统计各个数值与对应的频数，构建map映射；然后就是木桶排序了，这里的木桶索引的意义是『频数』，存放的是该频数对应的所有数值的List，也就是从map的keySet()遍历各个key的value，根据这个value确定索引，然后把key给add到木桶对应索引的List中。最后再木桶末尾往前取k个即可。
- TA：木桶法确实不太好想具体的索引意义，但是用普通的堆你应该是能想到才对，就像这个，priorityQueue或者TreeMap都可以啊。PriorityQueue需要根据map的value从大到小排序，才能保证队首拿的是频数最高的，而TreeMap可以任意从头从尾取，所以默认的话就是从小到大，从尾取即可。
- Map遍历用keySet()获得key的集合，再for-each逐个取吧。Map在put的时候可以用
getOrDefault(key, defalutValue)来省去判断containsKey的单独的if。
348. design-tic-tac-toe
- XXOO游戏，两个玩家，每一行、每一列、两条对角线都是一样的话，对应玩家就赢了。要设计一个class，其中包含move函数，给坐标和玩家编号，在图里放，如果该玩家赢了就返回玩家编号。每行、每列需要统计两个玩家各自的个数，如果都是其中一个玩家都就赢了，两条对角线也是。
- 记录行、列、两条对较线。区分两个玩家的O和X就通过正负一来判断，这样如果有一个玩家赢了就意味着一路相加结果是n或者-n1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162class TicTacToe {private int[] rows;private int[] cols;private int diag1, diag2;private int n;/** Initialize your data structure here. */public TicTacToe(int n) {rows = new int [n];cols = new int [n];diag1 = 0;diag2 = 0;this.n = n;}/** Player {player} makes a move at ({row}, {col}).@param row The row of the board.@param col The column of the board.@param player The player, can be either 1 or 2.@return The current winning condition, can be either:0: No one wins.1: Player 1 wins.2: Player 2 wins. */public int move(int row, int col, int player) {if (row < 0 || row >= n || col < 0 || row >= n || player < 1 || player > 2) {return 0;}int addVal = player == 1? -1: 1;// for diag1if (row == col) {diag1 += addVal;if (isConnect(diag1)) {return player;}}// for diag2if (row + col == n - 1) {diag2 += addVal;if (isConnect(diag2)) {return player;}}// for rowrows[row] += addVal;if (isConnect(rows[row])) {return player;}// for colcols[col] += addVal;if (isConnect(cols[col])) {return player;}return 0;}private boolean isConnect(int val) {return val / n != 0;}}
349. intersection-of-two-arrays
- 给两个数组，求其中重复的项（交集），重复出现的只算一个。
- ME：用hashSet搞定。
- TA：其实有三种方法，后两种都是需要排序之后再操作。一个是排序后用俩指针挪动判断，一个是排序后用二分查找在第一个数组中搜索第二个数组的每个数字。
350. intersection-of-two-arrays-ii
- 给两个数组，求其中重复的项，只要重复就放进数组，不用管重不重复。
- ME：hashmap统计一波各个数字出现的频数，然后从第二个数字取数字，匹配到就放到List中并将map中的频数减1.写出来是这样。
- TA：题目有follow-up问题，如果排好序可以直接分别遍历两个数组去判断；如果数组规模太大无法一次性加载到内存中，这里有个办法就是external sort，然后每次只需要读进来两个数字就好了。
352. data-stream-as-disjoint-intervals
- 自定义了类Interval，给一个数组作为data stream，要求把它转化成Interval的List。
- ME：直觉就是二分查找，但是。。。木有自己写出来。
- TA：TreeMap来处理Interval边界问题。TreeMap的key是每个interval的起始点，新来的一个val可以在treeMap中找到小于它、大于它的key。分情况讨论，val可能可以恰好把前后两个interval连起来、可能落在前面的区间内/区间后方一位、可能落在后面的区间的前方一位（不可能在区间内，否则lowerKey就是后面这个区间了）、也可能就是独立的一个val。TreeMap的
lowerKey,higherKey,put,remove都是O(logN)的。123456789101112131415161718192021222324252627282930class SummaryRanges {private TreeMap<Integer, Interval> treeMap;/** Initialize your data structure here. */public SummaryRanges() {treeMap = new TreeMap<>();}public void addNum(int val) {if (treeMap.containsKey(val)) {return;}Integer lower = treeMap.lowerKey(val);Integer higher = treeMap.higherKey(val);if (lower != null && higher != null && treeMap.get(lower).end + 1 == val && val + 1 == higher) {treeMap.get(lower).end = treeMap.get(higher).end; // merge前后两段treeMap.remove(higher);} else if (lower != null && treeMap.get(lower).end + 1 >= val) {treeMap.get(lower).end = Math.max(treeMap.get(lower).end, val);} else if (higher != null && val + 1 == higher) {treeMap.put(val, new Interval(val, treeMap.get(higher).end));treeMap.remove(higher);} else {treeMap.put(val, new Interval(val, val));}}public List<Interval> getIntervals() {return new ArrayList<>(treeMap.values());}}
353. design-snake-game
- 模拟贪吃蛇游戏，给两个int表示grid大小，给一个food数组表示每次吃完食物之后下一个食物出现的坐标，保证不会出现在贪吃蛇的路径上。每次调用一次move函数，给定移动方向，返回移动之后的分数，若挂了就返回-1.
- 移动本身不难，难点一是如何维护蛇本身，由于需要在头部增加点、在尾部删除点（若吃到食物则尾部不删除），需要从两头操作，因此想到Deque；二是如何判断蛇有没有hit到自身，通过重写equal和hash函数就可以将自定义的Point类丢进Set中。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182class SnakeGame {class Point {int row, col;public Point(int row, int col) {this.row = row;this.col = col;}public boolean equals(Object o) {if (o instanceof Point) {Point that = (Point) o;return this.row == that.row && this.col == that.col;} else {return false;}}public int hashCode() {return Objects.hash(row, col);}}int rowTotal, colTotal, score;Deque<Point> snake;Set<Point> body;int[][] food;/** Initialize your data structure here.@param width - screen width@param height - screen height@param food - A list of food positionsE.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */public SnakeGame(int width, int height, int[][] food) {this.rowTotal = height;this.colTotal = width;this.food = food;this.score = 0;this.snake = new LinkedList<>();this.body = new HashSet<>();snake.addFirst(new Point(0, 0));body.add(snake.peekFirst());}/** Moves the snake.@param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down@return The game's score after the move. Return -1 if game over.Game over when snake crosses the screen boundary or bites its body. */public int move(String direction) {Point head = snake.peekFirst();Point nextHead = null;if (direction.equals("U")) {nextHead = new Point(head.row - 1, head.col);} else if (direction.equals("D")) {nextHead = new Point(head.row + 1, head.col);} else if (direction.equals("L")) {nextHead = new Point(head.row, head.col - 1);} else if (direction.equals("R")) {nextHead = new Point(head.row, head.col + 1);}// System.out.println(nextHead.row + ", " + nextHead.col + " " + checkOutBound(nextHead) + " " + hitSelf(nextHead));if (nextHead == null || checkOutBound(nextHead) || hitSelf(nextHead)) {return -1;}if (score < food.length && nextHead.row == food[score][0] && nextHead.col == food[score][1]) {score++;} else {Point tail = snake.pollLast();body.remove(tail);}snake.addFirst(nextHead);body.add(nextHead);return score;}private boolean checkOutBound(Point p) {return p.row < 0 || p.row >= rowTotal || p.col < 0 || p.col >= colTotal;}private boolean hitSelf(Point p) {return !p.equals(snake.peekLast()) && body.contains(p);}}
354. russian-doll-envelopes
- 给一个数组，存放的是各个信封的规格，要让信封能套进去必须长和宽都小于外面的信封，求最多可以有多少个信封套在一起。
- ME：搞了半天没搞出来，各种WA。
- TA：这个利用Arrays.binarySearch的方法真的给力。Arrays.binarySearch方法的定义可以看这里 )，有一个很叼的地方是这个二分查找在搜索不到key的情况下会返回
- 插入索引 - 1，这样就可以直接知道往哪里插入了。算法总思路是，先根据信封的[0]从小到大排序，[0]相等的情况下[1]大的排在前面。然后遍历原数组，根据[1]去二分查找DP数组，找不到就更正index为最小的大于目标值的索引，然后直接覆盖或插入，最后返回DP的有效长度即可。写出来是这样。还有一个完全暴力的方法，我一开始就打算这么搞的不过没有注意到更新的时候需要Math.max一下，正解写出来是这样。还有个大神提出信封在现实中肯定可以旋转之后塞进去，挺有意思。 - Arrays.sort自定义排序参考了这个，传入第二个参数
(a, b) -> { if return xxx }。1234567891011121314151617181920212223242526272829303132333435363738394041class Solution {public int maxEnvelopes(int[][] envelopes) {if (envelopes == null || envelopes.length == 0) {return 0;}// 先按照宽度升序排序，然后按照高度降序排序Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);int[] heights = new int[envelopes.length];for (int i = 0; i < envelopes.length; i++) {heights[i] = envelopes[i][1];}// 在宽度是升序的情况下，只要保证高度升序即可嵌套return getLenOfLongestIncreasingSequence(heights);}// https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-she-ji-zui-chang-di-zeng-zi-xu-lieprivate int getLenOfLongestIncreasingSequence(int[] nums) { // O(NlogN)int piles = 0;int[] tops = new int[nums.length];for (int num : nums) {int index = binarySearchInsertion(tops, piles, num);tops[index] = num;if (index == piles) {piles++;}}return piles;}private int binarySearchInsertion(int[] nums, int len, int target) {int left = 0, right = len;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid;} else {left = mid + 1;}}return left;}}
355. design-twitter
- 设计题，模拟twitter的发推、关注、取关操作，以及对于给定用户返回最近10条应当显示的推文id。
- ME：用Map存储用户id和关注的其他用户的Set，然后自定义一个推文类，用个List存总的timeline，没有删除推文省事很多。写出来是这样。
- TA：好吧，每次我调取给定用户应显示的最近十条推文的方法很低效，因为是直接遍历总的timeline然后判断是否是当前用户关注的对象。这里有个看起来很6的设计。它给每个Tweet设置一个时间戳，这样就可以判断谁先谁后了。然后每个用户发送Tweet的时候放在该用户对象的Tweet的链表的头部。在取feed的时候就将每个用户follow的用户的Tweet链表头放到PriorityQueue中（排序规则是时间戳大的在前），然后往外取的时候同时把Tweet的next再插入PriorityQueue，这样就可以保持时间戳大的、且是follow用户发的推文先被取出。
356. line-reflection
- 给一系列在二维坐标系中点的坐标（可能重复），判断是否存在一条垂直线，使所有点的分布关于它对称。
- 这种两两匹配的问题，最直观的办法就是用set找pair中的另一半，第一次遍历将点存入set并且找出横轴的最大最小值以求出对称轴位置，第二次遍历就从set中逐对判断了。一开始想到的是排序之后双指针一前一后夹逼判断，但这样时间复杂度高，而且排序规则本身也十分tricky。12345678910111213141516171819202122class Solution {public boolean isReflected(int[][] points) {if (points == null || points.length == 0) {return false;}int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;Set<String> set = new HashSet<>();for (int[] point : points) {min = Math.min(min, point[0]);max = Math.max(max, point[0]);set.add(point[0] + "," + point[1]);}int sum = min + max;for (int [] point : points) {if (!set.contains((sum - point[0]) + "," + point[1])) {return false;}}return true;}}
357. count-numbers-with-unique-digits
- 给一个非负整数n，求在
[0, 10^n)范围内有多少个数的各位数字各不相同。 - ME：一开始总想着怎么减出结果，后来还是偷看了discuss。。。
- TA：这个告诉你，直接用排列组合的思路不就好了嘛！第一位是1~9九个数字，第二位就是0~9减去第一位用掉的数字还剩九个数字，第三位是八个数字，以此类推。写出来是这样。当然还有用回溯法的，用一个used表示是否用了索引对应的数字。
358. rearrange-string-k-distance-apart
- 给一个只含有小写字母的字符串，再给一个长度k，求其中相同字符串每隔k个才出现的版本。例如
s = "aabbcc", k = 3，整理后就是abcabc. - greedy可破。先统计每个字母的出现频数，然后塞入PriorityQueue每次取（consume）频数最高的拼接上去，同时将用掉的这个字符暂存到另一个waitQueue中，之后当用足了长度k，再从waitQueue中取（produce）放回pq。12345678910111213141516171819202122232425262728293031323334353637383940class Solution {public String rearrangeString(String s, int k) {if (s == null || s.length() == 0) {return "";}if (k == 0) {return s;}Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (!map.containsKey(c)) {map.put(c, 1);} else {map.put(c, map.get(c) + 1);}}PriorityQueue<Map.Entry<Character, Integer>> q = new PriorityQueue<>((a, b) -> {return b.getValue() != a.getValue()? b.getValue() - a.getValue() : a.getKey() - b.getKey();});q.addAll(map.entrySet());Queue<Map.Entry<Character, Integer>> waitQueue = new LinkedList<>();StringBuilder sb = new StringBuilder();while (!q.isEmpty()) {Map.Entry<Character, Integer> entry = q.poll();sb.append(entry.getKey());entry.setValue(entry.getValue() - 1);waitQueue.offer(entry);if (waitQueue.size() < k) {continue;}Map.Entry<Character, Integer> next = waitQueue.poll();if (next.getValue() > 0) {q.add(next);}}return sb.length() == s.length()? sb.toString() : "";}}
359. logger-rate-limiter
- 给一个string和timestamp，判断是否输出， 输出的条件是在10秒内没有输出过。skip。
360. sort-transformed-array
- 给一个sorted的int数组，给a, b, c并对数组每个元素求
a*x^2 + b*x + c，返回排好序的结果，要求时间复杂度O(N)。 - 如果是二次函数就是个轴对称问题，一开始实现的时候也是按照这个思路先用二分查找来到中间，然后双指针往外扩张，分了很多种情况讨论。但其实更简单的方法是从两边往中间夹逼，而且只需要讨论a是否大于0即可，不需要再针对b有什么操作。1234567891011121314151617181920212223242526272829303132333435class Solution {public int[] sortTransformedArray(int[] nums, int a, int b, int c) {if (nums == null || nums.length == 0) {return new int[0];}int n = nums.length, left = 0, right = n - 1;int[] ans = new int[n];int index = a >= 0 ? n - 1 : 0;while (left <= right) {int leftVal = calculate(nums[left], a, b, c);int rightVal = calculate(nums[right], a, b, c);if (a >= 0) {if (leftVal >= rightVal) {ans[index--] = leftVal;left++;} else {ans[index--] = rightVal;right--;}} else {if (leftVal <= rightVal) {ans[index++] = leftVal;left++;} else {ans[index++] = rightVal;right--;}}}return ans;}private int calculate(int x, int a, int b, int c) {return a * x * x + b * x + c;}}
362. design-hit-counter
- 实现一个hitCount类，通过hit(timestamp)表示在什么时候出现了hit（可能同一时刻有多次hit），然后通过getHits得到最近300s内hit了多少次。
- 利用循环数组记录hits即可，容量可以直接设为300，这样最多就可以同时记录300s中每一秒的hit数量，在getHis的时候直接遍历一边如何保证每个bucket都是valid的count呢，就需要记录每一个bucket对应的hit的时刻是几时，因此需要另一个time数组来记录。12345678910111213141516171819202122232425262728293031323334class HitCounter {private int[] hits;private int[] time;final private int TIMEWINDOW = 300;/** Initialize your data structure here. */public HitCounter() {hits = new int [TIMEWINDOW];time = new int [TIMEWINDOW];}/** Record a hit.@param timestamp - The current timestamp (in seconds granularity). */public void hit(int timestamp) {int index = timestamp % TIMEWINDOW;if (time[index] != timestamp) {time[index] = timestamp;hits[index] = 1;} else {hits[index]++;}}/** Return the number of hits in the past 5 minutes.@param timestamp - The current timestamp (in seconds granularity). */public int getHits(int timestamp) {int count = 0;for (int i = 0; i < TIMEWINDOW; i++) {if (timestamp - time[i] < TIMEWINDOW) {count += hits[i];}}return count;}}
363. max-sum-of-rectangle-no-larger-than-k
- 给一个二维int数组，给一个目标值k，求这个矩阵中的子矩阵各项之和不超过k的最大值。
- ME：偷看了这个才写出了这个O(N^4)的纯暴力法。先求从左上角到各个位置的和，然后四重循环固定一个位置往右下角遍历求子矩阵之和，取最接近k的值即可。
- TA：刚刚这个答案还给出了更高效的办法，利用了TreeSet。同样是先获取左上角到各格的和，然后固定行r1，让r2从r1开始往下遍历各行，在每个r2再遍历每一列c，求出
curr = sum[r2][c] - sum[r1 - 1][c]并存入TreeSet。然后最妙的地方出现了，根据curr - k到TreeSet中找『最小的不小于这个值的值』，如果这个值x存在，那么curr - x就是『最大的不大于k的值』，再和ans取个较大值即可。这是因为curr - k <= x，所以curr - x <= k。写出来是这样，妙哉啊妙哉但是为啥反而更慢了？大概是因为用了个更高级的数据结构TreeSet吧。follow-up还有个问题，如果行数比列数多得多怎么破？这个和刚刚的第二个TreeSet方法差不多，有一点点小区别是在第二重循环那里是从r1开始往0递减的，没啥区别其实。但是他在最开始根据行数和列数做了个类似于转置的操作，保证行数能大于列数，在后续的操作中就直接当作行大于列的矩阵操作了。
364. nested-list-weight-sum-ii
- 和339题目背景类似，只不过这里是反过来，层数约深weight越小，因此在最外层的要根据最深的层数确定weight.
既然需要求最深的深度，就先走一波求最深深度，然后最外层就乘这个weight，然后逐层叠加。
12345678910111213141516171819202122232425262728293031class Solution {public int depthSumInverse(List<NestedInteger> nestedList) {if (nestedList == null || nestedList.size() == 0) {return 0;}int depth = getDepth(nestedList);return getSum(nestedList, depth);}private int getDepth(List<NestedInteger> nestedList) {int maxDepth = 0;for (NestedInteger i : nestedList) {if (i.isInteger()) {maxDepth = Math.max(maxDepth, 1);} else {maxDepth = Math.max(getDepth(i.getList()) + 1, maxDepth);}}return maxDepth;}private int getSum(List<NestedInteger> nestedList, int depth) {int sum = 0;for (NestedInteger i : nestedList) {if (i.isInteger()) {sum += i.getInteger() * depth;} else {sum += getSum(i.getList(), depth - 1);}}return sum;}}这个weight其实就相当于加多少遍，因此在进入nested下一层的时候，把上一层的sum传进去重复叠加，即可达到weight的效果了。
1234567891011121314151617181920class Solution {public int depthSumInverse(List<NestedInteger> nestedList) {if (nestedList == null || nestedList.size() == 0) {return 0;}return getSum(nestedList, 0);}private int getSum(List<NestedInteger> nestedList, int prevLevelSum) {int sum = prevLevelSum; // 在当前level重复叠加List<NestedInteger> nextLevel = new ArrayList<>();for (NestedInteger i : nestedList) {if (i.isInteger()) {sum += i.getInteger();} else {nextLevel.addAll(i.getList());}}return nextLevel.size() == 0 ? sum : sum + getSum(nextLevel, sum);}}
365. water-and-jug-problem
- 给两个整数表示两个水樽的容量，再给一个目标值，判断仅用这两个水樽，通过加满水、清空水、倒到另一个水樽这三个操作能否获得目标值。
- ME：一开始想到用带状态记录的DFS，写出来是这样，但是爆内存了。即便我改成用
Map<Integer, Set<Integer>>的形式也还是爆。。 - TA：这儿有个超时的BFS方法估计和你的思路差不多，不过它报的错是超时，而不是爆内存。正解是用纯数学方法Bezout’s Identity利用最大公约数，比如这个解答，没啥意思。。。
- 最大公约数的求法要会！12345678int getGCD(int a, int b) {while (b > 0) {int temp = b;b = a % b;a = temp;}return a;}
366. find-leaves-of-binary-tree
- 给一个二叉树，求一层层仰视时所能看到的节点，看完后删除这些节点后继续仰视下一层。注意不是层级遍历！
- 其实就是利用高度的定义，对于每个节点对应地放到它所属的高度的位置即可。123456789101112131415161718class Solution {public List<List<Integer>> findLeaves(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();height(root, ans);return ans;}private int height(TreeNode node, List<List<Integer>> ans) {if (node == null) {return -1; // 保证叶子节点高度为0}int h = 1 + Math.max(height(node.left, ans), height(node.right, ans)); // 当前节点的高度 = 左右较大者 + 1if (ans.size() == h) { // 叶子结点高度为0，索引也为0ans.add(new ArrayList<>());}ans.get(h).add(node.val);return h;}}
367. valid-perfect-square
- 给一个int，判断它是否平方数。
- ME：二分查找破之，写出来是这样。
- TA：这个的第一个解法很有意思，直接用
1 + 3 + 5 + 7 + 9...是平方数的特性，逐渐减得结果。此外还有个牛顿法判断平方数，利用公式curr = (curr + (num / curr)) / 2不断更新，最后就根据curr * curr == num来判断是否平方数。这个。。。如果不知道根本不懂呀。
368. largest-divisible-subset
- 给一个int数组，元素各不相同，求最大的子序列使得其中的元素两两之间
x % y == 0或y % x == 0. - ME：一开始想的是DFS，先从小到大排个序，然后从前往后看到能模的就深入DFS，写出来是这样。然而超时。。。
- TA：没想到给的tag是DP。参考了这个，一下就懂了，dp[i]的意义是『到i为止的最长能整除子序列的长度』。一开始也是先排序，然后先从前往后走一波二重循环，求到每个索引处的满足要求的最长长度，同时找到储存最长长度的那个索引。接着重开一波循环，从最长长度的这个索引开始往前，若可以整除且对应的dp能对得上号，就加入List（不必在意顺序）。写出来是这样。
369. plus-one-linked-list
- 给一个用链表存储的int，返回将它加1之后的链表。递归解决。skip.
370. range-addition
- 给一系列
[startIndex, endIndex, value]的组成的二维数组，给一个length表示一个长度为length、初始值为0的数组，求经过这一系列操作之后的结果。例如length = 5, updates = [[1, 3, 2],[2, 4, 3],[0, 2, -2]]，返回[-2, 0, 3, 5, 3]。 - tricky的做法，用数组本身来标记从当前索引开始应该加什么value。因为[i, j]加value相当于[i, ~]加value同时[j + 1, ~]减value，因此直接在i处标记一个value，在结尾处j标记一个-value即可。注意这里都不能直接赋值，而是需要累加之前的结果。时间复杂度O(K + N).12345678910111213141516171819202122232425class Solution {// [i, j]加value相当于[i, ~]加value同时[j + 1, ~]减value// 因此直接在i处标记一个value，在结尾处j标记一个-value即可// 最后一波遍历的时候，直接用一个值delta加这些value，直接把delta赋值到对应位置即可public int[] getModifiedArray(int length, int[][] updates) {int[] ans = new int [length];if (updates == null || updates.length == 0) {return ans;}for (int[] update : updates) {ans[update[0]] += update[2]; // 标记i为valueif (update[1] + 1 < length) { // 标记j + 1为-valueans[update[1] + 1] -= update[2];}}int delta = 0;for (int i = 0; i < length; i++) {delta += ans[i];ans[i] = delta;}return ans;}}
371. sum-of-two-integers
- 不能使用加、减运算符，实现加法运算。
- ME：想到了位操作，但一开始这个只适用于正数，负数就WA了。负数的二进制表示是『除了符号位，所有位取反再加1』，位操作还是挺复杂的。。。
- TA：看了这个逆天的位操作总结，真的妙哉啊！回顾一下：
求给定数n的二进制表示中的bit为1的个数，不断更新n为
n & (n - 1)直到n等于0，所得的计数即是。12345678int countOne(int n) {int count = 0;while (n > 0) {n = n & (n - 1);count++;}return count;}判断是否4的幂：跟2的幂判断相比，多了一步判断那个1bit是否在奇数位置上，即AND 0x55555555不为0.
123boolean isPowerOfFour(int n) {return (n & (n - 1)) == 0 && (n & 0x55555555) != 0;}求两个整数的和：利用了异或操作『保留不同的bit、置0相同的bit』，在bit的加法中，不同的bit相加一定是1，而相同的bit如果都是0就没事，如果都是1，则需要在左侧产生进位，因此为了获得这个进位还需要对两个数AND一下获得『同为1』的bit，然后左移1形成进位。递归直到进位为0，加法完全结束。
123int getSum(int a, int b) {return b == 0? a: getSum((a ^ b), (a & b) << 1);}对于乱序的规模为n的数组，从0~n中选n个数任意放进去，求缺少的那个数：利用索引和元素的对应关系，持续异或，最后没有异或成0的即为结果。
12345678int missingNumber(int[] nums) {int ans = 0, n = nums.length;for (int i = 0; i < n; i++) {ans ^= i;ans ^= nums[i];}return (ans ^ n);}求不超过数n的最大的2的幂：利用了取或操作『保留尽可能多的1』，将n的最高位及其右边的位全部置为1，然后加1就来到了最高位的左边，再右移1即得。
123456int largestNumber(int n) {for (int i = 1; i <= 16; i <<= 1) {n = n | (n >> i);}return (n + 1) >> 1;}前后反转一个32bit无符号数的bit：从原数的最低位开始取bit，如果是1就对应或个Mask到ans中，其中mask持续右移，n也持续右移，这样每次都取最低位事实上就是从最低到最高取n的各个bit。
1234567891011int reverseBits(int n) {int mask = 1 << 31, ans = 0;for (int i = 0; i < 32; i++) {if (n & 1 != 0) {ans |= mask;}mask >>= 1;n >>= 1;}return ans;}给一个范围[lo, hi]，求这个范围内所有数的AND的值：其实就是找lo和hi的最长高位相同部分，lo和hi同时向右移，右移的次数用一个count记录下来，直到lo == hi时跳出循环，此时lo或hi左移count位即为所求。
123456789int rangeAND(int lo, int hi) {int count = 0;while (lo != hi) {lo >>= 1;hi >>= 1;count++;}return lo << count;}
372. super-pow
- 给一个整数a表示底数，给一个数组形式的超大整数b表示幂，求(a ^ b) % 1337的值。
利用
num ^ 1,2,3,4 = (num ^ 1,2,3) ^ 10 * a ^ 4，也就是按照个十百千万来拆分大数，再利用递归解决括号中间的部分。1234567891011121314151617181920212223242526class Solution {private final int MOD = 1337;public int superPow(int a, int[] b) {return superPow(a, b, b.length - 1);}private int superPow(int a, int[] b, int index) {if (index < 0) {return 1;}int part1 = getPow(a, b[index]);int part2 = getPow(superPow(a, b, index - 1), 10);return (part1 * part2) % MOD;}private int getPow(int a, int k) {if (a == 1 || k == 0) {return 1;}a %= MOD;int retVal = 1;for (int i = 0; i < k; i++) {retVal *= a;retVal %= MOD;}return retVal;}}优化：这里的getPow可以利用以下公式加速：
!img12345678910111213private int getPow(int a, int k) {if (a == 1 || k == 0) {return 1;}a %= MOD;// 偶数砍半if (k % 2 == 0) {int half = getPow(a, k / 2);return (half * half) % MOD;} else {return (a * getPow(a, k - 1)) % MOD;}}
373. find-k-pairs-with-smallest-sums
- 给两个排好序的递增int数组，要求从两个数组中分别取一个元素出来组成的数对之和小者排在前面，求前k个这样的组合。
- ME：一开始又想得太简单，结果并不是用两个索引就可以搞定的。。。
- TA：看了这个，直接把数组对象存入优先队列，数对和小的排在前面，同时数组末尾再增添一个索引，表示当前数组第二个数对应到第二个原数组中的索引，这样就可以把后续的继续添加到优先队列中了。写出来是这样。其实挺简单的。。。
- 数组的初始化可以不用指定规模，而且后面跟的花括号中的元素可以不是const，例如
new int[] {i, j, 0}。
374. guess-number-higher-or-lower
- 给一个整数n表示在[1, n]内找一个未知数字，通过调用guess(num)的返回值来判定当前猜的数大了还是小了，返回最终猜中的结果。
- ME：没啥好说的，二分查找搞定。
- TA：没啥。
375. guess-number-higher-or-lower-ii
- 还是给一个整数n，但是这次猜错了就要交对应数目的罚款，求保证猜对的情况下至少要准备多少罚款。
- ME：一开始还以为是二分查找，后来发现是个夹逼猜测的策略更有效，但是不懂怎么推广，找不到可以转换成代码的规律呀。。。
- TA：这他喵的就是个带有状态记录的DFS嘛，你应该能写出来才对。第一个递归的方法思路是从起始位置遍历到结束位置，在循环过程中确定当前取的数字加入罚款，然后递归求左半边和右半边的罚款，然后求总和，再用一个变量记录当前这一层调用的最小罚款值，循环结束后就将最小罚款值更新到状态记录的二维数组中，这个二维数组其实只用到了右上部分，因为table[i][j]表示从i到j所需要的最少罚款，而i必须小于j。写出来是这样。第二个就是递归的方法，需要三重循环，第一重循环j=[2, j]，表示结束的位置，即状态记录数组当前已更新到的列数；接下来一重递减循环i=[j-1, 1]表示起始位置；最内层循环k=[i+1, j)就是中界了，中界本身的罚款加上左、右两侧的最小罚款就是当前位置的最小罚款了。
376. wiggle-subsequence
- 给一个int数组，求最长的wiggle子序列，即子序列中的元素一大一小震锯齿形地往后。
- ME：直接一个for循环搞定了，写出来是这样。
- TA：我的方法算是贪心吧，看这里有个总结，不过他的贪心写得更优雅。
377. combination-sum-iv
- 给一个不含重复元素的正整数数组，再给一个target，求有多少中组合方式（元素可重复使用）凑成target。
- ME：DFS呗，先从小到大排个序，for循环逐个取出来，然后用target减之得到新的target，再递归去求，当刚好新的target为0的时候，就表示这是一种方式，返回1即可；而在循环过程中减出来的新的target小于0，就直接结束循环了，因为排过序之后后续的元素肯定更大，减出来更负。不过一开始没有设置状态记录数组，导致DFS计算了很多重复的情况，引入cache[target]表示目标为target的时候对应的组合数目，若一波循环之后还是0，则设置为负数，表示当前的target访问过且无法组合出来。写出来是这样。
- TA：我这个也能算作是DP了吧。不过这个写得更加优雅，因为他是一开始直接将状态数组全部置为-1，而访问的时候则是从0开始递归累加，省去了很多判断。事实上这是个top-down的思路，还有一个bottom-up的思路，也就是二重循环从前往后更新。写出来是这样。
378. kth-smallest-element-in-a-sorted-matrix
- 求排好序的二维数组中从小到大排在第k个的元素。这里的排好序意思是同一行从左到右递增、同一列从上到下递增。
- ME：一开始理解成了从左到右递增同时下一行的比上一行的都大，还觉得这题怎么这么无脑。。结果还是太天真。。。
- TA：看了这个才知道要怎么做。第一个是使用最没技术含量的方式，自定义Item类，先将第一行元素全部入优先队列，然后每次取队首即最小元素出来，取它的下方和右方元素入队，为了防止重复入队，我还申请了二维的boolean数组标记，不过按照原po的做法，他只取出队元素的下方元素，就不用考虑重复的问题了。写出来是这样。第二种方法是二分查找，答主总结得很好，二分有两种二分的对象，一个是索引一个是值。这里不能用索引是因为这是两个方向的顺序，没办法形成索引大小关系和实际值之间的一一映射，因此直接对值进行二分，以左上角元素为下界、右下角元素为上界开始查找。不过相比一般的二分查找，在内部还需要两波循环。外层循环从第一行开始向下，内层循环则从最后一列开始向前，要做的是查找共有多少元素小于等于mid值（内层循环条件就是当前元素大于mid值），而由于同一列的元素是从上到下递增的，因此当前元素如果大于mid，则下面的全部都大于mid，直接将内层循环变量向前挪就行了。计算出小于等于mid的元素数目后，与k比较。如果
count < k，说明mid还太小，需要提升下界；否则说明mid略大，就需要降低上界。注意不能在count == k的时候就返回mid了，因为这个mid是由lo和hi计算出来的，并不一定存在于原矩阵当中。最后当lo不小于hi时结束查找，返回lo。写出来是这样。
379. design-phone-directory
- 实现get, check, release函数，分别对应申请一个号码、查询给定号码是否已分配、释放一个号码。
- 用数组记录是否被占用、用Queue返回可用号码。一开始用Set，其实没必要，因为对号码的顺序没有要求。如果有要求，可用PriorityQueue。写出来是这样.
380. insert-delete-getrandom-o1
- 设计题，实现一个类似于set的类，要求平均在O(1)的时间内完成插入、删除、随机获取一个值等操作。
- ME：这个O(1)的时间要求搞死我。本来想用Set + List + 自定义类搞的，但是卡在了O(1)时间要求这里，而且Set没法获取原本存储在其中的对象了。后来偷看了discuss还是改掉了。
- TA：我看的是这个。他用到了Map + List，O(1)的秘诀就是在删除的时候，直接将最后一个元素覆盖到List中要删除的那个元素的位置，然后再删除List的最后一个元素即可。写出来是这样。
- java.util.Random类：使用
r.nextInt(val)可以获取[0, val)中的一个随机数。Java的随机数实现默认是根据当前时间种子System.currentTimeMillis()生成的，因此每次执行的结果不一样。要想传入特定种子，可以在构造时写成Random((long)seed)，这样每次执行的结果就一样了。
381. insert-delete-getrandom-o1-duplicates-allowed
- 和上一题相比，允许在自定义的这个Set类中插入相同元素。
- ME：我虽然这样做出来了，但是用Queue的方式在remove的时候并不是O(1)的，所以严格来说我自己没有做出来。
- TA：还是参考大神的，他把我的Queue给换成了LinkedHashSet，我研究了一下，感觉直接用Set也行，至于访问元素直接用一下
set.iterator().next()即可。写出来是这样。
382. linked-list-random-node
- 给一个链表，实现一个getRandom函数，随机返回一个节点的值，要求每个节点被返回的概率一样。
- ME：转成了ArrayList，结合java.util.Random搞定了。写出来是这样。但是follow-up说如果长度过长，且不能使用额外space怎么破？这就触及到我知识的盲区了。。。
- TA：事实上这是一个蓄水池抽样问题，中文博客在此，代码在此。假设链表元素为
[1, 2, 3]，每次只能读入一个数字。一开始读入1，只能保留它，概率为1；然后读入2，这是1和2之间保留谁的概率就是1/2；然后读入3，此时保留的数字与3只能保留一个，为了保证概率均等，需要在0~2中产生随机数，只有等于2的时候才选择索引为2的元素即3，概率为1/3，而上一步保留的那个数字留下来的概率则是1/2 * 2/3 = 1/3，概率依然相等。这个算法还可以推广到取k个元素出来的情况，这样内存中始终就只有非常少量（k + 1）的数字需要读入了。写出来是这样。
383. ransom-note
- 写勒索信的时候要从杂志上剪一些字母出来，给勒索信内容字符串和杂志内容字符串，判断能不能拼出来。
- ME：用HashMap存字符和对应到杂志中的索引，下次再找这个字母的时候就从map中索引的下一位开始查找。
- TA：没注意到题目说只有lowercase的字母，所以可以把map改成数组就好了，像这个。而且他不需要用到String的indexOf查找函数，直接就两波遍历，杂志的字母加、勒索信的字母减，最后只要没有负数就说明可以拼出来。
384. shuffle-an-array
- design题，实现一个类，传入元素各不相同的int数组后可以生成shuffle后的数组，调用reset还能返回原数组。要求所有可能的答案返回的概率相同。
- ME：第一次接触这种shuffle题，我就只是简单地用Random产生随机的index再结合ArrayList的remove功能，取出该索引对应元素后就删掉它。写出来是这样，但感觉ArrayList的remove非常耗时。
- TA：看了这个才知道，原来根本就不需要借助ArrayList，直接在数组上操作，至于生成随机数后如何删除，还是前面那个方法——对调法，直接和最后一个元素swap一下，再把生成随机数的区间减小一个，就不会再访问swap到后面的元素了，也就相当于删掉了。写出来是这样，不过怎么还更慢了？
385. mini-parser
- design提，又是NestedInteger类，要求从String形式转化成NestedInteger的形式。
- ME：用递归的方法搞咯。本来还想着直接用逗号split的，但是
[12,[12,23],2,[1,[2,[3,4],5]]]中用逗号分隔会是各个碎片。所以还是得手动找segment，如果是数字就直接转成NestedInteger了，如果有方括号就往后找到结束位置，然后递归求里面的NestedInteger。写出来是这样，出乎意料地快。 - TA：大神又用Stack改写成了Iterative的方法。用Stack存放NestedInteger，若为左括号，则将当前的NestedInteger入栈；若为右括号，则先看看前一位是否是正常的数字，是的话就转成NestedInteger加入当前的NestedInteger，再把栈顶元素取出来，把当前元素作为栈顶元素包含的NestedInteger给add进去；若为逗号，则先看看前一位是否是方括号，不是方括号说明前面是正常的数字，直接转就好。
386. lexicographical-numbers
- 给一个整数n，从1～n按字典序存入List。字典序即先看数字小的在前面，前缀部分相同则长度短的在前面。
- ME：感觉明明不难，又是磕磕绊绊持续debug才搞出来。我是用递归搞的，从
curr = 1开始，如果curr的十倍依然在范围内就取它的十倍去递归，直到超过n为止，这时就从curr开始往后逐步加1，但是怎么控制加多少个1呢，我用到的是比较前缀法，例如原本进入递归时curr是11，那就要保证我加1的时候除了不能超过n、而且不能超过20，这就需要除一下10来判断前缀部分是否一致了。而在加1之后如果新形成的curr的十倍又符合要求，则继续。写出来是这样。 - TA：这里有个iterative的方法，需要精确地找出规律，每一步都直接跳到下一个正确的数字，不太好想。反正就是从1开始，先尝试乘10并放到list中，然后尝试加1直到末位为9，然后就往前回溯到起点，需要找到9左边第一个非9的数字，然后加1继续。我上面的方法应该也算是DFS，这里还有个更简洁明显的DFS，visualize成一个树，每个节点都是需要放入List的数字，然后下一层就是父节点的数乘以10后加上1～9的结果，然后一层层深入下去找，相当于多叉树的前序遍历吧，写出来是这样。
387. first-unique-character-in-a-string
- 给一个只含有小写字母的字符串，求其中第一个出现的『只出现了一次的字母』的索引。
- ME：循环两波，第一波记录各个字母出现的次数，第二波看字母出现的次数为1时就直接输出了。写出来是这样。不过其实里面的index数组多余了。。。
- TA：没啥。
388. longest-absolute-file-path
- 给一个用字符串表示的文件系统目录，求其中的文件（以.xxx结尾的文件）的最长目录长度。
- ME：用自定义类加Stack搞咯。自定义类中存放层级数，然后通过
\t来计算当前目录的层级数，如果小于等于栈顶的层级数，说明前一部分的文件目录已经结束了，弹出直到栈顶层级小于当前目录层级，然后再入栈。写出来是这样。 - TA：我擦，O(N)并不一定是One-pass呀，我是何必呢。而且，不需要自定义类，看看人家这个。思路是利用一个stack数组，
stack[i]表示第i - 1层目录的长度，stack[0]为0。利用split将原字符串拆分成String的数组，遍历之，根据每个字符串的\t数目确定level（可以利用lastIndexOf找到最后一个\t的索引），然后到stack[level]取出第level - 1层的长度，加上当前字符串长度，再加上1（后续\n的长度），再减去level（因为最终结果中所有的\t都是不存在的，只有换行变成了斜杠），就得到了当前level的长度。写出来是这样。
389. find-the-difference
- 给一个只含有小写字母的字符串，打乱他后再随机插入一个小写字母，形成新的字符串，求插入的这个字符。
- ME：用Bucket记录字母出现的频数咯，一个加一个减，频数为负的就是插入的咯。写出来是这样。
- TA：没啥。
390. elimination-game
- 给一个正整数n，表示有1~n这么多个数，从左到右从第一个开始隔一个删一个，然后从右往左从第一个隔一个删一个。求最后留下来的那个数。
- ME：想了一下，没想出来高效的办法，不可能暴力搞吧。。
- TA：看了这个，找规律找得真6.设置一个头元素head，remain表示剩下多少数字，如果剩下一个就直接输出head了。如果是从左到右，那么删完了一波之后第一个元素就是head加上步长。如果是从右到左，就要看剩下的元素数remain的奇偶性了，只有剩下奇数个从右到左的时候才需要更新head。写出来是这样。此外还有一个break down的方法，直接想挺难想出来的。。。还有这个一行递归的，我的天。也是通过找规律搞出来的。
391. perfect-rectangle
- 给若干个矩形的左下和右上顶点坐标，判断是否可以组成一个完整的矩形。
- ME：看到hard就怂了，结果看到别人写的规律感觉并不难。。暗中观察出的rule是：这些点中最左下和最右上的顶点组成的大矩形的面积必须等于这些小矩形的面积之和；同时把每个矩形的四个顶点都求出来，除了最外侧的四个顶点只出现一次，其余点必须恰好出现偶数次。这个抽象真的完美，写出来是这样。
- TA：我上面看的就是这个答案，确实很好懂。还有一个略微复杂的方法，用的是sweepline的思想，从左到右定义每个矩形的竖边为event发生的时间点，定义一个class含有time和完整两个点的坐标数组的类，并重写compareTo函数，先根据发生的时间排序、相同则end的边在前。遍历一波将每个矩形的两个Event都放入pq中，并更新y坐标的上届和下界。然后声明一个TreeSet根据y坐标在下的在前，若两个矩形的竖边有重叠则视为相等。然后从pq里取每个时间点的边进行y范围判断并维护一个当前时间点的y长度，如果它是一个end边就直接从yLen中扣除，为开始边泽加上，如果在开始边的时候发现y有重合（TreeSet加入返回false）则直接不行了；结尾边就直接从set中remove掉，不用管end的yLen是因为start总在end前面嘛，start都通过了那end边也一定不重合；然后当前时间点结束后，就看看目前所得的长度是否是最外围的长度，注意如果是最后的end边，这时长度会降到0（正确的情况下），这需要先判断pq是否为空，为空了就说明完全OK，不为空就说明还没到最后，再和最外围的y判断一下。写出来是这样，略慢啊。。
392. is-subsequence
- 给两个字符串，判断其中一个字符串是否是另一个字符串的子串，这个字串不要求字符连续出现，只要求出现顺序一致且全部出现即可。
- ME：一开始想到扫长的扫一遍记录下每个字符在其中出现的位置，然后在较短串（咦好像少了这个判断在开头）中从头到尾各个字符在长串中的出现索引是否能形成从小到大的顺序，但是写出来谜之WA。后来一看这个，嗬，根本不List来记录嘛，直接两个指针分别扫就是了，写出来是这样，不过那个判断长度那里应该放到if里面更好。虽然这么写似乎很不错，速度也很快，但是根据tag，这题考的其实是二分法和DP，follow-up问的是如果有若干个短串需要check而长串特别长的时候，怎么优化。
- TA：看了这个发现我原来的方法似乎是可以的，只不过我是线性地往后找大于prev的索引，而二分查找就把这个过程加速了。总结就是先把长串的每个字符出现的位置存入List，然后根据短串的字符取出对应的在长串中出现的索引List，给定二分查找的key pos，如果找到就完美下一位，找不到就是「-(insertion point) - 1」，因此取个负再减1就是该字符在长串中pos后面的最前一位了。写出来是这样。
- List数组的声明不能再忘啦！
List<Integer>[] list = new List[n];
394. decode-string
- 给一个数字 + 中括号 + 字符串的经过encode的字符串，要求以数字作为后续中括号中字符串的频数decode成完整的字符串。
- ME：玛德这么简单的题搞了这么半天。。用了双Stack，一个存频数，一个存后续的字符串。当出现数字时进行乘10的累加，并且在嵌套的情况下意味着前面的字符串结束了，push到栈中；当出现左括号时说明前面的数字结束了，push到栈中；出现右括号时先将当前的字符串push到栈中，然后将栈顶的字符串拼接栈顶的频数那么多次，作为当前的字符串。这样一直到最后，留下的当前字符串就是所求了。写出来是这样。
- TA：为什么别人写出来的就这么简洁呢。。。这个跟我的思路基本就是一样的，就是这么简洁。我在提交那里还看到了一个递归的方法，利用全局的index控制起始位置，碰到数字的时候直接往后找左括号确定频数，然后就递归到下一层看对应的字符串是什么，然后根据频数不断地拼接即可；遇到右括号就意味着当前的这部分字符串已经到头，break出来直接返回上层即可。写出来是这样.
395. longest-substring-with-at-least-k-repeating-characters
- 给一个只有小写字母的字符串，再给一个频数，求最长子字符串的长度使得其中字母出现的次数都不少于给定的频数。
- ME：束手无策。。
- TA：看了这个解释之后，豁然开朗。这是个O(N^2)分治的做法，揪出当前子串中不满足频数要求的字母，排除掉它，然后递归看左右两边子串的情况，直接返回；如果统计好出现次数后发现它们全都符合要求，那就直接返回目前这段的全长即可。写出来就是这样，还是很直接的。还有一种O(N)双指针的做法，思路是用左右两个索引划定出子字符串的区间，再定义「在这个区间中所能出现的不重复的字符数」，这个字符数就是最外层循环的边界1～26，内层就根据给定的频数和这个限制确定挪动左边界还是右边界：先尝试挪动右边界，如果这个字符在这部分字符串中是否出现过（利用count数组统计频数），并看看更新频数后这个频数是否满足了给定最小频数；如果这一波下来发现当前的子字符串中所有出现的字符都满足最小频数，就更新长度；至于什么时候挪动左边界呢？当子字符串中出现的字符数超过外层循环限制时，就需要挪动左边界，同时更新count数组和相关的变量，例如挪出后出现的字符数和满足最小频数的字符数都可能会受到count数组的影响。写出来是这样。
396. rotate-function
- 定义一个rotate函数，
F(0)表示不旋转、F(1)表示后挪一位…函数输出的是各索引的数字乘以索引之和。求从F(0)到F(n-1)中的最大值。 - ME：我只想到了暴力法，感觉也不难实现就啥也没管直接试了一发，就是按照函数的定义这样暴力实现出来，讲道理应该是O(N^2)的时间复杂度，我原本都做好了超时的心理准备了，竟然改好WA之后（一开始以为全是正数，就没有把初始值设成最小负数）这样子就过了。不过看了一下，速度是勉强过的那种，说明症结正解还不是这样。
- TA：看到discuss版一溜的O(N)，我震惊了。看了这个顿悟，这踏马的是数列问题啊！根据F的公式可以推导出F(k)和F(k-1)的关系，那就可以从F(0)开始逐步往后更新，用到哪更新到哪，每一步都求一个最大值就好了。写出来O(N)这个果然就快很多了。
397. integer-replacement
- 给一个数字n，如果是偶数则除2，奇数则加1或减1，求最少经过多少步能从n变成1.
- ME：第一反应就是DP，但直接用n作为dp数组的规模会导致内存爆炸。后来偷看了一下discuss，发现时bit manipulation位操作，于是又暗中观察了一下，找出了规律。对于偶数可以直接右移一位，奇数则需要递归看看加1和减1的偶数的情况。但是第一次提交还是错误，因为Integer.MAX_VALUE边界情况有点奇怪，正常来说只能是前一个偶数的操作数加1，但是这题其实是允许unsigned数字出现的，因此实际上它还可以往后一个偶数2^31递归，这时就只是简单地从31右移到第0位了，因此是1 + 31.不过我还是觉得很怪。。。写出来是这样。
- TA：其实我一开始看的是这个但其实没有认真看答主的思路。他的想法是，每步操作都尽量减少1的个数，对于偶数没话说直接unsigned shift，对于奇数就需要判断一下最后一位之前是0还是1，如果是0说明当前数减1是个好选择，如果是1说明当前数加1能消除尽量多的结尾1.
398. random-pick-index
- 给一个数组，然后给一个目标值，随机返回一个在数组中这个目标值出现的索引。
- ME：偷看了一下discuss，发现又是reservior抽样问题，和前面382很像。。先来一遍找出target出现的所有索引并add到List中，然后从前往后生成Random.nextInt来刷新结果，最后返回。懂了之后写出来是这样。
- TA：我看的就是这个，答主并没有用到额外的ArrayList，而是巧妙地利用了索引为0的情况。模仿了一下。
399. evaluate-division
- 用字符串代表一些数值，给出一系列字符串对，再给一系列它们对应相除的结果，然后给一组字符串对，求这些query的相除结果。
- ME：Ummm，一开始WA了一波，只能reshape思路了。偷看了一下别人的思路，我才意识到这是一个graph题，可以抽象成一个双向图，每个字符串都作为节点，然后权重就是两个节点的商。我的做法分三步：遍历一遍形成str到index的映射，然后建立邻接矩阵并把权重填充进去（正反都放，不存在就是0），最后就query的时候就用DFS，遍历当前节点所有能走到的节点看看能否到达终点。写出来是这样，没想到出奇地快。
- TA：自己会了之后看类似的就不太有动力看了。。这个倒是挺简洁的，而且也提示我，是不是可以对应修改一下matrix中的值？这样下次query就不会重复计算了。
400. nth-digit
- 给一个正整数n，求1, 2, 3, …这一系列数组组成的连续字符串中的第n个数字。
- ME：一开始自己做居然他喵的超时了。。。
- TA：还是看了大神的杰作。思路是先根据数字的长度找到要求的这个n所在的数字具体是几位数，一位数有9个，两位数有90个， 三位数有900个…然后在这个范围内求n所在的数字具体是几，这就可以通过定义一个x位数的起始数字往后加的形式求得了，也就是在前面求n所在范围时不断减去一位数、两位数的个数这样，然后到了当前范围内的第n个，就可以用
(n - 1) / 几位数来求n在第几个数，加上起始数字就找到了。最后就是看看n在这个数字内部是第几个，那同样是(n - 1) % 几位数就可以找到了。写出来是这样。