Leetcode

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.“Example:Input: citations = [0,1,3,5,6]Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, her h-index is 3.Note:If there are several possible values for h, the maximum one is taken as the h-index.Follow up:This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.Could you solve it in logarithmic time complexity?难度：medium题目：给定一个研究人员的引用数组(每个引用都是一个非负整数)，编写一个函数来计算研究人员的h-index。根据维基百科关于h-index的定义，一个科学家的h-index为h，即其N篇文章中有h篇的引用不低于h, 并且其它文章引用数不超过h.思路：弄清题义即可。Runtime: 3 ms, faster than 100.00% of Java online submissions for H-Index II.Memory Usage: 43 MB, less than 6.00% of Java online submissions for H-Index II.class Solution { public int hIndex(int[] citations) { if (null == citations || citations.length < 1) { return 0; } int n = citations.length; int hIndex = 0; for (int i = n - 1; i >= 0; i–) { if (citations[i] >= n - i) { hIndex++; } else { break; } } return hIndex; }} ...

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.“Example:Input: citations = [3,0,6,1,5]Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, her h-index is 3.Note: If there are several possible values for h, the maximum one is taken as the h-index.难度：medium 题目：给定一个研究人员的引用数组(每个引用都是一个非负整数)，编写一个函数来计算研究人员的h-index。根据维基百科关于h-index的定义，一个科学家的h-index为h，即其N篇文章中有h篇的引用不低于h, 并且其它文章引用数不超过h.思路：弄清题义即可。Runtime: 3 ms, faster than 100.00% of Java online submissions for H-Index.Memory Usage: 37.2 MB, less than 65.22% of Java online submissions for H-Index.class Solution { public int hIndex(int[] citations) { if (null == citations || citations.length < 1) { return 0; } Arrays.sort(citations); int n = citations.length; int hIndex = 0; for (int i = n - 1; i >= 0; i–) { if (citations[i] >= n - i) { hIndex++; } else { break; } } return hIndex; }} ...

当我第一次看到这个题目时候我我心想不就是两数相除嘛，这么简单的题目为什么要放到 Medium 中，事实证明我当时的想法Too young,Too simple,Too naive 以至于被打脸n次，可以直接查看最后答案，中间我的思路自白可以忽略。题目大意给两个数字，除数和被除数，在不使用乘、除、取模的方法做除法，返回两数之商备注：1.除数和被除数都是32位有符号整数2.除数不为03.假设我们正在处理一个只能在32位有符号整数范围内存储整数的环境[−231, 231 − 1],对于这个问题如果结果溢出了，则可以返回231 − 1解题代码public class Solution { /整体思路是用减法/ public int divide(int dividend, int divisor) { // 符号相同用减法 if(dividend==Integer.MIN_VALUE&&divisor==-1) { return Integer.MAX_VALUE; } if ((dividend ^ divisor) >= 0) { return getQuotientUsesSubtraction(dividend, divisor); } else { int absDividend = Math.abs(dividend); int absDivisor = Math.abs(divisor); if (absDividend < 0) { absDivisor = -absDivisor; } else if (absDivisor < 0) { absDividend = -absDividend; } return 0 - getQuotientUsesSubtraction(absDividend, absDivisor); } } /** * 使用减法获取两个数的商 除数dividend，被除数divisor * 条件：dividend*divisor >0 且divisor>0 */ private int getQuotientUsesSubtraction(int dividend, int divisor) { int quotient = 0; if (dividend >= 0) while (dividend >= divisor) { quotient++; dividend = dividend - divisor; } else { while (dividend <= divisor) { quotient++; dividend = dividend - divisor; } } return quotient; }}测试用例用的是 junit5，如果是4或者3的胖友自己修改下import org.junit.Assert;import org.junit.jupiter.api.DisplayName;import org.junit.jupiter.api.Test;@DisplayName(“不用乘除取模运算计算除数”)public class TestSolution { @Test @DisplayName(“MIN_VALUE情况和1”) void e1() { int out = Integer.MIN_VALUE; Solution s = new Solution(); Assert.assertEquals(out, s.divide(Integer.MIN_VALUE, 1)); } @Test @DisplayName(“MIN_VALUE情况和-1”) void e9() { int out = Integer.MAX_VALUE; Solution s = new Solution(); Assert.assertEquals(out, s.divide(Integer.MIN_VALUE, -1)); } @Test @DisplayName(“除数是0情况”) void e2() { int out = 0; Solution s = new Solution(); Assert.assertEquals(out, s.divide(0, 1)); } @Test @DisplayName(“符号相反”) void e3() { int out = -1; Solution s = new Solution(); Assert.assertEquals(out, s.divide(1, -1)); } @Test @DisplayName(“符号相同”) void e4() { int out = 1; Solution s = new Solution(); Assert.assertEquals(out, s.divide(-1, -1)); } @Test @DisplayName(“除数MIN_VALUE和被除数MAX_VALUE”) void e5() { int out = -1; Solution s = new Solution(); Assert.assertEquals(out, s.divide(Integer.MIN_VALUE, Integer.MAX_VALUE)); } @Test @DisplayName(“除数MAX_VALUE和被除数MIN_VALUE”) void e6() { int out = 0; Solution s = new Solution(); Assert.assertEquals(out, s.divide(Integer.MAX_VALUE, Integer.MIN_VALUE)); } @Test @DisplayName(“冒烟测试10,3”) void e7() { int out = 3; Solution s = new Solution(); Assert.assertEquals(out, s.divide(10, 3)); } @Test @DisplayName(“冒烟测试7,-3”) void e8() { int out = -2; Solution s = new Solution(); Assert.assertEquals(out, s.divide(7, -3)); }}时间和空间复杂度看到上面的运行时间心里凉了大半啊！，看来还有更好的方法，有时间的话写一下最优解的思路,此处立下flag，我要写 Part 2靠大家初级解题思路（????♀️此处开始为我折腾过程不重要，可以忽略）既然乘、除、取模都用不了就用减法吧。两数取商用减法的角度思考????就是，被除数可以减几个除数。因为题目取值范围是包含负值的所以要区分符号，相同符号则返回正数，符号相反则返回负值第一次尝试（失败????）思路：取两个数的绝对值当被除数大于除数时，计算相减次数，小于时则直接返回0当两数相同符号则返回相减次数，符号相反则返回相减次数负值代码：class Solution { public int divide(int dividend, int divisor) { int absDividend= Math.abs(dividend); int absDivisor= Math.abs(divisor); int quotient =0; while(absDividend>absDivisor){ quotient++; absDividend=absDividend-absDivisor; } if((dividend^divisor)>= 0){ return quotient; }else{ return 0-quotient; } }}结果 自测的两个冒烟测试用例通过，但是用例[1,1]没用通过第二次尝试（失败????）分析失败原因 循环的时候没有考虑相等的情况修改方式while(absDividend>absDivisor)改为while(absDividend>=absDivisor)修改后[1,1]用例通过，但是未通过用例[-2147483648,-1]第三次尝试（失败????）分析失败原因 没有考虑负数的最大值的绝对值溢出了修改方式 修改思路 1.符号相同的时候直接获取相减次数 2.符号不同的时候，取两数的绝对值 3.判断两数的绝对值是否大于0，（小于0的情况是取值为−231） 4.大于0时，返回相减次数的绝对值 5.小于0时，将大于0的数取反数再计算相减次数，返回相减次数的反数代码class Solution { public int divide(int dividend, int divisor) { // 符号相同用减法 if ((dividend ^ divisor) >= 0) { return getQuotientUsesSubtraction(dividend, divisor); } else { int absDividend = Math.abs(dividend); int absDivisor = Math.abs(divisor); if (absDividend < 0) { absDivisor = -absDivisor; } else if (absDivisor < 0) { absDividend = -absDividend; } return 0 - getQuotientUsesSubtraction(absDividend, absDivisor); } } private int getQuotientUsesSubtraction(int dividend, int divisor) { int quotient = 0; if (dividend >= 0) while (dividend >= divisor) { quotient++; dividend = dividend - divisor; } else { while (dividend <= divisor) { quotient++; dividend = dividend - divisor; } } return quotient; }}结果 未通过用例[-2147483648,-1]，但是可以处理除数或被除数为-2147483648的其他用例可以处理第四次尝试（成功✌️）分析失败原因 没有考虑负数最大值除以-1导致溢出修改方式 直接将这个用例视为特殊情况处理之，直接返回整值最大 ...

Write a program to find the n-th ugly number.Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example:Input: n = 10Output: 12Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.Note: 1 is typically treated as an ugly number.n does not exceed 1690.难度：medium题目：写程序找出第n个丑数。丑数公因子只由2,3,5构正的正整数。思路：三路指针。Runtime: 2 ms, faster than 99.79% of Java online submissions for Ugly Number II.Memory Usage: 36.8 MB, less than 32.39% of Java online submissions for Ugly Number II.class Solution { public int nthUglyNumber(int n) { int[] ugly = new int[n]; ugly[0] = 1; int p2 = 0, p3 = 0, p5 = 0; for (int i = 1; i < n; i++) { ugly[i] = Math.min(ugly[p2] * 2, Math.min(ugly[p3] * 3, ugly[p5] * 5)); if (ugly[i] == ugly[p2] * 2) { p2++; } if (ugly[i] == ugly[p3] * 3) { p3++; } if (ugly[i] == ugly[p5] * 5) { p5++; } } return ugly[n - 1]; }} ...

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and .Example 1:Input: “2-1-1"Output: [0, 2]Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2Example 2:Input: “23-45"Output: [-34, -14, -10, -10, 10]Explanation: (2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10难度：medium题目：给定一包含数字和操作符的字符串，计算并返回其所有数字与操作符组合的结果。有效的操作符为+,-,思路：类似unique binary tree, generate parentheses. 卡特兰数。 Runtime: 2 ms, faster than 84.52% of Java online submissions for Different Ways to Add Parentheses.Memory Usage: 38.6 MB, less than 18.35% of Java online submissions for Different Ways to Add Parentheses.class Solution { public List<Integer> diffWaysToCompute(String input) { return diffWaysToCompute(input, 0, input.length()); } private List<Integer> diffWaysToCompute(String str, int start, int end) { if (!hasOperator(str, start, end)) { List<Integer> result = new ArrayList<>(); result.add(Integer.parseInt(str.substring(start, end))); return result; } List<Integer> root = new ArrayList<>(); for (int i = start; i < end; i++) { char c = str.charAt(i); if (’+’ == c || ‘-’ == c || ‘’ == c) { List<Integer> left = diffWaysToCompute(str, start, i); List<Integer> right = diffWaysToCompute(str, i + 1, end); for (Integer l: left) { for (Integer r : right) { if (’+’ == c) { root.add(l + r); } else if (’-’ == c) { root.add(l - r); } else if (’’ == c) { root.add(l * r); } } } } } return root; } private boolean hasOperator(String s, int start, int end) { for (int i = start; i < end; i++) { char c = s.charAt(i); if (’+’ == c || ‘-’ == c || ‘*’ == c) { return true; } } return false; }} ...

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:Integers in each row are sorted in ascending from left to right.Integers in each column are sorted in ascending from top to bottom.Example:Consider the following matrix:[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]Given target = 5, return true.Given target = 20, return false难度：medium题目：设计高效算法在矩阵中搜索给定的值。矩阵特性如下：每行元素从左到右递增，每列元素从上到下递增。思路：在第一个行中找出首元素大于target的列，在第一个列中找出首元素大于target的行。然后对每行进行二叉搜索。Runtime: 6 ms, faster than 97.21% of Java online submissions for Search a 2D Matrix II.Memory Usage: 46.6 MB, less than 23.14% of Java online submissions for Search a 2D Matrix II.class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length == 0 || matrix[0].length == 0) { return false; } int m = matrix.length, n = matrix[0].length; int row = 0, column = 0; for (; column < n; column++) { if (matrix[0][column] > target) { break; } } for (; row < m; row++) { if (matrix[row][0] > target) { break; } } for (int i = 0; i < row; i++) { if (Arrays.binarySearch(matrix[i], 0, column, target) >= 0) { return true; } } return false; }} ...

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].Example:Input: [1,2,3,4]Output: [24,12,8,6]Note: Please solve it without division and in O(n).Follow up:Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)难度: medium题目：给定一整数组其长度大于1, 返回输出数组其元素由除当前输入元素外所有元素的乘积组成。思路：先用输出数组从右向左计算累积元素的乘积，然后从左向左计算nums[i] = product(0, i-1) * result(i + 1)Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.Memory Usage: 40.8 MB, less than 84.97% of Java online submissions for Product of Array Except Self.class Solution { public int[] productExceptSelf(int[] nums) { if (null == nums || nums.length < 2) { return new int[] {1}; } int n = nums.length; int[] result = new int[n]; int product = 1; for (int i = n - 1; i >= 0; i–) { result[i] = product * nums[i]; product = result[i]; } result[0] = result[1]; product = nums[0]; for (int i = 1; i < n - 1; i++) { result[i] = product * result[i + 1]; product *= nums[i]; } result[n - 1] = product; return result; }} ...

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.Note: The algorithm should run in linear time and in O(1) space.Example 1:Input: [3,2,3]Output: [3]Example 2:Input: [1,1,1,3,3,2,2,2]Output: [1,2]难度：medium题目：给定一整数数组，找出其元素出现次数大于其三分之一长度的所有元素。注意：算法时间复杂度O(n),空间复杂度为O(1)思路：投票法。1 找出三个不同的候选人，各消除一票，如果票数为0 退出候选人队列。2 最后对剩下的候选人重新统计票数Runtime: 2 ms, faster than 97.44% of Java online submissions for Majority Element II.Memory Usage: 39.8 MB, less than 29.68% of Java online submissions for Majority Element II.class Solution { public List<Integer> majorityElement(int[] nums) { List<Integer> result = new ArrayList<>(); if (null == nums) { return result; } int[] elems = new int[2]; int[] count = new int[2]; for (int i = 0; i < nums.length; i++) { if (elems[0] == nums[i]) { count[0]++; } else if (elems[1] == nums[i]) { count[1]++; } else { if (count[0] > 0 && count[1] > 0) { count[0]–; count[1]–; } else if (0 == count[0]) { elems[0] = nums[i]; count[0] = 1; } else if (0 == count[1]) { elems[1] = nums[i]; count[1] = 1; } } } int c0 = 0, c1 = 0; for (int i = 0; i < nums.length; i++) { if (count[0] > 0 && nums[i] == elems[0]) { c0++; } if (count[1] > 0 && nums[i] == elems[1]) { c1++; } } if (c0 > nums.length / 3) { result.add(elems[0]); } if (c1 > nums.length / 3) { result.add(elems[1]); } return result; }} ...

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]Example 1:Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output: 3Explanation: The LCA of nodes 5 and 1 is 3.Example 2:Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output: 5Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.Note:All of the nodes’ values will be unique.p and q are different and both values will exist in the binary tree.难度：medium题目：给定一二叉树，找出给定的两个结点的最低层的共同祖先结点。根据LCA维基百科定义，最低公共祖先定义为两个节点p和q之间的最低公共祖先，它是T中同时具有p和q作为子代的最低节点(我们允许一个节点作为自身的子代)思路：递归，后续遍历。Runtime: 5 ms, faster than 100.00% of Java online submissions for Lowest Common Ancestor of a Binary Tree.Memory Usage: 33.9 MB, less than 69.83% of Java online submissions for Lowest Common Ancestor of a Binary Tree./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); return left == null ? right : right == null ? left : root; }} ...

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows. Please note that both secret number and friend’s guess may contain duplicate digits.Example 1:Input: secret = “1807”, guess = “7810"Output: “1A3B"Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.Example 2:Input: secret = “1123”, guess = “0111"Output: “1A1B"Explanation: The 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow.Note: You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.难度：medium题目：你在和朋友玩bulls和cows游戏：你写下一个数字让你的朋友去猜。每次你的朋友猜一个数字，你给出提示有多少个数字值与位置相同（叫bulls)，有多少个数字值相同但位置不相同（叫cows)。你的朋友持续猜测直到获取正确的数字。写一方法根据你朋友的猜测来返回提示，A表示bulls B表示cows.思路：先找出所有精确匹配，然后单独统计值相同位置不相同的字符。Runtime: 9 ms, faster than 21.94% of Java online submissions for Bulls and Cows.Memory Usage: 35.6 MB, less than 78.72% of Java online submissions for Bulls and Cows.class Solution { public String getHint(String secret, String guess) { int bulls = 0, cows = 0; int[] secretTable = new int[256]; int[] guessTable = new int[256]; for (int i = 0; i < secret.length(); i++) { if (secret.charAt(i) == guess.charAt(i)) { bulls++; } else { secretTable[secret.charAt(i)]++; guessTable[guess.charAt(i)]++; } } for (int i = 0; i < 256; i++) { cows += Math.min(secretTable[i], guessTable[i]); } return String.format("%dA%dB”, bulls, cows); }} ...

Given an unsorted array of integers, find the length of longest increasing subsequence.Example:Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note:There may be more than one LIS combination, it is only necessary for you to return the length.Your algorithm should run in O(n2) complexity.Follow up: Could you improve it to O(n log n) time complexity?难度：medium题目：给定一无序的整数数组，找出其递增的最大子序列。思路：动态规划， 用一个长度与输入数组相同长度的数组记录从0到当前元素的最大递增元素个数。dp(i) = Math.max(dp[j]…) + 1, (nums[i] > nums[j])dp(i) = 1 (nums[i] <= nums[j], 0 <= j <= i - 1)class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length, maxIncLength = 0; int[] incLength = new int[n]; for (int i = 0; i < n; i++) { int curMaxIncLength = 0; for (int j = 0; j <= i; j++) { if (nums[j] < nums[i]) { curMaxIncLength = Math.max(curMaxIncLength, incLength[j]); } } incLength[i] = curMaxIncLength + 1; maxIncLength = Math.max(maxIncLength, incLength[i]); } return maxIncLength; }} ...

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.Example:Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]sumRegion(2, 1, 4, 3) -> 8sumRegion(1, 1, 2, 2) -> 11sumRegion(1, 2, 2, 4) -> 12Note:You may assume that the matrix does not change.There are many calls to sumRegion function.You may assume that row1 ≤ row2 and col1 ≤ col2.难度：medium题目：给定二维矩阵，找出方框内所包含元素的各，方框由左上角与右下角座标表示。思路：求出（0,0)到(i,j)所有元素之和。(x1, y1, x2, y2) = (x2, y2) + (x1 - 1, y1 - 1) - (x1 - 1, y2) - (x2, y1 - 1)Runtime: 60 ms, faster than 100.00% of Java online submissions for Range Sum Query 2D - Immutable.Memory Usage: 48.7 MB, less than 16.67% of Java online submissions for Range Sum Query 2D - Immutable.class NumMatrix { private int[][] matrix; public NumMatrix(int[][] matrix) { this.matrix = matrix; for (int i = 0; i < matrix.length; i++) { for (int j = 1; j < matrix[i].length; j++) { matrix[i][j] += matrix[i][j - 1]; } } for (int i = 1; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { matrix[i][j] += matrix[i - 1][j]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { int rightUp = (row1 - 1 >= 0) ? matrix[row1 - 1][col2] : 0; int leftTop = (row1 - 1 >= 0 && col1 - 1 >= 0) ? matrix[row1 - 1][col1 - 1] : 0; int leftBottom = (col1 - 1 >= 0) ? matrix[row2][col1 - 1] : 0; return matrix[row2][col2] + leftTop - rightUp - leftBottom; }}/** * Your NumMatrix object will be instantiated and called as such: * NumMatrix obj = new NumMatrix(matrix); * int param_1 = obj.sumRegion(row1,col1,row2,col2); */ ...

DescriptionGiven two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.Note: You should try to optimize your time and space complexity.Example 1:Input:nums1 = [3, 4, 6, 5]nums2 = [9, 1, 2, 5, 8, 3]k = 5Output:[9, 8, 6, 5, 3]Example 2:Input:nums1 = [6, 7]nums2 = [6, 0, 4]k = 5Output:[6, 7, 6, 0, 4]Example 3:Input:nums1 = [3, 9]nums2 = [8, 9]k = 3Output:[9, 8, 9]描述给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。说明: 请尽可能地优化你算法的时间和空间复杂度。示例 1:输入:nums1 = [3, 4, 6, 5]nums2 = [9, 1, 2, 5, 8, 3]k = 5输出:[9, 8, 6, 5, 3]示例 2:输入:nums1 = [6, 7]nums2 = [6, 0, 4]k = 5输出:[6, 7, 6, 0, 4]示例 3:输入:nums1 = [3, 9]nums2 = [8, 9]k = 3输出:[9, 8, 9]思路子问题 1 ：对于一个给定的无序整数数组，从其中找出 k 个数构成一个新的整数，k 个数之间的相对位置不变，使得新构成的整数的值最大。我们借助栈来实现，我们即给的给定的数组的元素为 n，需要的取出的元素个数为 k，剩下的元素个数为 t = n - k，我们不断的遍历数组中的元素，如果当前元素比栈顶的元素大，并且此时剩下的可以被踢掉的元素个数 t 大于零，我们弹出栈顶元素；否则我们将当前元素压入栈顶。子问题 2 ：给定两个数组，从这两个数组中交替的选数字出来，只能从前往后选，构成一个新数组，使得这个数组最大。「数组大小的比较：依次标胶每一个元素，遇到第一数大的数组大」。用两个队列来实现，如果队列 1 大于队列 2，我们弹出队列 1 的元素到结果数组中，否则弹出队列 2 的元素，直到所有的元素都被取完。本题：我们从第一个数组中取 i 个元素找到一个最数组，从第二个数组中取出 k - i 个数构成最大数组，将两个数组合并构成新的数组，在所有的新的数组中我们取最大的数组。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-24 14:35:27# @Last Modified by: 何睿# @Last Modified time: 2019-02-26 16:08:04from collections import dequeclass Solution: def maxNumber(self, nums1: [int], nums2: [int], k: int) -> [int]: ans = [] for i in range(k + 1): # 如果已经超出了第一个数组的范围，循环结束 if i > len(nums1): break # 如果 k - i 比第二个数组的元素个数更多， # 说明第二个数组不能够提供足够的元素，继续循环 if k - i > len(nums2): continue # 产生新的组合 newans = self._merge(self._Max(nums1, i), self._Max(nums2, k - i)) # 取最大的组合 ans = max(ans, newans) return ans def _Max(self, nums, k): # 需要去掉的个数 drop = len(nums) - k stack = [] # 遍历每一个元素 for num in nums: # 如果栈不为空 并且 drop 大于零 并且 num 大于栈顶元素 while stack and drop > 0 and num > stack[-1]: # 弹出栈顶元素 stack.pop() # 需要弹出的元素个数减一 drop -= 1 stack.append(num) # 返回前 k 个元素 return stack[:k] def _merge(self, num1, nums2): # 将列表转换成队列 queue1 = deque(num1) queue2 = deque(nums2) res = [] while queue1 and queue2: # 队列大小的比较 # 对队列每个元素从前向后比较，只要有一个比较大，则该队列比较大 if queue1 > queue2: res.append(queue1.popleft()) else: res.append(queue2.popleft()) # 添加队列剩下的元素 if queue1: res += queue1 if queue2: res += queue2 return res源代码文件在 这里 。©本文首发于 何睿的博客 ，欢迎转载，转载需保留 文章来源 ，作者信息和本声明. ...

题目给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其层次遍历结果：[ [3], [9,20], [15,7]]题解我们数据结构的书上教的层序遍历,就是利用一个队列,不断的把左子树和右子树入队。但是这个题目还要要求按照层输出。所以关键的问题是： 如何确定是在同一层的。我们很自然的想到：如果在入队之前,把上一层所有的节点出队,那么出队的这些节点就是上一层的列表。由于队列是先进先出的数据结构,所以这个列表是从左到右的。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } /class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> currentRes = new LinkedList<>(); // 当前队列的大小就是上一层的节点个数, 依次出队 while (size > 0) { TreeNode current = queue.poll(); if (current == null) { continue; } currentRes.add(current.val); // 左子树和右子树入队. if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } size–; } res.add(currentRes); } return res; }}这道题可不可以用非递归来解呢?递归的子问题：遍历当前节点, 对于当前层, 遍历左子树的下一层层,遍历右子树的下一层递归结束条件: 当前层,当前子树节点是null/* * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } /class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } levelOrderHelper(res, root, 0); return res; } /* * @param depth 二叉树的深度 */ private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) { if (root == null) { return; } if (res.size() <= depth) { // 当前层的第一个节点,需要new 一个list来存当前层. res.add(new LinkedList<>()); } // depth 层,把当前节点加入 res.get(depth).add(root.val); // 递归的遍历下一层. levelOrderHelper(res, root.left, depth + 1); levelOrderHelper(res, root.right, depth + 1); }}热门阅读技术文章汇总【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树 ...

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.Example:Given the sorted linked list: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5难度：medium题目：给定一个单链表其元素为升序排列，将其转换成高度平衡的二叉搜索树思路：中序遍历Runtime: 1 ms, faster than 99.17% of Java online submissions for Convert Sorted List to Binary Search Tree.Memory Usage: 41 MB, less than 9.56% of Java online submissions for Convert Sorted List to Binary Search Tree./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } //* * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode sortedListToBST(ListNode head) { if (null == head) { return null; } ListNode ptr = head; int count = 0; for (; ptr != null; ptr = ptr.next, count++); ListNode[] headList = {head}; return sortedListToBST(headList, 0, count - 1); } public TreeNode sortedListToBST(ListNode[] head, int start, int end) { if (start > end) { return null; } int mid = start + (end - start) / 2; TreeNode left = sortedListToBST(head, start, mid - 1); TreeNode root = new TreeNode(head[0].val); root.left = left; head[0] = head[0].next; root.right = sortedListToBST(head, mid + 1, end); return root; }} ...

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.Example 1:Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2Output: 1Example 2:Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1Output: 3Follow up:What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?难度：medium题目：给定二叉搜索树，找出其值第K小的结点。思路：中序遍历Runtime: 0 ms, faster than 100.00% of Java online submissions for Kth Smallest Element in a BST.Memory Usage: 38.9 MB, less than 19.71% of Java online submissions for Kth Smallest Element in a BST./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public int kthSmallest(TreeNode root, int k) { int[] result = {root.val}; kthSmallest(root, k, new int[1], result); return result[0]; } public void kthSmallest(TreeNode root, int k, int[] count, int[] result) { if (root == null || count[0] >= k) { return; } kthSmallest(root.left, k, count, result); count[0]++; if (count[0] == k) { result[0] = root.val; return; } kthSmallest(root.right, k, count, result); }} ...

DescriptionThere are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.Example:Input: 3Output: 1 Explanation: At first, the three bulbs are [off, off, off].After first round, the three bulbs are [on, on, on].After second round, the three bulbs are [on, off, on].After third round, the three bulbs are [on, off, off]. So you should return 1, because there is only one bulb is on.描述初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。示例:输入: 3输出: 1 解释: 初始时, 灯泡状态 [关闭, 关闭, 关闭].第一轮后, 灯泡状态 [开启, 开启, 开启].第二轮后, 灯泡状态 [开启, 关闭, 开启].第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1，因为只有一个灯泡还亮着。思路数学题，对给定的数字开平方向下取整即是答案。暴力求解（会超时），但是通过暴力解法可以发现规律。我们声明一个长度为 n 的数组，数组初始值为 0 。然后我们按照题目要求对其进行改变状态的操作，0 表示关，1 表示开。我们通过这个会发现如果给定的 n 为前三个数（13）会有 1 盏灯亮着，如果给定的 n 为接下来的 5 个数 （48），会有 2 盏灯亮着，接下来的 7 个数（915）会有3 盏灯两者，我们称给定的所有可能的 n 中，最后剩下相同的灯亮着的情况的 n 为一组，于是可以发现每组 n 的个数是一个首项为 3 公差为 2 的等差数列。于是有了第一个解法：我们不断的从 n 中减去，3，5，7 … （n 小于零就停止），能减少多少次就有多少盏灯亮着。我们可以发现 13：1；48：2；915：3，16~25：4，不难发现我们对 n 开放取整就可以得到答案，关于严格的数学证明请参考 这里-solution-with-explanation) 。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-23 18:46:36# @Last Modified by: 何睿# @Last Modified time: 2019-02-23 19:46:07class Solution: def bulbSwitch(self, n: int) -> int: return int(n**0.5) def bulbSwitch2(self, n: int) -> int: count, i = 0, 3 # 首项为3，公差为 2 的等差数列 # n 为这些数字的和 while n > 0: # 每次从 n 中去掉一项 n -= i i += 2 # 记录去掉的次数 count += 1 # 次数就是剩下的晾着的灯泡个数 return count def bulbSwitch3(self, n: int) -> int: # 最直观的思路，用一个数组表示灯泡的开关情况，0 表示关，1 表示开 # !!! 此方法会超时 bulbs = [0 for i in range(n)] for i in range(n): j = i # 每轮调整 i 整数倍的位置 while j < n: bulbs[j] ^= 1 j += i + 1 # 统计最后剩下的 1 的个数 return bulbs.count(1)源代码文件在 这里 。©本文首发于 何睿的博客 ，欢迎转载，转载需保留 文章来源 ，作者信息和本声明. ...

Given a sorted integer array without duplicates, return the summary of its ranges.Example 1:Input: [0,1,2,4,5,7]Output: [“0->2”,“4->5”,“7”]Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.Example 2:Input: [0,2,3,4,6,8,9]Output: [“0”,“2->4”,“6”,“8->9”]Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.难度：medium题目：给定排序且无重复元素的整数数组，返回其连续元素的范围。思路：用以变量记录连续元素的开始。Runtime: 5 ms, faster than 7.57% of Java online submissions for Summary Ranges.Memory Usage: 37.5 MB, less than 5.02% of Java online submissions for Summary Ranges.class Solution { public List<String> summaryRanges(int[] nums) { List<String> result = new ArrayList<>(); if (null == nums || nums.length < 1) { return result; } for (int i = 1, start = 0; i <= nums.length; i++) { if (i == nums.length || nums[i] - nums[i - 1] != 1) { result.add((i - 1 == start) ? String.format("%s", nums[start]) : String.format("%s->%s", nums[start], nums[i - 1])); start = i; } } return result; }} ...

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.Example 1:Input: A = [0,1,0], K = 1Output: 2Explanation: Flip A[0], then flip A[2].Example 2:Input: A = [1,1,0], K = 2Output: -1Explanation: No matter how we flip subarrays of size 2, we can’t make the array become [1,1,1].Example 3:Input: A = [0,0,0,1,0,1,1,0], K = 3Output: 3Explanation:Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]Note:1 <= A.length <= 300001 <= K <= A.length难度：Hard题目：在一个只包含0和1的数组中，每次可以翻转Ｋ个元素，其中所有的0翻转成1,1翻转成0. 返回其最小的翻转次数。如果不存在则返回－1.思路：贪心算法，每次找到第1个0后翻转从该元素开始的Ｋ个元素。Runtime: 140 ms, faster than 71.57% of Java online submissions for Minimum Number of K Consecutive Bit Flips.Memory Usage: 48.4 MB, less than 6.43% of Java online submissions for Minimum Number of K Consecutive Bit Flips.class Solution { public int minKBitFlips(int[] A, int K) { int i = 0, count = 0; while (i <= A.length - 1) { if (1 == A[i]) { i++; continue; } if (i + K > A.length) { return -1; } count++; for (int t = i; t < i + K; t++) { A[t] = (A[t] + 1) & 1; } } return count; }} ...

DescriptionGiven a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.Example 1:Input: [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]Output: 16 Explanation: The two words can be “abcw”, “xtfn”.Example 2:Input: [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]Output: 4 Explanation: The two words can be “ab”, “cd”.Example 3:Input: [“a”,“aa”,“aaa”,“aaaa”]Output: 0 Explanation: No such pair of words.描述给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。示例 1:输入: [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]输出: 16 解释: 这两个单词为 “abcw”, “xtfn”。示例 2:输入: [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]输出: 4 解释: 这两个单词为 “ab”, “cd”。示例 3:输入: [“a”,“aa”,“aaa”,“aaaa”]输出: 0 解释: 不存在这样的两个单词。思路基本思路很简单：对给定的单词两两组合，如果这两个单词没有相同的字符，记下者两个单词长度值的乘积，返回最大值。如何判断两个单词是否使用了相同的单词：我们使用位运算，整形有 32 位，字符只有 26 个。我们让二进制的数第一位表示 a ，第二位表示 b … 第 26 位表示 z 。如果某个字母在给定的单词中出现了，我们记字母对应位置的二进制位 1 。如果两个单词没有使用相同的字母，那么这两个单词对应的二进制按位与一定为 0 ，因为两个单词没有使用相同的字母，所以二进制中的 1 都是错开的。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-23 13:14:24# @Last Modified by: 何睿# @Last Modified time: 2019-02-23 14:24:48import itertoolsclass Solution: def maxProduct(self, words) -> int: # bits 是字典，键为单词 word 对应的二进制码，值为一个二进制码对应的最长单词 # 最长单词：单词 a，aa，aaa，aaaa，对应的二进制码都是 0b1，为了获得最大的乘积 # 我们取最长的单词 aaaa，所以 0b1 对应 4 bits = {} for word in words: # 获取单词单词对应的 二进制码，有点类似哈希，但是不完全相同 bit = self.getBit(word) # 建立键值对，这样可以避免多次 len(word) # 值为最长单词的长度 bits[bit] = max(bits.get(bit, 0), len(word)) # 对一个列表的所有元素进行两两组合 # 也可以用循环，如 maxProduct2 中示例 # 但是在 python 中 itertools.combinations 更快 com = itertools.combinations(bits.keys(), r=2) # 对所有组合中单词没有重复的求乘积，这里也可以写成循环的形式 # 但是在 python 中列表解析式的执行速度更快 return max([bits[x] * bits[y] for x, y in com if x & y == 0] or [0]) def maxProduct2(self, words) -> int: res = 0 bits = [self.getBit(word) for word in words] for i in range(len(words)): for j in range(i + 1, len(words)): if bits[i] & bits[j] == 0: res = max(res, len(words[i]) * len(words[j])) return res def getBit(self, word): bit = 0 # 按位或 # 字母 a 对一二进制第 1 位，b 对应第 2 位 … z 对应 第 26 位 for char in word: bit = bit | (1 << (ord(char) - 97)) return bit源代码文件在 这里 。©本文首发于 何睿的博客 ，欢迎转载，转载需保留 文章来源 ，作者信息和本声明. ...

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.OJ’s undirected graph serialization (so you can understand error output):Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}.The graph has a total of three nodes, and therefore contains three parts as separated by #.First node is labeled as 0. Connect node 0 to both nodes 1 and 2.Second node is labeled as 1. Connect node 1 to node 2.Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.Visually, the graph looks like the following: 1 / \ / \ 0 — 2 / \ _/Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.难度：medium题目：给定一图的头结点，返回其深拷贝。每个结点包含一个标签及一组邻结点。在给定的结点与其邻结点之间都有一边。思路：BFSRuntime: 6 ms, faster than 19.61% of Java online submissions for Clone Graph.Memory Usage: 37.9 MB, less than 95.96% of Java online submissions for Clone Graph./** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (null == node) { return null; } Queue<UndirectedGraphNode> queue = new LinkedList<>(); queue.add(node); Map<UndirectedGraphNode, UndirectedGraphNode> nodes = new HashMap<>(); while (!queue.isEmpty()) { UndirectedGraphNode tNode = queue.poll(); nodes.put(tNode, new UndirectedGraphNode(tNode.label)); for (UndirectedGraphNode n: tNode.neighbors) { if (!nodes.containsKey(n)) { queue.add(n); } } } for (Map.Entry<UndirectedGraphNode, UndirectedGraphNode> e: nodes.entrySet()) { UndirectedGraphNode copyNode = e.getValue(); for (UndirectedGraphNode n : e.getKey().neighbors) { copyNode.neighbors.add(nodes.get(n)); } } return nodes.get(node); }} ...

Given inorder and postorder traversal of a tree, construct the binary tree.Note:You may assume that duplicates do not exist in the tree.For example, giveninorder = [9,3,15,20,7]postorder = [9,15,7,20,3]Return the following binary tree: 3 / \ 9 20 / \ 15 7难度：medium题目：给定二叉树中序及后序遍历，构造二叉树，注意二叉树中的结点不重复。思路；分治。从后序遍历数组中由后向前取结点r在中序遍历中找到r的位置，并由此结点分成两部分，继续执行1.Runtime: 4 ms, faster than 68.02% of Java online submissions for Construct Binary Tree from Inorder and Postorder Traversal.Memory Usage: 37.6 MB, less than 42.45% of Java online submissions for Construct Binary Tree from Inorder and Postorder Traversal./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if (null == postorder || postorder.length < 1) { return null; } return buildTree(inorder, 0, inorder.length - 1, postorder, postorder.length - 1); } public TreeNode buildTree(int[] inorder, int start, int end, int[] postorder, int idx) { if (start > end || idx < 0) { return null; } TreeNode root = new TreeNode(postorder[idx]); int rIdx = start; for (; rIdx <= end; rIdx++) { if (inorder[rIdx] == postorder[idx]) { break; } } root.left = buildTree(inorder, start, rIdx - 1, postorder, idx - (end - rIdx) - 1); root.right = buildTree(inorder, rIdx + 1, end, postorder, idx - 1); return root; }} ...

Given preorder and inorder traversal of a tree, construct the binary tree.Note:You may assume that duplicates do not exist in the tree.For example, givenpreorder = [3,9,20,15,7]inorder = [9,3,15,20,7]Return the following binary tree: 3 / \ 9 20 / \ 15 7难度：Medium题目： 给定二叉树的前序和中序遍历，构造二叉树，注意：二叉树结点值不重复。思路：分治，在前序中找出根结点r，再在中序中找出r的位置，以该结点一分为二，继续执行1Runtime: 8 ms, faster than 57.64% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.Memory Usage: 37.5 MB, less than 49.23% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (null == preorder || preorder.length < 1) { return null; } return buildTree(preorder, 0, inorder, 0, inorder.length - 1); } private TreeNode buildTree(int[] preorder, int idx, int[] inorder, int s, int e) { if (s > e) { return null; } TreeNode root = new TreeNode(preorder[idx]); int rIdx = s; for (; rIdx <= e; rIdx++) { if (inorder[rIdx] == preorder[idx]) { break; } } root.left = buildTree(preorder, idx + 1, inorder, s, rIdx - 1); root.right = buildTree(preorder, idx + rIdx - s + 1, inorder, rIdx + 1, e); return root; }} ...

DescriptionGiven a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.Example 1:Input: “bcabc"Output: “abc"Example 2:Input: “cbacdcbc"Output: “acdb"描述给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。示例 1:输入: “bcabc"输出: “abc"示例 2:输入: “cbacdcbc"输出: “acdb"思路字典序最小：对于两个字符串 S 和 T，如果 S1 < T1，则 字符串 S 的字典序更小。比如第一个例子字符串 “bcabc” 去掉重复后可能的结果有：1.bca 2. bac 3. cab 4.abc 「注意只能从前往后遍历取出字符」。对于 1 和 2，由于 b == b,c > a，所以 2 的字典序比1小，同理 2 的字典序比 3 小，4 的字典序比 2 小，所以最终答案是 4。我们使用 stack 和 字典这两种数据结构。我们用一个字典记录每个字符出现的次数。核心思路是：假设 stack 中记录了给定的 S 中前 i 个字符的结果，那么针对第 i+1 个字符，如果第 i+1 个字符还没有出现在 stack 中，如果：1.第 i+1 个字符比栈顶元素小并且栈顶元素在第 i+1 个元素之后还会出现，那么 第 i+1 个元素应该在 stack 栈顶元素的前面，于是我们弹出 stack 栈顶元素，并用第 i+1 个元素和现在的栈顶元素比较，如果此时第 i+1 个元素仍比栈顶元素小并且此时的栈顶元素在第 i+1 个元素之后仍会出现，我们继续弹出栈顶元素 …2.第 i+1 个字符比栈顶元素小但是栈顶元素在这之后不会出现了，我们把当前元素追加到栈顶。3.如果当前元素本身就比栈顶元素大，我们把当前元素追加到栈顶。如上，我们需要知道一个元素在之后会不会出现：我们借助字典来实现，字典的键为字符，值为字符在给定的字符串中出现的次数，如果一个字符对应的值大于零，说明这个字符还会出现，如果等于零则不会出现。每次访问一个字符的时候，我们首先让字典中该字符对应的值自减一次，表示已经访问了一次。我们还需要知道一个字符是否已经出现过了在 stack 中，也就是有没有被处理过，我们用 Hastset 来实现，每访问到一个字符，我们都把它加入到 set 中，在第 1 种情况种，如果一个元素从栈顶被弹出了，我们也从 set 中移除这个元素，表示这个元素还没有被处理。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-22 14:27:31# @Last Modified by: 何睿# @Last Modified time: 2019-02-22 15:38:39import collectionsclass Solution: def removeDuplicateLetters(self, s: ‘str’) -> ‘str’: # stack 用于存储已经获取的结果 # visited 表示当前的字符已经遍历过 stack, visited = [], set() # times 是一个字典，键为字符，值为字符出现过的次数 times = collections.Counter(s) for item in s: # 让字典 times 中记录的对应次数减少一次 times[item] -= 1 # 如果 item 还没有遍历过，即 item 没有出现在结果中 # visited 和 stack 里面的字符内容是一样的 # 只不过我们用stack 是为了从栈顶开始删除 # 用 visited 可以在 O(1) 时间复杂度内判断一个元素是否被遍历过并且在 O(1) 内删除一个元素 if item not in visited: # 如果当前元素比栈顶元素小并且栈顶元素在当前元素后面还会出现 # 那么当前元素应该带栈顶元素的前面 # 我们弹出栈顶元素，在 visited 中删除栈顶元素的记录 while stack and item < stack[-1] and times[stack[-1]] != 0: visited.remove(stack.pop()) # 此时有下列三种情况 # 1. 栈已经空了 # 2. 当前元素大于栈顶元素 # 3. 当前元素小于栈顶元素但是栈顶元素在当前元素后面不再出现 # 我们将当前元素压入栈顶，在 visited 元组中记录当前元素已经被访问过 stack.append(item) visited.add(item) # 注意题目要求返回字符串 return ‘’.join(stack)源代码文件在 这里。©本文首发于 何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明. ...

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.Example 1:Input: nums = [1,2,3,1], k = 3, t = 0Output: trueExample 2:Input: nums = [1,0,1,1], k = 1, t = 2Output: trueExample 3:Input: nums = [1,5,9,1,5,9], k = 2, t = 3Output: false难度：medium题目：给定一整数数组，找出是否存在两个不同的索引i, j使其索引差的绝对值小于等于k, 值的差的绝对值小于等于t.思路：暴力破解，使用滑动窗口和TreeSet是为了使得滑动窗口有序，TreeSet底层是二叉搜索树, 如果暴力破解时间复杂度为O(kn), 改用TreeSet使得搜索时间复杂度为O(log K), 故总的时间复杂度为O(nlog K)。Runtime: 22 ms, faster than 70.38% of Java online submissions for Contains Duplicate III.Memory Usage: 40.4 MB, less than 5.58% of Java online submissions for Contains Duplicate III.class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(nums == null || nums.length < 2 || k < 1 || t < 0){ return false; } TreeSet<Long> treeSet = new TreeSet<>(); for (int i = 0; i < nums.length; i++) { if (!treeSet.subSet((long) nums[i] - t, true, (long) nums[i] + t, true).isEmpty()) { return true; } if (i >= k) { treeSet.remove((long) nums[i - k]); } treeSet.add((long) nums[i]); } return false; }}Runtime: 987 ms, faster than 5.06% of Java online submissions for Contains Duplicate III.Memory Usage: 38.8 MB, less than 56.75% of Java online submissions for Contains Duplicate III.class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < Math.min(nums.length, i + k + 1); j++) { if (nums[i] > 0 && nums[j] < 0 || nums[i] < 0 && nums[j] > 0) { if (Math.abs(nums[i]) - t > 0 || Math.abs(nums[i]) - t + Math.abs(nums[j]) > 0) { continue; } } if (Math.abs(nums[i] - nums[j]) <= t) { return true; } } } return false; }} ...

DescriptionYou are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].Example:Input: [5,2,6,1]Output: [2,1,1,0] Explanation:To the right of 5 there are 2 smaller elements (2 and 1).To the right of 2 there is only 1 smaller element (1).To the right of 6 there is 1 smaller element (1).To the right of 1 there is 0 smaller element.描述给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。示例:输入: [5,2,6,1]输出: [2,1,1,0] 解释:5 的右侧有 2 个更小的元素 (2 和 1).2 的右侧仅有 1 个更小的元素 (1).6 的右侧有 1 个更小的元素 (1).1 的右侧有 0 个更小的元素.思路基本思路是我们从后往前遍历，依次把数字插入到一个数据结构中，每次插入的时候返回数据结构中比这个数小的数的个数，用一个数组记录返回的结果，这里把记录结果的数组命名为 res。我们最后返回 res 的逆序 「因为我们是逆序地从给定的数组中选取数字的」。关于数据结构的选取：方法一：对于 python 语言，我们借助 python 自带的库函数 bisect ，通过数组来实现。有关 bisect 的语法，请参考 这里。bisect.bisect_left(list, item) 函数把 item 插入到 list 中，并且保持 list 是排序的顺序，如果 item 已经存在于 list 将会把 item 插入到 list 的最左边。我们声明一个数组 visited 用于插入元素，我们用 bisect.bisect_left(visited, item) 获得 item 应该插入到 visited 中的位置，把这个值添加到数组 res 中。这个位置的值就是数组中小于等于 item 元素的个数，注意 ：这里一定要用 bisect_left，不能用 bisect_right 因为如果出现了 重复的元素，bisect_right 把重复的元素算在内 「因为 bisect_right 会插入在重复元素的右边」，而题意是找小于当前元素的元素个数，不包含等于。获取了元素插入的位置后，我们使用 bisect.insort_right 将元素插入到 visited 中 「使用 bisect.insort_left 也可以」。返回 res 的逆序。方法二：使用二叉搜索数。有关二叉搜索数和平衡二叉搜索树请参考这个 视频。注意：1. 我们这里的二叉搜索树不需要实现全部功能，这道题里面只需要用到 insert 功能。2. 二叉搜索树不存储重复的元素。二叉树的节点我们声明五个变量：1. value 用于存储节点的值。 2. count 用于表示当前值出现的次数，默认为1。3. smaller 表示比当前节点值小的节点的个数。 4. left_child 左子树。5. right_child 右子树。在向二叉树中插入值 value 的时候，如果插入的值比当前的节点小，当前节点的 smaller 自增一次，并且将 value 插入到左子树中，在最后创建新节点的后返回 0。如果插入的值比当前节点的值大，我们记下当前位置比 value 小的节点个数 count + smaller，然后将 value 插入到当前节点的右子树中，在最后创建新节点后返回 count + smaller。如果要插入的元素的值和当前节点的值相等，返回 当前节点的 smaller 值。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-20 13:55:15# @Last Modified by: 何睿# @Last Modified time: 2019-02-21 11:48:51# python 内部二分搜索库import bisect# 二叉搜索树的节点class Node: def init(self, value=None): # 节点的值 self.value = value # 二叉搜索树不存储重复节点，我们用 count 来存值出现的次数 self.count = 1 # 比当前元素值小的元素个数 self.smaller = 0 # 左子树 self.left_child = None # 右子树 self.right_child = Noneclass BinarySearchTree: def init(self): self.root = None def insert(self, value): if self.root == None: self.root = Node(value) return 0 else: return self._insert(value, self.root) def _insert(self, value, node): # 如果当前需要插入的值比当前节点的值小 if value < node.value: # node.smaller 自增一次 node.smaller += 1 # 如果当前节点还没有左子树 if node.left_child == None: # 创建一个新的节点 node.left_child = Node(value) # 返回 0 表示比当前插入元素还小的元素个数为 0 return 0 else: # 否则将当前元素插入到当前节点的左子树 return self._insert(value, node.left_child) # 如果当前需要插入的值比当前节点的值大 elif value > node.value: # smaller 表示当前节点连接的左子树的所有节点个数 # 左子树的所有节点值一定比当前节点小 # 由于树是动态创建的，因此比 value 值小的节点在当前节点的左子树和当前节点的右子树的左子树中 smaller = node.count + node.smaller # 如果当前节点还没有右子树 if node.right_child == None: # 创建一个新的节点 node.right_child = Node(value) # 返回 smaller return smaller else: # 如果有右子树，说明当前值不仅比当前节点的左子树的节点值大 # 有可能比当前节点的右子树的左子树节点大， # smaller 仅仅记录了当前节点的左子树 # 返回 smaller + 当前节点右子树中比要插入的值小的元素个数 return smaller + self._insert(value, node.right_child) else: # 如果当前要插入的值已经在二叉搜索树中，count 自增一次 node.count += 1 # 返回 node.smaller return node.smallerclass Solution: # 第一种方法，我们借助二叉搜索树实现 # 需要自己实现二叉搜索数 「只需要实现插入部分，查找和删除在这里用不到」 def countSmaller(self, nums: ‘List[int]’) -> ‘List[int]’: Tree = BinarySearchTree() res = [] for num in nums[::-1]: # 从后向前插入，每次插入一个值，返回树中比当前元素小的元素的个数 res.append(Tree.insert(num)) # 因为我们是从后面向前插入的，所以需要返回逆序的结果数组 return res[::-1] # 方法二，借助python 二分搜索库 def countSmaller2(self, nums: ‘List[int]’) -> ‘List[int]’: res, visited = [], [] for num in nums[::-1]: # num 插入位置的索引就是比他小的元素的个数 res.append(bisect.bisect_left(visited, num)) # 将 num 元素插入到 visited 数组中 # 这里使用 insort_right 或者 insort_left 均可 bisect.insort_right(visited, num) # 返回逆序的结果数组 return res[::-1]源代码文件在 这里。©本文首发于 何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明. ...

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.Example 1:Input: nums = [1,2,3,1], k = 3Output: trueExample 2:Input: nums = [1,0,1,1], k = 1Output: trueExample 3:Input: nums = [1,2,3,1,2,3], k = 2Output: false难度：easy题目：给定一整数数组和一整数K,找出是否存在两个不同的下标使用得nums[i]=nums[j]并且i与j之差的绝对值小于等于k.思路：hashmapRuntime: 9 ms, faster than 81.45% of Java online submissions for Contains Duplicate II.Memory Usage: 41 MB, less than 77.21% of Java online submissions for Contains Duplicate II.public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> mii = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (mii.containsKey(nums[i]) && i - mii.get(nums[i]) <= k) { return true; } mii.put(nums[i], i); } return false; }} ...

Given an array of integers, find if the array contains any duplicates.Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.Example 1:Input: [1,2,3,1]Output: trueExample 2:Input: [1,2,3,4]Output: falseExample 3:Input: [1,1,1,3,3,4,3,2,4,2]Output: true难度：easy题目：给定整数数组，找出其中是否含有重复元素。方法应该返回true如果发现某元素至少出现两次，否则返回false.思路：hashsetRuntime: 10 ms, faster than 64.18% of Java online submissions for Contains Duplicate.Memory Usage: 40.9 MB, less than 81.42% of Java online submissions for Contains Duplicate.class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (set.contains(nums[i])) { return true; } set.add(nums[i]); } return false; }} ...

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.Example:Input: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0Output: 4难度：medium题目：给定由0,1组成的矩阵，找出由1组成的最大方块并返回其面积。思路：动态规划转换方程grid[i][j] = Math.min(grid[i][j - 1], grid[i - 1][j], grid[i - 1][j - 1]) + 1 (matrix[i][j] = ‘1’)Runtime: 7 ms, faster than 97.80% of Java online submissions for Maximal Square.Memory Usage: 40.8 MB, less than 70.46% of Java online submissions for Maximal Square.class Solution { public int maximalSquare(char[][] matrix) { if (null == matrix || matrix.length < 1) { return 0; } int maxSquare = 0, m = matrix.length, n = matrix[0].length; int[][] grid = new int[m][n]; for (int i = 0; i < m; i++) { if (‘1’ == matrix[i][0]) { grid[i][0] = 1; maxSquare = 1; } } for (int i = 0; i < n; i++) { if (‘1’ == matrix[0][i]) { grid[0][i] = 1; maxSquare = 1; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (‘1’ == matrix[i][j]) { grid[i][j] = Math.min(grid[i - 1][j - 1], Math.min(grid[i - 1][j], grid[i][j - 1])) + 1; maxSquare = Math.max(maxSquare, grid[i][j]); } } } return maxSquare * maxSquare; }} ...

Given a complete binary tree, count the number of nodes.Note:Definition of a complete binary tree from Wikipedia:In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.Example:Input: 1 / \ 2 3 / \ /4 5 6Output: 6难度：medium题目：给定完全二叉树，统计其结点数。思路：后序遍历Runtime: 1 ms, faster than 100.00% of Java online submissions for Count Complete Tree Nodes.Memory Usage: 40.4 MB, less than 45.43% of Java online submissions for Count Complete Tree Nodes./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int countNodes(TreeNode root) { if (null == root) { return 0; } return countNodes(root.left) + countNodes(root.right) + 1; }} ...

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.Example 1:Input: [3,2,1,5,6,4] and k = 2Output: 5Example 2:Input: [3,2,3,1,2,4,5,5,6] and k = 4Output: 4Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.难度：medium题目：找出在没有排序的数组中第K大的元素，注意是排序后的第K大的元素，不是第Ｋ个不同元素。思路：快速排序Runtime: 29 ms, faster than 36.08% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 38.8 MB, less than 51.09% of Java online submissions for Kth Largest Element in an Array.class Solution { public int findKthLargest(int[] nums, int k) { int idx = -1; k = nums.length - k; for (int i = 0, j = nums.length - 1; i <= j && idx != k;) { idx = quickSort(nums, i, j); if (idx < k) { i = idx + 1; } else if (idx > k) { j = idx - 1; } } return nums[idx]; } private int quickSort(int[] nums, int i, int j) { int piovt = nums[i]; while (i < j) { while (i < j && nums[j] >= piovt) { j–; } nums[i] = nums[j]; while (i < j && nums[i] < piovt) { i++; } nums[j] = nums[i]; } nums[i] = piovt; return i; }} ...

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.Note:All numbers will be positive integers.The solution set must not contain duplicate combinations.Example 1:Input: k = 3, n = 7Output: [[1,2,4]]Example 2:Input: k = 3, n = 9Output: [[1,2,6], [1,3,5], [2,3,4]]难度：medium题目：找出所有可能的Ｋ个数之和为n的组合，只可以使用1到9之间的数。注意：所有数都为正，给出的答案中不包含重复的数。思路：递归Runtime: 1 ms, faster than 66.65% of Java online submissions for Combination Sum III.Memory Usage: 35 MB, less than 54.02% of Java online submissions for Combination Sum III.class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<>(); if (n > 45 || n < 1 || k < 1 || k > 9) { return result; } combination(1, k, 0, n, new Stack<>(), result); return result; } private void combination(int begin, int k, int sum, int n, Stack<Integer> stack, List<List<Integer>> result) { if (k < 0 || sum > n) { return; } if (0 == k && sum == n) { result.add(new ArrayList<>(stack)); return; } for (int i = begin; i <= 9 - k + 1; i++) { stack.push(i); combination(i + 1, k - 1, sum + i, n, stack, result); stack.pop(); } }} ...

There are a total of n courses you have to take, labeled from 0 to n-1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.Example 1:Input: 2, [[1,0]] Output: [0,1]Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .Example 2:Input: 4, [[1,0],[2,0],[3,1],[3,2]]Output: [0,1,2,3] or [0,2,1,3]Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .Note:The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.You may assume that there are no duplicate edges in the input prerequisites.难度：medium题目：现有标记为0到n-1的课程需要学习。某些课程有预备课程需要学习，如果学习课程0就要先学习课程1，表示形式如[0, 1].给定所有课程及其预备课程关系，返回可以学习完所有课程的顺序。这种顺序有许多种，你只需要返回其一即可，如果无法完成所有课程学习，则返回空。思路：找出0入度结点然后逐个删除其边，重复1.Runtime: 5 ms, faster than 98.86% of Java online submissions for Course Schedule II.Memory Usage: 43.8 MB, less than 66.87% of Java online submissions for Course Schedule II.class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { // (Array -> List) to store graph List<Integer>[] nodes = new ArrayList[numCourses]; for (int i = 0; i < numCourses; i++) { nodes[i] = new ArrayList<Integer>(); } // count in degree int[] inDegree = new int[numCourses]; for (int i = 0; i < prerequisites.length; i++) { (nodes[prerequisites[i][0]]).add(prerequisites[i][1]); inDegree[prerequisites[i][1]] += 1; } // count zero in degree int zeroInDegreeCount = 0; List<Integer> zeroInDegreeList = new ArrayList<>(); for (int i = 0; i < inDegree.length; i++) { if (inDegree[i] <= 0) { zeroInDegreeList.add(i); zeroInDegreeCount++; } } // bfs for (int i = 0; i < zeroInDegreeList.size(); i++) { for (Integer node : nodes[zeroInDegreeList.get(i)]) { if (–inDegree[node] <= 0) { zeroInDegreeList.add(node); zeroInDegreeCount++; } } } if (zeroInDegreeCount == numCourses) { int[] result = new int[numCourses]; for (int i = 0; i < numCourses; i++) { result[numCourses - 1 - i] = zeroInDegreeList.get(i); } return result; } return new int[0]; }} ...

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.This is case sensitive, for example “Aa” is not considered a palindrome here.Note:Assume the length of given string will not exceed 1,010.Example:Input:“abccccdd"Output:7Explanation:One longest palindrome that can be built is “dccaccd”, whose length is 7.难度：easy题目：给定包含大小写字符组成的字符串，找出用这些字符串所能够成的最长回文串。思路：字符统计Runtime: 5 ms, faster than 90.61% of Java online submissions for Longest Palindrome.Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Longest Palindrome.class Solution { public int longestPalindrome(String s) { int[] table = new int[255]; for (char c: s.toCharArray()) { table[c]++; } int length = 0, odd = 0; for (int i = 0; i < 255; i++) { if (table[i] % 2 > 0) { odd = 1; } length += table[i] - table[i] % 2; } return length + odd; }} ...

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.Note: Do not modify the linked list.Example 1:Input: head = [3,2,0,-4], pos = 1Output: tail connects to node index 1Explanation: There is a cycle in the linked list, where tail connects to the second node.Example 2:Input: head = [1,2], pos = 0Output: tail connects to node index 0Explanation: There is a cycle in the linked list, where tail connects to the first node.Example 3:Input: head = [1], pos = -1Output: no cycleExplanation: There is no cycle in the linked list.Follow up:Can you solve it without using extra space?难度：medium题目：给定一链表，返回环的起始结点。如果无环返回空。为了表示链表中的环，使用整数来表示起如结点位置即尾结点所指向的位置。如果位置为－1则表示无环。注意：不要修改链表。思路：快慢指针。Runtime: 0 ms, faster than 100.00% of Java online submissions for Linked List Cycle II.Memory Usage: 35.2 MB, less than 100.00% of Java online submissions for Linked List Cycle II./** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { if (null == head) { return head; } ListNode slow = head, fast = head; do { slow = slow.next; fast = fast.next; fast = (fast != null) ? fast.next : fast; } while (fast != null && slow != fast); if (null == fast) { return null; } for (slow = head; slow != fast; slow = slow.next, fast = fast.next); return slow; }} ...

题目要求Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.Note:1.Each of the array element will not exceed 100.2.The array size will not exceed 200.Example 1:Input: [1, 5, 11, 5]Output: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].Example 2:Input: [1, 2, 3, 5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets.假设有一个全为正整数的非空数组，将其中的数字分为两部分，确保两部分数字的和相等。思路和代码这和0-1背包问题是完全一样的，01背包问题是指假设有n个物品，每个物品中为weight[i]，假设背包的承重为k，问如何选择物品使得背包中的承重最大。而这里的问题等价于，有n个物品，每个物品承重为input[i]，问如何挑选物品，使得背包的承重搞好为所有物品重量和的一般。假设我们已经知道前i个物品是否能够构成重量k，我们令该值为dpi，那么第i+1个物品是否能够构成重量取决于dpi和dpi], 即i+1个物品能够构成重量k有两种情况，第一种选择了i+1个物品，则要寻找前i个物品是否构成k-input[i+1]的重量，第二种就是没有选择第i+1个物品，则直接判断前i个物品是否已经构成了k的重量。代码如下： public boolean canParition(int[] nums) { int sum = 0; for(int n : nums) { sum += n; } if(sum % 2 != 0) return false; int half = sum / 2; boolean[][] sums = new boolean[nums.length+1][half+1]; for(int i = 0 ; i<=nums.length ; i++) { for(int j = 0 ; j<=half ; j++) { if(i==0 && j==0){ sums[i][j] = true; }else if(i==0) { sums[i][j] = false; }else if(j==0){ sums[i][j] = true; }else { sums[i][j] = sums[i-1][j] || (nums[i-1] <= j ? sums[i-1][j-nums[i-1]] : false); } } } return sums[nums.length][half]; } ...

题目要求Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.This is case sensitive, for example “Aa” is not considered a palindrome here.Note:Assume the length of given string will not exceed 1,010.Example:Input:“abccccdd"Output:7Explanation:One longest palindrome that can be built is “dccaccd”, whose length is 7.输入一个字符串，计算用这个字符串中的值构成一个最长回数的长度是多少。思路和代码这是一道easy难度的题目，但是一次性写对也有挑战。直观来看，我们立刻就能想到统计字符串中每个字符出现的次数，如果该字符出现次数为偶数，则字符一定存在于回数中。但是我们忽略了一点，即如果字符中存在一个额外的单个字符位于中间，该字符串也能构成回数，如aabaa。这个细节需要注意。下面是O(N)时间的实现： public int longestPalindrome(String s) { int[] count = new int[52]; int max = 0; for(char c : s.toCharArray()) { if(c>=‘a’ && c<=‘z’){ count[c-‘a’]++; if(count[c-‘a’] % 2 == 0) { max +=2; } } if(c>=‘A’ && c<=‘Z’){ count[c-‘A’ + 26]++; if(count[c-‘A’+26] % 2 == 0) { max += 2; } } } if(max < s.length()) { max++; } return max; } ...

DescriptionWrite a program to find the nth super ugly number.Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.Example:Input: n = 12, primes = [2,7,13,19]Output: 32 Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19] of size 4.Note:1 is a super ugly number for any given primes.The given numbers in primes are in ascending order.0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.The nth super ugly number is guaranteed to fit in a 32-bit signed integer.描述编写一段程序来查找第 n 个超级丑数。超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。示例:输入: n = 12, primes = [2,7,13,19]输出: 32 解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。说明:1 是任何给定 primes 的超级丑数。给定 primes 中的数字以升序排列。0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。第 n 个超级丑数确保在 32 位有符整数范围内。思路这道题和第 264 题 Ugly Number II 做法类似。我们使用动态规划。状态：我们用 index 用于记录 primes 中每个质数上一次产生丑数的有效位置，并用一个数组 uglynum 记录产生的丑数。比如 index[2] = 7， 表示质数 primes[2] 上一次产生的质数在 uglynum 中的索引为 7 ，即产生的丑数为 uglynum[7]。初始值：index 所有值初始化 0，ugly 第一个值初始化为1。状态转移方程：获取下一个丑数：我们用 index 中记录的上一次质数产生的丑数在 uglynum 中的位置获得对应的丑数 uglynum[index[i]]，并用对应的质数 primes[i] 与 uglynum[index[i]] 相乘作为下一次可能的丑数，所有的丑数用一个临时数组 _next 存储。我们取所有数中的最小值作为下个丑数。更新 index 数组：如果 uglynext == _next[i]，我们让 index[i] 自增一次。结果：丑数数组的最后一个值。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-19 15:35:20# @Last Modified by: 何睿# @Last Modified time: 2019-02-19 16:11:26class Solution: def nthSuperUglyNumber(self, n: ‘int’, primes: ‘List[int]’) -> ‘int’: """ :type n: int :rtype: int """ # 处理特殊情况，如果n为1或者primes为空，返回1 if n < 2 or not primes: return 1 # 声明一个数组，用于存储获取的丑数 uglynum = [1] # 辅助变量，primes的个数，当前生成的丑数的个数 num, count = len(primes), 1 # index数组用于存储primes中每个数上一次产生有效数的下一个位置 index = [0 for _ in range(num)] while count < n: # 动态规划，用primes中的每个数从上一次产生有效位置的地方产生下一个数 _next = [primes[i] * uglynum[index[i]] for i in range(num)] # 下一个丑数是产生的丑数中最小的数 uglynext = min(_next) # 更新索引值 for i in range(num): if uglynext == _next[i]: index[i] += 1 uglynum.append(uglynext) count += 1 # 返回最后一个丑数 return uglynum[-1]源代码文件在 这里。©本文首发于 何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明. ...

题目要求Suppose we abstract our file system by a string in the following manner:The string “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext” represents:dir subdir1 subdir2 file.extThe directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.The string “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext” represents:dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.extThe directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is “dir/subdir2/subsubdir2/file2.ext”, and its length is 32 (not including the double quotes).Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.Note:The name of a file contains at least a . and an extension.The name of a directory or sub-directory will not contain a ..Time complexity required: O(n) where n is the size of the input string.Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.要求从String字符串中找到最长的文件路径。这里要注意，要求的是文件路径，文件夹路径不予考虑。文件和文件夹的区别在于文件中一定包含.。这里\n代表根目录平级，每多一个\t就多一层路径，这一层路径都是相对于当前的上层路径的。以dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext为例dir为第0层目录\n\tsubdir1代表subdir1是第一层目录，且其是当前父目录dir的子目录\n\t\n\tsubdir2代表subdir2为第一层目录，且其是当前父目录dir的子目录，此时的一级父目录从subdir1更新为subdir2\n\t\tfile.ext代表tfile.ext为二级目录，位于当前一级目录subdir2之下思路和代码综上分析，我们可以记录一个信息，即当前每一级的目录究竟是谁，每次只需要保留当前一级目录已有的路径长度即可。还是拿上面的例子dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext：遍历完dir: 0级目录长度为3遍历完\n\tsubdir: 0级目录长度为3, 1级目录长度为11（dir/subdir1）遍历完\n\tsubdir2: 0级目录长度为3, 1级目录长度为11（dir/subdir2）遍历完\n\t\tfile.ext: 0级目录长度为3, 1级目录长度为11（dir/subdir2）, 2级目录长度为20综上，最长的文件路径长为20代码如下： public int lengthLongestPath(String input) { if(input==null || input.isEmpty()) return 0; //记录当前每一级路径对应的路径长度 List<Integer> stack = new ArrayList<Integer>(); int left = 0, right = 0; int max = 0; int curDepth = 0; //当前遍历的是文件还是文件夹 boolean isFile = false; while(right < input.length()) { char c = input.charAt(right); if(c == ‘\n’ || c == ‘\t’) { //如果是文件分割符的起点，则处理前面的字符串 if(right-1>=0 && input.charAt(right-1)!=’\n’ && input.charAt(right-1)!=’\t’) { int length = right - left; if(stack.isEmpty()) { stack.add(length+1); }else if(curDepth == 0){ stack.set(0, length+1); }else{ int prev = stack.get(curDepth-1); int now = prev + length + 1; if(stack.size() <= curDepth) { stack.add(now); }else{ stack.set(curDepth, now); } } if(isFile) { max = Math.max(max, stack.get(curDepth)-1); } left = right; isFile = false; } //如果是文件分隔符的末尾，则处理文件分隔符，判断是几级路径 if(right+1<input.length() && input.charAt(right+1)!=’\n’ && input.charAt(right+1) !=’\t’){ curDepth = right - left; left = right+1; } }else if(c == ‘.’) { isFile = true; } right++; } //处理最后的字符串 if(left != right && isFile) { if(curDepth == 0) { max = Math.max(max, right - left); }else { max = Math.max(max, stack.get(curDepth-1) + right - left); } } return max; } ...

DescriptionGiven n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.Find the maximum coins you can collect by bursting the balloons wisely.Note:You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100Example:Input: [3,1,5,8]Output: 167 Explanation: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> [] coins = 315 + 358 + 138 + 181 = 167描述有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] nums[i] nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。求所能获得硬币的最大数量。说明:你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100示例:输入: [3,1,5,8]输出: 167 解释: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> [] coins = 315 + 358 + 138 + 181 = 167思路这道题使用动态规划。状态：我们声明一个二维数组 matrix[len(nums)][len(nums)]，matrix[i][j] 表示戳数组 nums[i] (包括) 到数组 nums[j]的气球可以获得的最大值。初始状态：matrix 的每一个值都为0。状态转移方程：从第 left 个位置到第 rigth 个位置，我们以 left 到 right 中的任意一个位置 k 为例，假设最后一个戳 k 气球（其他所有气球已经戳爆了）则我们可以获得的硬币为 num[left:k] + nums[left-1] * nums[k] * nums[right+1] + nums[k:right]num[left:k]：戳破 k 位置左边所有气球的可以获得的硬币。nums[left-1] * nums[k] * nums[right+1]：戳破当前位置可以获得的气球，由于 num[left:right] 中只有 k 为位置没有被戳破，所以 k 位置左边的位置为 nums[left-1]，如果越界则置为1，右边的有效值为 nums[right+1] ，如果越界则置为1。nums[k:right]：戳破 k 位右边所有气球的可以获得的硬币。结果：matrix[0][len(nums)-1]。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-18 14:52:28# @Last Modified by: 何睿# @Last Modified time: 2019-02-18 15:44:09class Solution: def maxCoins(self, nums: ‘List[int]’) -> ‘int’: # 如果数组为空，我们返回0 if not nums: return 0 # 声明一个二维矩阵，matrix[i][j]表示戳num[i]到num[j]的气球可以获得的最大值 matrix = [[0] * len(nums) for _ in range(len(nums))] # left表示起点，right表示中点，count表示right-left的值 # 辅助变量初始化为0 left, right, count = 0, 0, 0 for count in range(0, len(nums)): # 每一趟循环，left都从最左边开始 left = 0 # right表示所有可能的中点 for right in range(count, len(nums)): # 临时变量用于记录最大值 _max = 0 # 从left到right中，我们以每一个位置为最后一个戳气球的位置 for j in range(left, right + 1): # 当前位置左边可以获得的最大值 _left = matrix[left][j - 1] if j - 1 >= left else 0 # 当前位置右边可以获得的最大值 _right = matrix[j + 1][right] if j + 1 <= right else 0 # 当前串的左边界的左边一个值 leftnum = nums[left - 1] if left - 1 >= 0 else 1 # 当前串的有边界的右边一个值 rightnum = nums[right + 1] if right + 1 < len(nums) else 1 # 以当前位置为嘴后一个戳气球的位置，可以获得的硬币个数 product = _left + nums[j] * leftnum * rightnum + _right _max = max(_max, product) # 更新最大值 matrix[left][right] = _max left += 1 # matrix[0][len(nums) - 1]表示从0到len(nums)可以获得的最多的硬币个数 return matrix[0][len(nums) - 1]源代码文件在 这里。©本文首发于 何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明. ...

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1:输入: [1,2,0]输出: 3示例 2:输入: [3,4,-1,1]输出: 2示例 3:输入: [7,8,9,11,12]输出: 1答案参考：/** * @param {number[]} nums * @return {number} */var firstMissingPositive = function(nums) { for (let i = 1; i < nums.length + 2; i++) { if (nums.indexOf(i) == -1) return i; }};

判断一个 9x9的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。上图是一个部分填充的有效的数独。数独部分空格内已填入了数字，空白格用 ‘.’ 表示。示例 1:输入:[ [“5”,“3”,".",".",“7”,".",".",".","."], [“6”,".",".",“1”,“9”,“5”,".",".","."], [".",“9”,“8”,".",".",".",".",“6”,"."], [“8”,".",".",".",“6”,".",".",".",“3”], [“4”,".",".",“8”,".",“3”,".",".",“1”], [“7”,".",".",".",“2”,".",".",".",“6”], [".",“6”,".",".",".",".",“2”,“8”,"."], [".",".",".",“4”,“1”,“9”,".",".",“5”], [".",".",".",".",“8”,".",".",“7”,“9”]]输出: true示例 2:输入:[ [“8”,“3”,".",".",“7”,".",".",".","."], [“6”,".",".",“1”,“9”,“5”,".",".","."], [".",“9”,“8”,".",".",".",".",“6”,"."], [“8”,".",".",".",“6”,".",".",".",“3”], [“4”,".",".",“8”,".",“3”,".",".",“1”], [“7”,".",".",".",“2”,".",".",".",“6”], [".",“6”,".",".",".",".",“2”,“8”,"."], [".",".",".",“4”,“1”,“9”,".",".",“5”], [".",".",".",".",“8”,".",".",“7”,“9”]]输出: false解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。说明:一个有效的数独（部分已被填充）不一定是可解的。只需要根据以上规则，验证已经填入的数字是否有效即可。给定数独序列只包含数字 1-9 和字符 ‘.’ 。给定数独永远是 9x9 形式的。答案参考：/** * @param {character[][]} board * @return {boolean} */var isValidSudoku = function(board) {// 检查每一行 for (let arr of board) { let row = [] for (let c of arr) { if (c !== ‘.’) row.push(c); } let set = new Set(row) if (set.size !== row.length) return false; } // 检查每一列 for (let i = 0; i < 9; i++) { let col = [] board.map( arr => { if (arr[i] !== ‘.’) col.push(arr[i]) }) let set = new Set(col) if (set.size !== col.length) return false; } // 检查每个小方块 for (let x = 0; x < 9; x += 3) { for (let y = 0; y < 9; y += 3) { let box = [] for (let a = x; a < 3 + x; a ++) { for (let b = y; b < 3 + y; b ++) { if (board[a][b] !== ‘.’) box.push(board[a][b]) } } let set = new Set(box) if (set.size !== box.length) return false } } return true}; ...

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：1112112111112211 被读作 “one 1” (“一个一”) , 即 11。11 被读作 “two 1s” (“两个一”）, 即 21。21 被读作 “one 2”, “one 1” （“一个二” , “一个一”) , 即 1211。给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。注意：整数顺序将表示为一个字符串。示例 1:输入: 1输出: “1"示例 2:输入: 4输出: “1211"答案参考：/** * @param {number} n * @return {string} */var countAndSay = function(n) { let ans = “1” let i = 1 while(i < n) { ans = say(ans) i++ } return ans};function say(s){ let curChar = s[0] let curCount = 1 let ans = "” for (let i = 1; i < s.length; i++){ if (s[i] == curChar){ curCount++ } else { ans += curCount + curChar curChar = s[i] curCount = 1 } } ans += curCount + curChar return ans} ...

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]示例 2:输入: candidates = [2,5,2,1,2], target = 5,所求解集为:[[1,2,2],[5]]答案参考：/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */var combinationSum2 = function(candidates, target) { var item=[],path=[]; candidates=candidates.sort(function(a,b){return a-b}) GG(candidates,target,target,item,path,0) return item function GG(candidates,target,remain,item,path,start){ if(remain<0) return; if(remain==0){ path=path.slice() item.push(path); } else{ for(var i=start;i<candidates.length;i++){ if(i>start&&candidates[i]==candidates[i-1]) continue; path.push(candidates[i]) GG(candidates,target,remain-candidates[i],item,path,i+1) path.pop() } } }}; ...

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。示例 1:输入: candidates = [2,3,6,7], target = 7,所求解集为:[[7],[2,2,3]]示例 2:输入: candidates = [2,3,5], target = 8,所求解集为:[[2,2,2,2],[2,3,3],[3,5]]答案参考：/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */var combinationSum = function(candidates, target) { var item=[],path=[]; no_repetition(candidates,target,0,item,path); function no_repetition(candidates,target,it,item,path){ if(target<0) return; if(target==0){ path=path.slice() item.push(path); return } for(var i=it;i<candidates.length;i++){ path.push(candidates[i]); no_repetition(candidates,target-candidates[i],i,item,path) path.pop() } } return item};

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1答案参考：/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */var nextPermutation = function(nums) { for(var i = nums.length - 1; i > 0 && nums[i] <= nums[i - 1]; i–); if(i === 0){ reverse(0, nums.length - 1); return; } for(var j = i + 1; j < nums.length && nums[i - 1] < nums[j]; j++); swap(i - 1, j - 1); reverse(i, nums.length - 1); return; function reverse(start, end){ while(start < end){ swap(start, end); start++; end–; } } function swap(i, j){ var tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }}; ...

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。示例 1:输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]示例 2:输入: nums = [5,7,7,8,8,10], target = 6输出: [-1,-1]答案参考：/** * @param {number[]} nums * @param {number} target * @return {number[]} */var searchRange = function (nums, target) { let targetIndex = binarySearch(nums, target, 0, nums.length - 1) if (targetIndex == -1) return [-1, -1] let l = targetIndex, r = targetIndex while(l > 0 && nums[l - 1] == target){ l– } while(r < nums.length - 1 && nums[r + 1] == target){ r++ } return [l, r]};function binarySearch(arr, val, lo, hi) { if (hi < lo) return -1 let mid = lo + parseInt((hi - lo) / 2) if (val < arr[mid]) { return binarySearch(arr, val, lo, mid - 1) } else if (val > arr[mid]) { return binarySearch(arr, val, mid + 1, hi) } else { return mid }} ...

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。示例 1:输入: [1,3,5,6], 5输出: 2示例 2:输入: [1,3,5,6], 2输出: 1示例 3:输入: [1,3,5,6], 7输出: 4示例 4:输入: [1,3,5,6], 0输出: 0答案参考：/** * @param {number[]} nums * @param {number} target * @return {number} */var searchInsert = function(nums, target) { //遍历数组 for (var i = 0,len = nums.length; i < len; i++) { //这里处理值被插在数组头和数组中的情况 if (nums[i] >= target ) { return i; } } //这里处理值被插在数组尾的情况 return len;}

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.Note: A leaf is a node with no children.Example:Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \7 2 5 1Return:[ [5,4,11,2], [5,8,4,5]]难度：medium题目：给定二叉树与一个数和sum，找出所有由根到叶结点的和为sum的路径思路：递归（前序遍历）Runtime: 2 ms, faster than 56.03% of Java online submissions for Path Sum II.Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Path Sum II./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> result = new ArrayList<>(); pathSum(root, sum, new Stack<>(), result); return result; } private void pathSum(TreeNode root, int sum, Stack<Integer> stack, List<List<Integer>> result) { if (null != root) { if (null == root.left && null == root.right) { if (sum == root.val) { stack.push(root.val); result.add(new ArrayList<>(stack)); stack.pop(); } } else { stack.push(root.val); pathSum(root.left, sum - root.val, stack, result); pathSum(root.right, sum - root.val, stack, result); stack.pop(); } } }} ...

给定两个整数，被除数 dividend和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。示例 1:输入: dividend = 10, divisor = 3输出: 3示例 2:输入: dividend = 7, divisor = -3输出: -2说明:被除数和除数均为 32 位有符号整数。除数不为 0。假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。答案参考：/** * @param {number} dividend * @param {number} divisor * @return {number} */var divide = function (dividend, divisor) { let result = 0, sign = 1, mul = 1; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { sign = -1; } dividend = Math.abs(dividend); divisor = Math.abs(divisor); divisor2 = divisor; while (dividend >= divisor2) { if (dividend > (divisor2 + divisor2)) { divisor2 += divisor2; mul += mul; } dividend -= divisor2; result += mul; } while (dividend >= divisor) { dividend -= divisor; result += 1; } if (sign == 1 && result > (Math.pow(2, 31) - 1)) { return Math.pow(2, 31) - 1; } else if (sign == -1 && result < -Math.pow(2, 31)) { return -Math.pow(2, 31); } if (sign == 1) { return result; } else { return -result; }}; ...

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).For example:Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7return its zigzag level order traversal as:[ [3], [20,9], [15,7]]难度：medium题目：给定二叉树，返回其之字型层次遍历结点值。思路：层次遍历Runtime: 1 ms, faster than 90.32% of Java online submissions for Binary Tree Zigzag Level Order Traversal.Memory Usage: 37.1 MB, less than 100.00% of Java online submissions for Binary Tree Zigzag Level Order Traversal./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (null == root) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int currentLevelCount = 1, nextLevelCount = 0; boolean direction = true; while (!queue.isEmpty()) { List<Integer> curLevelElems = new ArrayList<>(currentLevelCount); for (int i = 0; i < currentLevelCount; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.add(node.left); nextLevelCount++; } if (node.right != null) { queue.add(node.right); nextLevelCount++; } if (direction) { curLevelElems.add(node.val); } else { curLevelElems.add(0, node.val); } } result.add(curLevelElems); currentLevelCount = nextLevelCount; nextLevelCount = 0; direction = !direction; } return result; }} ...

实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。示例 1:输入: haystack = “hello”, needle = “ll"输出: 2示例 2:输入: haystack = “aaaaa”, needle = “bba"输出: -1说明:当needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。答案参考：/** * @param {string} haystack * @param {string} needle * @return {number} */var strStr = function(haystack, needle) { //判断查询字符串是否为空 if (!needle) { return 0; } //调用indexOf函数返回子串的位置 return haystack.indexOf(needle);};

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。示例 1:给定 nums = [3,2,2,3], val = 3,函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。示例 2:给定 nums = [0,1,2,2,3,0,4,2], val = 2,函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0,1,3,0,4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。说明:为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。你可以想象内部操作如下:// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。for (int i = 0; i < len; i++) { print(nums[i]);}答案参考：/** * @param {number[]} nums * @param {number} val * @return {number} */var removeElement = function(nums, val) { //遍历数组 for (var i = 0; i < nums.length; i++) { //找出值等于 val 的元素 if (nums[i] == val) { //删除之并向前移位 nums.splice(i,1); i–; } } //返回修改后数组的长度 return nums.length;}; ...

题目要求Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.Example 1:Input:s = “aaabb”, k = 3Output:3The longest substring is “aaa”, as ‘a’ is repeated 3 times.Example 2:Input:s = “ababbc”, k = 2Output:5The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.找出字符串中的最长子字符串，满足该子字符串中任何字符出现的次数都大于k。思路和代码这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元素一定不在子字符串中，只需要将其作为分界点，分别找出左半部分和右半部分的满足条件的最长子字符串。 public int longestSubstring(String s, int k) { return longestSubstring(s, k, 0, s.length()-1); } public int longestSubstring(String s, int k, int left, int right) { if(left > right) { return 0; } int[] count = new int[26]; for(int i = left ; i<=right ; i++) { count[s.charAt(i) - ‘a’]++; } int result = right - left + 1; for(int i = left ; i<=right ; i++) { if(count[s.charAt(i)-‘a’] < k && count[s.charAt(i)-‘a’] > 0) { int leftLongest = longestSubstring(s, k, left, i-1); int rightLongest = longestSubstring(s, k, i+1, right); result = Math.max(leftLongest, rightLongest); break; } } return result; } ...

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.Example:Input: 3Output:[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3]]Explanation:The above output corresponds to the 5 unique BST’s shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3难度：medium题目：给出整数n，生成其所有可能BST.思路：递归，分别把1到n作为根结点，例如i, 则1到i-1作为左子树，i+1到n作为右子树。Runtime: 2 ms, faster than 89.21% of Java online submissions for Unique Binary Search Trees II.Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Unique Binary Search Trees II./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<TreeNode> generateTrees(int n) { if (n <= 0) { return new ArrayList<TreeNode>(); } return generateTrees(1, n); } private List<TreeNode> generateTrees(int left, int right) { if (left > right) { List<TreeNode> treeNodes = new ArrayList<>(); treeNodes.add(null); return treeNodes; } List<TreeNode> result = new ArrayList<>(); for (int i = left; i <= right; i++) { List<TreeNode> leftList = generateTrees(left, i - 1); List<TreeNode> rightList = generateTrees(i + 1, right); for (TreeNode lChild: leftList) { for (TreeNode rChild: rightList) { TreeNode root = new TreeNode(i); root.left = lChild; root.right = rChild; result.add(root); } } } return result; }} ...

Given a binary tree, flatten it to a linked list in-place.For example, given the following tree: 1 / \ 2 5 / \ \3 4 6The flattened tree should look like:1 \ 2 \ 3 \ 4 \ 5 \ 6难度：medium题目：给定二叉树，原地扁平化。思路：后序遍历Runtime: 6 ms, faster than 100.00% of Java online submissions for Flatten Binary Tree to Linked List.Memory Usage: 40 MB, less than 100.00% of Java online submissions for Flatten Binary Tree to Linked List./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public void flatten(TreeNode root) { rightFlatten(root); } private TreeNode rightFlatten(TreeNode root) { if (null == root) { return root; } TreeNode left = rightFlatten(root.left); TreeNode right = rightFlatten(root.right); if (left != null) { root.left = null; root.right = left; TreeNode rightMost = left; while (rightMost.right != null) { rightMost = rightMost.right; } rightMost.right = right; } return root; }} ...

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?Example:Input: 3Output: 5Explanation:Given n = 3, there are a total of 5 unique BST’s: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3难度：medium题目：给定整数n，计算有多少种BST结构。class Solution { public int numTrees(int n) { long c = 1; // Catalan number // Catalan (n+1) = (4n+2) / (n+2) Catalan n for(int i = 1; i < n; i++){ c = c * 2 * (2 * i + 1) / (i + 2); } return (int) c; }} ...

Given a binary tree, determine if it is a valid binary search tree (BST).Assume a BST is defined as follows:The left subtree of a node contains only nodes with keys less than the node’s key.The right subtree of a node contains only nodes with keys greater than the node’s key.Both the left and right subtrees must also be binary search trees.Example 1:Input: 2 / \ 1 3Output: trueExample 2: 5 / \ 1 4 / \ 3 6Output: falseExplanation: The input is: [5,1,4,null,null,3,6]. The root node’s value is 5 but its right child’s value is 4.难度：medium题目：给定二叉树，判断其是否为二叉搜索树。思路：递归，并记录当前结点的取值范围。Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Binary Search Tree.Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Validate Binary Search Tree./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public boolean isValidBST(TreeNode root) { if (null == root) { return true; } return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean isValidBST(TreeNode root, long minVal, long maxVal) { if (null == root) { return true; } if (root.val >= maxVal || root.val <= minVal) { return false; } return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal); }} ...

题目要求A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:For 1-byte character, the first bit is a 0, followed by its unicode code.For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.This is how the UTF-8 encoding would work: Char. number range | UTF-8 octet sequence (hexadecimal) | (binary) ——————–+——————————————— 0000 0000-0000 007F | 0xxxxxxx 0000 0080-0000 07FF | 110xxxxx 10xxxxxx 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxxGiven an array of integers representing the data, return whether it is a valid utf-8 encoding.Note:The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.Example 1:data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.Return true.It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.Example 2:data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.Return false.The first 3 bits are all one’s and the 4th bit is 0 means it is a 3-bytes character.The next byte is a continuation byte which starts with 10 and that’s correct.But the second continuation byte does not start with 10, so it is invalid.检验整数数组能否构成合法的UTF8编码的序列。UTF8的字节编码规则如下：每个UTF8字符包含1~4个字节如果只包含1个字节，则该字节以0作为开头，剩下的位随意如果包含两个或两个以上字节，则起始字节以n个1和1个0开头，例如，如果该UTF8字符包含两个字节，则第一个字节以110开头，同理，三个字符的第一个字节以1110开头。剩余的字节必须以10开头。思路和代码首先我们整理一下，每一种类型的UTF8字符包含什么样的规格：只包含一个字节，该字节格式为0xxxxxxx，则转换为整数的话，该整数必须小于128（1000000）包含多个字节，则头字节格式为110xxxxx, 1110xxxx, 11110xxx。而紧跟其后的字符必须格式为10xxxxxx。综上所述：num<1000000: 单字节10000000=<num<11000000: 多字节字符的跟随字节11000000<=num<11100000: 两个字节的起始字节11100000<=num<11110000: 三个字节的起始字节11110000<=num<11111000: 四个字节的起始字节下面分别是这题的两种实现：递归实现： private static final int ONE_BYTE = 128; //10000000 private static final int FOLLOW_BYTE = 192; //11000000 private static final int TWO_BYTE = 224; //11100000 private static final int THREE_BYTE = 240;//11110000 private static final int FOUR_BYTE = 248;//11111000 public boolean validUtf8(int[] data) { return validUtf8(data, 0); } public boolean validUtf8(int[] data, int startAt) { if(startAt >= data.length) return true; int first = data[startAt]; int followLength = 0; if(first < ONE_BYTE) { return validUtf8(data, startAt+1); }else if(first < FOLLOW_BYTE){ return false; }else if(first <TWO_BYTE) { followLength = 2; }else if(first < THREE_BYTE) { followLength = 3; }else if(first < FOUR_BYTE) { followLength = 4; }else { return false; } if(startAt + followLength > data.length) return false; for(int i = 1 ; i<followLength ; i++) { int next = data[startAt + i]; if(next < ONE_BYTE || next >= FOLLOW_BYTE) { return false; } } return validUtf8(data, startAt + followLength); }循环实现： private static final int ONE_BYTE = 128; //10000000 private static final int FOLLOW_BYTE = 192; //11000000 private static final int TWO_BYTE = 224; //11100000 private static final int THREE_BYTE = 240;//11110000 private static final int FOUR_BYTE = 248;//11111000 public boolean validUtf8(int[] data) { return validUtf8(data, 0); } public boolean validUtf8(int[] data, int startAt) { int followCount = 0; for(int num : data) { if(num < ONE_BYTE) { if(followCount != 0) { return false; } }else if(num < FOLLOW_BYTE) { if(followCount == 0) { return false; } followCount–; }else if(num < TWO_BYTE) { if(followCount != 0) { return false; } followCount = 1; }else if(num < THREE_BYTE) { if(followCount != 0) { return false; } followCount = 2; }else if(num < FOUR_BYTE) { if(followCount != 0) { return false; } followCount = 3; }else { return false; } } return followCount == 0; } ...

DescriptionFor an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.FormatThe graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.Example 1 :Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]] 0 | 1 / \ 2 3 Output: [1]Example 2 :Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] 0 1 2 \ | / 3 | 4 | 5 Output: [3, 4]Note:According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.描述对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。注意：该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。示例 1:输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]] 0 | 1 / \ 2 3 输出: [1]示例 2:输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] 0 1 2 \ | / 3 | 4 | 5 输出: [3, 4]说明:根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。树的高度是指根节点和叶子节点之间最长向下路径上边的数量。思路最小高度树的根节点是图中最长路径的中间节点.我们用一个 List[set()] 的结构存储每个节点可以访问到的其他节点。一般情况下应该使用字典，以节点为键，能够遍历到的节点组成的哈希set为键，但由于题中的节点是从0开始的数字，我们可以用 List 来代替，索引就是键。最长路径的中间节点最多会有两个：最长路径有奇数个节点，则中间节点有 1 个；最长路径有偶数个节点，则中间节点有 2 个。基本思路是:找到所有的叶子节点，去掉所有叶子节点，找到新的所有叶子节点，去掉所有叶子节点 … 直到剩下的节点个数小于等于2个。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-17 13:46:09# @Last Modified by: 何睿# @Last Modified time: 2019-02-17 14:15:30class Solution: def findMinHeightTrees(self, n: ‘int’,edges: ‘List[List[int]]’) -> ‘List[int]’: # 如果只有一个节点，直接返回当前节点 if n == 1: return [0] # 路径：记录每个节点可以访问到的所有节点 type:list[set()] # 更一般的情况是利用字典实现，利用节点作为键，节点能够走到的所有节点 # 组成的set作为值，但是题中得节点为从0开始的数值，因此可以用list代替字典 paths = [set() for _ in range(n)] # 找到每个节点可以走到的下一个节点 for node1, node2 in edges: paths[node1].add(node2) paths[node2].add(node1) # 找到所有的叶子节点 leaves = [node for node in range(n) if len(paths[node]) == 1] # root用于记录剩下的节点 roots = n while roots > 2: # 更新剩下的节点个数 roots -= len(leaves) # 新的叶子节点 newleaves = [] for node in leaves: # 获取叶节点的父节点 parent = paths[node].pop() # 从叶节点的父节点中删除当前节点 paths[parent].remove(node) # 如果当前节点的父节点只能访问一个节点，则添加到新叶节点中 if len(paths[parent]) == 1: newleaves.append(parent) leaves = newleaves return leaves源代码文件在这里.©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明. ...

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:struct Node { int val; Node *left; Node right; Node next;}Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.Initially, all next pointers are set to NULL.Example:Input: {"$id":“1”,“left”:{"$id":“2”,“left”:{"$id":“3”,“left”:null,“next”:null,“right”:null,“val”:4},“next”:null,“right”:{"$id":“4”,“left”:null,“next”:null,“right”:null,“val”:5},“val”:2},“next”:null,“right”:{"$id":“5”,“left”:{"$id":“6”,“left”:null,“next”:null,“right”:null,“val”:6},“next”:null,“right”:{"$id":“7”,“left”:null,“next”:null,“right”:null,“val”:7},“val”:3},“val”:1}Output: {"$id":“1”,“left”:{"$id":“2”,“left”:{"$id":“3”,“left”:null,“next”:{"$id":“4”,“left”:null,“next”:{"$id":“5”,“left”:null,“next”:{"$id":“6”,“left”:null,“next”:null,“right”:null,“val”:7},“right”:null,“val”:6},“right”:null,“val”:5},“right”:null,“val”:4},“next”:{"$id":“7”,“left”:{"$ref":“5”},“next”:null,“right”:{"$ref":“6”},“val”:3},“right”:{"$ref":“4”},“val”:2},“next”:null,“right”:{"$ref":“7”},“val”:1}Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.Note:You may only use constant extra space.Recursive approach is fine, implicit stack space does not count as extra space for this problem.难度：medium题目：给定一满二叉树，所有叶结点在同一层，每个结点都有左右子树。思路：自上至下自左至右遍历Runtime: 0 ms, faster than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node.Memory Usage: 36.1 MB, less than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node./// Definition for a Node.class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val,Node _left,Node _right,Node _next) { val = _val; left = _left; right = _right; next = _next; }};/class Solution { public Node connect(Node root) { Node ptr = root; while (ptr != null) { Node head = ptr, rightMost = null; ptr = ptr.left; while (head != null && head.left != null) { if (rightMost != null) { rightMost.next = head.left; } head.left.next = head.right; rightMost = head.right; head = head.next; } } return root; }} ...

Given a binary treestruct Node { int val; Node *left; Node right; Node next;}Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.Initially, all next pointers are set to NULL.Example:Input: {"$id":“1”,“left”:{"$id":“2”,“left”:{"$id":“3”,“left”:null,“next”:null,“right”:null,“val”:4},“next”:null,“right”:{"$id":“4”,“left”:null,“next”:null,“right”:null,“val”:5},“val”:2},“next”:null,“right”:{"$id":“5”,“left”:null,“next”:null,“right”:{"$id":“6”,“left”:null,“next”:null,“right”:null,“val”:7},“val”:3},“val”:1}Output: {"$id":“1”,“left”:{"$id":“2”,“left”:{"$id":“3”,“left”:null,“next”:{"$id":“4”,“left”:null,“next”:{"$id":“5”,“left”:null,“next”:null,“right”:null,“val”:7},“right”:null,“val”:5},“right”:null,“val”:4},“next”:{"$id":“6”,“left”:null,“next”:null,“right”:{"$ref":“5”},“val”:3},“right”:{"$ref":“4”},“val”:2},“next”:null,“right”:{"$ref":“6”},“val”:1}Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.Note:1. You may only use constant extra space.2. Recursive approach is fine, implicit stack space does not count as extra space for this problem.难度：medium题目：给定二叉树，计算结点指向其相邻右结点的下一跳指针。如果没有相邻的右结点则next为NULL.思路：递归Runtime: 3 ms, faster than 18.40% of Java online submissions for Populating Next Right Pointers in Each Node II.Memory Usage: 51.8 MB, less than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node II./// Definition for a Node.class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val,Node _left,Node _right,Node _next) { val = _val; left = _left; right = _right; next = _next; }};/class Solution { public Node connect(Node root) { Node ptr = root; while (ptr != null) { ptr = buildNodeNext(ptr); } return root; } private Node buildNodeNext(Node head) { if (null == head) { return null; } Node nextLevelLeftMost = buildNodeNext(head.next); Node left = head.left; Node right = head.right; if (left != null && right != null) { left.next = right; right.next = nextLevelLeftMost; return left; } if (left != null && right == null) { left.next = nextLevelLeftMost; return left; } if (left == null && right != null) { right.next = nextLevelLeftMost; return right; } return nextLevelLeftMost; }} ...

Given a string s, partition s such that every substring of the partition is a palindrome.Return all possible palindrome partitioning of s.Example:Input: “aab"Output:[ [“aa”,“b”], [“a”,“a”,“b”]]难度：medium题目：给定一字符串，切分字符串使得每个子串为回文字符串。返回所有可能的切分。思路：首先利用动态规划找出所有回文定义pi 表示从子串p从i到j是回文。转换方程p[i][j] = p[i + 1][j - 1] && s[i] == s[j]然后利用递归收集所有可能的切分Runtime: 3 ms, faster than 99.87% of Java online submissions for Palindrome Partitioning.Memory Usage: 39.5 MB, less than 100.00% of Java online submissions for Palindrome Partitioning.class Solution { public List<List<String>> partition(String s) { if (null == s || s.length() < 1) { return new ArrayList(); } int n = s.length(); if (1 == s.length()) { return Arrays.asList(Arrays.asList(s)); } char[] sc = s.toCharArray(); boolean[][] bc = new boolean[n][n]; // 初始化 p1 p2 for (int i = 0; i < n - 1; i++) { bc[i][i] = true; if (sc[i] == sc[i + 1]) { bc[i][i + 1] = true; } } bc[n - 1][n - 1] = true; // i indicates string length for (int i = 3; i <= n; i++) { // j indicates string index for (int j = 0; j <= n - i; j++) { boolean b = (sc[j] == sc[j + i - 1]); bc[j][j + i - 1] = b && bc[j + 1][j + i - 1 - 1]; } } //收集切分 List<List<String>> result = new ArrayList<>(); buildPalindrome(bc, result, new Stack<>(), s, 0, n); return result; } private void buildPalindrome(boolean[][] bc, List<List<String>> result, Stack<String> stack, String s, int depth, int n) { if (n == depth) { result.add(new ArrayList(stack)); return; } for (int i = depth; i < n; i++) { if (bc[depth][i]) { stack.push(s.substring(depth, i + 1)); buildPalindrome(bc, result, stack, s, i + 1, n); stack.pop(); } } }} ...

题目要求Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.Note:The array size can be very large. Solution that uses too much extra space will not pass the judge.Example:int[] nums = new int[] {1,2,3,3,3};Solution solution = new Solution(nums);// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.solution.pick(3);// pick(1) should return 0. Since in the array only nums[0] is equal to 1.solution.pick(1);设计一个数据结构，使得从该数据结构中查询一个数字时，能够以等概率返回该数字所在的任何下标。额外的要求是只要占用O(1)的额外的空间复杂度。思路一：O(2n)的实现其实要是想在O(1)的时间内完成随机数的获取，只需要缓存每个数字出现的下标，但是这意味着需要先对数据进行遍历，并且还需要O(n)的空间来额外存储数字下标的集合。这违背了题目意思。所以我们只能每次在获取数字的时候来统计数字出现的次数，然后针对次数获取随机数下标。代码如下： private int[] nums; private Random r; public Solution(int[] nums) { this.nums = nums; this.r = new Random(); } public int pick(int target) { int count = 0; int result = -1; for(int i = 0 ; i<nums.length ; i++) { if(target == nums[i]) { count++; } } int index = r.nextInt(count); for(int i = 0 ; i<nums.length ; i++) { if(target == nums[i]) { index–; if(index == -1){ result = i; break; } } } return result; }思路二：蓄水池问题有没有可能在一次的遍历中，找到这个随机下标呢？这就涉及到一个概率问题，即当我在遍历过程中遇到这个数字时，我是否需要选择它作为我的结果值。首先介绍一下蓄水池抽样算法。蓄水池抽样算法主要对应的是这样的一个问题，假设有一个非常大的数据集，或者是一个以流的形式作为输入的数据集，希望从中选择K个样本，此时我们可能无法把所有的样本都放在内存中，因此只能保存一个大小为K的集合，每次遇到一个数据时，决定是否将其放入样本中。因此，假设当前遇到的数据总共有N个，如果N小于K，则每个数据被选中的概率为1，如果N>K，则每个数据被选中的概率为K/N，旧样本中数据被保留的概率为1 - K(N-K)/N即K/N，因此每一个旧的数据被替换掉的概率为1/N。按照这个思路，我们在下面的遍历时，每遇到一个新元素，就判断当前选中的元素是否会被该元素替换掉即可。 private int[] nums; private Random r; public Solution(int[] nums) { this.nums = nums; this.r = new Random(); } public int pick(int target) { int count = 0; int result = -1; for(int i = 0 ; i<nums.length ; i++) { if(nums[i] == target) { int index = r.nextInt(++count); if(index == 0) { result = i; } } } return result; } ...

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.An example is the root-to-leaf path 1->2->3 which represents the number 123.Find the total sum of all root-to-leaf numbers.Note: A leaf is a node with no children.Example:Input: [1,2,3] 1 / \ 2 3Output: 25Explanation:The root-to-leaf path 1->2 represents the number 12.The root-to-leaf path 1->3 represents the number 13.Therefore, sum = 12 + 13 = 25.Example 2:Input: [4,9,0,5,1] 4 / \ 9 0 / \5 1Output: 1026Explanation:The root-to-leaf path 4->9->5 represents the number 495.The root-to-leaf path 4->9->1 represents the number 491.The root-to-leaf path 4->0 represents the number 40.Therefore, sum = 495 + 491 + 40 = 1026.难度：medium题目：给定结点值只包含0-9的二叉树，每条从根到叶子的路径表示一个整数。找出所有这样的数并返回其和。注意：叶结点即没有左右子结点/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int sumNumbers(TreeNode root) { return sumNumbers(root, “”); } private int sumNumbers(TreeNode root, String s) { if (null == root) { return 0; } s += root.val; if (null == root.left && null == root.right) { return Integer.parseInt(s); } return sumNumbers(root.left, s) + sumNumbers(root.right, s); }} ...

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.For example, given the following triangle[ [2], [3,4], [6,5,7], [4,1,8,3]]The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).Note:Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.难度：medium题目：给定一三角形数组，找出从上到下最小的路径和。每步只可以向下一行的相邻元素移动。Runtime: 4 ms, faster than 87.60% of Java online submissions for Triangle.Memory Usage: 38.5 MB, less than 100.00% of Java online submissions for Triangle.class Solution { public int minimumTotal(List<List<Integer>> triangle) { int m = triangle.size(); if (1 == m) { return triangle.get(0).get(0); } int[][] table = new int[m][m]; for (int i = 0; i < m; i++) { for (int j = 0; j <= i; j++) { table[i][j] = triangle.get(i).get(j); } } int result = table[0][0]; for (int i = 1; i < m; i++) { result = table[i][0] + table[i - 1][0]; for (int j = 0; j <= i; j++) { if (0 == j) { table[i][j] += table[i - 1][j]; } else if (j == i) { table[i][j] += table[i - 1][j - 1]; } else { table[i][j] += Math.min(table[i - 1][j], table[i - 1][j - 1]); } result = Math.min(table[i][j], result); } } return result; }} ...

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.Example:X X X XX O O XX X O XX O X XAfter running your function, the board should be:X X X XX X X XX X X XX O X XExplanation:Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ on the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.难度：medium题目：给定由X和O组成的二维表格，找出所有由X包含的区域并将O转成X.思路：遍历二维表格四边将以0开始的元素延伸到整个二维表并将其值置成非X非O（如Ｂ）字符用以区分与其它元素。然后遍历整个二维表将除Ｂ以外的所有元素设为X, Ｂ元素恢复为ORuntime: 4 ms, faster than 96.33% of Java online submissions for Surrounded Regions.Memory Usage: 40.7 MB, less than 100.00% of Java online submissions for Surrounded Regions.class Solution { public void solve(char[][] board) { if (null == board || board.length <= 1 || board[0].length <= 1) { return; } int m = board.length, n = board[0].length; for (int i: Arrays.asList(0, m - 1)) { for (int j = 0; j < n; j++) { if (board[i][j] == ‘O’) { color(board, i, j); } } } for (int i: Arrays.asList(0, n - 1)) { for (int j = 0; j < m; j++) { if (board[j][i] == ‘O’) { color(board, j, i); } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == ‘O’ || board[i][j] == ‘X’) { board[i][j] = ‘X’; } else { board[i][j] = ‘O’; } } } } private void color(char[][] board, int i, int j) { if (i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] != ‘O’) { return; } board[i][j] = ‘B’; color(board, i + 1, j); color(board, i - 1, j); color(board, i, j + 1); color(board, i, j - 1); }} ...

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.Return a deep copy of the list.难度：medium题目：给定一链表其每个结点包含一随机指针可以指向任意一结点或是为空。思路：hash mapRuntime: 2 ms, faster than 72.52% of Java online submissions for Copy List with Random Pointer.Memory Usage: 38.5 MB, less than 100.00% of Java online submissions for Copy List with Random Pointer./** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */public class Solution { public RandomListNode copyRandomList(RandomListNode head) { Map<RandomListNode, RandomListNode> mrr = new HashMap<>(); RandomListNode ptr = head; while (ptr != null) { mrr.put(ptr, new RandomListNode(ptr.label)); ptr = ptr.next; } ptr = head; while (ptr != null) { RandomListNode node = mrr.get(ptr); node.next = mrr.get(ptr.next); node.random = mrr.get(ptr.random); ptr = ptr.next; } return mrr.get(head); }} ...

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).For example:Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7return its level order traversal as:[ [3], [9,20], [15,7]]难度：medium题目：给定二叉树，返回其层次遍历结点值。思路：队列(FIFO)Runtime: 1 ms, faster than 86.63% of Java online submissions for Binary Tree Level Order Traversal.Memory Usage: 37.5 MB, less than 100.00% of Java online submissions for Binary Tree Level Order Traversal./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (null == root) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int currentLevelCount = 1, nextLevelCount = 0; List<Integer> currentLevelElements = new ArrayList<>(); while (!queue.isEmpty()) { TreeNode node = queue.poll(); currentLevelElements.add(node.val); if (node.left != null) { queue.add(node.left); nextLevelCount++; } if (node.right != null) { queue.add(node.right); nextLevelCount++; } currentLevelCount–; if (0 == currentLevelCount) { result.add(currentLevelElements); currentLevelElements = new ArrayList<>(); currentLevelCount = nextLevelCount; nextLevelCount = 0; } } return result; }} ...

Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…You may not modify the values in the list’s nodes, only nodes itself may be changed.Example 1:Given 1->2->3->4, reorder it to 1->4->2->3.Example 2:Given 1->2->3->4->5, reorder it to 1->5->2->4->3.难度：medium题目：给定一单链表 L: L0→L1→…→Ln-1→Ln, 重新排序为: L0→Ln→L1→Ln-1→L2→Ln-2→…思路：先使用快慢指针一个一次走一步，另一个一次走两步，找出中间点。再使用头插法处理后半段，最后合并两链表。Runtime: 2 ms, faster than 99.27% of Java online submissions for Reorder List.Memory Usage: 40.4 MB, less than 100.00% of Java online submissions for Reorder List./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public void reorderList(ListNode head) { if (null == head) { return; } ListNode oneStepPtr = head, twoStepsPtr = head, midPtr = oneStepPtr; while (twoStepsPtr != null) { midPtr = oneStepPtr; oneStepPtr = oneStepPtr.next; twoStepsPtr = (null == twoStepsPtr.next) ? null : twoStepsPtr.next.next; } midPtr.next = null; ListNode dummyHead = new ListNode(0), node = null; while (oneStepPtr != null) { node = oneStepPtr; oneStepPtr = oneStepPtr.next; node.next = dummyHead.next; dummyHead.next = node; } ListNode ptr = head; dummyHead = dummyHead.next; while (ptr != null && dummyHead != null) { node = ptr; ptr = ptr.next; ListNode qNode = dummyHead; dummyHead = dummyHead.next; qNode.next = ptr; node.next = qNode; } }} ...

Leetcode 95不同的二叉搜索树 II输入: 3输出:[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3]]解释:以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3Leetcode 86不同的二叉搜索树给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？示例:输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3题解搜索二叉树(BST)的定义若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。给点一个数，去构造BST.[1, 2, 3]可以把这个数列做左子树和右子树的划分:[1] [2, 3][1, 2] [3][1, 2] [2, 3] 又可以做左子树和右子树的划分.这是一个递归的过程.把递归的结果构造起来,即可成为答案./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) return new ArrayList<>(); return generateBST(1, n); } private List<TreeNode> generateBST(int left, int right) { List<TreeNode> res = new LinkedList<>(); if (left > right) { // 划分不到的时候,这时候填null. res.add(null); return res; } for (int i = left; i <= right; i++) { List<TreeNode> leftTrees = generateBST(left, i - 1); List<TreeNode> rightTrees = generateBST(i + 1, right); for (TreeNode leftTree : leftTrees) { for (TreeNode rightTree : rightTrees) { // 注意,每个循环都要构造新的节点,不能在for 循环外面生成. TreeNode root = new TreeNode(i); root.left = leftTree; root.right = rightTree; res.add(root); } } } return res; }}如果只需要数目,不需要生成具体的BST的话,只要能求出左子树有几种构造,右子树有几种构造,就可以最终确定.而确定左子树和右子树的问题的时候,又可以划分为子问题.eg:求 [1,2,3,4] 依赖于:[1,2,3] [2,3,4]又依赖于:[1,2] [2,3] [3,4]的构造有几种.class Solution { public int numTrees(int n) { int[] res = new int[n + 2]; res[0] = 1; res[1] = 1; // 没有左子树和右子树 res[2] = 2; for (int i = 3; i <= n; i++) { // 从3求到n for (int j = 1; j <= i; j++) { // 求解过程中,需要依赖于之前的解,状态转移方程为每一种划分的左子树和右子树的构造方法乘积. res[i] += res[j - 1] * res[i - j]; } } return res[n]; }} ...

Sort a linked list in O(n log n) time using constant space complexity.Example 1:Input: 4->2->1->3Output: 1->2->3->4Example 2:Input: -1->5->3->4->0Output: -1->0->3->4->5难度：medium题目：排列链表，时间复杂度为O(n logn) 空间复杂度为O(1).思路：快速排序Runtime: 232 ms, faster than 9.03% of Java online submissions for Sort List.Memory Usage: 41.8 MB, less than 100.00% of Java online submissions for Sort List./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution { public ListNode sortList(ListNode head) { quickSort(head, null); return head; } private void quickSort(ListNode head, ListNode tail) { if (head == tail) { return; } int val = head.val; ListNode prevSwapPtr = head; for (ListNode ptr = head.next; ptr != tail; ptr = ptr.next) { if (ptr.val < val) { int t = prevSwapPtr.next.val; prevSwapPtr.next.val = ptr.val; ptr.val = t; prevSwapPtr = prevSwapPtr.next; } } head.val = prevSwapPtr.val; prevSwapPtr.val = val; quickSort(head, prevSwapPtr); quickSort(prevSwapPtr.next, tail); }} ...

Given a binary tree, return the preorder traversal of its nodes’ values.Example:Input: [1,null,2,3] 1 \ 2 / 3Output: [1,2,3]Follow up: Recursive solution is trivial, could you do it iteratively?难度：medium题目：给定二叉树，返回其前序遍历结点值。（不要使用递归）/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<Integer> preorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); List<Integer> result = new ArrayList<>(); // root, left, right while (root != null || !stack.isEmpty()) { if (null == root) { root = stack.pop(); } result.add(root.val); if (root.right != null) { stack.push(root.right); } root = root.left; } return result; }} ...

这两天专门训练了backtracking类型的问题，包括N皇后、全排列全组合等等，我到现在也无法完全清晰描述recursive里的运行过程，但是多做了几道这种类型的题目之后发现还是很有套路的，即使思路不是很清晰也可以“凑”出代码。recursive的代码有两点关键：1.出口条件 2.循环的写法出口条件：出口条件还是挺容易，如全排列中list的长度为nums的length就把它加入到result list中，比如combination中sum等于target循环的写法：1.全排列中用for (int i = 0; i < mums.length; i ++), 全组合中用for (int i = index; i < mums.length; i ++),用一个visited数组来记录元素是否被访问过，if (visited[I] == true) continue;2.如何处理有重复的情况？首先均需经过sort的预处理，全组合去除重复组合的写法: if (i > index && nums[i] == nums[i-1]) continue; 全排列去除重复组合的方法：if (i > 0 && nums[i] == nums[i-1] && visited[i-1] == false) continue;

题目要求Design a data structure that supports all following operations in average O(1) time.Note: Duplicate elements are allowed.insert(val): Inserts an item val to the collection.remove(val): Removes an item val from the collection if present.getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.Example:// Init an empty collection.RandomizedCollection collection = new RandomizedCollection();// Inserts 1 to the collection. Returns true as the collection did not contain 1.collection.insert(1);// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].collection.insert(1);// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].collection.insert(2);// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.collection.getRandom();// Removes 1 from the collection, returns true. Collection now contains [1,2].collection.remove(1);// getRandom should return 1 and 2 both equally likely.collection.getRandom();设计一个数据结构，支持能够在O(1)的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。强烈建议先看一下这个问题的基础版本，传送门在这里。思路和代码遵循之前基础版本的思路，当解决这种问题的时候我们会用数组和hashmap来做位置的存储，从而更新的时候无需检索。但是在这题的情境下，存在一个问题，举个例子：假如现在插入1,2,3,3,4,3,3此时的map中应当是如下：1:[0] 2:[1] 3:[2,3,5,6] 4:[4]我们先执行删除1，按照之前的规则，我们会删除数组中最后一个元素，并将其值移动到这个位置上map应当被更新为2:[1] 3:[2,3,5,0] 4:[4]接着我们再删除2，此时虽然最后一个元素还是3，但是这个3在位置数组中的位置却是需要O(n)的时间来查询的，这就违反了O(1)的删除时间复杂度。网上有一些java实现采用OrderSet来解决，这是不合理的。因为有序堆本质上底层是一个最大堆或最小堆，它的插入和删除操作都需要O(lgn)的时间复杂度来完成这里我们采用的方式是继续冗余，即我们在插入每一个元素的时候，同时记录该元素在下标数组中的位置，举个例子：先插入1，则map的值为[1:[0]]，list的值为[[1,0]] 此处的0代表1这个值在下标数组[0]中位于第0个位置上。在插入2，则map的值为[1:[0], 2:[1]], list的值为[[1,0],[2,0]]再插入1，此时map=[1:[0, 2], 2:[1], list的值为[[1,0],[2,0],[1,1]]此时删除2，同理，我们还是会将数组中最后一个元素的值替换在删除掉元素的位置，此处我们从map中得出2最后一次在数组中出现的下标为1，我们需要将最后位置上的1替换掉当前2的值，之后我们还能从数组中得知，1这个数字它对应的位置下标的索引为2，因此我们再将map[1]中map[1][2]的值替换为2所在的新的位置，即1。此时的map=[1:[0, 1], 2:[] list=[[1,0], [1,1]]代码如下：public class InsertDeleteGetRandomDuplicatesallowed_381 { private List<Pair> list; private Map<Integer, List<Integer>> index; /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. / public InsertDeleteGetRandomDuplicatesallowed_381() { list = new ArrayList<>(); index = new HashMap<>(); } public boolean insert(int val) { boolean contains = true; if(!index.containsKey(val) || index.get(val).isEmpty()) { contains = false; } List<Integer> tmp = index.getOrDefault(val, new ArrayList<>()); tmp.add(list.size()); index.put(val, tmp); list.add(new Pair(val, tmp.size()-1)); return !contains; } /* Removes a value from the collection. Returns true if the collection contained the specified element. / public boolean remove(int val) { if(!index.containsKey(val) || index.get(val).isEmpty()) { return false; } List<Integer> tmp = index.get(val); int position = tmp.remove(tmp.size()-1); if(position != list.size()-1) { Pair lastPair = list.get(list.size()-1); int lastValue = lastPair.value; List<Integer> lastValuePositions = index.get(lastValue); lastValuePositions.set(lastPair.position, position); list.set(position, lastPair); } list.remove(list.size()-1); return true; } /* Get a random element from the collection. */ public int getRandom() { int position = (int)Math.floor((Math.random() * list.size())); return list.get(position).value; } public static class Pair{ int value; int position; public Pair(int value, int position) { this.value = value; this.position = position; } } } ...

Sort a linked list using insertion sort.A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.With each iteration one element (red) is removed from the input data and inserted in-place into the sorted listAlgorithm of Insertion Sort:1.Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.2.At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.3.It repeats until no input elements remain.Example 1:Input: 4->2->1->3Output: 1->2->3->4Example 2:Input: -1->5->3->4->0Output: -1->0->3->4->5难度：medium题目：用直插法实现链表排序。思路：插入排序。Runtime: 28 ms, faster than 56.45% of Java online submissions for Insertion Sort List.Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Insertion Sort List./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode insertionSortList(ListNode head) { if (null == head) { return head; } ListNode dummyHead = new ListNode(0); while (head != null) { ListNode tNode = head; head = head.next; tNode.next = null; ListNode nHead = dummyHead; while (nHead.next != null && tNode.val > nHead.next.val) { nHead = nHead.next; } tNode.next = nHead.next; nHead.next = tNode; } return dummyHead.next; }} ...

Evaluate the value of an arithmetic expression in Reverse Polish Notation.Valid operators are +, -, , /. Each operand may be an integer or another expression.Note:Division between two integers should truncate toward zero.The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.Example 1:Input: [“2”, “1”, “+”, “3”, “"]Output: 9Explanation: ((2 + 1) * 3) = 9Example 2:Input: [“4”, “13”, “5”, “/”, “+"]Output: 6Explanation: (4 + (13 / 5)) = 6Example 3:Input: [“10”, “6”, “9”, “3”, “+”, “-11”, “”, “/”, “”, “17”, “+”, “5”, “+"]Output: 22Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5= ((10 * (6 / (12 * -11))) + 17) + 5= ((10 * (6 / -132)) + 17) + 5= ((10 * 0) + 17) + 5= (0 + 17) + 5= 17 + 5= 22难度：medium题目：求算术表达式在反波兰表示法中的值。有效的操作符是+、-、、/。每个操作数可以是一个整数或另一个表达式。思路：栈Runtime: 6 ms, faster than 91.00% of Java online submissions for Evaluate Reverse Polish Notation.Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Evaluate Reverse Polish Notation.class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); int tNum = 0; for (int i = 0; i < tokens.length; i++) { switch(tokens[i]) { case “+” : stack.push(stack.pop() + stack.pop()); break; case “-” : tNum = stack.pop(); stack.push(stack.pop() - tNum); break; case “” : stack.push(stack.pop() * stack.pop()); break; case “/” : tNum = stack.pop(); stack.push(stack.pop() / tNum); break; default : stack.push(Integer.parseInt(tokens[i])); } } return stack.pop(); }} ...

Given an input string, reverse the string word by word.Example:Input: “the sky is blue”,Output: “blue is sky the”.Note:A word is defined as a sequence of non-space characters.Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.You need to reduce multiple spaces between two words to a single space in the reversed string.Follow up: For C programmers, try to solve it in-place in O(1) space.难度：medium题目：给定字符串，反转字符串中的单词。注意：单词指一组非空字符。输入的字符串可能包含前后空格。你需要在两个单词之间只保留一个空格。思路：先反转，然后逐个单词反转。Runtime: 9 ms, faster than 37.01% of Java online submissions for Reverse Words in a String.Memory Usage: 38.8 MB, less than 100.00% of Java online submissions for Reverse Words in a String.public class Solution { public String reverseWords(String s) { StringBuilder sb = new StringBuilder(" " + s + " “); sb.reverse(); StringBuilder result = new StringBuilder(); int begin = 0; for (int i = 0; i < sb.length() - 1; i++) { char c1 = sb.charAt(i); char c2 = sb.charAt(i + 1); if (c1 == ’ ’ && c2 != ’ ‘) { begin = i; } else if (c1 != ’ ’ && c2 == ’ ‘) { for (int j = i; j >= begin; j–) { result.append(sb.charAt(j)); } } } return result.toString().trim(); }} ...

On a broken calculator that has a number showing on its display, we can perform two operations:Double: Multiply the number on the display by 2, or;Decrement: Subtract 1 from the number on the display.Initially, the calculator is displaying the number X.Return the minimum number of operations needed to display the number Y.Example 1:Input: X = 2, Y = 3Output: 2Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.Example 2:Input: X = 5, Y = 8Output: 2Explanation: Use decrement and then double {5 -> 4 -> 8}.Example 3:Input: X = 3, Y = 10Output: 3Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.Example 4:Input: X = 1024, Y = 1Output: 1023Explanation: Use decrement operations 1023 times.Note:1 <= X <= 10^91 <= Y <= 10^9难度：medium题目：在一个显示数字的坏计算器上，我们可以执行两个操作:加倍:将显示的数字乘以2，或;递减:从显示的数字中减去1。最初，计算器显示的是数字X。返回显示数字Y所需的最小操作数。思路：从Ｙ到Ｘ，可执行的操作为自增1和减半。如果为奇数则自增1,如果为偶则减半。如果Ｘ大于Ｙ则只能自减。Runtime: 3 ms, faster than 100.00% of Java online submissions for Broken Calculator.Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Broken Calculator.class Solution { public int brokenCalc(int X, int Y) { int step = 0; while (X != Y) { if (Y < X) { step += X - Y; break; } Y = Y % 2 == 1 ? Y + 1 : Y / 2; step++; } return step; }} ...

原文在这，可以来我blog翻翻哦。第二天。今天AC掉了一道之前没AC掉的题目。。。今天的题目是6. ZigZag Conversion题目描述：The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)P A H NA P L S I I GY I RAnd then read line by line: “PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion given a number of rows:string convert(string s, int numRows);Example 1:Input: s = “PAYPALISHIRING”, numRows = 3Output: “PAHNAPLSIIGYIR"Input: s = “PAYPALISHIRING”, numRows = 4Output: “PINALSIGYAHRPI"Explanation:P I NA L S I GY A H RP I恩，又是一道“编程题“， 并不涉及到什么算法，静下心来仔细想想还是能做出来的。做这道题的思路就是一点一点跑例子，找出其中的规律就好了。我们先以输入为s = “PAYPALISHIRING”, numRows = 3为例子，这是题目给出的例子，正确答案已经有了。先把Z字型画出来（不难发现，题目在最开始其实已经给出了答案）：P A H NA P L S I I GY I R观察上面的例子我们可以发现：第一行中的元素在原来的字符串中下标相差4个。第二行中的元素在原来字符串中下标相差2个。ok，看起来好像找到了一些规律，继续跑一个例子验证一下，这次的输入是s = “PAYPALISHIRING”, numRows = 3，把Z字型画出来：P I NA L S I GY A H RP I可以看到第一行的元素在原来字符串中的下标相差6个，但是第二行却出现了一些不一样的情况：A与L相差4个，L与S却相差2个S与I相差4个，I与G却相差2个看起来offset是有规律的，而且好像需要分成两种情况，继续看看第3行：Y与A相差2个，A与H相差4个H与R相差4个，如果还有元素的话，下一个元素与R之间显然相差2个。从上面的例子来看显然是要分成两种情况的，某一行中下标之间的offset是不断在两个数字间不断变换的。我们尝试用两个数组来保存这些offset，我们把这两个数组定义为skipDown和skipUp。其中skipDown表示下标在z字型中经过了一个向下的剪头，如第二个例子中，第一行的P移动到I时，P经过了AYPAl组成的向下的剪头。skipUp同理可推。如果我们继续跑例子的话，应该是比较容易找出规律的：第i行的skipDown为2*(i-1)，而第一行和最后一行的skipDown都应该为2*(numRows)。skipDown与skipUp是逆序的关系。综上，我们可以写出下面的代码：string convert(string s, int numRows) { if (numRows < 2) return s; vector<int> skipDown(numRows); vector<int> skipUp(numRows); skipDown[0] = 2*(numRows-1); skipUp[0] = 0; for(int i = 1;i < numRows; i++) { skipDown[i] = skipDown[i-1] - 2; skipUp[i] = skipUp[i-1] + 2; } skipDown[numRows-1] = skipDown[0]; skipUp[0] = skipUp[numRows-1]; string res(s.size(), ’ ‘); int index = 0; for(int i = 0;i < numRows; i++) { bool flag = true; for(int j = i;j < s.size();index++) { res[index] = s[j]; if (flag) { j += skipDown[i]; } else { j += skipUp[i]; } flag = !flag; } } return res;}当然这肯定不是最优的代码，比如其实我们可以不用两个数组，甚至不用数组来保存的offset，但是这样写会比较容易理解，代码会比较简单点。 ...

题目要求Design a data structure that supports all following operations in average O(1) time.insert(val): Inserts an item val to the set if not already present.remove(val): Removes an item val from the set if present.getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.Example:// Init an empty set.RandomizedSet randomSet = new RandomizedSet();// Inserts 1 to the set. Returns true as 1 was inserted successfully.randomSet.insert(1);// Returns false as 2 does not exist in the set.randomSet.remove(2);// Inserts 2 to the set, returns true. Set now contains [1,2].randomSet.insert(2);// getRandom should return either 1 or 2 randomly.randomSet.getRandom();// Removes 1 from the set, returns true. Set now contains [2].randomSet.remove(1);// 2 was already in the set, so return false.randomSet.insert(2);// Since 2 is the only number in the set, getRandom always return 2.randomSet.getRandom();设计一个数据结构，使得能够在O(1)的时间复杂度中插入数字，删除数字，以及随机获取一个数字。要求所有的数字都能够被等概率的随机出来。思路和代码其实有几个思路入手：如何实现O(1)的插入这里数字的插入还需要能够去重，即需要首先判断该数字是否已经存在，已经存在的话就不执行任何插入操作。如果底层是一个一般的数组，我们知道查询的时间复杂度为O(n)，明显不满足题目的意思。一个有序的数组能够将查询的时间复杂度下降到O(lgn），但是这依然不满足条件1，而且也无法做到所有的元素被等概率的查询出来，因为每插入一个元素都将改动之前元素的位置。而唯一能够做到O(1)时间查询的只有一个数据结构，即hash。因此，使用hash来查询时不可避免的。如何实现O(1)的删除这个其实是一个很经典的问题了，只要能够利用hash在O(1)的时间内找到这个数字的位置，就有两种方法来实现O(1)的删除，一个是利用伪删除，即每一个位置都对应一个状态为，将状态位社会为已经删除即可，还有一种就更有意思，就是将被删除位替换为数组最后一位的值，然后只需要删除最后一位就行。这种删除就无需将删除位右侧的元素全部左移造成O(n)的时间复杂度。这里我们采用的是第二种方法。如何实现O(1)的随机查询这个其实就是强调一点，我们需要维持原有的插入顺序，从而保证各个元素等概率被随机。综上所述，我们底层需要两种数据结构，一个hashmap来支持O(1)的查询，以及一个list来支持随机数的获取。代码实现如下：public class InsertDeleteGetRandom_380 { private List<Integer> list; private Map<Integer, Integer> hash; public InsertDeleteGetRandom_380() { list = new ArrayList<Integer>(); hash = new HashMap<Integer, Integer>(); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. / public boolean insert(int val) { if(hash.containsKey(val)) { return false; } list.add(val); hash.put(val, list.size()-1); return true; } /* Removes a value from the set. Returns true if the set contained the specified element. / public boolean remove(int val) { if(!hash.containsKey(val)){ return false; } int position = hash.get(val); if(position != list.size()-1) { int last = list.get(list.size()-1); list.set(position, last); hash.put(last, position); } list.remove(list.size()-1); hash.remove(val); return true; } /* Get a random element from the set. */ public int getRandom() { int position = (int)Math.floor((Math.random() * list.size())); return list.get(position); }} ...

原文在此, 可以来我Blog翻翻哦。hhh, 开始一天一道LeetCode吧, 恩, 忘记了之前算到第几天了, 那么从头开始吧, 今天是第一天.今天的题目是(8. String to Integer (atoi))[https://leetcode.com/problems…]题目描述:Implement atoi which converts a string to an integer.The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.If no valid conversion could be performed, a zero value is returned.Note:Only the space character ’ ’ is considered as whitespace character.Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. If the numerical value is out of the range of representable values, INT_MAX (2^31 − 1) or INT_MIN (−2^31) is returned.Example 1:Input: “42"Output: 42Example 2:Input: " -42"Output: -42Explanation: The first non-whitespace character is ‘-’, which is the minus sign. Then take as many numerical digits as possible, which gets 42.Example 3:Input: “4193 with words"Output: 4193Explanation: Conversion stops at digit ‘3’ as the next character is not a numerical digit.Example 4:Input: “words and 987"Output: 0Explanation: The first non-whitespace character is ‘w’, which is not a numerical digit or a +/- sign. Therefore no valid conversion could be performed.Example 5:Input: “-91283472332"Output: -2147483648Explanation: The number “-91283472332” is out of the range of a 32-bit signed integer. Thefore INT_MIN (−231) is returned.怎么说呢， 这是一道编程題， 而不是算法题， 事实上没用到什么算法， 把逻辑理清楚， 然后注意一下坑就好了。我们现在来理一理atoi()的逻辑：我们要跳过字符串开头的所有空格。第一个非空格字符，只能是+, -以及0到9的所以数字。如果第一个非空格字符是-， 我们就要返回一个负数。解析字符串中的数字， 直到遇到第一个非数字就结束（或者遍历晚字符串）然后如果在解析数字的时候发现， 如果溢出了， 就直接返回INT_MAX或INT_MIN(看前面是否有符号)感觉整个逻辑还是比较好写的， 就只有一个麻烦点：怎么判断是否溢出了？有两个方法：方法一：因为atoi()只解析32位的有符号整数， 所以我们可以直接用64位的整数来计算结果，这样就可以直接判断是否超出32位的范围了，也就是用long long, 但是这样要计算64位的乘法和加法，会比较耗时。方法二：直接用32位的整数来计算结果， 在解释这个方法前，我们先看下是如何解析数字的, 解析数字主要就是把单个字符转成数字， 然后通过以下等式来迭代计算结果res = res * 10 + i;。可以看到这里有一个乘10的计算，所以我们可以在计算这个等式之前， 用INT_MAX/10来判断是否溢出。int myAtoi(string str) { int res = 0; // clear space int beg = 0; while(beg < str.size()) { char c = str[beg]; if (c == ’ ‘) beg++; else if (c == ‘-’ || c == ‘+’||(c <= ‘9’ && c >= ‘0’)) break; else return res; } int sign = 1; int max_num = INT_MAX; // if we have ‘+’ or ‘-’ if (str[beg] == ‘+’) { beg++; } else if (str[beg] == ‘-’) { beg++; sign = -1; max_num = INT_MIN; } const int c = INT_MAX/10; for(;beg < str.size() && str[beg] >= ‘0’ && str[beg] <= ‘9’; beg++) { int i = str[beg]-‘0’; if (res > c || (res == c && i > 7)) return max_num; res = res * 10 + i; } return sign*res;} ...

题目要求Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.Note that it is the kth smallest element in the sorted order, not the kth distinct element.Example:matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15]],k = 8,return 13.Note: You may assume k is always valid, 1 ≤ k ≤ n2.在一个从左到右，从上到下均有序的二维数组中，找到从小到第k个数字，这里需要注意，不要求一定要是唯一的值，即假设存在这样一个序列1,2,2,3，则第三个数字是2而不是3。思路一：优先队列当涉及到从一个集合中查找一个元素这样的问题时，我们往往会立刻想到查找的几种方式：有序数组查找，无序数组查找，堆排序。这里如果将二维数组转化为一维有序数组，成本未免太大了。同理，将其中所有元素都转化为堆，也会存在内存不足的问题。因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第k个元素的值进行堆排序就可以了。 public int kthSmallest(int[][] matrix, int k) { //优先队列 PriorityQueue<Tuple> queue = new PriorityQueue<Tuple>(); //将每一行的第一个元素放入优先队列中 for(int i = 0 ; i<matrix.length ; i++) { queue.offer(new Tuple(i, 0, matrix[i][0])); } //对优先队列执行k次取操作，取出来的就是第k个值 for(int i = 0 ; i<k-1 ; i++) { Tuple t = queue.poll(); //判断是否到达行尾，若没有，则将下一个元素作为潜在的第k个元素加入优先队列中 if(t.y == matrix[0].length-1) continue; queue.offer(new Tuple(t.x, t.y+1, matrix[t.x][t.y+1])); } return queue.poll().value; } /** * 存储矩阵中x，y和该下标上对应的值的Tuple */ public static class Tuple implements Comparable<Tuple>{ int x; int y; int value; public Tuple(int x, int y, int value) { this.x = x; this.y = y; this.value = value; } @Override public int compareTo(Tuple o) { // TODO Auto-generated method stub return this.value - o.value; } }思路二：二分法查找二分查找的核心问题在于，如何找到查找的上界和下届。这边我们可以矩阵中的最大值和最小值作为上界和下界。然后不停的与中间值进行比较，判断当前矩阵中小于该中间值的元素有几个，如果数量不足k，就将左指针右移，否则，就将右指针左移。直到左右指针相遇。这里需要注意，不能在数量等于k的时候就返回mid值，因为mid值不一定在矩阵中存在。 public int kthSmallest2(int[][] matrix, int k){ int low = matrix[0][0], high = matrix[matrix.length-1][matrix[0].length-1]; while(low <= high) { int mid = low + (high - low) / 2; int count = 0; int i = matrix.length-1 , j = 0; //自矩阵左下角开始计算比mid小的数字的个数 while(i>=0 && j < matrix.length){ if(matrix[i][j]>mid) i–; else{ count+=i+1; j++; } } if(count < k) { low = mid + 1; }else{ high = mid - 1; } } return low; } ...

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).Find the minimum element.You may assume no duplicate exists in the array.Example 1:Input: [3,4,5,1,2] Output: 1Example 2:Input: [4,5,6,7,0,1,2]Output: 0难度：medium题目：假设一个按升序排序的数组在某个未知的轴上旋转。假定数组中没有重复元素。思路：分情况二叉搜索Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.class Solution { public int findMin(int[] nums) { return findMin(nums, 0, nums.length - 1); } public int findMin(int[] nums, int left, int right) { int mid = left + (right - left) / 2; // 升序 if (nums[left] <= nums[mid] && nums[mid] <= nums[right]) { return nums[left]; } // 降序 if (nums[left] >= nums[mid] && nums[mid] >= nums[right]) { return nums[right]; } // 升序占大降序占小 if (nums[left] >= nums[mid]) { return findMin(nums, left, mid); } // 升序占小降序占大 return findMin(nums, mid, right); }} ...

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.Example 1:Input: [2,3,-2,4]Output: 6Explanation: [2,3] has the largest product 6.Example 2:Input: [-2,0,-1]Output: 0Explanation: The result cannot be 2, because [-2,-1] is not a subarray.难度：medium题目：给定整数数组，找出乘积最大的子数组。思路：结合最大子数组和，这里用两个变量分别记下包含当前元素的最大乘积和最小乘积，因为下一个元素正负不定。Runtime: 2 ms, faster than 74.69% of Java online submissions for Maximum Product Subarray.Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Maximum Product Subarray.public class Solution { public int maxProduct(int[] nums) { if (null == nums || nums.length < 1) { return 0; } int maxVal = nums[0]; int curMaxVal = nums[0], curMinVal = nums[0]; for (int i = 1; i < nums.length; i++) { int pCurMinVal = curMinVal; int pCurMaxVal = curMaxVal; curMaxVal = Math.max(Math.max(nums[i], curMaxVal * nums[i]), pCurMinVal * nums[i]); curMinVal = Math.min(Math.min(nums[i], curMinVal * nums[i]), pCurMaxVal * nums[i]); maxVal = Math.max(maxVal, curMaxVal); } return maxVal; }} ...

A peak element is an element that is greater than its neighbors.Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.You may imagine that nums[-1] = nums[n] = -∞.Example 1:Input: nums = [1,2,3,1]Output: 2Explanation: 3 is a peak element and your function should return the index number 2.Example 2:Input: nums = [1,2,1,3,5,6,4]Output: 1 or 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.Note:Your solution should be in logarithmic complexity.难度：medium题目：峰值指当前元素大于其邻居，给定一数组相离元素不等，找出其峰值并返回其索引。数组可能包含多个峰值，返回任一即可。注意：时间复杂度为对数思路：二叉搜索，nums[mid] > nums[mid + 1] 留下左边，nums[mid] > nums[mid + 1]意味着nums[mid]可为潜在的峰值，如果左边是升序则其为峰值，否则继续查找。如果mid已是最左边的数，则为其为峰值。Runtime: 2 ms, faster than 100.00% of Java online submissions for Find Peak Element.Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Find Peak Element.public class Solution {public int findPeakElement(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[mid + 1]) { right = mid; } else { left = mid + 1; } } return left;}} ...

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.Calling next() will return the next smallest number in the BST.Example:BSTIterator iterator = new BSTIterator(root);iterator.next(); // return 3iterator.next(); // return 7iterator.hasNext(); // return trueiterator.next(); // return 9iterator.hasNext(); // return trueiterator.next(); // return 15iterator.hasNext(); // return trueiterator.next(); // return 20iterator.hasNext(); // return falseNote:next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.难度：medium题目：实现二叉搜索树的遍历。迭代器用根结点初始化。调用next()将会返回下一个最小的结点。Runtime: 76 ms, faster than 37.23% of Java online submissions for Binary Search Tree Iterator.Memory Usage: 52.1 MB, less than 100.00% of Java online submissions for Binary Search Tree Iterator./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } /class BSTIterator { private Stack<TreeNode> stack; public BSTIterator(TreeNode root) { stack = new Stack<>(); while (root != null) { stack.push(root); root = root.left; } } /* @return the next smallest number / public int next() { TreeNode node = stack.pop(); TreeNode ptr = node.right; while (ptr != null) { stack.push(ptr); ptr = ptr.left; } return node.val; } /* @return whether we have a next smallest number / public boolean hasNext() { return !stack.isEmpty(); }}/* * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */ ...

Given a binary tree, return the inorder traversal of its nodes’ values.Example:Input: [1,null,2,3] 1 \ 2 / 3Output: [1,3,2]Follow up: Recursive solution is trivial, could you do it iteratively?难度：medium题目：给定二叉树，返回其中序遍历结点。（不要使用递归）思路：栈Runtime: 1 ms, faster than 55.50% of Java online submissions for Binary Tree Inorder Traversal.Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for Binary Tree Inorder Traversal./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<Integer> inorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); List<Integer> result = new ArrayList<>(); while (!stack.isEmpty() || root != null) { if (root != null) { stack.push(root); root = root.left; } else { TreeNode node = stack.pop(); result.add(node.val); root = node.right; } } return result; }} ...

题目要求We are playing the Guess Game. The game is as follows:I pick a number from 1 to n. You have to guess which number I picked.Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.Example:n = 10, I pick 8.First round: You guess 5, I tell you that it’s higher. You pay $5.Second round: You guess 7, I tell you that it’s higher. You pay $7.Third round: You guess 9, I tell you that it’s lower. You pay $9.Game over. 8 is the number I picked.You end up paying $5 + $7 + $9 = $21.Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.一个猜数字游戏，数字区间为1~n，每猜一次，会有人告诉你猜中了或者当前的数字是大于结果值还是小于结果值。猜对则本次猜测免费，猜错则本次猜测需要花费和数字等额的金钱。问如果要确保能够猜中数字，最少要花费多少钱。其实这题的英文表述有些问题，确切来说，在所有能够确保找到目标值的方法中，找到花费金钱最少的哪种。思路我们先用一个比较简单的数字来找规律。当n等于3时，即从1,2,3中找到目标数字，确保找到一个数字至少需要多少钱。查询序列如下：目标值3：1,2 2目标值2：1,3目标值1：3,2,2可见如果要找到1，2，3中任意一个数字，最少要花费2元钱，即从2开始查询，如果命中，则花费0元，如果没有命中也知道目标值比2小还是比2大，下次猜测一定命中，因此该序列中找到任何一个数字最多花费2元钱。如此可见，假如要知道min(1,n)的值，只要找到花费最小的中间点k，即递归的公式相当于min(1,n) = k + Math.max(min(1, k-1), min(k+1,n)) 1<=k<=n找到最小的min即可。思路一：自顶向下的动态规划 public int getMoneyAmount(int n) { int[][] tmp = new int[n+1][n+1]; for(int[] row: tmp){ Arrays.fill(row, Integer.MAX_VALUE); } return getMoneyAmount(n, 1, n, tmp); } public int getMoneyAmount(int n, int lft, int rgt, int[][] tmp) { if(lft>=rgt) return 0; if(tmp[lft][rgt] != Integer.MAX_VALUE) return tmp[lft][rgt]; for(int i = lft ; i<=rgt ; i++) { tmp[lft][rgt] = Math.min(tmp[lft][rgt], Math.max(i + getMoneyAmount(n, lft, i-1, tmp), i + getMoneyAmount(n, i+1, rgt, tmp))); } return tmp[lft][rgt]; }思路二：自底向上的动态规划 public int getMoneyAmount(int n) { int[][] dp = new int[n+1][n+1]; for(int i = 2 ; i<=n ; i++) { for(int j = i-1 ; j>0 ; j–) { int min = Integer.MAX_VALUE; for(int k = j+1 ; k<i ; k++) { min = Math.min(min, k + Math.max(dp[j][k-1], dp[k+1][i])); } dp[j][i] = j + 1 == i ? j : min; } } return dp[1][n]; } ...

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.Example:Input: [1,2,3,null,5,null,4]Output: [1, 3, 4]Explanation: 1 <— / \2 3 <— \ \ 5 4 <—难度： medium题目： 给定二叉树，想像一下你站在树的右边，返回能看到的所有结点，结点从上到下输出。思路：层次遍历，ＢＦＳRuntime: 1 ms, faster than 79.74% of Java online submissions for Binary Tree Right Side View.Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Binary Tree Right Side View./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (null == root) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int qSize = queue.size(); for (int i = 0; i < qSize; i++) { TreeNode node = queue.poll(); if (node.right != null) { queue.add(node.right); } if (node.left != null) { queue.add(node.left); } if (0 == i) { result.add(node.val); } } } return result; }} ...

Given a list of non negative integers, arrange them such that they form the largest number.Example 1:Input: [10,2]Output: “210"Example 2:Input: [3,30,34,5,9]Output: “9534330"难度：medium题目：给定非负整数数组，重组其序使其形成最大值。思路：定制排序算法的比较策略，nums[i]拼接nums[j] 与 nums[j]拼接nums[i] 相比。Runtime: 51 ms, faster than 26.58% of Java online submissions for Largest Number.Memory Usage: 35.7 MB, less than 100.00% of Java online submissions for Largest Number.class Solution { public String largestNumber(int[] nums) { if (null == nums) { return “0”; } int n = nums.length; String[] ss = new String[n]; for (int i = 0; i < n; i++) { ss[i] = String.valueOf(nums[i]); } Arrays.sort(ss, (s1, s2) -> { String s1s2 = s1 + s2; String s2s1 = s2 + s1; return s2s1.compareTo(s1s2); }); StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.append(ss[i]); } String result = new String(sb); return ‘0’ == result.charAt(0) ? “0” : result; }} ...

Compare two version numbers version1 and version2.If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.You may assume that the version strings are non-empty and contain only digits and the . character.The . character does not represent a decimal point and is used to separate number sequences.For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.Example 1:Input: version1 = “0.1”, version2 = “1.1"Output: -1Example 2:Input: version1 = “1.0.1”, version2 = “1"Output: 1Example 3:Input: version1 = “7.5.2.4”, version2 = “7.5.3"Output: -1Example 4:Input: version1 = “1.01”, version2 = “1.001"Output: 0Explanation: Ignoring leading zeroes, both “01” and “001” represent the same number “1”Example 5:Input: version1 = “1.0”, version2 = “1.0.0"Output: 0Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to “0"Note:Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.Version strings do not start or end with dots, and they will not be two consecutive dots.难度：medium题目：比较两个版本version1和version2.如果1大于2返回1,1小于2返回－1，否则返回0.假定版本字符串中非空且只含有数字和点。点不是小数点只是用作分隔符。思路：按点号分割转成数字比较。Runtime: 1 ms, faster than 89.87% of Java online submissions for Compare Version Numbers.Memory Usage: 33.1 MB, less than 100.00% of Java online submissions for Compare Version Numbers.class Solution { public int compareVersion(String version1, String version2) { String[] vs1 = version1.split(”\.”); String[] vs2 = version2.split(”\.”); for (int i = 0; i < Math.max(vs1.length, vs2.length); i++) { int i1 = i < vs1.length ? Integer.parseInt(vs1[i]) : 0; int i2 = i < vs2.length ? Integer.parseInt(vs2[i]) : 0; if (i1 - i2 > 0) { return 1; } if (i1 - i2 < 0) { return -1; } } return 0; }} ...

随便说说好几天没有认真刷题了，这两天猛刷了一把SQL题目。然后用hexo搭建了自己的BLOG，还在摸索中，后续渐渐的就会两边都同步文章。SQL题集leetcode上对于数据库是有单独的19题的，我现在的进度是8/19，刷的还是有点慢，而且很多地方效率不高，还得做n刷处理。毕竟后续如果考虑到要说数据分析的话，取数上的效率也得保证。第一题175. 组合两个表难度：简单表1: Person列名类型PersonIdintFirstNamevarcharLastNamevarcharPersonId 是上表主键表2: Address列名类型AddressIdintPersonIdintCityvarcharStatevarcharAddressId 是上表主键编写一个 SQL 查询，满足条件：无论 person 是否有地址信息，都需要基于上述两表提供 person 的以下信息：FirstName, LastName, City, State我的题解：SELECT Person.FirstName,Person.LastName,Address.City,Address.StateFrom Person Left Join AddressON Person.PersonId = Address.PersonId解题思路：因为无论address可能为空，所以用left join的方式，加入Address表。其他：很久没有用过left join，有些概念有点忘记，顺便来复习下知识点。在left join之前的左表是会被完全返回的，哪怕left join的右表没有对应的数据。select * from table_1 left join table_2这里的话会返回所有table_1的行。sql的left join 、right join 、inner join之间的区别：　-　left join(左联接) 返回包括左表中的所有记录和右表中联结字段相等的记录 -　right join(右联接) 返回包括右表中的所有记录和左表中联结字段相等的记录　-　inner join(等值连接) 只返回两个表中联结字段相等的行第二题176. 第二高的薪水难度：简单编写一个 SQL 查询，获取 Employee 表中第二高的薪水（Salary） 。IdSalary110022003300例如上述 Employee 表，SQL查询应该返回 200 作为第二高的薪水。如果不存在第二高的薪水，那么查询应返回 null。SecondHighestSalary200我的题解：SELECT MAX(Salary) AS SecondHighestSalary FROM EmployeeWHERE Salary < (SELECT MAX(Salary) FROM Employee)解题思路：使用max()来获取两次最大值，因为是同一张表，小于最大值的“最大值”就是第二大的值了。其他：一般主要查找最大值，这题查找的是第二大的值。主要是思路上要调整下，一般程序语言上会做排序。SQL里面也可以考虑用排序试下，如果要取第二条数据的话，就得先取前两条数据，再倒序取第一条。第三题181. 超过经理收入的员工难度：简单Employee 表包含所有员工，他们的经理也属于员工。每个员工都有一个 Id，此外还有一列对应员工的经理的 Id。IdNameSalaryManagerId1Joe7000032Henry8000043Sam60000NULL4Max90000NULL给定 Employee 表，编写一个 SQL 查询，该查询可以获取收入超过他们经理的员工的姓名。在上面的表格中，Joe 是唯一一个收入超过他的经理的员工。EmployeeJoe我的题解：SELECT p1.Name AS Employee FROM Employee p1,Employee p2WHERE p1.ManagerId = p2.IdAND p1.Salary > p2.Salary解题思路：查询两次同一张表，主条件为匹配经理Id和用户Id,再做比对大小。其他：对于同一张表查询两次，其实应该验证下效率到底如何，检查下是否有更快的查询方案。第四题182. 查找重复的电子邮箱难度：简单编写一个 SQL 查询，查找 Person 表中所有重复的电子邮箱。示例：IdEmail1a@b.com2c@d.com3a@b.com根据以上输入，你的查询应返回以下结果：Emaila@b.com说明：所有电子邮箱都是小写字母。我的题解：SELECT distinct(p1.Email) from Person p1,Person p2where p1.Email = p2.EmailAND p1.Id != p2.Id解题思路：还是查询同一张表两次，然后使用distinct，只输出单个结果。其他：distinct用于返回唯一不同的值。有distinct的字段必须放在开头。第五题183. 从不订购的客户难度：简单某网站包含两个表，Customers 表和 Orders 表。编写一个 SQL 查询，找出所有从不订购任何东西的客户。Customers 表：IdName1Joe2Henry3Sam4MaxOrders 表：IdCustomerId1321例如给定上述表格，你的查询应返回：CustomersHenryMax我的题解：SELECT c.name AS Customers FROM Customers cWHERE c.Id Not in(SELECT CustomerId FROM Orders)解题思路：取出Order表的数据，然后和Customers的Id做校验。其他：如果不是用取出Customers的ID来做比较的，就是Id!=CusomerId，而是查询两张表直接输出结果的话，会把每次的不对应的结果都输出。因为等于两张表都被完整比对过一次。第六题184. 部门工资最高的员工难度：中等Employee 表包含所有员工信息，每个员工有其对应的 Id, salary 和 department Id。IdNameSalaryDepartmentId1Joe7000012Henry8000023Sam6000024Max900001Department 表包含公司所有部门的信息。IdName1IT2Sales编写一个 SQL 查询，找出每个部门工资最高的员工。例如，根据上述给定的表格，Max 在 IT 部门有最高工资，Henry 在 Sales 部门有最高工资。DepartmentEmployeeSalaryITMax90000SalesHenry80000我的题解：select d.Name as Department,e.Name as Employee,e.Salary from Department d,Employee ewhere e.DepartmentId = d.IDand e.Salary = (select max(Salary) from Employee where d.id = DepartmentId)解题思路：这题参考了其他人的思路，后续需要自己再写一次。其实是转了两次弯，第一次是根据部门Id查询出每个部门最高的薪水，再根据这个薪水找到对应的人。 其他：第七题196. 删除重复的电子邮箱难度：简单编写一个 SQL 查询，来删除 Person 表中所有重复的电子邮箱，重复的邮箱里只保留 Id 最小 的那个。IdEmail1john@example.com2bob@example.com3john@example.comId 是这个表的主键。例如，在运行你的查询语句之后，上面的 Person 表应返回以下几行:IdEmail1john@example.com2bob@example.com我的题解：DELETE p1 FROM Person p1,Person p2WHERE p1.Email = p2.Email and p1.Id > p2.Id解题思路：这题一开始也有点被绕住了，后面渐渐做多了两次查询同步一张表就还好，核心思路就是查询相同的值，且Id不同，我们delete的是Id较大的那一行。其他：Null.第八题596. 超过5名学生的课难度：简单有一个courses 表 ，有: student (学生) 和 class (课程)。请列出所有超过或等于5名学生的课。例如,表:studentclassAMathBEnglishCMathDBiologyEMathFComputerGMathHMathIMath应该输出:classMath我的题解：select class From course group by class having count(class)>=5解题思路：对课程进行分组，分组后记数大于等于5的就取出数值。其他Null学生在每个课中不应被重复计算。我的题解：SELECT class FROM (select distinct * from courses) as newGROUP BY class HAVING count(*) >= 5解题思路：其他： ...

Given a string containing only digits, restore it by returning all possible valid IP address combinations.Example:Input: “25525511135"Output: [“255.255.11.135”, “255.255.111.35”]难度：medium题目：给定一字符串仅包含数字，恢复该字符串为所有可能合法的IP地址组合。思路：递归Runtime: 2 ms, faster than 91.11% of Java online submissions for Restore IP Addresses.Memory Usage: 34.8 MB, less than 0.90% of Java online submissions for Restore IP Addresses.class Solution { public List<String> restoreIpAddresses(String s) { List<String> result = new ArrayList(); if (null == s || s.length() < 4 || s.length() > 12) { return result; } restoreIpAddresses(s, 0, 0, “”, result); return result; } private void restoreIpAddresses(String s, int i, int cnt, String str, List<String> result) { int sLength = s.length(); if (i >= sLength && cnt >= 4) { result.add(str.substring(0, str.length() - 1)); return; } int i1 = (i + 1) <= sLength ? Integer.parseInt(s.substring(i, i + 1)) : -1; if (i1 >= 0 && cnt < 4) { restoreIpAddresses(s, i + 1, cnt + 1, str + i1 + “.”, result); } int i2 = (i + 2) <= sLength ? Integer.parseInt(s.substring(i, i + 2)) : -1; if (i2 >= 10 && i2 <= 99 && cnt < 4) { restoreIpAddresses(s, i + 2, cnt + 1, str + i2 + “.”, result); } int i3 = (i + 3) <= sLength ? Integer.parseInt(s.substring(i, i + 3)) : -1; if (i3 >= 100 && i3 <= 255 && cnt < 4) { restoreIpAddresses(s, i + 3, cnt + 1, str + i3 + “.”, result); } }} ...

Reverse a linked list from position m to n. Do it in one-pass.Note: 1 ≤ m ≤ n ≤ length of list.Example:Input: 1->2->3->4->5->NULL, m = 2, n = 4Output: 1->4->3->2->5->NULL难度：medium题目：反转从m到n的链表元素。一次遍历。思路：记录m及m之前的位置，然后使用头插法。Runtime: 2 ms, faster than 97.09% of Java online submissions for Reverse Linked List II.Memory Usage: 36.9 MB, less than 0.95% of Java online submissions for Reverse Linked List II./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (m == n) { return head; } ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode ptr = head, prevMPtr = dummyHead, tailPtr = head; for (int i = 1; i <= n; i++) { ListNode node = ptr; ptr = ptr.next; if (i < m) { prevMPtr = node; } else if (i == m) { tailPtr = node; node.next = null; } else { node.next = prevMPtr.next; prevMPtr.next = node; } } tailPtr.next = ptr; return dummyHead.next; }} ...

DescriptionSay you have an array for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day).Example:Input: [1,2,3,0,2]Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]描述给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例:输入: [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]思路这道题使用动态规划。状态：colldown 表示当天休息能够获得的最大价值，hold 表示当天持有股票能够获得的最大价值，sold 表示当天持有股票能够获得的最大价值。初始状态：colldown = 0, hold = －∞, sold = 0。状态转移方程：colldown ：如果当前休息，那么当前的价值可以来自于前一天休息或者前一天卖出股票（前一天买进股票不会产生收益），所以 colldown = max(colldown, sold)；hold ：如果当天选择继续持有股票，则当天可以选择继续持有昨天的股票，或者昨天休息今天买进股票，所以hold = max(oldhold, colldown - prices[i]); sold :当天卖出股票，则其价值只能来自于昨天买进今天卖出 sold = oldhold + prices[i]。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-02-13 14:21:33# @Last Modified by: 何睿# @Last Modified time: 2019-02-13 17:36:21import sysclass Solution: def maxProfit(self, prices: ‘List[int]’) -> ‘int’: # 少于两天无法进行交易 if len(prices) < 2: return 0 colldown, hold, sold = 0, -sys.maxsize, 0 for day in range(len(prices)): oldhold = hold # 当天持有：当天可以什么都不做，持有昨天持有的股票 # 或者当天买进股票 # 所以：当天价值可以来自前一天持有的价值，或者前一天休息今天买入的价值 hold = max(oldhold, colldown - prices[day]) # 当天休息：当天的价值可以来自于前一天休息的价值 # 或者前一天卖出的价值 colldown = max(colldown, sold) # 当天卖出：当前价值来自前一天持有加上今天的价值 sold = oldhold + prices[day] return max(colldown, sold)源代码文件在这里.©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明. ...

Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.Determine if you are able to reach the last index.Example 1:Input: [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:Input: [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index. 难度：medium题目：给定一非负整数数组，初始位置在数组第一个元素上。每个数组元素的值表示最大能到达的距离。判断是否可以到达数组最好的位置。思路：计算每个位置所能到达的最大位置，然后取最大值作为最远到达距离。Runtime: 4 ms, faster than 93.15% of Java online submissions for Jump Game.Memory Usage: 40.5 MB, less than 0.98% of Java online submissions for Jump Game.class Solution { public boolean canJump(int[] nums) { int steps = nums[0]; for (int i = 0; i <= steps; i++) { steps = Math.max(i + nums[i], steps); if (steps >= nums.length - 1) { return true; } } return false; }} ...

题目要求Given an encoded string, return it’s decoded string.The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].Examples:s = “3[a]2[bc]”, return “aaabcbc”.s = “3[a2[c]]”, return “accaccacc”.s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.将一个字符串解码，要求按照次数展开原字符串中的中括号。如3[a]2[bc]对应的字符串就是aaabcbc，即a展开3次，bc展开2次。注意，源字符串中的括号是允许嵌套的，且展开的字符中不会包含任何数字。思路一：递归其实递归的思路是很明显的，一旦我们遇到一个左括号，我们就可以找到其对应的右括号，然后对括号中的内容递归的展开，再将返回结果给上层，根据上次的次数再次展开。如3[a2[c]]=>3[acc]=>accaccacc。递归这里需要注意的是如何找到当前括号对应的右括号。这里可以采用一个小技巧，即从当前括号位置开始，每遇到一个左括号计数就+1，遇到一个右括号计数就-1，当计数器第一次被减为0时，则该位置上的右括号就是我们所要找的对应的右括号。代码如下： public String decodeString2(String s) { if (s.length() == 0) return “”; StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c >= ‘0’ && c <= ‘9’) { // 解析次数 int digitStart = i++; while (s.charAt(i) >= ‘0’ && s.charAt(i) <= ‘9’) i++; int num = Integer.parseInt(s.substring(digitStart, i)); // 找到对应的右括号 int strStart = i+1; // number must be followed by ‘[’ int count = 1; i++; while (count != 0) { if (s.charAt(i) == ‘[’) count++; else if (s.charAt(i) == ‘]’) count–; i++; } i–; // 取子字符串 String subStr = s.substring(strStart, i); // 将子字符串解码 String decodeStr = decodeString(subStr); // 将解码的结果拼接到当前的字符串后面 for (int j = 0; j < num; j++) { sb.append(decodeStr); } } else { // 添加首元素 sb.append(c); } } return sb.toString(); }思路二：栈我们知道，有一些递归的思路是可以转化为栈的，这里同样如此。利用栈我们可以存储外围层已持有的字符串以及应当展开的次数。用栈的思路来写要求思路更加严谨，以免出现逻辑错误。首先，我们会用两个指针lft，rgt分别来记录数字的起始位置和结束位置。同时，rgt还作为我们遍历整个字符串的指针。rgt的情形有如下几种可能：rgt指向[rgt指向]rgt指向数字rgt指向字母下面我们来逐个分析各种场景：1. rgt指向[此时左括号的左侧只会有一种情形，它的左边一定是数字。因此当我们遇到左括号时，我们应当记录左括号左边的数字，并将lft指针移动到左括号下一个位置。这里需要额外注意的是，如果当前该括号外围存在父元素，则我们应当将父元素的计数和已有字符串压入栈中。可以将这个操作理解为上下文切换。2. rgt指向]右括号意味着当前的字符展开序列遍历完毕，因此我们需要做以下几件事情：将lft和rgt之间的内容append到当前上下文的字符串中根据展开次数展开当前上下文的字符串如果存在父元素，则从栈中弹出父元素，恢复父级上下文将当前上文得到的结果append到父元素的字符串中3. rgt指向字母我们需要将rgt指向的字母添加到当前的上下文字符串中去。不要忘记将左指针移动到当前位置后面4. rgt指向数字数字将会在遇见[时提取出来，因此我们无需进行任何处理一个具体的例子假如现在输入的字符串为3[a2[c]]，我们有字符串栈s，计数栈c，指针lft，rgt，并用临时变量tmp，number分别记录当前上下文中计数和字符串。运行情况如下：lft=0 rgt=0 : 不执行任何操作lft=0 rgt=1 : 解析当前上下文应当展开的次数 number=3, lft=2lft=2 rgt=2 : 将当前的字符添加到当前的上下文中去，tmp=“a” lft=3lft=3 rgt=3 : 不做任何处理lft=3 rgt=4 : 将父级上下文压入栈中，并解析当前上下文的展开次数 s:[“a”] c:[3] lft=5 tmp="" number=2lft=5 rgt=5 : 将当前的字符添加到当前的上下文中去，tmp=“c” lft=6lft=6 rgt=6 : 展开当前字符串，并恢复父级上下文, tmp=“a”+“cc”, number=3 s:[] c:[] lft=7lft=7 rgt=7 : 展开当前字符串，= 此时没有父级上下文，因此无需恢复。tmp=“accaccacc” number=0代码如下： public String decodeString(String s) { Stack<Integer> count = new Stack<>(); Stack<StringBuilder> letters = new Stack<>(); int lft = 0, rgt = -1; int number = 0; StringBuilder result = null; while(++rgt < s.length()) { char c = s.charAt(rgt); if(c == ‘[’) { if(result != null) { count.push(number); letters.push(result); } result = new StringBuilder(); number = Integer.valueOf(s.substring(lft, rgt)); lft = rgt+1; }else if(c == ‘]’) { result.append(s.substring(lft, rgt)); StringBuilder tmp = new StringBuilder(result); for(int i = 0 ; i<number-1 ; i++) { result.append(tmp); } if(!letters.isEmpty()) { StringBuilder pop = letters.pop(); pop.append(result); result = pop; number = count.pop(); } lft = rgt+1; }else if(Character.isAlphabetic(c)) { if(result==null) { result = new StringBuilder(); } result.append(c); lft = rgt+1; } } if(result == null) { result = new StringBuilder(); } result.append(s.substring(lft, rgt)); return result.toString(); }想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~ ...

题目要求Given an integer n, return 1 - n in lexicographical order.For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.将1n这n个数字按照字母序排序，并返回排序后的结果。即如果n=13，则113的字母序为1,10,11,12,13,2,3,4,5,6,7,8,9思路和代码这题其实要求我们将数字是做字母来进行排序，因此当我们排序的时候可以看到，假如已知当前的数字为i，则它首先后一位数字应当是(i x 10)，如果(i x 10)大于n，再考虑i+1, 如果i+1也大于n，此时再考虑(i/10)+1。 public List<Integer> lexicalOrder(int n) { List<Integer> result = new ArrayList<Integer>(); for(int i = 1 ; i<=9 ; i++) { lexicalOrder(n, i, result); } return result; } public void lexicalOrder(int n, int cur, List<Integer> result) { if(cur > n) return; result.add(cur); for(int i = 0 ; i <=9 ; i++) { lexicalOrder(n, cur*10+i, result); } }想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~ ...

Given a set of distinct integers, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.Example:Input: nums = [1,2,3]Output:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]难度：medium题目：给定一不含重复元素的集合，求其所有子集。注意：答案不能包含重复的子集。思路：递归Runtime: 1 ms, faster than 100.00% of Java online submissions for Subsets.Memory Usage: 37.2 MB, less than 0.96% of Java online submissions for Subsets.class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { subsets(nums, 0, i + 1, new Stack<>(), result); } result.add(new ArrayList<>()); return result; } private void subsets(int[] nums, int idx, int k, Stack<Integer> stack, List<List<Integer>> result) { if (k <= 0) { result.add(new ArrayList<>(stack)); return; } for (int i = idx; i < nums.length - k + 1; i++) { stack.push(nums[i]); subsets(nums, i + 1, k - 1, stack, result); stack.pop(); } }} ...