Recursion

题目要求You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Example:Input: 1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULLOutput:1-2-3-7-8-11-12-9-10-4-5-6-NULL思路一：递归实现深度优先遍历从深度优先遍历的角度来看，每次遇到一个包含子节点中间双链表节点，就递归的调用展开方法将其展开，并将展开的结果插入到当前节点的后面。这里需要注意双链表前节点前后指针的变更。步骤如下： ...

题目要求Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.Example:Input: matrix = [[1,0,1],[0,-2,3]], k = 2Output: 2 Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).Note:1. The rectangle inside the matrix must have an area > 0.2. What if the number of rows is much larger than the number of columns?现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少?注：后面的文章中将使用[左上角顶点坐标，右下角顶点坐标]来表示一个矩阵，如[(1,2),(3,4)]表示左上角顶掉坐标为(1,2)，右下角顶点坐标为(3,4)的矩阵。用S[(1,2),(3,4)]表示该矩阵的面积。顶点的坐标系以数组的起始点作为起点，向下为x轴正方向，向右为y轴正方向。 ...

题目要求Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).For example, given a 3-ary tree: We should return its level order traversal:[ [1], [3,2,4], [5,6]] Note:The depth of the tree is at most 1000.The total number of nodes is at most 5000.对N叉树进行水平遍历，并输出每一行遍历的结果。 思路和代码这个和一般的水平遍历有所区别，因为它会记录每一行的水平遍历结果分别存在结果数组相应行。因此首先可以用水平遍历的通用解法，即队列的方式，进行解决： public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(root != null) { LinkedList<Node> queue = new LinkedList<Node>(); queue.offer(root); //下一行的元素数量 int next = 1; List<Integer> levelOrderPerHeight = new ArrayList<Integer>(); while(!queue.isEmpty()) { next--; Node tmp = queue.poll(); levelOrderPerHeight.add(tmp.val); if(tmp.children != null && !tmp.children.isEmpty()) { for(Node child : tmp.children) { queue.offer(child); } } //当前行遍历完成，则更新当前行 if(next == 0) { result.add(levelOrderPerHeight); levelOrderPerHeight = new ArrayList<Integer>(); next = queue.size(); } } } return result; }上面的实现中使用next值来记录下一行的元素的个数。但是其实因为结果是采用List<List>的形式来记录的，也就是第i层的水平遍历的结果会记录于数组下标i-1的位置上。因此无需再用队列来额外存储每一行的水平遍历，可以直接通过递归将遍历结果插入到相应行的结果集中。 ...

题目要求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); } }想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~ ...

题目要求There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.We keep repeating the steps again, alternating left to right and right to left, until a single number remains.Find the last number that remains starting with a list of length n.Example:Input:n = 9,1 2 3 4 5 6 7 8 92 4 6 82 66Output:6假设有1-n一共n个数字，从左往右开始每隔一位删除一个数字，到达最右侧后，再从右往左每隔一位删除一个数字，如此反复，直到剩下最后一个数字。问最后剩下的数字是多少。思路一：递归先从一个例子入手，当n等于7时，数字序列为1,2,3,4,5,6,7, 删除序列如下：1 2 3 4 5 6 7 2 4 6 4可以看到，第一轮删除后剩下的2，4，6就相当于是1，2，3的两倍，我们可以等价于从右往左删除1，2，3后剩余的结果乘2。由此可见，假如我们定义一个递归函数f(n, left),我们可以有f(n/2, right)来获取结果。 public int lastRemaining(int n) { return lastRemaining(n, true); } public int lastRemaining(int n, boolean left) { if(n == 1) { return 1; } if(n % 2 == 1) { return lastRemaining(n / 2, !left) * 2; }else{ if( left ) { return lastRemaining(n/2, !left) * 2; }else { return lastRemaining(n/2, !left) * 2 -1; } } }思路二这里其实存在一个镜像删除的问题，也就是说，对于任何一个1~n的序列来说，从左往右开始删除和从右往左开始删除剩余的结果的和一定为(n+1)，也就是所谓的镜像删除问题。举个例子：从左往右开始删除1 2 3 4 5 6 2 4 6 4 从右往左开始删除1 2 3 4 5 61 3 5 3 可以看到二者剩余的值加起来一定为n+1即7。根据这个原理，我们可以优化上面的递归，无需再利用left值来标记是从左往右删除还是从右往左删除，直接执行镜像删除即可。 public int lastRemaining2(int n) { return n == 1 ? 1 : (1 + n / 2 - lastRemaining2(n/2)) * 2; } ...

ProblemGiven a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn’t have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.The right-most node is also defined by the same way with left and right exchanged.Example 1Input: 1 \ 2 / \ 3 4Ouput:[1, 3, 4, 2]Explanation:The root doesn’t have left subtree, so the root itself is left boundary.The leaves are node 3 and 4.The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.So order them in anti-clockwise without duplicates and we have [1,3,4,2].Example 2Input: 1_ / \ 2 3 / \ / 4 5 6 / \ / \ 7 8 9 10 Ouput:[1,2,4,7,8,9,10,6,3]Explanation:The left boundary are node 1,2,4. (4 is the left-most node according to definition)The leaves are node 4,7,8,9,10.The right boundary are node 1,3,6,10. (10 is the right-most node).So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].Solutionclass Solution { public List<Integer> boundaryOfBinaryTree(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; res.add(root.val); helper(root.left, true, false, res); helper(root.right, false, true, res); return res; } private void helper(TreeNode root, boolean leftBound, boolean rightBound, List<Integer> res) { if (root == null) return; if (root.left == null && root.right == null) { res.add(root.val); return; } if (leftBound) res.add(root.val); helper(root.left, leftBound, root.right == null && rightBound, res); helper(root.right, root.left == null && leftBound, rightBound, res); if (rightBound) res.add(root.val); }} ...

ProblemGiven two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.Example 1:Input:Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output:Merged tree: 3 / \ 4 5 / \ \ 5 4 7Note: The merging process must start from the root nodes of both trees.Solutionclass Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == null) return t2; if (t2 == null) return t1; int value = t1.val + t2.val; TreeNode root = new TreeNode(value); root.left = mergeTrees(t1.left, t2.left); root.right = mergeTrees(t1.right, t2.right); return root; }} ...

ProblemGiven a nested list of integers represented as a string, implement a parser to deserialize it.Each element is either an integer, or a list – whose elements may also be integers or other lists.Note: You may assume that the string is well-formed:String is non-empty.String does not contain white spaces.String contains only digits 0-9, [, - ,, ].Example 1:Given s = “324”,You should return a NestedInteger object which contains a single integer 324.Example 2:Given s = “[123,[456,[789]]]",Return a NestedInteger object containing a nested list with 2 elements:An integer containing value 123.A nested list containing two elements: i. An integer containing value 456. ii. A nested list with one element: a. An integer containing value 789.Solution/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * // Constructor initializes an empty nested list. * public NestedInteger(); * * // Constructor initializes a single integer. * public NestedInteger(int value); * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // Set this NestedInteger to hold a single integer. * public void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * public void add(NestedInteger ni); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return null if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */Implementation:class Solution { public NestedInteger deserialize(String s) { NestedInteger res = new NestedInteger(); if (s == null || s.length() == 0) return res; if (s.charAt(0) != ‘[’) res.setInteger(Integer.parseInt(s)); else if (s.length() > 2) { int i = 1, count = 0, j = 1; while (j < s.length()) { char ch = s.charAt(j); if (count == 0 && (ch == ‘,’ || j == s.length()-1)) { NestedInteger cur = deserialize(s.substring(i, j)); res.add(cur); i = j+1; } else if (ch == ‘[’) count++; else if (ch == ‘]’) count–; j++; } } return res; }} ...