101. symmetric-tree
- 给一个二叉树根节点，判断这棵树是否对称。recursive和iterative都想想。
- ME：只想到了recursive，很好写。iterative一开始想到了中序遍历转成前后对称的数组来判断，但感觉是小题大作了，毕竟中序遍历似乎并不必要。偷看了一下关键词，DFS和BFS。
- TA：这个告诉你，原来可以借助Stack！每次取栈顶两个节点，先判断其值是否相等，然后将二者的左、右子节点和右、左子节点入栈，继续判断。
- JAVA可以重载呀，同名方法、不同参数列表即可，不用绞尽脑汁想另一个名字哇。1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253// recursiveclass Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return helper(root.left, root.right);}private boolean helper(TreeNode left, TreeNode right) {if (left == null && right == null) {return true;}if (left == null || right == null) {return false;}if (left.val == right.val) {return helper(left.left, right.right) && helper(left.right, right.left);}return false;}}// iterativeclass Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}Stack<TreeNode> stack = new Stack<>();stack.push(root.left);stack.push(root.right);while (!stack.isEmpty()) {TreeNode left = stack.pop(); // take two nodes from stack topif (stack.isEmpty()) {return false; // should always have 2 at}TreeNode right = stack.pop();if (left == null && right == null) {continue;}if (left == null || right == null|| left.val != right.val) { // ensure equalreturn false;}stack.push(left.left); // push 2 symmetric positions into stackstack.push(right.right);stack.push(left.right);stack.push(right.left);}return true;}}
102. binary-tree-level-order-traversal
- level层面的遍历二叉树，返回一个
List<List<Integer>>。 - ME：用了辅助的
List<List<TreeNode>>记录每一层的节点情况，同时为了防止加入空的List，设置了一个isNull
布尔值判断是否这一层已经没有后续节点了。相当于BFS。 - TA：BFS原来不用多一个双重List，直接一个Queue就搞定了。这个DFS方法则是通过Level层级控制当前节点应当塞到哪一层对应的List当中。1234567891011121314151617181920212223242526class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if (root == null) {return ans;}Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {List<Integer> curr = new ArrayList<>();int len = q.size();while (len-- != 0) {TreeNode node = q.poll();curr.add(node.val);if (node.left != null) {q.add(node.left);}if (node.right != null) {q.add(node.right);}}ans.add(curr);}return ans;}}
103. binary-tree-zigzag-level-order-traversal
- level层面的遍历二叉树，但是遍历顺序不是固定的从左到右，而是蛇形，这一层从左到右、下一行从右到左。
- ME：使用
Queue<TreeNode>+按照每层节点计数循环遍历的BFS比较容易想到，根据level的奇偶，在加入结果之前将当前层级的List使用Collections.reverse反转一下就好了。而DFS也是利用level的奇偶，决定把当前节点的值插入List的头还是尾。DFS还是略快一点。 - TA：看这个发现，BFS的时候也可以用LinkedList的addFirst将当前值插入头部（或者ArrayList的add(index, Element)），而不必在最后来Collections.reverse。
- should be simple to come up with reversed version of normal level-traverse…12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if (root == null) {return ans;}Queue<TreeNode> q = new LinkedList<>();q.add(root);boolean rev = false;while (!q.isEmpty()) {int len = q.size();List<Integer> list = new ArrayList<>();while (len-- != 0) {TreeNode node = q.poll();list.add(node.val);if (node.left != null) {q.add(node.left);}if (node.right != null) {q.add(node.right);}}if (rev) {Collections.reverse(list);}ans.add(list);rev = !rev;}return ans;}}class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if (root == null) {return ans;}dfs(root, ans, 0);return ans;}private void dfs(TreeNode root, List<List<Integer>> ans, int level) {if (root == null) {return;}if (level == ans.size()) {ans.add(new LinkedList<Integer>());}List<Integer> list = ans.get(level);if (level % 2 == 1) { // odd level should reverselist.add(0, root.val);} else {list.add(root.val);}dfs(root.left, ans, level + 1);dfs(root.right, ans, level + 1);}}
104. maximum-depth-of-binary-tree
- 求二叉树的深度。
- ME：三行的递归。毕竟衣洗题。
- TA：没啥了。
105. construct-binary-tree-from-preorder-and-inorder-traversal
- 给出前序遍历和中序遍历的数组，构造一个完整的二叉树，树的节点值不会重复。
- ME：明明是数据结构讲树的时候讲过的，但是就是不记得了。。。憋了很久，不会。偷看了一下tag，提到了DFS。更可怕的是，我发现中序和前序被我搞反了，做的草稿都是反的。
- TA：这个介绍得很清楚，在preorder中先出现的一定是root，那么对应在inorder中找到它的位置，其左到inStart都是它左子树的节点，其右到inEnd都是它右子树的节点，递归下去找root的左节点和右节点即可。注意此题说了节点的值不重复，因此用循环在inorder中找root的位置时一旦找到就可以break；但如果允许值重复，则应当保证是当前查找范围内『最后一个出现的』，这也是上面这个答案的方式。我一开始一直在思考怎么用Stack，似乎记得老师讲过，果然看到了这个用栈的iterative方法，不过其实这个Java版的更简洁，或者看我提交的，Java版的思路是先把跟节点入栈，然后每次从取栈顶元素和inorder比，不匹配则继续把preorder元素入栈；一旦匹配则持续出栈并继续与inorder后续元素比较，直到栈顶元素不再匹配，则把最后一个匹配的栈顶元素的右节点设为preorder的元素并入栈。
- very basic isn’t it? But need to know the iterative one.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || inorder == null) {return null;}return helper(preorder, inorder, 0, 0, inorder.length - 1);}private TreeNode helper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {if (preStart == preorder.length || inStart > inEnd) {return null;}int pos = inStart;for (int i = inStart; i <= inEnd; i++) {if (inorder[i] == preorder[preStart]) { // get the pos of current root in inorderpos = i;}}TreeNode root = new TreeNode(preorder[preStart]);// all in front of pos in inorder are in left part, while latter are in right partroot.left = helper(preorder, inorder, preStart + 1, inStart, pos - 1);root.right = helper(preorder, inorder, preStart + 1 + pos - inStart, pos + 1, inEnd);// note that right part need to shift (pos - inStart), which means how many elements in left.return root;}}class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {return null;}Stack<TreeNode> stack = new Stack<>();TreeNode root = new TreeNode(preorder[0]);TreeNode prev = root;int indexPre = 1, indexIn = 0;while (indexPre < preorder.length) {if (prev.val == inorder[indexIn]) { // reaches a root of its subtreeindexIn++;while (!stack.isEmpty() && inorder[indexIn] == stack.peek().val) {prev = stack.pop(); // pop until reaches previous rootindexIn++;}TreeNode curr = new TreeNode(preorder[indexPre]); // always take from preorderprev.right = curr; // set to previous root's rightprev = curr; // go into right} else {TreeNode curr = new TreeNode(preorder[indexPre]); // take from preorderprev.left = curr; // simply means curr is prev's leftstack.push(prev);prev = curr;}indexPre++;}return root;}}
106. construct-binary-tree-from-inorder-and-postorder-traversal
- 给出中序遍历和后续遍历的数组，构造一个完整的二叉树。节点值不重复。
- ME：按照上一题学习的，用Stack搞的iterative方法和recursive的方法都搞定了，毕竟刚刚才做过，记忆还很新鲜。
- TA：由于元素不重复，因此可以考虑用一个HashMap来保存inorder中的值与对应的索引，这样就省去了线性查找的时间了。
107. binary-tree-level-order-traversal-ii
- 给一个二叉树的头结点，返回按从下到上的层级遍历的结果。
- ME：老办法，BFS用一个Queue从上到下遍历，返回之前Collections.reverse一发。还尝试了一波DFS，借助level，最后reverse。
- TA：我的方法应该是有点取巧了lol，虽然应该是比add(index, Element )好一点的，取反是一波流，而每次插入挪动的元素反而还多。通常大家的做法是，BFS中每次添加到结果的时候用add(0, List )，DFS中则是get的时候不是直接get对应level的那个List去添加，而是size - level - 1取到对称位置的。
108. convert-sorted-array-to-binary-search-tree
- 给一个排好序的数组，构造出对应的二分查找树。
- ME：recursive的方法，每次进行二分找到根节点，然后在前、后两半各自确定左、右子节点。
- TA：同样有大神将recursive的方法改成了iterative的方法，利用了三个stack模拟递归。递归的方法都可以通过栈来改写成遍历。
- Recursive OK.123456789101112131415161718192021class Solution {public TreeNode sortedArrayToBST(int[] nums) {if (nums == null) {return null;}return helper(nums, 0, nums.length - 1);}private TreeNode helper(int[] nums, int start, int end) {if (start > end) {return null;}if (start == end) {return new TreeNode(nums[start]);}int mid = (start + end) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, start, mid - 1);root.right = helper(nums, mid + 1, end);return root;}}
109. convert-sorted-list-to-binary-search-tree
- 这回给的是一个排好序的链表的头结点，构造出对应的二分查找树。
- ME：采用快慢指针的方式找中间节点，需要分节点数为奇、偶两种情况适当地挪动来取得中间节点作为当前根节点。
- TA：这个解答也是快慢指针，但写起来比你的简洁好多。它传入了start和end，slow和fast一开始都指向start，利用tail判断什么时候停止挪动fast，然后直接将slow作为当前的根节点，其left和right递归去找就可以了，这个代码真的很漂亮。还有一种是先遍历一遍得到长度，然后根据长度分成左半部分和右半部分，速度也不慢，不过借助了一个全局变量来遍历原链表，不太喜欢，也不好懂，毕竟在递归的时候变来变去的比较绕。
110. balanced-binary-tree
- 给一个二叉树，判断它是否balanced。
- ME：一开始想法错了，以为左、右子树都是balanced就是了（你想想为啥）。后来改成老老实实根据高度来判断，若出现了左右两子树高度差大于1则返回-1，一直回溯到根。WA了两次才过，丢人呀还是个衣洗题。
- TA：这里提到了两种，一种是比较浪费时间的自顶向下每次求高度法，另一种就是自下向上累计高度法。我就用的累计法，方便确认平衡状态嘛。
- Recursive OK.12345678910111213141516171819class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) >= 0;}private int getHeight(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int left = getHeight(root.left);int right = getHeight(root.right);if (left == -1 || right == -1 || Math.abs(left - right) > 1) {return -1;}return Math.max(left, right) + 1; // accumulate with max of left sub and right sub.}}
111. minimum-depth-of-binary-tree
- 求最小深度，即从根到最浅的叶子节点经过的节点数。
- ME：递归搞定。
- TA：没啥了。12345678910111213class Solution {public int minDepth(TreeNode root) {if (root == null) {return 0;}int left = minDepth(root.left);int right = minDepth(root.right);if (left == 0 && right == 0) {return 1;}return 1 + (left == 0? right: right == 0? left: Math.min(left, right));}}
OK.112. path-sum
- 给一个整数和一棵二叉树，判断是否存在路径使得经过的节点的值之和是给定的这个sum。
- ME：递归搞定，每次深入之前先把sum减掉当前节点的值，达到sum的时候再判断是否是叶子节点。
- TA：差不多吧。123456789101112class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}if (root.val == sum && root.left == null && root.right == null) {return true;}int newSum = sum - root.val;return hasPathSum(root.left, newSum) || hasPathSum(root.right, newSum);}}
OK.113. path-sum-ii
- 给一个整数和一棵二叉树，返回所有的从根到叶的和为sum的路径。
- ME：DFS递归搞定。
- TA：没啥了。1234567891011121314151617181920class Solution {public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> ans = new ArrayList<>();dfs(root, sum, ans, new ArrayList<Integer>());return ans;}private void dfs(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> curr) {if (root == null) {return;}curr.add(root.val);if (root.val == sum && root.left == null && root.right == null) {ans.add(new ArrayList<Integer>(curr));} else {dfs(root.left, sum - root.val, ans, curr);dfs(root.right, sum - root.val, ans, curr);}curr.remove(curr.size() - 1);}}
114. flatten-binary-tree-to-linked-list
- 给一个二叉树，将它in-place地改造成一个以右节点为next的链表状的树。
- ME：作死地看了一下提示。。用DFS和本身的flatten相互嵌套递归，然后将左子树的最右下叶子节点的右指针指向经过flatten的右子树，返回给root。这种嵌套的写法，写是写得出来，但似乎不太好跟人解释。
- TA：写得太短真心不好懂，比如这个，摆个全局变量在那，很不好想。这个给改成了传参版，也。。
- This is really an extremely beautiful solution:12345678910111213class Solution {private TreeNode prev = null;public void flatten(TreeNode root) { // sth like post orderif (root == null) {return;}flatten(root.right); // but go right first to locate prev at root of rightflatten(root.left); // prev will be connected to the very right of left subroot.left = null; // prev will become root of left subroot.right = prev;prev = root;}}
115. distinct-subsequences
- 给两个字符串S和T，在S中任意去除字符后得到T，求总共有多少种操作可以做到。
- ME：画了个
dp[tLen+1][sLen+1]，DP搞定。dp[i][j]表示T从0取到i-1位、S从0取到j-1位的时候，S有多少种删法能完美得到T。对于第i=0行来说，T是空，因此S不论取多少都只有一种删法能得到T；从i=1开始就要逐位确认字母是否匹配，若匹配则为左一位和左上一位之和，即dp[i][j] = dp[i-1][j-1] + dp[i][j-1]；若不匹配，则j-1这一位的字母必须删除，因此直接由左一位决定，即dp][i][j] = dp[i][j-1]。 - TA：DP嘛，都差不多。最下面这个给改成了一维，确实是可以的，因为我更新dp table的时候刚好也是斜向下对角线更新的。
116. populating-next-right-pointers-in-each-node
- 给一个二叉树，要求把所有节点的next都指向其同level的右边的节点。只能用O(1)的extra space，且这里的二叉树一定是perfect的，所有叶子都在一个level上、每个节点都有两个子树。
- ME：第一次碰到不给run的题目，只能写完直接submit。还是递归嘛，每个根节点都先右后左地深入去connect，但这样还不够，因为从左子树和右子树的节点也有要相连的，因此又写了个connectL2R方法。不过这样一来感觉会浪费一些时间，因为两边深入下去搞完了回到根节点，还要再深入一次。
- TA：这个很强，我一开始也想用一个prev一个curr搞的，但是逻辑没有理清楚。这里prev从root开始，让curr从prev的左子树开始挪动设置next，最妙的是左右两个子树的连接，是通过curr的next是否为null判断之后办到的，如果curr的next存在，那么curr.right.next就应当指向curr.next.left，画个图就明白了。之后curr就挪到curr.next，继续设置。妙哉！这样节省了我方法里的重复深入，而且不需要递归呢。
- Did not come up with prev + curr method.1234567891011121314151617181920public class Solution {public void connect(TreeLinkNode root) {if (root == null) {return;}TreeLinkNode prev = root; // first of each levelTreeLinkNode curr = null; // go throught the levelwhile (prev.left != null) {curr = prev;while (curr != null) {curr.left.next = curr.right; // nodes on this level have set nextif (curr.next != null) {curr.right.next = curr.next.left;}curr = curr.next;}prev = prev.left;}}}
117. populating-next-right-pointers-in-each-node-ii
- 给一个二叉树，要求把所有节点的next都指向其同level的右边的节点。只能用O(1)的extra space，但不一定是perfect的了。
- ME：用上一题学到的prev+curr写法，写了一大堆条件判断，因为不是perfect的话，curr在设置next的时候要考虑很多情况，prev在挪动的时候也不只是简单的prev.left了，而是先判断如果当前是叶子，得往next找下一层的首个节点。WA了三四次才过。
- TA：手动再见。看人家这个写的，多么清晰简洁，既然每一层的head无法直接确定，那不妨多设一个变量来存放嘛，每一层每一层这样设置next，非常优雅！还有一个使用dummyHead的方法，dummyHead作为每一层伪头部，总是指向该层的首个元素，再用一个pre去往后设置next，当上一层的root.next为null说明当前这一层设置完成，root来到dummy.next就到达当前这一层的首个元素了，这时需要切断dummy.next，再继续设置。妙哉！
- Similar to 116, just generalized.1234567891011121314151617181920212223242526public class Solution {public void connect(TreeLinkNode root) {if (root == null) {return;}TreeLinkNode fakeHead = new TreeLinkNode(0);TreeLinkNode prev = fakeHead; // previous node that should set its nextwhile (root != null) {if (root.left != null) {prev.next = root.left;prev = prev.next; // should not be put outside}if (root.right != null) {prev.next = root.right;prev = prev.next;}root = root.next;if (root == null) { // means the level of root is expiredroot = fakeHead.next; // go to next levelprev = fakeHead;fakeHead.next = null; // IMPORTANT! reset fakeHead to ensure root will become null}}}}
118. pascals-triangle
- 给一个整数，返回对应层数的完整的杨辉三角。
- ME：暴力O(n^2)做呀，List嘛。
- TA：没啥了。
119. pascals-triangle-ii
- 给一个整数，返回该层的杨辉三角，如
row = 0则返回[1]。 - ME：说是只能用O(k)的空间，那么我就用了两个List交替更新，一开始理解错这个rowIndex了搞死我。写出来发现速度好慢啊。
- TA：我发现我好像搞错了，我那样其实还是有多余的空间，真正精简的O(k)应该是这样，而且答主还用了我一直想用的数组，省去了set的麻烦。妙哉！还有直接用公式的，这个就。。。
- 数组转List可以用Arrays.asList()，不过这个数组不能是基本类型的，要改成对应的封装类。
120. triangle
- 给一个List
- ME：一个dp数组先拷贝最低端的n个数字，然后自底向上在相邻两个数之间选较小值加上上一层的数，更新到数组中。一直更新到最顶层，dp[0]即为所求。
- TA：你写的这个在第二重循环中从右到左搞，没有必要啊！搞得你还要用一个额外的变量来存放old值。。大家思路都差不多，DP嘛，bottom-up已然最优了。
121. best-time-to-buy-and-sell-stock
- 给一个int数组表示一个股票走势，求某一次最佳买入&卖出点的情况下，收益是多少。
- ME：维护了一个数组保存到当前位置位置的最低买入点价格，然后从右往左更新maxprofit。特别慢。
- TA：在提交的时候看了一下比较快的做法，竟然一波流就搞定了，当前值大于sofarMin的时候就判断是否需要更新maxprofit，否则就更新sofarMin，讨论版里也有类似的。此外，讨论版里这个提出了一个变种题，就是给的数组不再是当前股票价格，而是想比前一天的差，在这种情况下求最大收益。思路是每次都求差值，若为正则继续累加，若为负则重置为0.
122. best-time-to-buy-and-sell-stock-ii
- 给一个int数组表示股票走势，允许多次买入卖出操作，求总共最大的收益。
- ME：sofarMin的更新稍微变了一下，不仅是当前值小于sofarMin时、在当前值小于前面一个值的时候也要更新，同时将当前的profit累加到sum中。
- TA：大神直接假设天天都能买入卖出，虽然不符合『卖出之后才能买入』的规则，但是这代码的结果也是对的。
123. best-time-to-buy-and-sell-stock-iii
- 给一个int数组表示股票走势，至多允许两次买入卖出操作，求最大收益。
- ME：以为和前面那题类似，一开始就按照累加那样的形式扫一遍，然后稍微更新一下max1和max2，但是没想到类似于
[1,2,4,2,5,7,2,4,9]的情况，即按照前一题的做法得到的是3,5,7三个里面，取较大二者则为12；但实际上可以取到6 + 7 = 13。WA后一筹莫展了。看了下tag，DP。。。 - TA：由于我考虑过从两端分别遍历，所以先参考的是这个，维护了一个leftProfit数组，表示从最左开始到当前位置的最大收益；然后再从右端遍历，这时就不需要维护一个数组了，而是在每次计算出从当前到最右端的最大收益时，加上leftProfit数组对应位置的值，取个Math.max，意义为从0~i的最大收益加上从i~end的收益（虽然这个i这一点疑似又买又卖，但实际上不会发生）。此外，还有这个消除了DP中冗余变量的方法，思想是假设一开始本金是0，release2表示第二次卖掉股票后剩余多少钱、hold2表示第二次买入股票时剩余多少钱、release1表示第一次卖掉股票后剩余多少钱、hold1表示第一次买入股票时剩余多少钱。通过for-each每次取出prices中的数值，依次更新这四个值。还有这个就是推广了到允许多次交易的情形，真的非常不好懂。。。
124. binary-tree-maximum-path-sum
- 给一个二叉树，求其中的任意一条路径使得经过所有节点的值最大，不一定要经过root。
- ME：一筹莫展。。。看了下tag，是DFS。
- TA：这个竟然这么轻松就给解出来了，非常简洁明了，一学就会。需要用一个辅助函数不断递归，先不断向左深挖，直到空，向右；辅助函数返回的是左和右的较大者加上当前根节点，且必须为正数才能取（负数那就越加越小了），而返回值则是用一个全局变量维护，每次尝试
left + right + node.val，相当于把当前node作为根节点而不经过全局的root了。 - Fail.12345678910111213141516class Solution {private int max; // store the value of taking current root as swag point "^"public int maxPathSum(TreeNode root) {max = Integer.MIN_VALUE;return Math.max(dfs(root), max);}private int dfs(TreeNode root) {if (root == null) {return 0;}int left = Math.max(0, dfs(root.left));int right = Math.max(0, dfs(root.right));max = Math.max(max, left + right + root.val); // take both of the branchesreturn root.val + Math.max(left, right); // means only take one of the branches}}
125. valid-palindrome
- 给一个字符串，忽略字母大小写并只考虑数字和字母，判断它是否中心对称。
- ME：前指针+后指针搞，若不是字母或数字则用while不断找。
- TA：这个很简单粗暴，用正则表达式+replaceAll，把非字母数字的替换成空，然后reverse一下，直接判断是否相等即可。
126. word-ladder-ii
- 给一个List的String，然后一个初始String一个目标String，要求每次变动一个字母且变动后的词语来自该List的情况下，返回所有最短变换得到目标String的方式（List的形式）。
- ME：这个涉及到去重，所以想到的是DFS，但是做出来发现超时。没办法又回到BFS，但是如何防止走回头路的同时保证同一层的其他节点还能够正常走这条路径到达endWord？又是手足无措.jpg。
- TA：看了discuss，发现竟然是DFS和BFS结合！真的复杂，第一次做题做到毫无耐心。。。暂时放一放。。。。然而没想到一而再再而三地见到这个题及其变种，不能不搞懂了。。。其实就是个图论题，词典中每一个词都是一个node，要从起点到终点，如果只是求最短路径的长度，那只需要一步BFS构建每个节点的邻居就可以了，只要邻居中出现了终点，就输出距离。但是如果要记录这些最短的路径具体是怎么走的，就需要再来一个DFS，从起点开始一直往后（不走回头路利用的是后出现的节点的距离一定是先经过的节点的距离+1），如果到了终点就把经过的路径存起来。最后形成的就是路径的列表了。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {List<List<String>> ans = new ArrayList<>();if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0|| beginWord.length() != endWord.length() || wordList == null || wordList.size() == 0) {return ans;}Map<String, Integer> distMap = new HashMap<>();for (String word : wordList) {distMap.put(word, Integer.MAX_VALUE);}if (!distMap.containsKey(endWord)) {return ans;}distMap.put(beginWord, 0);Map<String, Set<String>> neighborMap = new HashMap<>();Queue<String> toVisit = new LinkedList<>();toVisit.offer(beginWord);boolean found = false;while (!toVisit.isEmpty() && !found) {int size = toVisit.size();for (int i = 0; i < size; i++) {String currWord = toVisit.poll();if (currWord.equals(endWord)) {break;} else {bfs(currWord, distMap, neighborMap, toVisit);}}}dfs(beginWord, endWord, distMap, neighborMap, ans, new ArrayList<>());return ans;}public void bfs(String fromWord, Map<String, Integer> distMap,Map<String, Set<String>> neighborMap, Queue<String> q) {StringBuilder sb = new StringBuilder(fromWord);for (int i = 0; i < sb.length(); i++) {char origin = sb.charAt(i);for (int k = 0; k < 26; k++) {char c = (char)('a' + k);sb.setCharAt(i, c);String curr = sb.toString();if (distMap.containsKey(curr) && distMap.get(fromWord) + 1 <= distMap.get(curr)) {q.add(curr);distMap.put(curr, distMap.get(fromWord) + 1);neighborMap.putIfAbsent(fromWord, new HashSet<>());neighborMap.get(fromWord).add(curr);}}sb.setCharAt(i, origin);}}public void dfs(String fromWord, String toWord, Map<String, Integer> distMap,Map<String, Set<String>> neighborMap, List<List<String>> ans, List<String> path) {path.add(fromWord);if (fromWord.equals(toWord)) {ans.add(new ArrayList<>(path));path.remove(path.size() - 1);return;}Set<String> neighbors = neighborMap.get(fromWord);if (neighbors != null) {for (String neighbor : neighbors) {if (distMap.get(neighbor) == distMap.get(fromWord) + 1) {dfs(neighbor, toWord, distMap, neighborMap, ans, path);}}}path.remove(path.size() - 1);}
127. word-ladder
- 给一个List的String，然后一个初始String一个目标String，要求每次变动一个字母且变动后的词语来自该List的情况下，最短需要变几次得到目标String。
- ME：毫无头绪，也不像是有DP的那种状态转换啊。稍微看了下Discuss里的关键词，BFS。
- TA：BFS果然好用，看这个搞出来的，思路是利用queue确定下一层要访问的字符串，然后对每一层进行遍历，遍历时就是用26个字母逐一替换进去看看是否在所给的字典中，存在则放入下一层，这样最快找到endWord就是最短路径了，其实有一点点图论的意思。答主还提到了加速的方法，这里也有大神进行了解释，即从前和后同时开始找，每次选择规模较小的方向进行BFS，但这样为什么就能提速呢？
possible lossy conversion from int to char说明出现潜在的精度丢失，需要在运算式子最前面加个括号强制转换。Queue用LinkedList，不是push而是add；Set用HashSet，有contains、remove等方法。
128. longest-consecutive-sequence
- 给一个数组，要求在O(n)的时间内，返回其最长的连续子序列的长度。
- ME：毫无头绪，偷看了下tag，提到了并查集。然而似乎不能直接用类似木桶法那样的数组搞啊，八成会越界。
- TA：看了这个用了HashMap和
val+1、val-1判断的答案，其实我本来有往这方面考虑的啊哭。思路是维护一个map，存储的是以当前数值为边界的最大连续长度，先从原数组中逐个取出数值n，再到map中查找n-1和n+1对应的长度left和right，那么加上当前数值之后的长度就为left+right+1了，判断一下取个max即为结果，注意要更新两个边界的长度，即map中n+left和n+right处的值。若原数组中有重复元素，即已经在map中出现了，就不能再拿来更新了。此外，还有一个使用set实现的，模仿了一下也AC了。这种也是有点图论的感觉，n-1和n+1就是邻居，看n最远可以走到哪。
129. sum-root-to-leaf-numbers
- 给一个二叉树，每个节点值只可能为0~9，从根到叶经过的节点表示一个数字，求所有这些数字之和。
- ME：DFS搞定。
- TA：差不多吧。不过我用了一个全局变量，其实可以直接用返回值的，避免类中的全局变量。改成返回值版后，真的快了。
- Not really OK…12345678910111213141516171819202122class Solution {public int sumNumbers(TreeNode root) {return dfs(root, 0);}private int dfs(TreeNode root, int val) {if (root == null) {return val;}if (root.left == null && root.right == null) { // is leafreturn root.val + val; // previous val add current node val}int newVal = (root.val + val) * 10;int sum = 0;if (root.left != null) {sum += dfs(root.left, newVal);}if (root.right != null) {sum += dfs(root.right, newVal);}return sum;}}
130. surrounded-regions
- 给一个只含有
XXOO的char二维数组，要求把所有被X完美包围的O替换成X，而绵延到边界的O就不替换。 - ME：总感觉这题似曾相识，我最担心的情况出现了——在费劲地想和之前做过的什么题相似，而思路本身却卡壳了。我只能想到利用一个辅助二维table帮助判定是边界的O还是内部的O，一旦是边界的就向四个方向拓展判断。测试了一下算法是对的，但是递归的时候StackOverflow了。。。
- TA：原来我的DFS方法是可以的，但是这个StackOverflow是因为你递归太多层了，而且也没有必要来多一个辅助的table，直接在原棋盘上操作就好了。这个大神给出了解释，当从首行开始改变
O的时候，如果向后一直蛇形连成一长串O，那么从(0, 0)开始的DFS会一路递归下去，规模非常可观。虽然改了之后可以AC，但是对于这个大神提出的第二个情况，DFS还是不行的。因此，还是不能偷懒搞DFS+recursive，得BFS+iterative，我参考了这个写出来了自己的，思路就是遍历四条边的O，碰到就对它进行BFS，在BFS中先把O给换成别的什么字符，利用Queue来保存该O四个方向相邻的O（用了个内部类），入Queue之前也要把O给换掉，然后一直遍历Queue中的O直到Queue为空。最后把四个边界遍历完成后，再从头到尾来一波，把特殊字符换回O，把剩余的O换成X。此外还有一个使用并查集的方法，不是太好懂。。。似乎答主的灵感还是来自MIT的coursera作业，然而我没搞= =
131. palindrome-partitioning
- 给一个字符串，求它所有的划分方式使得每一个子字符串都是自对称的。
- ME：DFS暴力搞，从头开始取1、2…长度的自字符串，判断是否自对称，是则固定并以下一个字符为起始继续DFS。不过速度奇慢，我一开始还怀疑会超时的其实。。。
- TA：原来可以用DP提速！思路是利用一个二维的boolean数组
isPalin[i][j]表示字符串从i到j的部分是自对称的，然后维护一个类似于三维的List<List<String> [len]数组result，result[x]表示从第一个字符到x的前一个字符为止的List
132. palindrome-partitioning-ii
- 给一个字符串，求最少的划分数使得每一个子字符串都是自对称的。
- ME：用了刚刚学到的DP方法，用一个二维的boolean表示从i到j是自对称的，然后再用一个dp重新遍历一遍它，dp[x]就表示长度为x的部分的最少划分数，dp[x]由前面的划分数以及对称情况确定，若本身就对称了那划分数为0，否则找到前面子字符串中划分数最少的加一即得。但速度并不快，大概是因为我是O(2 * n^2 )？
- TA：这个思路和我一样，而且也是用到了一个table加一个数组，不过他直接把我的两部给合并到一起了，模仿了一波果然快了。然后优化的话可以考虑把table给省掉，只用O(n )的空间，双重循环，对当前字符向左右扩展判断是否对称，注意要区分奇数和偶数的子串长度两种情况分别扩展。老实说，不太好懂。
133. clone-graph
- 给一个无向有环图的其中一个节点，要求拷贝一个完整的无向有环图，并返回拷贝而成的对应的该节点。而且竟然两个节点之间可以有多条通路。
- ME：DFS+一个map。既然label是唯一的，那么在复制当前节点之前需要先看看map里面是否已经有了当前节点，若有就直接取出来即可，若无，再进一步复制。复制时又分两种情况，当前节点没有更多邻居，则直接new一下再put进map里就可以返回了，若还有邻居，则需要先看看是否它自己（成环），是环就直接在neighbor里add自己就行，若不是环再去递归克隆。
- TA：这个则是一个
BFS + map + Queue的iterative方法，队列中存放的是原节点，map中存放的是label对应的新创建的拷贝节点。每次从队首poll一个出来，把它的首次出现的邻居都存入queue、new一个存入map（用map判断是否首次出现），然后根据label从map中把拷贝的节点取出来，给它的neighbor列表加上map中对应的节点。BFS还是不太熟啊。。。
134. gas-station
- 假设一个环形的路线，给一个gas数组表示每个索引处对应的供应油量，cost数组表示从当前索引到下一索引所需的油量，求从哪个索引开始能够保证油量足够绕一圈。
- ME：一开始按照最直接的想法DFS，暴力从每个索引出发判断油量够不够，结果超时。改成了一个O(n)的根据剩余油量正负来更新start的方法，又是WA。看了一下标签，就是个Greedy，不知道我Greedy的逻辑哪不对。。
- TA：这个和我WA的O(n)很像，思路是从头开始算剩余油量，当油量为负就累计一下『所欠的油量』，然后将剩余油量归0再往后遍历，遍历完后看看剩余油量够不够所欠油量，够就可以把start输出了。就差一点呀，关键就是这个『所欠油量』！这个也很6，有个trick比较难想到，把最后一个索引当成start、第一个索引当成end，将剩余油量初始化为最后一个索引处往第一个索引处开之后的油量sum，若sum非负，则可以继续往后开（加上end这个索引处的油量情况），若sum负了说明从当前start不能开到end，需要让start往回滚找到能够开到end的起点。当start和end相遇仍没有办法让油量非负，说明无解。
135. candy
- 给一个ratings数组表示一排小朋友的优先级，要求每个小孩至少一颗糖，优先级高于相邻小朋友的必须得到多于邻居的糖。求发出去的糖果总数的最小值。
- ME：一开始超时的做法是，用一个candy数组表示每个小朋友所分得的糖果数，一旦小于前面的小朋友就默认发1颗，若出现相邻的小朋友rating不相等但糖数一样，就一直往前回滚每人多加一颗。注意若相邻小朋友优先级相等并不意味着糖数相等，例如
1,2,2,2,2的最少糖果分配方式是1,2,1,1,1。很气，怎么避免回滚呢，tag也只是个简单的Greedy。 - TA：玛德！原来可以把回滚放到最后求sum的循环里，从后往前判断ratings，若前一rating比后一rating高而糖果却不是前者多于后者，则直接把后者的糖果数加一赋给前者。又是只差一点！还有一个constant space的方法，我一开始也有想过似乎可以不用数组，但看了这个答案发现没有我想的那么简单，这里有一个arithmetic progression的规律，所谓的『首项加上末项乘以项数除以二』，利用一个countDown表示逆序了多少位，一旦正序了就让result加上前面逆序部分所需的糖果数，即
(1+countDown ) * countDown / 2。但还有一个比较复杂的情形是正序部分最多的糖果少于逆序部分最多的糖果，除了用上面这个公式求最后一个正序到末尾这部分的糖果，还要判断一下countDown是否比最后一个正序所获得的糖果都多，因为可能出现[1,2,3,4,3,2,1,0,-1]这样的情形，4是最后一个正序，-1是末位，countDown是5而最后一次正序获得的糖果是4，如果只是简单地那样派糖果则[4]的糖果（4）就小于等于[3]的糖果（5）了，所以需要给最后一个正序的小孩补偿countDown - prev + 1个糖果，在这里就是补充两颗给他，这样就6>5了。
136. single-number
- 给一个int数组，其中有一个单身狗，其他都是恰好出现两次，返回这个单身狗的值。
- ME：用HashMap搞定，若不存在就put，存在就remove，最后用new ArrayList<>(map.values( ) )揪出单身狗。follow up要去不借助额外的内存，那就不给用map咯。想了一阵没头绪。。。
- TA：还有这种骚操作？？？原来是位运算，利用异或XOR的交换律，一路往后异或，最后剩下的就是单身狗。btw，位运算跑起来的效率比香港记者还快，多熟悉。
137. single-number-ii
- 给一个int数组，其中有一个单身狗，其他都是恰好出现三次，返回这个单身狗的值。
- ME：用HashMap搞定，第一次出现直接put，再次出现且value等于key，说明是第二次，直接让value和key不同就好了，再次出现且value不等于key，说明是第三次，remove掉。最后剩下的就是单身狗了。follow up还是要求no extra memory。异或似乎不行了。。。
- TA：这个大神标题6得不行，结合了异或、取反和与运算。至于解释，必须看这个大神的推广，适用于『一数组中大部分数出现k次，唯独一个数只出现p次』的问题。不太好理解原理，先记下来怎么写吧。将k写成
101的形式，从右往左对应x1,...,xm是否取反。xm全部初始化为0，mask也是0。遍历原数组，从xm开始更新，xm ^= x(m-1 ) & ... & x1，然后mask = ~(x1 & x2 ... & xm )，注意其中的xm有可能要取个反，例如对应于101就是mask = ~(x1 & ~x2 & x3 )，最后再从xm与一波，xm &= mask。
138. copy-list-with-random-pointer
- 一个链表，其中含有一个指向任意节点的random引用。深复制这个链表。
- ME：感觉跟前面有个复制图的很像，一开始就直接用HashMap递归着搞了，结果stack overflow。改成HashMap+iterative就AC了。
- TA：这个不用Map的constant space的方法给跪，思路是把每一个拷贝的节点拼接到原节点的后面，这样一轮循环过后所有节点都有了一份拷贝；第二轮循环就是为random赋值了，既然知道原节点之后就是对应的拷贝节点，那random的引用也就可以直接获得了。最后一轮循环则是把拷贝的节点正确地拼接起来，最后返回。66666
139. word-break
- 给一个List表示词典，给一个String，求能否把该String按照某种方式以空格分割，使得每个单词都来自于字典。
- ME：一开始用DFS搞，先建立一个以首字母开头的
map<Character, HashSet<String>>，结果超时，这个思路也就比暴力破解好在有个『首字母查找』吧。。而且又用到eclipse来找bug，扎心了。想改成BFS又不知可不可行，而且也不太会。看了一下tag，原来是DP！然而也似乎找不到状态转换在哪里。。。手足无措ing - TA：这个是一个BFS的方法，利用了visited trick加速，否则估计也是超时的。BFS思路是先直接把List转成HashSet，用Queue存放『下一个要尝试的起始索引』，trick在于用一个HashSet visited存放Queue中的这些索引，表示『这个索引之前的是true的，需要从当前索引开始尝试』，如果都已经在visited中出现过了，说明前面已经有结果覆盖到了这个索引，那么后续再碰到这个索引就不用再试了。每次遍历都从Queue中poll一个索引出来，若在Set中不存在说明没尝试过，那就一直往后尝试取子字符串是否在字典中，有就把那个截止位置索引入队，表示下一个从那里开始尝试；当截止位置达到String的末尾，说明前面都符合了，返回true即可。tag里所说的DP方法，短得令人发指，不过我更喜欢经过maxLen优化的这个。思想和BFS有点像，状态转换在于『某索引之前的部分符合字典词，那往后判断也是字典词的话就是了』。DP别总想着多维数组，一维数组难道就不能DP了么？此外，DFS经过优化也是可以的，优化点和BFS类似，利用一个Set记录走过的Path，在前面BFS中的set记录的是『该索引之前的是OK的』，而DFS这里的Set记录的是『以当前索引结尾的是不行的』，估计二者是可以转换的吧。总之这里的DP可以转换成
DFS/BFS + path memorization，面试别一上来就DP最优了。
140. word-break-ii
- 给一个List表示词典，给一个String，求所有以空格分割的单词组成的字符串，使得每个单词都来自于字典。
ME：用上面学到的DP方法搞，结果跪在一个比较长的、不存在解的情况。我就先来一个O(n^2)的DP判断一下有没有解，然后再深入DP去求，终于过了，而且速度居然超过98%，我也是一脸懵逼。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354class Solution {public List<String> wordBreak(String s, List<String> wordDict) {List<String> ans = new ArrayList<>();if (s == null || wordDict == null) {return ans;}Set<String> set = new HashSet<>();int minLen = Integer.MAX_VALUE, maxLen = 0;for (String word : wordDict) {set.add(word);minLen = Math.min(minLen, word.length());maxLen = Math.max(maxLen, word.length());}if (canForm(s, set)) {List<StringBuilder>[] bucket = new List[s.length() + 1];bucket[0] = new ArrayList<>();bucket[0].add(new StringBuilder());for (int right = 1; right <= s.length(); right++) {for (int left = Math.max(right - maxLen, 0); left < right; left++) {String curr = s.substring(left, right);if (set.contains(curr) && bucket[left] != null) {if (bucket[right] == null) {bucket[right] = new ArrayList<>();}for (StringBuilder prev : bucket[left]) {bucket[right].add(new StringBuilder(prev).append(curr).append(" "));}}}}if (bucket[s.length()] != null) {for (StringBuilder sb : bucket[s.length()]) {sb.setLength(sb.length() - 1);ans.add(sb.toString());}}}return ans;}private boolean canForm(String s, Set<String> set) {boolean[] dp = new boolean[s.length() + 1];dp[0] = true;for (int right = 1; right <= s.length(); right++) {for (int left = right - 1; left >= 0; left--) {if (dp[left] && set.contains(s.substring(left, right))) {dp[right] = true;break;}}}return dp[s.length()];}}TA：WOW，没想到这个memorized DFS方法还更优雅，思路是利用一个
Map<String, LinkedList<String>>记录以该Key开头的后续的组合。对于当前字符串s来说，首先看看字典中有没有刚好可以作为开头部分的（s.startsWith(word)），有则固定它，往后取字符串，再向后进行DFS，这样一直深入到末尾，返回一个空字符串的List。当取得后续字符串的所有组合后，就一个个取出来然后把当前的s拼到最前面，形成新的以空格分隔的组合，记得在返回当前的组合之前，要放到map里面。- StringBuilder的append会影响到原sb的，String可以直接用
+拼接。String有个startsWith方法很6。
141. linked-list-cycle
- 判断一个链表是否有环。
- ME：这个印象十分深刻好吧，快慢指针，如果碰到一起了就是有环，如果快指针都到null了还没有，就无环。
- TA：没啥，毕竟衣洗题。
142. linked-list-cycle-ii
- 返回一个链表的环的起始位置（从哪里开始进入了环），如果没有环则返回Null。
- ME：用一个HashMap瞬秒。不给用extra space的话。。。一时想不出来。。
- TA：这个解释了快慢指针的原理，若快慢指针都从head出发，从head到环的起始经过了A，假设慢指针经过A+B与快指针相遇，快指针速度是慢指针的两倍，那么快指针走过了
2*(A+B )，假设环的长度为N，快指针比慢指针就多走了一个环的距离，即A+B+N = 2*(A+B )。那么此时再来一个指针从head出发，同时慢指针也出发，往后挪A了之后，慢指针一定是回到环的起点，因为N - A = B，相当于慢指针往回挪了B。妙哉！
143. reorder-list
- 给一个链表，要求in-place地重新调整顺序，让第一个与最后一个相连、第二个与倒数第二个相连…
- ME：一开始没有用辅助函数强行递归，每次都要重新遍历求最后一个元素，怒超时一波。顿时陷入了一个江局。。。
- TA：看了这个才明白trick在哪，原来可以分三步走，第一步找到中间节点，第二步把中间节点之后的部分全部反转，第三步把前半部分和后半部分对应相连。注意按照这种方法求得的两半部分长度在偶数时前后相等，奇数时前半部分少于后半部分，因此在第三步要适当判断一下前半部分是否已经空了。
144. binary-tree-preorder-traversal
- 给一个二叉树，返回其前序遍历。要求iterative。
- ME：Stack搞定。先让右节点入栈，再让左节点入栈，每次从栈顶节点的值输出到List中。
- TA：这个Iterative的方法也是用stack，但只用存右边的节点，小优化一波。
145. binary-tree-postorder-traversal
- 给一个二叉树，返回其后序遍历。要求iterative。
- ME：双Stack搞定。
- TA：大神给出了Iterative的前中后序遍历总结。
146. lru-cache
- 实现一个cache类的put和get方法，这个cache符合Least recently used规则来覆盖旧元素。
- ME：存储键值对当然用HashMap，为了维护这个Least recently used我用的是LinkedList来不断地线性查找remove然后再add到最后，每次空间不够就poll最前面的即可。然而超时。关键就是这个LRU要如何高效更新呢？？陷入江局。。。
- TA：这个告诉你，自己新创一个DLinkedNode类构建双向链表，让Hash表由key映射到这样的节点上，每个DLinkedNode要存储key和value，value当然是为了get的时候返回，而保存key则是为了当链表的容量爆了的时候，弹出末尾的这个节点时能获得这个key，告诉map去remove。
- 双向链表的特点是插入和删除都不需要额外传入prev节点，不需要像通常单向链表那样O(n)遍历找到插入/删除的位置。
147. insertion-sort-list
- 给一个链表，实现插入排序。
- ME：用一个swapAfter用于交换当前节点后面的两个节点，比较当然也就是比较后面这两个节点辣。每次遍历完之后都回到头部，需要用一个swapped的标志表示上一次是否有交换，若已经没有交换了说明已经有序了。实现了但是神慢，没试过垫底成这样。。。
- TA：这个写得比较清晰，回头看看感觉我的那个并不能看出来是『插入排序』。正确的思路是，设置一个伪头部表示排序后的链表，每次从原链表中取一个元素，然后在新链表中遍历找到正确的插入位置进行插入。
148. sort-list
- 给一个链表，实现O(n*logn )时间复杂度的排序。
- ME：用归并排序搞定了，每次先找到中间节点，一分为二，分别去归并，直到伪头部之后只剩一个有效节点，就开始合并，前一半一定比后一半小才行，通过改next指向实现，到最后若左半部分空了而右半部分还有有效节点，直接把左半部分最后一个节点的next指向右半部分的next即可。速度还行吧，打败了38%。
- TA：差不多都是MergeSort，小伙子有眼光哇。在提交那里看到比较快的是QuickSort的，我当时没敢搞是因为对『以首元素为pivot』的快排写法没把握，之前自己练的快排都是『以中间元素为pivot然后左边都小于pivot、右边都大于pivot』。值得学习一个。
149. max-points-on-a-line
- 给平面上点的坐标的数组，求最多有多少个点共线。
- ME：一开始直接用
HashMap<Double, Integer>搞，以每个点为起点向后遍历求斜率存入Map，若Map已有该斜率则++，WA后发现对于起始点在后续遍历中重复出现，则利用一个bonus变量统计，最后统一加上去。但依旧WA，因为计算精度的问题斜率没法精确求得，会误将两个坐标较大的点的斜率算成一样的。陷入江局。。。 - TA：高票答案，既然除法求Double有精度问题，那不妨就保留被除数和除数两个Integer的最简形式呗，利用嵌套的Map，外层Map的Key是约减后的dx，内层Map的Key是约减后的dy，所谓约减就是求横坐标差dx和纵坐标差dy的最大公约数gcd除一下。此外，为何不考虑使用long存储二者交叉相乘的结果呢？看提交这里靠前的比较快的算法，有个8ms的就是直接用三重循环的long乘法判断三点共线的，前面两重是正常求两点横纵坐标差，第三重就是往后求乘法看是否共线的。
- Double的精度丢失问题！最大公约数求法有这题用的辗转相除法，还有相减法，最小公倍数则是两数之积除以最大公约数！
150. evaluate-reverse-polish-notation
- 给一个String的数组，其中包含整数或者加减乘除四种符号表示一个Reverse Polish Notation，求该算式的结果。
- ME：印象深刻好吧，数据结构还是哪里讲到的，其实就是二叉树的遍历嘛后续遍历嘛，一个Stack存Integer.valueOf(str )，出现运算符就对应处理栈顶两个整数，然后把运算结果再入栈回去，最后栈顶剩下的就是运算结果辣。
- TA：如果不用stack的话就要用到递归求操作符前面的两个操作数，用一个指针从后往前怼，因为操作符一定是出现在数字后面的。改写了一波，速度超级快。
151. reverse-words-in-a-string
- 给一个句子，将句子以空格为分割的单词依次反过来（只是反单词顺序不是反单词里面的字符内容）。
- ME：先trim一下，从后往前找空格，依次添加到StringBuilder里面。
- TA：很欣赏这个大神的代码风格，分步走、分函数，非常清晰。不过他这个的做法，大概有点绕了？他是第一步先转成charArray，一口气欠火候对调反转过来；第二步再找出每个单词的边界，再内部再调用第一步的reverse，这样就将每个单词都反转了；第三步则是整理空格，使前后无多余空格且单词之间只有一个空格，这个就有点复杂化了。。。
152. maximum-product-subarray
- 给一个int数组，求截取其中的子数组使得各int之积最大。
- ME：I know it for sure that it should be solved with DP!!!!试了很久，然而发现我的思路只适用于子数组中只有两个负号的情况。。。陷入江局。。。
- TA：我的DP还想着用三个数组呢，其中有个pos和neg的交换和这个很像，这个真的是太妙了。思路是用imax和imin分别记录以当前索引处截止的最大/最小product，当出现负数的时候，先交换imax和imin再乘以这个负数，这样就能让最大/最小保持下去，因为交换过后就是用最小负数的乘以个负数自然得到的是最大的了、用最大的正数乘以个负数自然是最小的了。妙哉啊！！！
153. find-minimum-in-rotated-sorted-array
- 给一个int数组，原本已经从小到大排好序了，从某个元素开始前半部分和后半部分对调位置（rotate），求最小元素。此题数组中的元素不会重复。
- ME：一开始纳闷这题O(n)不就搞定了嘛，后来突然感觉四层相识，这种rotate过后『一定有一半的元素是正确的升序排列』，所以用类似于二分查找的方法来搞非常合适。所以就用二分查找搞定咯。
- TA：这个简洁好多，判断条件少了速度自然就快了。当left已经小于right，说明本身有序，直接返回left对应的即可；否则，当left小于mid，而left又大于right，说明应该在右半部分，因此
left = mid + 1，否则right = mid。不过为了和后面的对应，我都统一改写成了用mid和right比较来判断哪半部分有序。
154. find-minimum-in-rotated-sorted-array-ii
- 与上题的区别在于可能重复。
- ME：与上题相比增加了相等的判断，而且为了处理
[10,1,10,10,10]这样的情况即左中右均相等，还用到了recursive的方法向前、后半部分分别去找。过是可以过，但是很慢。 - TA：这个也是很简洁，我结合前一题改写成了这个。先根据left和right比较来判断是否本身有序，否则用mid和right比较判断哪半部分有序。对于mid与right相等的情况，则只能通过right一点点向前挪的方式来处理了，所以最坏情况是O(n)，其实和我上面递归的一样。
155. min-stack
- 实现一个最小栈，除了正常stack的push, top, pop操作，还要在constant time内返回当前栈内的最小值。
- ME：两个LinkedList搞定，一个正常按照后入先出的方式存元素，另一个则是起一个标记的作用，表示当前位对应的最小值是多少。然而速度比较慢。
- TA：这个只用一个stack和一个整数标记实现的答案很厉害。思路是每次在push的时候，如果这个元素比之前标记的Min还要小，那么就先把原本标记的min给push进去，紧接着再把新的元素push进去，同时更新min。对应地，在pop的时候如果发现和标记的min相同，就需要把栈中前面一个元素也pop出来赋给min，相当于一个恢复的过程。我还发 现了个bug就是stack为空的时候，调用getMin，LeetCode本身的代码竟然跑不出来。123456789101112131415161718192021222324252627282930313233343536373839// 升级的做法是用双stack，但minStack存放的是num-count pair，避免重复存放相同元素class MinStack {Deque<Integer> stack;Deque<int[]> minStack;/** initialize your data structure here. */public MinStack() {stack = new ArrayDeque<>();minStack = new ArrayDeque<>();}public void push(int x) {stack.push(x);if (minStack.isEmpty() || x < minStack.peek()[0]) {minStack.push(new int[] {x, 1});} else if (x == minStack.peek()[0]) {minStack.peek()[1]++;}}public void pop() {if (!minStack.isEmpty() && minStack.peek()[0] == stack.peek()) {minStack.peek()[1]--;if (minStack.peek()[1] == 0) {minStack.poll();}}stack.poll();}public int top() {return stack.peek();}public int getMin() {return minStack.isEmpty() ? 0 : minStack.peek()[0];}}
156. binary-tree-upside-down
- 给一个左优先二叉树，即每一个子树要么没有右子树、有右子树就一定是叶子且有对应的左子树。将树上下颠倒并把原右节点变成左leaf节点，返回转换后的树。
和逆转链表非常类似，也是考察递归、迭代的两种写法。递归时，root在上下反转之后就一定是在最下层的，root.left则会被提到root上方，root.right平移到左边。
12345678910111213class Solution {public TreeNode upsideDownBinaryTree(TreeNode root) {if (root == null || root.left == null) {return root;}TreeNode newRoot = upsideDownBinaryTree(root.left);root.left.left = root.right;root.left.right = root;root.left = null;root.right = null;return newRoot;}}iterative从root开始，从底层一步步构建新的树。新的root就是当前的left，当前的left应该是上一层的right、当前的right应该是上一层的root，然后需要传递当前的right到下一层去。
1234567891011121314151617181920class Solution {public TreeNode upsideDownBinaryTree(TreeNode root) {TreeNode curr = root;TreeNode next = null;TreeNode prevRight = null;TreeNode prev = null;while (curr != null) {next = curr.left;curr.left = prevRight;prevRight = curr.right;curr.right = prev;prev = curr;curr = next;}return prev;}}
157. read-n-characters-given-read4
- 给一个API read4，每次从某个source读取至多4个字符存入输入的char数组，返回值表示实际读入的字符。利用这个API实现readN.
- 手动实现，在read4时先判断还有没有剩余字符，有才继续操作。123456789101112131415161718192021222324/* The read4 API is defined in the parent class Reader4.int read4(char[] buf); */public class Solution extends Reader4 {/*** @param buf Destination buffer* @param n Maximum number of characters to read* @return The number of characters read*/private int N = 4;public int read(char[] buf, int n) {int index = 0;char[] temp = new char[N];int add = read4(temp);while (add > 0) {int j = 0;while (n > 0 && j < add && index < buf.length) {buf[index++] = temp[j++];n--;}add = read4(temp);}return index;}}
158. read-n-characters-given-read4-ii-call-multiple-times
- 给一个API read4，每次从某个source读取至多4个字符存入输入的char数组，返回值表示实际读入的字符。利用这个API实现readN.与上一题不同的是，每个call之间不是独立的，上一次如果读了4个但只consume了2个，那么这次要先consume上次没有用掉的字符。
- 用全局变量存放上一次读了多少和上一次index指向了哪里。123456789101112131415161718192021222324252627282930313233public class Solution extends Reader4 {/*** @param buf Destination buffer* @param n Maximum number of characters to read* @return The number of characters read*/private int N = 4, tempIndex = 0, lastLimit = 0;char[] temp = new char[N];public int read(char[] buf, int n) {if (n < 1) {return n;}int index = 0;if (tempIndex == lastLimit) {lastLimit = read4(temp);tempIndex = 0;}while (lastLimit > 0) {while (n > 0 && tempIndex < lastLimit && index < buf.length) {buf[index++] = temp[tempIndex++];n--;}// 如果n读够了，直接返回if (n == 0) {return index;}// 如果tempIndex到头了，可以继续读lastLimit = read4(temp);tempIndex = 0;}return index;}}
160. intersection-of-two-linked-lists
- 给两个单向链表，求其中是否有交汇点。
- ME：之前有一个求环的起始点的，和这个有那么一丢丢相似。我的思路是，从两个链表头出发，每次都判断是否相等，一旦相等就直接是交汇点了。若不等，则继续后移，当其中一个已经移到Null的时候，就跳转到另一条链表的头部，这样继续找。在纸上画画能看出来，假设链表A的独立部分长度为m，公共部分长度为a，链表B的独立部分为n，那么从A出发的指针经过了m+a+n，从B出发的指针经过了n+a+m，二者交汇的地方恰好就是交汇点。不过一开始陷入了死循环，这是因为没有设置一个shift的标志，因为至多只可能这样从null跳到另一条链表两次。
- TA：额，怎么我的方法反而没有暴力pass两个链表求长度
O(A.length + B.length + max[lenA,lenB])快。。。Anyway，我的思路和这个一样，O(m + n + a )，应该比暴力pass稍快一点才对？他没有用到shift标志，而是直接比较两个ptr来控制循环跳出，比我高明。
161. one-edit-distance
- 给两个字符串s和t，问是否是one edit away，即往s中插入、删除、替换一个字符后得到t。
- 插入和删除是可以看作是互逆操作，可以用一个函数实现；替换用另一个函数实现。12345678910111213141516171819202122232425262728293031323334353637383940414243class Solution {public boolean isOneEditDistance(String s, String t) {if (s == null || t == null || Math.abs(s.length() - t.length()) > 1) {return false;}if (s.length() > t.length()) {return checkInsert(t, s);} else if (s.length() < t.length()) {return checkInsert(s, t);} else {return checkReplace(s, t);}}private boolean checkInsert(String src, String dest) {int ptr1 = 0, ptr2 = 0, end1 = src.length(), end2 = dest.length();boolean inserted = false;while (ptr1 < end1 && ptr2 < end2) {if (src.charAt(ptr1) != dest.charAt(ptr2)) {if (inserted) {return false;}inserted = true;} else {ptr1++;}ptr2++;}return true;}private boolean checkReplace(String src, String dest) {int end = src.length();boolean replaced = false;for (int i = 0; i < end; i++) {if (src.charAt(i) != dest.charAt(i)) {if (replaced) {return false;}replaced = true;}}return replaced; // 一定要有replace才行}}
162. find-peak-element
- 给一个数组，求峰值对应的下标。峰值指的是比左右两邻居都大。要求时间复杂度O(logN)。
- ME：相当于在一个无序数组中找最大值的索引？为什么不求最大值本身而是求对应的索引？本身无序还怎么二分、怎么满足O(logN )？？反正我暴力O(n )是过了。。。不是很懂这题能有什么trick。
- TA：原来真的理解错题意了，这题不是求maximum，只是要求任意一个合法的峰值，只要它比旁边两个邻居大就可以。针对这题的二分法与一般的二分多出来一个
mid2 = mid1 + 1，每次判断的时候就比较mid1和mid2对应的值就行了，若小于则left = mid2，否则right = mid1。这题略无聊。。。
163. missing-ranges
- 给一个排好序的int数组和lower & upper bound(inclusive)，求missing的range List，用string表示每一段缺失的内容。如
nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99，就缺失了["2", "4->49", "51->74", "76->99"]。 - 直接遍历一波，利用一个expectedValue来判断是否出现了缺失。若当前数num大于expectedValue，说明expectedValue到num - 1都是缺失的。注意有个overflow问题，需要将expectedValue声明成long.1234567891011121314151617181920212223242526class Solution {public List<String> findMissingRanges(int[] nums, int lower, int upper) {List<String> ans = new ArrayList<>();if (nums == null) {return ans;}long expectedVal = lower;for (int num : nums) {if (num < expectedVal) {continue;} else {if (num > expectedVal) {ans.add(getString((int) expectedVal, num - 1));}expectedVal = (long) num + 1;}}if (expectedVal <= (long) upper) {ans.add(getString((int) expectedVal, upper));}return ans;}private String getString(int start, int end) {return start == end ? String.valueOf(start) : String.format("%d->%d", start, end);}}
164. maximum-gap
- 给一个乱序数组，要求O(n )的时间和空间复杂度内求它对应的有序数组中相邻两元素的最大gap。所有元素都是32-bit正整数，
- ME：一开始又想到木桶排序了，毕竟O(n )又是正整数的，然而如果出现2147483647的话又会爆内存，只能另寻出路。偷看了下tag，只写了个sort，废话。。。
- TA：真的是可以用bucket木桶法的，关键是如何压缩bucket不要浪费空间。该答主的做法是，首先O(N )一遍找出min和max值，然后利用min, max, 数组本身元素数确定gap值（
gap = ceiling[(max - min ) / (N - 1 )]），因为N个数就有N-1个相邻间隔，平均分布值再取个ceiling得到的就是『尽量大』的平均gap。其实这貌似是个鸽子洞理论。维护两个bucketMIN和bucketMAX，其索引表示的是『当前数字距离最小值大概占了平均gap的多少份』，计算索引用index = (num - min ) / gap，MIN和MAX木桶分别存储相同份数数字中的最小和最大值，这样就完美地解决了木桶空间浪费的问题。最后再从头到尾遍历，取MIN木桶值与前一个MAX木桶的值相减看看间隔多少，而同一索引对应的MIN和MAX就不用比了，因为一个平均gap都没到，当然比不过大于一个gap的了（牢记索引的含义是gap的份数，因此相邻的索引所存数字的间隔必然超过一份gap）。这个方法，妙是妙，但得学会怎么迁移到别的问题呢。。。此外，还有使用基数排序的这个方法，原来基数排序的时间复杂度也是O(dN )的！基数排序就是根据个十百千万等各个位置的数字大小，利用一个count数组记录每个该位出现了多少个数字，然后将count从前往后加一波，表示『以当前索引i为当前位的数字num在新数组中的位置必须在count[i-1]以后』，此时再引入一个aux辅助数组，在原数组从后往前取数字判断它在aux中的索引。最后排好序了再一波流看看相邻的最大间隔是多少。挺好的，通过这个对基数排序又学习了一波。
165. compare-version-numbers
- 给两个表示版本号的字符串，比较谁更新，返回1/0/-1。
- ME：直接从头部开始找小数点，找到了就Integer.valueOf得出数值，两者比较，一旦不相等就可以输出结果了。若相等再继续往后找。若前面都相等但二者长度不同，需要继续往更长的那串后面确认数值，如果都是0那二者版本号还是一样的。
- TA：这个又用到了强大的split函数，根据小数点将String拆分存储到数组中，然后取较长者作为界限进行遍历，若其中一个数组超出了自身的界限则直接赋值为0.同时为了方便，直接用Integer类的compareTo函数，直接就返回的是1/0/-1。
166. fraction-to-recurring-decimal
- 将分数转换成小数，若是无限循环小数则将循环部分用括号括起来，如
0.16666 = 0.1(6 )。 - ME：一开始的想法很简单，int越界问题用long搞定，确认完符号就直接开始除，出现小数点后每次从后往前取2、4、6看看是否出现了重复，若重复就直接当成循环输出了，对于连续出现的单个数字还好办，直接判断一下数字就好了，但是对于多个数字就不行了。。后来不断思考，又不小心瞄了一眼discuss看到了HashMap，突然想到我为什么要先插入再比较呢，为什么不直接利用HashMap把当前的被除数与对应的小数点位置存起来呢？当被除数在之前出现过，就一定会开始循环，那么获得它首次出现时对应的位置，然后插入一个
(，最后再append一个)，不就美滋滋了？果然OK了。。。 - TA：差不多的思路，怎么大神的版本就简洁这么多呢。首先对于符号处理就很优雅，一个异或就确定了要不要加负号。然后整数部分直接一除就出来了，HashMap中存储的索引直接就是被除数所对应的商的位置，这样直接就能替换了。还有一个更短的，循环条件直接就是看有没有出现重复的被除数，最后直接将结果用0用括号括起来，若是循环部分则是有效的，可以保留；若没有循环，最后的结果就是0，因此输出前直接将
(0 )替换掉就好。 StringBuilder.replace("target", "newStr" );
167. two-sum-ii-input-array-is-sorted
- 给一个排好序的数组，再给一个target，求两个索引使得索引对应的数字之和等于target。
- ME：印象深刻好吧，第一题就是它，当时我用到就是先排序再二分查找的办法。这里也可以。此外还用了学到的HashMap记录索引的方法，也可以。
- TA：tag给了个two pointer，原来有个O(N )的方法，思想和二分有点点像吧，前后两个指针对应的数字相加，与target比较，大了则右指针向前、小了则左指针向后。二分得有O(N * logN )吧。
168. excel-sheet-column-title
- 输入一个int，转换成excel中的那种column字母。
- ME：循环除法和取模搞定。但是速度怎么那么慢？？？
- TA：丧心病狂，递归一行就解决了。。。
169. majority-element
- 给一个数组，求其中的majority number。mj指的是出现次数超过一半规模的数字。
- ME：傻傻地用HashMap来存每个数字出现的次数，达到就输出。
- TA：这里介绍了三种方法。一是直接sort一下，取中间索引的即可，因为超过一半嘛，就算是最小/最大值，也得越过中线啊。还有一个是Moore voting方法，利用一个count计数，假设首位为major开始，往后遍历，如果当前元素与major匹配则count++，否则count–，当count到达0的时候说明前面打成平手没有谁是major，那么再设置当前元素为major继续向后pk。毕竟极端情况是major刚好比不major的元素多1个，因此一定会保证count到最后胜者为王。
170. two-sum-iii-data-structure-design
- 实现一个class，包含add（加入新的数字）和find（给定sum判断是否包含两个数字相加得到该sum）。
- 使用Map记录每一个加入number及其个数，在find的时候减一下即可。12345678910111213141516171819202122232425262728293031class TwoSum {private Map<Integer, Integer> map;private int min, max;/** Initialize your data structure here. */public TwoSum() {map = new HashMap<Integer, Integer>();min = Integer.MAX_VALUE;max = Integer.MIN_VALUE;}/** Add the number to an internal data structure.. */public void add(int number) {min = Math.min(number, min);max = Math.max(number, max);map.put(number, map.getOrDefault(number, 0) + 1);}/** Find if there exists any pair of numbers which sum is equal to the value. */public boolean find(int value) {if (value < 2 * min || value > 2 * max) {return false;}for (int n : map.keySet()) {if (map.containsKey(value - n)) {if (n == value - n && map.get(n) < 2) {continue;}return true;}}return false;}}
171. excel-sheet-column-number
- 与168对应，给的是excel中column字母的字符串，返回对应的数字。
- ME：直接循环，
ans = ans * 26 + (ch - 'A' + 1 )搞定。 - TA：没啥。
172. factorial-trailing-zeroes
- 在logarithmic时间复杂度内求N的阶乘末尾有几个0。
- ME：这个衣洗题竟然搞得我毫无头绪，给的tag就只有个Math。有什么规律啊？？？
- TA：这个的思路很清楚，在阶乘中末尾产生
0完全可以归结于2 * 5，而2的数量肯定比5多多了，因此我们就判断一下当前数字可以拆分成几个5即可，有几个5就能产生几个trailing zeroes。为什么这么做是logarithmic呢？这里给出了解释，对应的iterative实现这里其实是log5(N )的复杂度，以5为底数。
173. binary-search-tree-iterator
- 给一个二分查找树的根节点，实现next和hasNext函数，前者每次返回下一个未访问的最小节点int值。要求这两个函数的时间复杂度为常数，空间复杂度为O(height)，即数的高度。
- ME：卡在了iterative实现中序遍历这儿n久。最后还是参考了这个才搞出来这个。但是！不符合要求！因为你这一波遍历就是彻底的中序遍历，不只是O(h )而是O(N )了。
- TA：看了这个才明白，原来不需要在一开始就中序遍历把整个树搞出来，而是『breaks in-order traversal into hasNext( ) and next( )』。一开始只是尽可能地把左节点放入栈，当调用了next再把栈顶弹出，同时检查栈顶对应的这个节点是否有右节点，有则入栈并继续深挖左节点入栈。
- need to get more familiar with iterative *-order traversal.12345678910111213141516171819202122232425262728public class BSTIterator {Stack<TreeNode> stack;public BSTIterator(TreeNode root) {TreeNode curr = root;stack = new Stack<TreeNode>();while (curr != null) { // cache left sub in stackstack.push(curr);curr = curr.left;}}/** @return whether we have a next smallest number */public boolean hasNext() {return !stack.isEmpty();}/** @return the next smallest number */public int next() {TreeNode ret = stack.pop(); // pop the left mostTreeNode curr = ret.right;while (curr != null) { // then go into rightstack.push(curr); // continue to push left subcurr = curr.left;}return ret.val;}}
174. dungeon-game
- 给一个二维int数组，骑士从左上角出发，到右下角去救公主，没到达一个各自就会加血/扣血，一旦血为0就挂，求初始最少要有多少血。
- ME：DP搞定，二维数组dp[i][j]表示到达当前位置所需要的最少血，公主所在位置当然就是1了。更新从右下角开始，由于每个格子可能加血（正值）可能扣血（负值）。如果是负值，直接用dp减去它就是该位置之前一位（左、上）的最小血；如果是加血，显然不能从负数往上加，那么就需要与1作个判断，如果不是正数了那么前一位直接赋值为1.
- TA：我的思路和这个类似，不过答主是直接存储的是前一步应有的最小血了。没啥了。
175. largest-number
- 给一个非负的int数组，用它们拼成一个最大的数字，以String的形式返回。
- ME：原本的思路是直接将int转换成String来搞，自定义实现Comparator的compare函数，高位数字越大的就排前面，若相同部分长度相等，则需要继续向后与首位元素进行比较。就是在这里疯狂地WA，头晕眼花，条件判断太多了。边缘情况例如
[830,8308]这种，你说怎么排序？我只能想到，当与首位又相同时，需要假设进行拼接，挪动指针来判断，例如8308308和8308830这两个，就需要指针i和j分别来到8和3，这样就能看出是要8308排在前面了。 - TA：我他喵的就呵呵了，直接拼接之后用String的compareTo就搞定了，我相当于手动实现了一遍。。。
186. reverse-words-in-a-string-ii
- 给一个char数组，反转单词出现顺序。
I love programming变成programming love I。 - 先反转全部，再根据空格位置反转每个单词。12345678910111213141516171819202122232425class Solution {public void reverseWords(char[] str) {if (str == null || str.length == 0) {return;}reverse(str, 0, str.length - 1);int start = 0;for (int i = 0; i < str.length; i++) {if (str[i] == ' ') {reverse(str, start, i - 1);start = i + 1;}}reverse(str, start, str.length - 1);}private void reverse(char[] str, int start, int end) {while (start < end) {char temp = str[start];str[start] = str[end];str[end] = temp;start++;end--;}}}
187. repeated-dna-sequences
- 给一个字符串表示DNA基因序列，求其中出现次数超过一次的长度为10的子串。
- ME：用Map记录每个子串出现的位置，后续再出现的话就放入set，最后遍历set存入list返回。一开始WA是因为不知道竟然重叠也可以算，我还以为一定要完美重复即前后错开呢。
- TA：这个告诉你，不用管前后索引重叠的话，直接用Set就可以判断『是否已经出现过』。此外，还有使用bit manipulation的，直接用数组实现map映射关系，因为字符都是确定的，只有那四种，那每次就取个差值就好啦，那么四种情况对应的就是两个bit，那么每次都右移两位再把当前字符的数值『或』上去，总共是20个Bit，这时再放进set里。注意有个trick是利用set.add的返回值判断是否重复了，而且需要额外的一个set防止重复输出，例如
"TTTTTTTTTTTTT"。 - [HashSet的遍历方法]有(1 )for-each (2 )Iterator
it; while (it.hasNext( ) )。
188. best-time-to-buy-and-sell-stock-iv
- 前面第123题的升级版，各一个整数数组表示股票价格走势，给定交易次数k（买卖各一次为一次交易），求最大收益。
- ME：前面123题那个两次交易的都勉勉强强搞定，这个k次交易的直接懵逼。我按照123看到的这个推广写了出来，但是爆内存了。我观察了一下，发现每次都只是用到上次的结果，因此可以把行数压缩成两行，但是又超时。陷入江局了。。。
- TA：这个告诉你原来当允许交易的数目大于等于长度的一半的时候，说明所有差值都可以纳入profit，直接一波流累计就好，不用DP慢慢搞了，终于过了。不过上面那个答案空间浪费挺多的，在提交这里最快的那个方法所用的优化是直接用两个数组（而不是我原本的二维数组）来存，最后直接交换一下就好。解决了之后真是神清气爽，希望可以牢记。
189. rotate-array
- 给一个数组，给一个k，要求rotate k，即所有元素一次向后挪k，末尾的k个元素则放到最前面。至少有三种方法。其中可以办到in-place。
- ME：用了规模为k的辅助数组，结合System.arraycopy完成的。总觉得in-place的有见到过，但想不出来。。。
- TA：原来这么简单，先整个反转，然后分段reverse。我就隐约感觉是要用到swap的，就是没想过要reverse之后再swap。这个是总结，其中第四个方法原帖在这里，就是梦寐以求的『直接根据正确的索引来swap』，确实不好想，而且这是C/C++中才有的数组名字就是个指针，因此可以在swap的时候任意挪动，这样前面已经到达正确位置的数字就不会参与到后续的swap了，而Java似乎办不到？
190. reverse-bits
- 给一个int，但是要把他当成无符号的数字，将该数字对应的bit串反转，得到对应的int输出。
- ME：首先我想的是，从原数字的最低位开始，用一个pivot和它逐位去与，获得的结果插入到新数字的末尾。交的这个版本没有办法处理超出Integer范围的问题。。。
- TA：参考了这个，答主用了『unsigned shift』
>>>，此外还有个边缘情况，就是当已经算到原数字最高位的时候，就不用再对ans进行左移了。至于follow-up问到的，如果这个函数多次被调用，如何优化？这种『反复被调用』的情况，很自然地想到优化之处在于cache，将之前算过的结果存下来。答主的策略是利用8 bit的byte存放计算过的结果，map
191. number-of-1-bits
- 给一个int，但是要把他当成无符号的数字，计算该数字的bit形式有多少个1。
- ME：用一个pivot从1开始往左移，和该数字作与，结果非0则该位为1，统计即可。
- TA：额，也可以反方向，每次都直接用1和它与，用
>>>获得前一位bit。一定要是『unsigned shift』！ - 位运算的优先级不如一般的
==, !=, <等，如果不加上括号可能出现『bad operand types for binary operator “&”』。
198. house-robber
- 给一个int数组表示每一户的财产，不能抢相邻的人家，问最多可以搞到多少财产。
- ME：有点DP的意思，不过只需要维护到前一家和再前一家为止能得到的财产。如果抢当前索引，则只能加到再前一家的财产，如果不抢当前索引，则还是维持前一家为止的数目。
- TA：没啥了。
199. binary-tree-right-side-view
- 给一个二叉树，返回从右侧看这个树所能看到的节点，从上到下输出。
- ME：也就是求每一层的最右侧节点吗，用BFS做level遍历，到达每层的最后一个节点时，即size - 1时便把值存起来就好。
- TA：DFS也能做，利用level来判断到达了哪一层。
200. number-of-islands
- 给一个二维char数组，其中只含有
'0'或'1'两种字符，分别表示水和陆地，上下左右直接相邻的两个陆地算作相连，求有几片独立的陆地。和前面130有一点点相似，然而只想起来了DFS。 - ME：申请了额外的二维int数组存放对应的陆地编号，当发现原char数组为陆地而辅助数组中尚未标记，就开始DFS上下左右，分别赋值为当前的陆地编号。原以为会超时，没想到这么朴素的DFS也能过。后来利用内部类定义坐标，用Queue改写成了BFS，结果速度更慢。
- TA：DFS和BFS大同小异。前面130没搞定的并查集方法，在这题里也可以用，比如这个，修改了一波，结合前面比较规范的130（加了rank）写出来了这个，速度也不快。。。并查集记得是大二在讲图论的时候介绍的，所以涉及什么连通性问题、可达不可达之类的就可以考虑。在UF类中维护一个id数组，这个id表示当前索引的祖宗的索引，若
id[idx] = idx说明它本身就是老大，初始时每个元素都是自己的老大。find(p)函数就是返回p的老大的索引，union(p, q)函数就是将索引p和q两伙合并起来，分别找到p和q的老大索引pRoot和qRoot，但是他们谁隶属于谁呢？rank就是在这时候起作用，将rank高的保留，rank低的老大合并到更高的老大那去，若两个老大一样，就随意了，合并后新老大的rank要加加。在外层函数真正使用UF的时候，遍历棋盘，遇到1就检查右方和下方的邻居是不是1，是就进行Union。在UF中还有一个count变量，其实就是算有几个独立老大的，初始时每个1都是老大，而每次成功调用union是count都会减减。