LeetCode题目解答——Hard部分

以下是LeetCode题目解答的最后一部分：Hard部分。

Text Justification

【题目】 Given an array of words and a length  L , format the text such that each line has exactly  L  characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly  L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

Return the formatted lines as:

[    "This    is    an",    "example  of text",    "justification.  " ]

Note: Each word is guaranteed not to exceed  L in length.

【解答】主要要把题意理解透彻，几个corner case的理解，包括最末一行的处理，还有面对空字符串的处理。遍历的时候，i从0遍历到words.length，在i==words.length的时候处理最末一行的情况。感觉这个题目其实没有太多技巧性，就是需要细心和耐心，把逻辑想清楚。

public class Solution {  public List<String> fullJustify(String[] words, int L) {   List<String> result = new ArrayList<String>();   StringBuilder sb = new StringBuilder();   List<String> list = new ArrayList<String>();   int lenSum = 0;   for (int i = 0; i <= words.length; i++) {    String cur;    if (i == words.length)     cur = "";    else     cur = words[i];    if (lenSum + cur.length() + list.size() > L || i == words.length) {     int slots = list.size() - 1;     int basicSpaces = 0;     if (slots != 0)      basicSpaces = (L - lenSum) / slots;     if (i==words.length)      basicSpaces = 1;     int moreSpaces = L - lenSum;     if (slots != 0 && basicSpaces > 0)      moreSpaces = (L - lenSum) % slots;     if (i==words.length)      moreSpaces = L - lenSum - slots;     // append     for (int j = 0; j < list.size(); j++) {      if (j != 0) {       for (int k = 0; k < basicSpaces; k++)        sb.append(' ');       if (moreSpaces > 0 && i != words.length) {        sb.append(' ');        moreSpaces--;       }      }      sb.append(list.get(j));     }     // trailing spaces     for (int k = 0; k < moreSpaces; k++) {      sb.append(' ');     }     list.clear();     lenSum = 0;     result.add(sb.toString());     sb = new StringBuilder();    }    list.add(cur);    lenSum += cur.length();   }   return result;  } } 

Search in Rotated Sorted Array

【题目】 Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., might become  ).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

【解答】不知道为什么这道题归为Hard，其实思路还是很容易找到的。如果是一个单纯的升序排列的数组，那就是二分法查找，现在这个数组可能被rotate了，那么还是借由二分法，只不过在找到中间的数了之后，需要比较中间数和最右数（或者最左数），有这样的结论：

• 1. 如果中间数大于最右数，那么最大最小数的分界点在右半支，而左半支严格单调递增，在这种情况下通过比较左半支的首尾两个数，判断目标数在不在左半支内，如果不在，就一定在右半支内。
• 2. 如果中间数小于最右数，那么最大最小数的分界点在左半支，而右半支严格单调递增，在这种情况下通过比较右半支的首尾两个数，判断目标数在不在右半支内，如果不在，就一定在左半支内。

public class Solution {  public int search(int[] A, int target) {   return search(A, target, 0, A.length-1);  }  private int search(int[] A, int target, int start, int end) {   if (start>end)    return -1;   int mid = (end+start)/2;   if (target==A[mid])    return mid;   if (A[end]>=A[mid]) { // the right part is increasing    if (target>A[end] || targetA[mid]) {     return search(A, target, mid+1, end);    } else {     return search(A, target, start, mid-1);    }   }  } } 

Binary Tree Maximum Path Sum

【题目】 Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:Given the below binary tree,

1       / /      2   3

Return .

【解答】定义一个maxSinglePath方法，用来返回以root为根的树从根开始存在的最大单向路径（根到某叶子或者根到某分支节点）。再定义一个pathSum方法，用来返回以root为根时，该树的最大path sum，在该方法内，调用maxSinglePath方法分别获取左子树和右子树的最大单向路径，二者之和再加上当前节点的值为包含当前root的最大path sum，再递归求出左子树的最大path sum和右子树的最大path sum，三者取最大值。

public class Solution {  public int maxPathSum(TreeNode root) {   if (null==root)    return 0;   Map<TreeNode, Integer> map = new HashMap<>();   return pathSum(root, map);  }  private int pathSum(TreeNode root, Map<TreeNode, Integer> map) {   int left = 0;   if (root.left!=null) {    left = maxSinglePath(root.left, map);    if (left<0)     left = 0;   }   int right = 0;   if (root.right!=null) {    right = maxSinglePath(root.right, map);    if (right<0)     right = 0;   }   int current = left + right + root.val;   if (root.left!=null) {    int l = pathSum(root.left, map);    if (l>current)     current = l;   }   if (root.right!=null) {    int r = pathSum(root.right, map);    if (r>current)     current = r;   }   return current;  }  private int maxSinglePath(TreeNode root, Map<TreeNode, Integer> map) {   if (map.containsKey(root))    return map.get(root);   int left = 0;   if (root.left!=null) {    left = maxSinglePath(root.left, map);    if (left<0)     left = 0;   }   int right = 0;   if (root.right!=null) {    right = maxSinglePath(root.right, map);    if (right<0)     right = 0;   }   int maxVal = Math.max(left, right) + root.val;   map.put(root, maxVal);   return maxVal;  } } 

Reverse Nodes in k-Group

【题目】 Given a linked list, reverse the nodes of a linked list  k  at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For k = 2, you should return:  2->1->4->3->5

For k = 3, you should return:  3->2->1->4->5

【解答】引入一个伪节点作为头，可以免去对head的特殊处理。基本思路是：一个快指针，一个慢指针，平时慢指针不动，快指针往前跑，在二者间距达到k时，令start=slow.next，end=fast，对于[start,end]这一段区间的节点指向反向，反向后令slow.next=end，fast=start。题目不难，小心一点便是。

public class Solution {  public ListNode reverseKGroup(ListNode head, int k) {   ListNode fake = new ListNode(0);   fake.next = head;   ListNode fast = fake;   ListNode slow = fake;   int count = 0;   while (fast!=null) {    if (count==k) {     ListNode start = slow.next;     ListNode end = fast;     fast = end.next;     ListNode n = start;     ListNode next = n.next;     while (n!=end) {      ListNode temp = next.next;      next.next = n;      n = next;      next = temp;     }     slow.next = end;     start.next = fast;     slow = start;     fast = slow;     count=0;    } else {     fast = fast.next;     count++;    }   }   return fake.next;  } } 

Binary Tree Postorder Traversal

【题目】 Given a binary tree, return the  postorder  traversal of its nodes’ values.

1     /      2     /    3

return [3,2,1] .

Note: Recursive solution is trivial, could you do it iteratively?

【解答】如果是递归遍历，没有任何难度，也不可能放到Hard级别里面来。用非递归方式，需要一个辅助栈，用来存放节点pop出来的当前状态。具体说：

• 当前节点不为空，就先遍历左子树，同时当前节点入栈，状态栈入true；
• 当前节点为空，退栈，如果状态为true，就遍历右子树，状态栈顶变为false；
• 当前节点为空，退栈，如果状态为false，就遍历退栈节点，相应状态元素退栈。

public class Solution {  public List<Integer> postorderTraversal(TreeNode root) {   Stack<TreeNode> stack = new Stack<>();   Stack<Boolean> status = new Stack<>();   List<Integer> result = new ArrayList<>();   TreeNode node = root;   while (!stack.isEmpty() || node!=null) {    if (null!=node) {     stack.push(node);     status.push(true);     node = node.left;    } else {     node = stack.peek();     boolean flag = status.pop();     if (flag) {      node = node.right;      status.push(false);     } else {      result.add(node.val);      stack.pop();      node = null;     }    }   }   return result;  } } 

Candy

【题目】 There are  N  children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

【解答】最开始我选择的做法是像分析函数曲线一样找拐点，如果知道这条曲线的拐点，比如极大值，那么极大值左侧是递增的，极大值右侧是递减的；极小值左侧递减，右侧递增。这里特别麻烦的地方在于，极小值取值是显然为1，但极大值的取值取决于极大值两侧单调曲线的长度，要取长的那一侧的最大值。

比如ratings=[1, 2, 3, 4, 5, 4, 1]，其中ratings[4]就是一个极大值，但是取值candies[4]取决于ratings[4]左右两侧单调曲线的长度，左侧比右侧长，因此要根据左侧来计数取值，在这里candies[4]就取5（如果根据右侧来取值就是3，那就错了）。还需要考虑一些特殊的case，比如极大、极小值出现在首尾，这种情况下是只有右侧或者只有左侧单调曲线的。因此这个办法的代码写起来比较复杂。

下面这个办法我也是参考了别人的解法的，两遍遍历，一遍正向，一遍逆向，思路非常清晰：

• 正向遍历的时候，如果发现递增序列，就放置一个从1开始依次递增的数，但是，存在这样错误的情况：如果是递减序列的情况呢，这里全放置了1；
• 那么这个问题就需要通过逆向遍历来消除。

那么这个办法对于我之前办法所说的那个不易处理的问题，通过逆向遍历中的一个关系为且的子判断条件candies[i]<=candies[i+1]给巧妙的规避掉了。

public class Solution {  public int candy(int[] ratings) {   if (ratings == null || ratings.length == 0)    return 0;   if (ratings.length == 1)    return 1;   int[] candies = new int[ratings.length];   candies[0] = 1;   // forward   for (int i = 1; i < ratings.length; i++) {    // rating: asc    if (ratings[i] > ratings[i - 1])     candies[i] = candies[i - 1] + 1;    else     candies[i] = 1;   }   // backward   for (int i = ratings.length - 2; i >= 0; i--) {    // rating: desc && candy: asc    if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])     candies[i] = candies[i + 1] + 1;   }   int total = 0;   for (int i = 0; i < ratings.length; i++)    total += candies[i];   return total;  } } 

Edit Distance

【题目】 Given two words  word1  and  word2 , find the minimum number of steps required to convert  word1  to  word2 . (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

【解答】遇到这种求两个东西之间距离的，要么回溯法，要么动态规划。这里就是动态规划，这个题目还是很有代表性的。建立一个dist二维数组，注意行、列的长度要分别比word1和word2的长度多1，dist[i][j]用来表示word1.substring(0,i)到word2.substring(0,j)的距离。因此dist[i][j]在i==0的时候为j，在j==0的时候为i。其余的情况，根据insert、delete和replace三种可能性分类讨论，取三种情况的最小距离。

public class Solution {  public int minDistance(String word1, String word2) {   Integer[][] dist = new Integer[word1.length()+1][word2.length()+1];   return min(word1, word2, word1.length(), word2.length(), dist);  }  private int min(String w1, String w2, int i, int j, Integer[][] dist) {   if (dist[i][j]!=null)    return dist[i][j];   if (i==0) {    dist[i][j] = j;    return j;   } else if (j==0) {    dist[i][j] = i;    return i;   }   char ci = w1.charAt(i-1);   char cj = w2.charAt(j-1);   if (ci==cj) {    dist[i][j] = min(w1, w2, i-1, j-1, dist);    return dist[i][j];   }   int insert = min(w1, w2, i-1, j, dist) + 1;   int replace = min(w1, w2, i-1, j-1, dist) + 1;   int delete = min(w1, w2, i, j-1, dist) + 1;   int result = Math.min(delete, Math.min(insert, replace));   dist[i][j] = result;   return result;  } } 

Recover Binary Search Tree

【题目】 Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

【解答】对于BST，对任一节点，满足左分支上面所有的节点都小于根节点，右分支上面所有的节点都大于根节点，而中序遍历能够保证形成正确的递增序列，因此遍历时能够保证当前节点的大小一定大于前一个节点的大小。这一点是做这道题的基础。

对于其中某两个节点被错误的swap了，这里有两种情况可供讨论：

• 两个错误节点是相邻的，比如：0,1,2,3,5,4,6，这种情况中序遍历的整个过程只能发现一次异常节点，在这里是4，这种情况，需要把异常节点和它前面那个节点调换，即4和5调换；
• 两个错误节点不相邻，比如：0,1,5,3,4,2,6，这种情况中序遍历的整个过程可以发现两次异常节点，在这里分别为3和2，这种情况下，需要把第一个异常节点的前面那个节点和第二个异常节点调换，即5和2。

掌握这两点规律以后问题就很好解了。下面的解法里面，en用于存储第一个异常节点，enLast表示第一个异常节点的前面那个节点。StopTraversalException的定义其实是可选的，用于在发现第二个异常节点之后直接交换错误值并返回，没必要再往后遍历了。

class StopTraversalException extends RuntimeException {  public StopTraversalException() {   super();  } } public class Solution {  private TreeNode en = null;  private TreeNode enLast = null;  private TreeNode last = new TreeNode(Integer.MIN_VALUE);  public void recoverTree(TreeNode root) {   if (null==root)    return;   try {    traverse(root);   } catch (StopTraversalException e) {    return;   }   swap(en, enLast);  }  private void traverse(TreeNode root) {   if (root.left!=null)    traverse(root.left);   if (last.val>root.val) {    if (en==null) {     en = root;     enLast = last;    } else {     swap(enLast, root);     throw new StopTraversalException();    }   }   last = root;   if (root.right!=null)    traverse(root.right);  }  private void swap(TreeNode n1, TreeNode n2) {   int temp = n1.val;   n1.val = n2.val;   n2.val = temp;  } } 

Populating Next Right Pointers in Each Node II

【题目】 Follow up for problem “ Populating Next Right Pointers in Each Node “.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,

Given the following binary tree,

1        /  /       2    3      / /    /     4   5    7

After calling your function, the tree should look like:

1 -> NULL        /  /       2 -> 3 -> NULL      / /    /     4-> 5 -> 7 -> NULL

【解答】看起来只是在《Populating Next Right Pointers in Each Node》基础上增加了一个节点可能为空的情况，但是难度其实增加不少。我把原有的递归改成这种从上到下一层一层循环执行的逻辑，我觉得是比较清晰的办法。对于每一层（level），引入一个fake节点来帮助掌控每一层的头部，按序构建next关联关系。

public class Solution {  public void connect(TreeLinkNode root) {   if (root == null)    return;    TreeLinkNode level = root;   while (level != null) {    TreeLinkNode n = level;    TreeLinkNode fake = new TreeLinkNode(0);    TreeLinkNode child = fake;     while (n != null) {     if (n.left != null) {      child.next = n.left;      child = child.next;     }      if (n.right != null) {      child.next = n.right;      child = child.next;     }      n = n.next;    }     child.next = null;    level = fake.next;   }  } }

Permutations II

【题目】 Given a collection of numbers that might contain duplicates, return all possible unique permutations.

【解答】大致的思路就是回溯法，但是这里需要注意去重的处理，如果这一点上思路选择不合适的话就会绕很大的圈子。先给num数组排序，那么对于任何重复数字的情况，例如num为1,2,2,3,4，其中2有重复，假设给这两个2分别标号：2-1和2-2，如果我可以保证最终输出的序列中，2的顺序也是一致的，即2-1一定出现在2-2之前，那么，就恰好去重了。

所以在下面的build方法里面的for循环中，第二个continue的判断条件，就用到了这样的逻辑——如果num[i]==num[i-1]且used[i-1]==false，这表示当有某个数重复出现时，这个序列先用到了后面的那个，这违背了重复数字保序性的要求。

public class Solution {  public List<List<Integer>> permuteUnique(int[] num) {   List<List<Integer>> total = new ArrayList<>();   if (num==null)    return total;   Arrays.sort(num);   boolean[] used = new boolean[num.length];   build(num, used, new ArrayList<Integer>(), total);   return total;  }  private void build (int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> total) {   if (list.size()==nums.length) {    total.add(list);    return;   }   for (int i=0; i<nums.length; i++) {    if (used[i])     continue;    if (i>0 && nums[i]==nums[i-1] && !used[i-1])      continue;    used[i] = true;    List<Integer> l = new ArrayList<>(list);    l.add(nums[i]);    build (nums, used, l, total);    used[i] = false;   }  } }  

Best Time to Buy and Sell Stock III

【题目】 Say you have an array for which the  i th  element is the price of a given stock on day  i .

Design an algorithm to find the maximum profit. You may complete at most two transactions.

【解答】最开始我还是按照《Best Time to Buy and Sell Stock》的思路来解题：那个思路已经可以给出一段区间内的max profit，保留该方法，当前这道题相当于给出一个切分点i，在[0,i]和[i,prices.length)这两段区间内分别求max profit，取二者之和的最大值。但是在遇到比较长的case的时候超时了，所以引入二维数组来缓存计算过的数据，减少重复计算：

public class Solution {  public int maxProfit(int[] prices) {   if (prices.length<=1)    return 0;   mins = new Integer[prices.length][prices.length];   maxs = new Integer[prices.length][prices.length];   int max = 0;   for (int i=0; i<prices.length; i++) {    int left = maxProfit(prices, 0, i+1);    int right = maxProfit(prices, i, prices.length-i);    if (left+right>max)     max = left+right;   }   return max;  }  private Integer[][] mins; // first n days  private Integer[][] maxs; // last n days  private int maxProfit(int[] prices, int offset, int len) {   if (len<=1) {    return 0;   }   if (mins[offset][0]==null)    mins[offset][0] = prices[offset];   if (maxs[offset+len-1][offset+len-1]==null)    maxs[offset+len-1][offset+len-1] = prices[offset+len-1];   // fill max prices, from right to left   for (int i=len-2; i>=0; i–) {    if (maxs[offset+len-1][i]==null) {     if (prices[offset+i]>maxs[offset+len-1][i+1])      maxs[offset+len-1][i] = prices[offset+i];     else      maxs[offset+len-1][i] = maxs[offset+len-1][i+1];    }   }   // fill min prices, and calculate the biggest profit, from left to right   int biggestProfit = 0;   for (int i=1; i<len; i++) {    if (mins[offset][i]==null) {     if (prices[offset+i]<mins[offset][i-1])      mins[offset][i] = prices[offset+i];     else      mins[offset][i] = mins[offset][i-1];    }    int profit = maxs[offset+len-1][i] – mins[offset][i];    if (profit>biggestProfit)     biggestProfit = profit;   }   return biggestProfit;  } } 

可是依然超时。这个思路毕竟也是换汤不换药，n平方的复杂度。造成这种局面的原因在于，

•  外层循环那个n是来自于寻找前半段和后半段的切分点，这一层循环是无论如何都少不了的；
•  里层循环那个n则是因为对每次前半段或者后半段自身，要再从后往前寻找最大价格，再从前往后遍历寻找最小价格，并且求出最大收益。

于是换个思路，改进球最大收益的过程，

•  第一遍，从前往后循环对每个i的取值计算[0,i]的最大收益；
•  第二遍，从后往前循环对每个i的取值计算[i,prices.length)的最大收益，并根据profits[i]的值相加球总收益，记录总收益的最大值。

于是复杂度变成n了：

public class Solution {  public int maxProfit(int[] prices) {   if (null == prices || prices.length <= 1)    return 0;    int[] profits = new int[prices.length];   profits[0] = 0;   int minPrice = prices[0], maxProfit = 0;   for (int i = 1; i < prices.length; i++) {    minPrice = Math.min(prices[i - 1], minPrice);    if (maxProfit < prices[i] - minPrice)     maxProfit = prices[i] - minPrice;    profits[i] = maxProfit;   }    int maxPrice = prices[prices.length - 1];   int maxFinalProfit = profits[prices.length - 1];   maxProfit = 0;   for (int i = prices.length - 2; i >= 0; i--) {    maxPrice = Math.max(maxPrice, prices[i + 1]);    if (maxProfit < maxPrice - prices[i])     maxProfit = maxPrice - prices[i];    if (maxFinalProfit < profits[i] + maxProfit)     maxFinalProfit = profits[i] + maxProfit;   }    return maxFinalProfit;  } }

Palindrome Partitioning II

【题目】 Given a string  s , partition  s  such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s .

【解答】借由《Palindrome Partitioning》的思路，对于给定的区间[start,end)，先判断是否是回文，如果不是，分别尝试在区间的各个位置截断，判断前半段和后半段是否都是回文。在对一些变态case超时以后，分两次加上了两个cache，isPalindromeCache和minCutCache，分别存储判断是否为回文的记录和计算cut次数的记录：

public class Solution {  public int minCut(String s) {   Boolean[][] isPalindromeCache = new Boolean[s.length()][s.length()];   Integer[][] minCutCache = new Integer[s.length()][s.length()];   if (isPalindrome(s, 0, s.length(), cache))    return 0;   return minCut(s, 0, s.length(), isPalindromeCache, minCutCache);  }  private int minCut(String s, int start, int end, Boolean[][] isPalindromeCache, Integer[][] minCutCache) {   if (end-start<=1)    return 0;   int min = end-start-1;   for (int i=1; i<end-start-1; i++) {    if (isPalindrome(s, start, start+i, isPalindromeCache)) {     if (isPalindrome(s, start+i, end, isPalindromeCache))      return 1;     int cut = minCut(s, start+i, end, isPalindromeCache)+1;     if (cut<min)      min = cut;    }   }   return min;  }  private boolean isPalindrome(String s, int start, int end, Boolean[][] isPalindromeCache) {   if (isPalindromeCache[start][end-1]!=null)    return isPalindromeCache[start][end-1];   for (int i=start, j=end-1; j>i; j--,i++) {    if (s.charAt(i)!=s.charAt(j))     return false;   }   return true;  } } 

可即便如此，在遇到另外一些变态case的时候依然超时，比如这样一个case：514个a，加两个b，再加946个a。下面这个方法的思路也是从别处借鉴来的：

public class Solution {     public int minCut(String s) {  int len = s.length();  int[] cut = new int[len + 1];  for (int i = 0; i <= len; i++)      cut[i] = len - i;  boolean[][] isPalindrome = new boolean[len][len];  for (int i = len - 1; i &>t;= 0; i--) {      for (int j = i; j < len; j++) {   if (s.charAt(i) == s.charAt(j)    && (j - i < 2 || isPalindrome[i + 1][j - 1])) {       isPalindrome[i][j] = true;       cut[i] = Math.min(cut[i], cut[j + 1] + 1);   }      }  }  return cut[0] - 1;     } } 

逻辑上看简单多了，但是其实要更不容易想出来。用一个二维数组isPalindrome存放是否为回文的状态，两层循环嵌套，i从后往前，j从i往后遍历，如果s[i]==s[j]，并且前一个状态，即isPalindrome[i+1][j-1]为真，那么isPalindrome[i][j]也为真。一维数组cut用来存放需要切分的次数，初始为字符串区域的长度。

N-Queens II

【题目】 Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

【解答】紧跟着N-Queens那道题，思路简直一模一样。不是很理解为啥弄两道差不多的题目。

public class Solution {  private int total = 0;  public int totalNQueens(int n) {   solveNQueens(0, n, new int[n]);   return total;  }  private void solveNQueens(int i, int n, int[] positions) {   if (i == n) {    total++;   } else {    for (int j = 0; j < n; j++) {     positions[i] = j; // row: i, col: j     if (validate(i, positions)) {      solveNQueens(i + 1, n, positions);     }    }   }  }  private boolean validate(int maxRow, int[] positions) {   for (int i = 0; i < maxRow; i++) {    if (positions[i] == positions[maxRow] // same column      || Math.abs(positions[i] - positions[maxRow]) == maxRow - i) // catercorner line     return false;   }   return true;  } } 

Substring with Concatenation of All Words

【题目】 You are given a string,  S , and a list of words,  L , that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

【解答】先把L放到一个map里面去，key为单词，value为该单词在L中出现的次数。再遍历S，以S中每个字母为开头时，寻找是否存在满足题目要求的子串：发现单词匹配，就从dictCopy里面给这个单词出现的次数减一，如果一切匹配，就不会出现num==null或者num==0的情况。

public class Solution {  public List<Integer> findSubstring(String S, String[] L) {   Map<String, Integer> dict = new HashMap<>();   for (String l : L) {    if (!dict.containsKey(l)) {     dict.put(l, 0);    }    dict.put(l, dict.get(l)+1);   }   int len = L[0].length();   int lenSum = len*L.length;   List<Integer> list = new ArrayList<>();   traverseS : for (int i=0; i<=S.length()-lenSum; i++) {    Map<String, Integer> dictCopy = new HashMap<>(dict);    for (int j=i; j<i+lenSum; j=j+len) {     String s = S.substring(j, j+len);     Integer num = dictCopy.get(s);     if (num==null || num==0)      continue traverseS;     num--;     dictCopy.put(s, num);    }    list.add(i);   }   return list;  } } 

Sudoku Solver

【题目】 Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.' .

You may assume that there will be only one unique solution.

...and its solution numbers marked in red.

【解答】回溯法，每个可以填写数字的位置挨个试，用validate方法来验证当前的填写是否正确，不需要等整个board全部填完了再判断，每填写一个数就可以判断了。办法挺死板的，当时想着不行的话再想办法优化，不过居然AC了，真是……

public class Solution {  public void solveSudoku(char[][] board) {   solve(board);  }  private boolean solve(char[][] board) {   for (int i=0; i<9; ++i) {    for (int j=0; j<9; ++j) {     if ('.' == board[i][j]) {      for (int k=1; k<=9; ++k) {       board[i][j] = (char)('0'+k);       if (validate(board, i, j) && solve(board))        return true;       board[i][j] = '.';      }      return false;     }    }   }   return true;  }  // x: row, y: col  private boolean validate(char[][] board, int x, int y) {   // col==y   for (int i=0; i<9; i++)    if (i!=x && board[i][y]==board[x][y])     return false;   // row==x   for (int j = 0; j<9; j++)    if (j!=y && board[x][j]==board[x][y])     return false;   // each cube   for (int i=3*(x/3); i<3*(x/3+1); i++)    for (int j=3*(y/3); j<3*(y/3+1); j++)     if (i!=x && j!=y && board[i][j]==board[x][y])      return false;   return true;  } } 

N-Queens

【题目】 The  n -queens puzzle is the problem of placing  n  queens on an  n × n  chessboard such that no two queens attack each other.

Given an integer n , return all distinct solutions to the  n -queens puzzle.

Each solution contains a distinct board configuration of the n -queens' placement, where  'Q' and  '.' both indicate a queen and an empty space respectively.

For example,There exist two distinct solutions to the 4-queens puzzle:

[  [".Q..",  // Solution 1   "...Q",   "Q...",   "..Q."],   ["..Q.",  // Solution 2   "Q...",   "...Q",   ".Q.."] ]

【解答】这个题目是比较经典的回溯法题目，很多教科书里面都有。根据国际象棋的规则，这里要求任意两个皇后不能在同一行，不能在同一列，不能在同一条对角线上。使用一个int数组来存放当前棋盘上皇后的状态，int[i]=j，表示第i行上，皇后放在第j列，这样天然避免了在同一行情况的出现，也避免了使用二维数组来保存状态；但是不能在同一列和不能在同一条对角线需要每次摆放一个皇后以后立马检查。

public class Solution {  public List<String[]> solveNQueens(int n) {   List<String[]> list = new ArrayList<String[]>();   solveNQueens(0, n, new int[n], list);   return list;  }  private void solveNQueens(int i, int n, int[] positions,    List<String[]> list) {   if (i == n) {    outputToList(n, positions, list);   } else {    for (int j = 0; j < n; j++) {     positions[i] = j; // row: i, col: j     if (validate(i, positions)) {      solveNQueens(i + 1, n, positions, list);     }    }   }  }  private void outputToList(int n, int[] positions, List<String[]> list) {   String[] result = new String[n];   for (int i = 0; i < n; i++) {    StringBuffer sb = new StringBuffer();    for (int j = 0; j < n; j++) {     if (j == positions[i])      sb.append('Q');     else      sb.append('.');    }    result[i] = sb.toString();   }   list.add(result);  }  private boolean validate(int maxRow, int[] positions) {   for (int i = 0; i < maxRow; i++) {    if (positions[i] == positions[maxRow] // same column      || Math.abs(positions[i] - positions[maxRow]) == maxRow - i) // catercorner line     return false;   }   return true;  } } 

Minimum Window Substring

【题目】 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example, S =  "ADOBECODEBANC" T =  "ABC"

Minimum window is "BANC" .

Note: If there is no such window in S that covers all characters in T, return the emtpy string  "" .

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

【解答】注意题目要求的复杂度是n阶的，因此不能在循环中去匹配变化子串和T，那样就n的平方阶了。可以通过一个有限长的int数组来表达这个字符串T，大致思路如下：

• 双指针，一左一右，[left,right]这段区域内的子串就是待认定的window substring；
• 把T用一个长度为128的int数组来表达，下标表示字符的ascii码，值表示该字符在T中出现的次数；
• 整个流程就是是right和left分别尝试右移的过程，始终尽量保持[left,right]包含window substring：
•     (1) 如果rightOrLeft为真，并且right能够右移，就右移并判定子串是否包含T，如果包含就判断是否需要更新min；如果包含或者干脆就不能右移，把移动的标志位置反。
•     (2) 如果rightOrLeft为false，考虑left右移，并判定子串是否包含T，如果包含就判断是否需要更新min；如果不包含就把移动的标志位置反，让下次迭代去尝试right右移。
• 注意处理开头的特殊情况，即初始状态left==right==0，需要先把S[0]放到source里面去，避免遗漏。

public class Solution {  public String minWindow(String S, String T) {   int[] target = new int[128];   for (int i=0; i<T.length(); i++) {    target[(int)(T.charAt(i))]++;   }   int left=0;   int right=0;   int[] source = new int[128];   source[(int)(S.charAt(0))]++;   String min = "";   if (T.equals(S.substring(0,1)))    min = S.substring(0,1);   boolean rightOrLeft = true; // true: right, false: left   while (true) {    if (rightOrLeft) {     if (right<S.length()-1) {      right++;      source[(int)(S.charAt(right))]++;     } else {      rightOrLeft = false;     }     if (match(source, target)) {      if ("".equals(min) || min.length()>right-left+1)       min = S.substring(left, right+1);      rightOrLeft = false;     }    } else {     if (left==S.length()-1)      break;     source[(int)(S.charAt(left))]--;     left++;     if (match(source, target)) {      if ("".equals(min) || min.length()>right-left+1)       min = S.substring(left, right+1);     } else {      rightOrLeft = true;     }    } // else   } // while   return min;  }  private boolean match(int[] left, int[] right) {   for (int i=0; i<128; i++) {    if (left[i]<right[i])     return false;   }   return true;  } } 

【题目】 Merge  k  sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

【解答】这道题是有一定典型意义的。如果是两个列表归并，那么显然就使用传统归并排序的方法就好了，但是现在是m个列表归并，这就意味着，在每一轮归并的迭代中，假使每个列表取一个元素，那么着m个元素的大小关系是完全不可知的，原有排好序的list特性并没有充分利用，这能优化吗？

进一步考虑，在对刚才说的m个元素排序以后，比如说我就知道了最小元素是来自7号链表的，那么，我可以想象，最终结果中，次小元素要么在当前这剩下的m-1个元素里面，要么就是7号链表剩下元素的头部了。要充分利用这个信息，才可以让算法的复杂度降下来。

要不断取得这m个元素中最小的，于是我联想到了堆排序（各种排序方法，包括堆排序，我以前在这篇文中总结过）。每次从最小堆中抽走堆顶，接下去就补充被抽走堆顶的next元素到堆中，重新恢复最小堆。分析一下复杂度，按照刚才的定义，全部元素是(m*n)，堆大小是m，那么整个复杂度就是m*n(log m)。

在Java中，其实已经有封装好堆排序的现成的东西了（这是个死知识），那个东西就是PriorityQueue：

public class Solution {  public ListNode mergeKLists(List<ListNode> lists) {   if (null==lists || lists.isEmpty())    return null;   PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.size(), new Comparator<ListNode>(){    @Override    public int compare(ListNode n1, ListNode n2) {     if (n1.val==n2.val)      return 0;     else if (n1.val<n2.val)      return -1;     else      return 1;    }   });   // initialization   for (ListNode n : lists) {    if (n==null)     continue;    queue.add(n);   }   ListNode fakeHead = new ListNode(0);   ListNode current = fakeHead;   while (!queue.isEmpty()) {    ListNode n = queue.poll();    current.next = n;    current = n;    if (n.next!=null)     queue.add(n.next);   }   return fakeHead.next;  } } 

Merge Intervals

【题目】 Given a collection of intervals, merge all overlapping intervals.

【解答】这题相对来说比较简单。先排序，按照start属性来排。之后开始遍历intervals，如果发现有重叠的interval，就合并；如果发现非重叠的interval，放置较靠前的一个到最终的list里面去。

public class Solution {  public List<Interval> merge(List<Interval> intervals) {   Collections.sort(intervals, new Comparator<Interval>(){    @Override    public int compare(Interval left, Interval right) {     if (left.start == right.start)      return 0;     else if (left.start < right.start)      return -1;     else      return 1;    }   });   List<Interval> list = new ArrayList<>();   Interval toCompare = null;   for (Interval interval : intervals) {    if (toCompare!=null && interval.end>=toCompare.start && interval.start<=toCompare.end) {     toCompare.start = Math.min(interval.start, toCompare.start);     toCompare.end = Math.max(interval.end, toCompare.end);    } else {     if (toCompare!=null)      list.add(toCompare);     toCompare = interval;    }   }   if (null!=toCompare)    list.add(toCompare);   return list;  } } 

Scramble String

【题目】 Given a string  s1 , we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 =  "great" :

great    /    /   gr    eat  / /    /  / g   r  e   at            / /           a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string  "rgeat" .

rgeat    /    /   rg    eat  / /    /  / r   g  e   at            / /           a   t

We say that "rgeat" is a scrambled string of  "great" .

Similarly, if we continue to swap the children of nodes "eat" and  "at" , it produces a scrambled string  "rgtae" .

rgtae    /    /   rg    tae  / /    /  / r   g  ta  e        / /       t   a

We say that "rgtae" is a scrambled string of  "great" .

Given two strings s1 and  s2 of the same length, determine if  s2 is a scrambled string of  s1 .

【解答】终于做到一道3维动态规划的题目了。最开始我就是简单的回溯遍历，结果执行超时了，于是想到DP。cache[i][j][k]表示的是，s1以下标i为起点，s2以下标j为起点，二者长度都为k时，这两个子串是否满足scramble关系，即s1的[i,i+k)和s2的[j,j+k)是否满足scramble关系。

这一点不难想到，并且想到以后就可以落实代码了。但是在写代码判断scramble关系的时候，考虑swap和非swap两种情况，而且很容易写错：

1. s1的[start1,start1+i)和s2的[start2,start2+i)满足scramble关系，并且s1的[start1+i,start1+len)和s2的[start2+i, start2+len)也满足scramble关系，这种情况是两个子串没有发生swap的；
2. 另一种情况自然就是两个子串发生了swap，即s1的[start1+len-i,start1+len)和s2的[start2, start2+i)满足scramble关系，并且s1的[start1,start1+len-i)和s2的[start2+i,start2+len)也满足scrmable关系。

上面两种情况只需具备其一就返回true，像这种比较绕的DP题目，我觉得写出数学通式是最关键的一步。

public class Solution {  public boolean isScramble(String s1, String s2) {   if (s1.length()!=s2.length())    return false;   // cache[i][j][k]: scramble between s1:[i,i+k) and s2:[j,j+k)   Boolean[][][] cache = new Boolean[s1.length()][s1.length()][s1.length()+1];   return isScramble(s1, s2, 0, 0, s1.length(), cache);  }  private boolean isScramble(String s1, String s2, int start1, int start2, int len, Boolean[][][] cache) {   if (cache[start1][start2][len]!=null)    return cache[start1][start2][len];   // exit   if (len==1) {    cache[start1][start2][len] = s1.charAt(start1)==s2.charAt(start2);    return cache[start1][start2][len];   }   // s1:[start1, start1+i) <=> s2:[start2, start2+i) and s1:[start1+i, start1+len) <=> s2:[start2+i, start2+len)   // or   // s1:[start1+len-i, start1+len) <=> s2:[start2, start2+i) and s1:[start1, start1+len-i) <=> s2:[start2+i, start2+len)   for (int i=1; i<len; i++) {    if (     (isScramble(s1, s2, start1, start2, i, cache) && isScramble(s1, s2, start1+i, start2+i, len-i, cache))     ||     (isScramble(s1, s2, start1+len-i, start2, i, cache) && isScramble(s1, s2, start1, start2+i, len-i, cache))    ) {     cache[start1][start2][len] = true;     return true;    }   }   cache[start1][start2][len] = false;   return false;  } } 

Trapping Rain Water

【题目】 Given  n  non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

【解答】这道题是hard里面相对比较简单的。大致的思路就是，找最长的两根杆子，分别为最长和次长，而两根杆子中间的部分，每个位置都去算距离次长杆子的距离，这些距离累加起来就是这两根杆子中间部分可以trap的雨水的量，而对于这两根杆子两侧的部分，继续递归求解。

public class Solution {  public int trap(int[] A) {   return trap(A, 0, A.length-1);  }  // [start, end]  private int trap(int[] A, int start, int end) {   if (start+1>=end)    return 0;   int maxIndex = -1;   int secondMaxIndex = -1;   for (int i=start; i<=end; i++) {    if (secondMaxIndex==-1 || A[i]>A[secondMaxIndex]) {     secondMaxIndex = i;     if (maxIndex==-1 || A[secondMaxIndex]>A[maxIndex]) {      int temp = maxIndex;      maxIndex = secondMaxIndex;      secondMaxIndex = temp;     }    }   }   int left = Math.min(maxIndex, secondMaxIndex);   int right = Math.max(maxIndex, secondMaxIndex);   int leftPart = trap(A, start, left);   int rightPart = trap(A, right, end);   int midPart = 0;   for (int i=left+1; i<right; i++) {    midPart += A[secondMaxIndex] - A[i];   }   return leftPart+midPart+rightPart;  } } 

Median of Two Sorted Arrays

【题目】 There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

【解答】首先要明确中位数的概念：在A和B的总数为奇数时，中位数是中间那个数；总数为偶数时，中位数是中间那两个数的算术平均数。

这道题麻烦的地方在于时间复杂度是log(m+n)，要得到这种时间复杂度，每个数遍历一遍显然是不可能的。于是就要充分利用好A和B都是有序的特点，而联想到二分搜索的时间复杂度恰好是log(n)，所以思路就是看看能不能利用或者借鉴上二分搜索。

再一个如果强化一下条件，假设这里m==n，那么拿A的中位数和B的中位数比较，如果A的中位数比较大，那么最后我们要求的A并B的中位数应该在B的后半段+A的前半段里，这样可以一直递归求解。现在m不一定等于n，这个结论也依然成立，每次分别比较A和B的中位数后可以给A、B分别砍掉半支，这样最后求解的复杂度恰好就是O(log(m+n))。

在求中位数的时候小心坐标运算的时候发生错误，我反正错了N次。思路好找，要写对还挺难的。

public class Solution {  public double findMedianSortedArrays(int A[], int B[]) {   if ((A.length + B.length) % 2 == 0) {    int midLeft = (A.length + B.length) / 2 - 1;    int midRight = (A.length + B.length) / 2;    return (0.0 + find(A, B, midRight, 0, A.length - 1, 0, B.length - 1) + find(      A, B, midLeft, 0, A.length - 1, 0, B.length - 1)) / 2;   } else {    int mid = (A.length + B.length) / 2;    return (double) find(A, B, mid, 0, A.length - 1, 0, B.length - 1);   }  }  private int find(int A[], int B[], int i, int aStart, int aEnd, int bStart,    int bEnd) {   if (aEnd - aStart < 0)    return B[bStart + i];   if (bEnd - bStart < 0)    return A[aStart + i];   if (i == 0)    return A[aStart] < B[bStart] ? A[aStart] : B[bStart];   int aRelativePos = (int) (((0.0 + (aEnd - aStart + 1)) / ((aEnd     - aStart + 1) + (bEnd - bStart + 1))) * i);   int aMid = aRelativePos + aStart;   int bMid = i - aRelativePos - 1 + bStart;   if (A[aMid] > B[bMid]) {    i -= bMid - bStart + 1;    aEnd = aMid;    bStart = bMid + 1;   } else {    i -= aMid - aStart + 1;    bEnd = bMid;    aStart = aMid + 1;   }   return find(A, B, i, aStart, aEnd, bStart, bEnd);  } } 

Maximal Rectangle

【题目】 Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

【解答】首先要理解题意，这里说的是要求这个矩形里面包含1，并且是只包含1，“ rectangle containing all ones ”，反正开始我是没有理解出，这句话是表示“只”包含1的。

比如这样一幅图：

1 0 1 0 1

1 1 1 0 0

0 1 1 0 1

那么这个矩形应该是用下划线标出的区域，因此应该返回4。

那怎么做呢？先降维思考一下，如果matrix只有一维，那就好办了，寻找连续的1，连续最多的就是最大的值。现在是二维，也可以往一维上面靠，做法就是：从上往下一行一行遍历，每一行的每个元素，都表示和上一行同一列连通（上下都是1就表示连通）的累加值。也就是说，上面这个图变成了：

1 0 1 0 1

2 1 2 0 0

0 2 2 0 1

只有上下连通，才会被累加，如果断掉了，就置为0。

现在，每一行遍历完毕的时候，我拿到该行的结果，就可以去计算截止到该行为止的最大值了。

比如最后这行：

0 2 2 0 1

把这个数组（命名为acc）画成等价的柱状图就是：

我拿Excel草草画的图，但是可见要求最大的矩形应该就是acc[1]和acc[2]的和，为4。但是在求最大值的时候，需要按照高度从1到acc里元素的最大值为上限依次遍历，寻找连续块的最大值。

public class Solution {  public int maximalRectangle(char[][] matrix) {   if (matrix.length==0 || matrix[0].length==0)    return 0;   int[] acc = new int[matrix[0].length];   int max = 0;   for (int i=0; i<matrix.length; i++) {    int singleMax = 0;    for (int j=0; j<matrix[i].length; j++) {     if (matrix[i][j]=='0') {      acc[j] = 0;     } else {      acc[j]++;      if (acc[j]>singleMax)       singleMax = acc[j];     }    }    int newMax = calculateMax(acc, singleMax);    if (newMax>max)     max = newMax;   }   return max;  }  private int calculateMax(int[] acc, int singleMax) {   int max = 0;   for (int i=1; i<=singleMax; i++) {    int accInRow = 0;    for (int j=0; j<acc.length; j++) {     if (acc[j]>=i) {      accInRow += i;      if (accInRow>max)       max = accInRow;     } else {      accInRow = 0;     } // else    } // for j   } // for i   return max;  } } 

AC了，代码其实并不复杂，但是其实复杂度够高的，达到了O(x*y*m)，其中x和y分别表示矩阵的长和宽，m表示某一行上积累的最大高度（acc里的最大值）。

当然，网传有更牛逼更简洁的解法，也更不好懂，这 有一篇文章 提到，我就不贴了。

Max Points on a Line

【题目】 Given  n  points on a 2D plane, find the maximum number of points that lie on the same straight line.

【解答】最开始我的做法是，O(n^2)的复杂度，每取得两个点，就可以列出一个直线方程：y=kx+b，并把该直线方程放到一个map里面去，后续出现新的直线的时候都要先到map里面去寻找是否能够找到重合的直线，但是值得注意的有两处：

• k和b都要表示成分数，不要使用double或者float，否则可能损失精度，比较两个float或者double的大小可能是不准确的；
• 在直线垂直于x轴的时候，原有方程不存在，直线方程为x=x0。

不过原始代码却执行超时了。

在此基础上整理一下思路，下面的解法AC，getCount方法，是对于给定的两个点p1、p2，寻找Point[]数组里面和p1、p2形成的直线斜率相同的点的个数（注意时刻都不要使用真正求斜率的除法，因为那样会引入double或者float型，丢失精度）：

public class Solution {  public int maxPoints(Point[] points) {   if (points.length <= 1)    return points.length;   int maxCount = 0;   for (int i = 0; i < points.length; i++) {    for (int j = 0; j < points.length; j++) {     if (points[i] == points[j])      continue;     int count = getCount(points, points[i], points[j]);     if (count > maxCount)      maxCount = count;    }   }   return maxCount;  }  public int getCount(Point[] points, Point p1, Point p2) {   int count = 0;   // vertical   if (p1.x == p2.x) {    for (Point p : points) {     if (p.x == p1.x)      count++;    }    return count;   }   // horizontal   if (p1.y == p2.y) {    for (Point p : points) {     if (p.y == p1.y)      count++;    }    return count;   }   for (Point p : points) {    // gradient: (p2.y-p1.y)/(p2.x-p1.x)    if ((p.y - p2.y) * (p1.x - p2.x) == (p1.y - p2.y) * (p.x - p2.x)) {     count++;    }   }   return count;  } } 

LRU Cache

【题目】 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:  get  and  set .

【解答】这里应用一点小知识，LinkedHashMap其实已经把这个LRU的事情做好了，只要覆写removeEldestEntry方法，判断如果大小大过容量，就返回true。构造方法，需要调用父类构造方法，传入的三个参数分别表示：初始大小、扩容增长因子、访问顺序（accessOrder）。其中第三个参数尤其重要，accessOrder为true时，每次调用get方法访问行为发生后，会把最近访问的对象移动到头部，而超出容量移除对象时，是从尾部开始的。

import java.util.LinkedHashMap; class LRULinkedHashMap extends LinkedHashMap<Integer, Integer> {  private final int capacity;  public LRULinkedHashMap(int capacity) {   super(capacity, 0.75F, true);   this.capacity = capacity;  }  @Override  protected boolean removeEldestEntry(Map.Entry paramEntry) {   if (this.entrySet().size()>capacity)    return true;   return false;  } } public class LRUCache {  private LRULinkedHashMap map;  public LRUCache(int capacity) {   this.map = new LRULinkedHashMap(capacity);  }  public int get(int key) {   Integer result = this.map.get(key);   if (null==result)    return -1;   return result;  }  public void set(int key, int value) {   this.map.put(key, value);  } } 

Longest Valid Parentheses

【题目】 Given a string containing just the characters  '('  and  ')' , find the length of the longest valid (well-formed) parentheses substring.

For "(()" , the longest valid parentheses substring is  "()" , which has length = 2.

Another example is ")()())" , where the longest valid parentheses substring is  "()()" , which has length = 4.

【解答】这道题也算hard里面相对简单的。基本思路是DP，但是最开始我用递归，从长串往短串方向递归调用，结果一个长case让我栈溢出了。于是改成循环，从短串往长串遍历（i从小到大），而在每次迭代中从右向左寻找包含s[i]的合法序列（j从大到小）：

• 每次循环迭代都拿包含s[i]的括号序列和不包含s[i]的括号序列（即前一次迭代的结果）比较，取较大值留下来。比如()()，i==2时，s[2]是(，结果是2；i==3时，s[3]是)，最长串是4，结果是2和4的最大值，为4。
• 用rightNum变量记录目前多余的右括号，需要继续找左括号来匹配。如果rightNum<0，就要跳出本次迭代，因为左括号太多了，而右括号又必须先于左括号出现（因为j从大到小变化），允许合法出现的机会已经错过了；只有当rightNum变为0时，表示当前的串是一个合法的结果，更新accumation为当前串的长度len。

public class Solution {  public int longestValidParentheses(String s) {   if (s==null)    return 0;   int longest = 0;   for (int i=0; i<s.length(); i++) {    int rightNum = 0;    int len = 0;    int accumulation = 0;    for (int j=i; j>=0; j--) {     char ch = s.charAt(j);     if (ch==')') {      rightNum++;     } else {      rightNum--;      if (rightNum<0)       break;      len += 2;      if (rightNum==0)       accumulation = len;     }    }    if (accumulation>longest)     longest = accumulation;   }   return longest;  } } 

Longest Consecutive Sequence

【题目】 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O( n ) complexity.

【解答】这道题的关键在于时间复杂度要求是O(n)的，这就意味着，排序不用想了，而遍历这个数组的时候，还得用常量时间复杂度去做额外的操作。如果拼命去想怎么从原数组里面挨个取出元素来，怎么放到某一个容器里面，在整个数组便利完成之后，要让这个最长序列的结果也得出来的话，就走入死胡同了。原因在于，比如有序列1,2,3,4的话，当你2先放入容器，4再放入的时候，很难找到和2之间的关联。但是，反过来就不一样了。先把所有的数都一股脑儿倒到一个set里面去，然后从中任取一个数，接着这个数开始往大的序列和往小的序列都挨个尝试从这个set里面取出来，取到说明有连续串，一直取到这一串数断掉为止。

public class Solution {  public int longestConsecutive(int[] num) {   if (num==null)    return 0;   Set<Integer> total = new HashSet<>();   for (int n : num) {    total.add(n);   }   int max = 0;   while (!total.isEmpty()) {    int n = total.iterator().next();    total.remove(n);    int count = 1;    int i = n;    while (total.remove(++i))     count++;    i = n;    while (total.remove(--i))     count++;    if (count>max)     max = count;   }   return max;  } } 

Copy List with Random Pointer

【题目】 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.

【解答】这题比较简单。首先，按照不考虑random属性的情况，过一遍这个list，创建一个新的list，但是，每过到一个节点的时候，就以<老节点,新节点>这样的组合放到map里面去。之后再过第二遍的时候，对于每一个老节点，以及它的random属性所指向的节点，都可以在这个map里面找到对应的新节点。

对于新建的链表，下面使用了一个fakeTargetHead来简化代码，避免head的特殊判断。

public class Solution {     public RandomListNode copyRandomList(RandomListNode head) {  Map<RandomListNode, RandomListNode> map = new HashMap<>();  RandomListNode fakeTargetHead = new RandomListNode(0);  RandomListNode src = head;  RandomListNode target = fakeTargetHead;  while (src!=null) {      RandomListNode node = new RandomListNode(src.label);      map.put(src, node);      target.next = node;      src = src.next;      target = target.next;  }  src = head;  while (src!=null) {      if (null!=src.random) {   RandomListNode node = map.get(src);   RandomListNode to = map.get(src.random);   node.random = to;      }      src = src.next;  }  return fakeTargetHead.next;     } } 

Largest Rectangle in Histogram

【题目】 Given  n  non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3] .

The largest rectangle is shown in the shaded area, which has area = unit.

For example,

【解答】这个题目可以看作是《Maximal Rectangle》中间的一部分，但是它时间上面的要求，要比那道题高得多。因此我一开始使用解那道题里面的办法来解，就超时了：

public class Solution {  public int largestRectangleArea(int[] height) {   if (height==null)    return 0;   int max = 0;   for (int h : height)    if (h>max)     max = h;   int largest = 0;   for (int i=1; i<=max; i++) {    int total = 0;    for (int h : height) {     if (h>=i) {      total += i;      if (total>largest)       largest = total;     } else {      total = 0;     }    }   }   return largest;  } } 

导致超时的case是[0,0,0,0,0,0,0,0,2147483647]，显然，我让i从1循环到2147483674，这太不合理了。于是我想，i不需要循环那么多，只需要循环height数组里面的那几个数就可以了，而height数组里面的数是可能有重复的，如果case有1000个1怎么办，其实i只需要取一次1就可以了，因此引入一个HashSet来去重：

public class Solution {  public int largestRectangleArea(int[] height) {   if (height==null)    return 0;   Set<Integer> set = new HashSet<>();   for (int h : height)    if (!set.contains(h))     set.add(h);   int largest = 0;   for (int i : set) {    int total = 0;    for (int h : height) {     if (h>=i) {      total += i;      if (total>largest)       largest = total;     } else {      total = 0;     }    }   }   return largest;  } } 

刚才那个case确实过了，但是碰到一个巨长无比的case又嗝屁了，归根到底这也是个n平方的复杂度。在网上这道题我找到了很多解法，有的解法虽然能AC，但是只是针对case做了优化，换一种类型的case其实还是会挂，因此并没有从实际上解决问题，但是，看看下面这个办法（来自 这个blog ），大致是思路就是从左往右遍历，用一个栈来存储递增的高度序列，如果发现高度递减，停止入栈，并不断出栈以分别计算以之前栈内存放的每个高度作为最终高度的矩形面积。具体解法刚才的blog链接上叙述得非常清楚了，图文并茂。这个办法是非常漂亮的，简洁清晰，而且时间复杂度也要低得多。

public class Solution {  public int largestRectangleArea(int[] height) {   Stack<Integer> stk = new Stack<>();   int i = 0;   int maxArea = 0;   while (i <= height.length) {    int currentHeight = 0;    if (i != height.length)     currentHeight = height[i];    if (stk.empty() || height[stk.peek()] <= currentHeight) {     stk.push(i++);    } else {     int t = stk.pop();     maxArea = Math.max(maxArea, height[t] * (stk.empty() ? i : i - stk.peek() - 1));    }   }   return maxArea;  } } 

Jump Game II

【题目】 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.

Your goal is to reach the last index in the minimum number of jumps.

The minimum number of jumps to reach the last index is . (Jump  step from index 0 to 1, then  steps to the last index.)

【解答】这个题目在hard的题目里算是简单的。在任意一个位置，都存在着当前jump数值可达的范围[x,range]，还存在着该区间的一系列A[i]+i所取的最大值nextRange，当i>range时，更新range为原nextRange，并且jump数加一。

public class Solution {  public int jump(int[] A) {   if (A.length == 1)    return 0;   int jump = 0;   int range = 0;   int nextRange = 0;   for (int i = 0; i < A.length; i++) {    if (range < i) {     if (i <= nextRange) {      jump++;      range = nextRange;     } else {      return -1; // unreachable     }    }    if (A[i] + i > nextRange)     nextRange = A[i] + i;    if (i == A.length - 1)     return jump;   }   return -1; // impossible  } } 

Interleaving String

【题目】 Given  s1 ,  s2 ,  s3 , find whether  s3  is formed by the interleaving of  s1  and  s2 .

【解答】这道题给我的第一感觉就是使用回溯法，分别从s1、s2和s3取一个字符，分别命名为c1、c2和c3，如果c1==c3而c2!=c3，那么这个字符从s1取；如果c2==c3而c1!=c3，那么字符从s2取。麻烦的是c1==c3且c2==c3的情况，相当于回溯的路径出现了分支，于是我使用一个stack来存放分支。最终回溯的路径会是深度优先遍历一棵二叉树。

class Fork {  int i1;  int i2;  int i3;  public Fork(int i1, int i2, int i3) {   this.i1 = i1;   this.i2 = i2;   this.i3 = i3;  } } public class Solution {  public boolean isInterleave(String s1, String s2, String s3) {   if (s1.length()+s2.length()!=s3.length())    return false;   int i1=0, i2=0, i3=0;   Stack<Fork> stack = new Stack<>();   while ((i1<s1.length() && i2<s2.length()) || !stack.isEmpty()) {    char c1 = 0;    char c2 = 0;    char c3 = 0;    if (i1<s1.length())     c1 = s1.charAt(i1);    if (i2<s2.length())     c2 = s2.charAt(i2);    if (i3<s3.length())     c3 = s3.charAt(i3);    if ( c1==0 || c2==0 || (c1!=c3&&c2!=c3) ) {     if (stack.isEmpty())      return false;     Fork fork = stack.pop();     i1 = fork.i1;     i2 = fork.i2;     i3 = fork.i3;     i2++;     i3++;     continue;    }    if (c1==c3 && c2==c3) {     Fork fork = new Fork(i1,i2,i3);     stack.push(fork);     i1++;     i3++;    } else if (c1==c3) {     i1++;     i3++;    } else {     i2++;     i3++;    }   }   while (i1<s1.length()) {    char c1 = s1.charAt(i1);    char c3 = s3.charAt(i3);    if (c1!=c3)     return false;    i1++;    i3++;   }   while (i2<s2.length()) {    char c2 = s2.charAt(i2);    char c3 = s3.charAt(i3);    if (c2!=c3)     return false;    i2++;    i3++;   }   return true;  } } 

但是很快遇到某case的时候超时了，仔细分析了一下这个方法，最好的情况下时间复杂度是n阶，最坏的情况下时间复杂度达到了2的n次方阶。

现在换个思路，不是从前往后，而是从后往前想，假如说result[i][j]表示s1的前i个字符形成的子串和s2的前j个字符形成的子串能否interleave成s3的前i+j个字符形成的子串，那么就有这样的递推关系：

只要 result[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1) 或者 result[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1) 有一个为真，result[i][j]就为真。

public class Solution {  public boolean isInterleave(String s1, String s2, String s3) {   if (s3.length() != (s2.length() + s1.length()))    return false;   boolean result[][] = new boolean[s1.length() + 1][s2.length() + 1];   result[0][0] = true;   for (int i = 1; i <= s1.length(); i++)    result[i][0] = result[i - 1][0] && (s1.charAt(i - 1) == s3.charAt(i - 1));   for (int j = 1; j <= s2.length(); j++)    result[0][j] = result[0][j - 1] && (s2.charAt(j - 1) == s3.charAt(j - 1));   for (int i = 1; i <= s1.length(); i++) {    for (int j = 1; j <= s2.length(); j++) {     boolean r = result[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);     result[i][j] = r || (result[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));    }   }   return result[s1.length()][s2.length()];  } } 

再看一下这个方法的复杂度，稳定在n的平方。

Insert Interval

【题目】 Given a set of  non-overlapping  intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

This is because the new interval [4,9] overlaps with  [3,5],[6,7],[8,10] .

【解答】循环过程中，分三种情况讨论：

• newInterval在interval的右侧，把左侧的interval加入list；
• newInterval在interval左侧，把左侧的newInterval加入list，把原右侧的interval置为新的newInterval；
• newInterval和interval有重叠，这种情况下，构造一个新的newInterval，覆盖范围为原有interval和newInterval的并集。

待循环结束，list里面添加余下的尚未处理的那个newInterval（因为它在右侧）。

public class Solution {  public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {   ArrayList<Interval> res = new ArrayList<Interval>();   for (Interval interval : intervals) {    if (interval.end < newInterval.start) { // [1,2] _[3,4]_     res.add(interval);    } else if (interval.start > newInterval.end) { // _[1,2]_ [3,4]     res.add(newInterval);     newInterval = interval;    } else if (interval.end >= newInterval.start || interval.start <= newInterval.end) { // [1,3] _[2,4]_ or _[1,3]_ [2,4]     int start = Math.min(interval.start, newInterval.start);     int end = Math.max(newInterval.end, interval.end);     newInterval = new Interval(start, end);    } else {     // unreachable    }   }   res.add(newInterval);   return res;  } } 

Wildcard Matching

【题目】 Implement wildcard pattern matching with support for  '?'  and  '*' .

'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).  The matching should cover the entire input string (not partial).  The function prototype should be: bool isMatch(const char *s, const char *p)  Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "*") → true isMatch("aa", "a*") → true isMatch("ab", "?*") → true isMatch("aab", "c*a*b") → false

【解答】看到题目以后，第一反应就是通过一个递归函数来解题：

public class Solution {  public boolean isMatch(String s, String p) {   return isMatch(s, 0, p, 0);  }  private boolean isMatch(String s, int si, String p, int pi) {   if (pi==p.length())    return si==s.length();   char cp = p.charAt(pi);   if (si==s.length()) {    if (cp=='*')     return isMatch(s, si, p, pi+1);    return false;   }   char cs = s.charAt(si);   if (cp=='*') {    for (int i=0; i<s.length()-si; i++) {     if (isMatch(s, si+i, p, pi+1))      return true;    }    return false;   } else if (cp=='?') {    return isMatch(s, si+1, p, pi+1);   } else {    if (cs==cp)     return isMatch(s, si+1, p, pi+1);    return false;   }  } } 

然后，在巨长的case上面执行超时了。于是想了想，除了星号（*）以外，其它情况的递归都显然可以免去；而如果遇到星号，要比较星号后面的字符，比如ababccccdddd去匹配*d，那么遇到星号以后，要看星号后面那个字符，在这里是d，去源字符串s里面找，如果不是d的话直接忽略掉，如果是d的话继续递归匹配：

public class Solution {  public boolean isMatch(String s, String p) {   return isMatch(s, 0, p, 0);  }  private boolean isMatch(String s, int si, String p, int pi) {   while (pi<p.length()) {    char cp = p.charAt(pi);    if (si==s.length()) {     if (cp=='*')      pi++;     return false;    }    char cs = s.charAt(si);    if (cp=='*') {     pi++;     int minLen = 0;     while (true) {      if (pi==p.length()) {       if (s.length()-si>=minLen)        return true;       else        return false;      }      char cp2 = p.charAt(pi);      if (cp2=='*') {       minLen = 0;       pi++;      } else if (cp2=='?') {       minLen++;       pi++;      } else {       for (int i=si; i<s.length(); i++) {        if (s.charAt(i)==cp2 && i-si>=minLen && isMatch(s, i+1, p, pi+1))         return true;       }       return false;      }     }    } else if (cp=='?') {     si++;     pi++;    } else {     if (cs==cp) {      si++;      pi++;     }     return false;    }   }   return si==s.length();  } } 

可是，遇到某变态case继续超时……于是搞了N久，最后可行的办法是，利用一个标识是否遇到星号的变量（asterisk），以及额外的两个标识在星号之后在s和p出现的指针sa和pa，整个大循环的逻辑是：

• 如果si和pi指向的字符相等，或者pi指向了问号，那么，si++，pi++，这两个是基本指针的前进；
• 如果pi指向了星号，把pi移到星号之后的那个字符，并且把此时是si存为sa，pi存为pa；
• 对于余下的情况，考虑在出现过星号的情况，因为两个字符不相等了，那么星号后面那个字符相应的匹配位置需要在s中往后移。

注意：在遇到星号的时候要把pi和si分别赋给pa和sa，而在有星号出现后的未匹配事件发生时，要把pa和sa赋回给pi和si（相当于pa和sa占住位置，pi和si往前试探着前行）；另外，循环完毕后，要判断p内还有没有非星号的字符，如果有就匹配失败了。

public class Solution {  public boolean isMatch(String s, String p) {   return isMatch(s, 0, p, 0);  }  private boolean isMatch(String s, int si, String p, int pi) {   boolean asterisk = false;   int sa = 0, pa = 0;   while (si < s.length()) {    if (pi == p.length()) {     if (asterisk) {      sa++;      si = sa;      pi = pa;      continue;     } else {      return false;     }    }    char cp = p.charAt(pi);    char cs = s.charAt(si);    if (cp == '*') {     asterisk = true;     pi++;     pa = pi;     sa = si;    } else if (cp == '?') {     si++;     pi++;    } else {     if (cs == cp) {      si++;      pi++;     } else if (asterisk) {      pi = pa;      sa++;      si = sa;     } else {      return false;     }    }   }   for (int i = pi; i < p.length(); i++) {    if (p.charAt(i) != '*')     return false;   }   return true;  } } 

Distinct Subsequences

【题目】 Given a string  S  and a string  T , count the number of distinct subsequences of  T  in  S .

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of  "ABCDE" while  "AEC" is not).

Return .

【解答】拿到这样的题目，首先，回溯法遍历所有情况肯定是可以做的，但是那样复杂度太高。为了减小复杂度，很容易考虑到使用动态规划。但是动态规划怎么设计递推关系就很重要了：

• 考虑到S.length()>=T.length()，那么其中一种递推关系是，假设f(i)表示S的[0,i)子串和T形成的distinct子串数量，那么如果可以找到f(i+1)和f(i)之间的递推关系就好解了，这是其中一个思路，写出来的DP是一维的；
• 也可以假设f(i,j)表示的是S的[0,i)子串和T的[0,j)子串，需要寻找f(i,j)和f(i-1,j)、f(i,j-1)、f(i-1,j-1)这样的递推关系，我采用的是这一条思路：

• 如果S[i]==T[j]，那么当S[i]没出现在T里面的时候，f(i,j)=f(i-1,j)，当S[i]出现在T里面，就有f(i,j)=f(i-1,j-1)，因此，这种情况下f(i,j) = f(i-1,j) + f(i-1,j-1)；
• 如果S[i]!=T[j]，那么显然S[i]不能出现在T里面，于是f(i,j) = f(i-1,j)。

注意程序出口，当j为0，即T变成了空串，序列数就是1；反过来，当S为空串的时候，T一定是空串，否则T的长度大于S的长度了。

public class Solution {  public int numDistinct(String S, String T) {   Integer[][] cache = new Integer[S.length()+1][T.length()+1];   return numDistinct(S, T, S.length(), T.length(), cache);  }  private int numDistinct(String S, String T, int i, int j, Integer[][] cache) {   if (cache[i][j]!=null)    return cache[i][j];   if (i>0) {    char sc = S.charAt(i-1);    char st = 0;    if (j>0)     st = T.charAt(j-1);    int prev = numDistinct(S, T, i-1, j, cache);    if (sc!=st || j==0) {     cache[i][j] = prev;     return prev;    } else {     int total = prev + numDistinct(S, T, i-1, j-1, cache);     cache[i][j] = total;     return total;    }   } else {    if (j==0) {     cache[i][j] = 1;     return 1;    } else {     cache[i][j] = 0;     return 0;    }   }  } } 

可是上的解法在某变态case的时候出现了StackOverflowError，通常这种情况下，如果你的编程语言支持尾递归，那可以考虑把它优化成尾递归的形式，如果不支持（比如Java），那就干脆尝试把它写成循环（其实下面的代码还是显得啰嗦，还可以继续优化，我留着这样是因为在思考过程中把所有分支情况全部写出来了，是最原始的分类讨论的体现，我觉得看起来直白；而且，空间复杂度上面，是可以从n平方降到n的，因为i是一直在增大，之前的数据没有必要保留，每次这个数组保存的都是当前i的迭代数据）：

public class Solution {  public int numDistinct(String S, String T) {   if (T.length()==0)    return 1;   if (S.length()==0)    return 0;   int[][] cache = new int[S.length()][T.length()];   for (int i=0; i<S.length(); i++) {    for (int j=0; j<=i && j<T.length(); j++) {     if (S.charAt(i)!=T.charAt(j)) {      if (i>j) { // i!=0       cache[i][j] = cache[i-1][j];      } else {       cache[i][j] = 0;      }     } else {      if (i>j) {       if (j==0)        cache[i][j] = cache[i-1][j] + 1;       else        cache[i][j] = cache[i-1][j] + cache[i-1][j-1];      } else {       if (i==0)        cache[i][j] = 1;       else        cache[i][j] = cache[i-1][j-1];      }     }    }   }   return cache[S.length()-1][T.length()-1];  } } 

Word Break II

【题目】 Given a string  s  and a dictionary of words  dict , add spaces in  s  to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

A solution is ["cats and dog", "cat sand dog"] .

【解答】动态规划求解。判断给定字符串是否以某单词结尾，如果是，就抠掉该结尾单词，余下子串继续递归判断。

public class Solution {  public List<String> wordBreak(String s, Set<String> dict) {   Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();   List<String> defaultList = new ArrayList<String>();   defaultList.add("");   map.put(-1, defaultList);   return getAllPossibleSentences(s, dict, s.length()-1, map);  }  private List<String> getAllPossibleSentences(String s, Set<String> dict, int pos, Map<Integer, List<String>> map){   if (map.containsKey(pos))    return map.get(pos);   String sub = s.substring(0, pos+1);   List<String> list = new ArrayList<String>();   for (String word : dict) {    if (sub.endsWith(word)) {     int firstSegEnd = pos - word.length();     if (firstSegEnd<-1) // no solution found      continue;     List<String> subList = getAllPossibleSentences(s, dict, firstSegEnd, map);     for (String str : subList) {      if ("".equals(str))       list.add(word);      else       list.add(str + " " + word);     }    } // if   }// for   map.put(pos, list)   return list;  } } 

First Missing Positive

【题目】 Given an unsorted integer array, find the first missing positive integer.

Your algorithm should run in O ( n ) time and uses constant space.

【解答】我开始只注意到了O(n)的时间复杂度，于是引入一个HashSet，把所有数往里一放，最后再从1开始累加，并挨个检查在set里面有没有，要没有就说明找到那个数了：

public class Solution {  public int firstMissingPositive(int[] A) {   Set<Integer> set = new HashSet<>();   for (int a : A)    set.add(a);   int i = 1;   while (i<=A.length) {    if (!set.contains(i))     return i;    i++;   }   return i;  } } 

但是后来看到题目要求常量的额外空间，那我的这个办法其实是错误的。要记录下这些数，又要常量复杂度，只能考虑能不能重用入参数组A了，按理说修改参数里面的东西是不会引入空间复杂度的。

对于数组A，如果所有的A[i]==i+1的话，那么说明这些数正好是从1开始的连续正整数序列，但是现在有可能有0，有负数，而正数序列也可能有重复，有断开的地方……但无论怎样，遍历一遍A，用交换的办法尽可能把每个数都放到该放的地方去，当然，只有大小不超过A长度的正整数才能够找到安居之所。即，把A[i]放到A[A[i]-1]去。这一遍遍历之后，从头开始数，第一个数值和下标对不上（即A[i]!=i+1）的那个元素的下标，就是要求的missing positive。

public class Solution {  public int firstMissingPositive(int[] A) {   Set<Integer> set = new HashSet<>();   for (int a : A)    set.add(a);   int i = 1;   while (i<=A.length) {    if (!set.contains(i))     return i;    i++;   }   return i;  } } 

虽说AC了，但是粗看我对其中的时间复杂度是否为n阶并不确定，看着一个for和一个while嵌套的。于是我改成了这样：

public class Solution {  public int firstMissingPositive(int[] A) {   int i=0;   while (i<A.length) {    if (A[i]!=(i+1) && A[i]>=1 && A[i]<=A.length && A[A[i]-1]!=A[i]) {     // swap     int temp = A[i];     A[i] = A[temp-1];     A[temp-1] = temp;    } else {     i++;    }   }   for (i=0; i<A.length; i++) {    if (A[i]!=i+1)     return i+1;   }   return A.length+1;  } } 

看着是少了一层嵌套循环，但是其实呢，做法上面换汤不换药，在每次swap发生的时候，i是不前进的，也就是说，对于A[i]，swap一次，把A[i]换到该去的地方去了，但是换过来一个别的数，而这个新数因为在A[i]上，要继续swap……直到条件不满足，没有继续swap的必要，i才继续前进。但是仔细分析，由于每个到来到A[i]的数都去了它应该去的地方，A[i]去了新地方以后便不会再被换走，因而复杂度确实为n。不管是写成上面那种形式还是这种形式。

这道题还是有些有趣的。

Word Ladder II

【题目】 Given two words ( start  and  end ), and a dictionary, find all shortest transformation sequence(s) from  start  to  end , such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Return

[     ["hit","hot","dot","dog","cog"],     ["hit","hot","lot","log","cog"]   ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

【解答】这道题刚拿到手的时候觉得挺简单的，BFS。每一层都去dict里面寻找所有的单词，如果二者只差一个字母（isNeighbor），就找到结果了。

public class Solution {  public List<List<String>> findLadders(String start, String end, Set<String> dict) {   List<List<String>> list = new ArrayList<>();   List<String> ll = new ArrayList<>();   ll.add(start);   list.add(ll);   dict.remove(start);   while (!dict.isEmpty()) {    Set<String> toRemove = new HashSet<>();    List<List<String>> newList = new ArrayList<>();    List<List<String>> matched = new ArrayList<>();    for (List<String> l : list) {     String from = l.get(l.size()-1);     for (String d : dict) {      if (isNeighbor(from, d)) {       toRemove.add(d);       List<String> nl = new ArrayList<>(l);       nl.add(d);       if (d.equals(end))        matched.add(nl);       else        newList.add(nl);      }     }    }    if (!matched.isEmpty())     return matched;    if (toRemove.isEmpty())     return new ArrayList<List<String>>();    dict.removeAll(toRemove);    list = newList;   }   return new ArrayList<List<String>>();  }  private boolean isNeighbor(String s1, String s2) {   boolean dif = false;   for (int i=0; i<s1.length(); i++) {    char c1 = s1.charAt(i);    char c2 = s2.charAt(i);    if (c1!=c2) {     if (!dif)      dif = true;     else      return false;    }   }   return true;  } } 

但是很快遇到某case就超时了。于是调整一下角度，对每次待匹配的单词，不是去dict里面匹配，而是根据该单词的每个字母，都可以变化成任意一个其它字母的规则，因为那样每次都形成一个新单词，再拿这个新单词到dict里面去寻找是否有匹配：

public class Solution {  public List<List<String>> findLadders(String start, String end, Set<String> dict) {   List<List<String>> list = new ArrayList<>();   List<String> ll = new ArrayList<>();   ll.add(start);   list.add(ll);   dict.remove(start);   while (!dict.isEmpty()) {    Set<String> toRemove = new HashSet<>();    List<List<String>> newList = new ArrayList<>();    List<List<String>> matched = new ArrayList<>();    for (List<String> l : list) {     String from = l.get(l.size()-1);     for (int i=0; i<from.length(); i++) {      for (char ch='a'; ch<='z'; ch++) {       char[] cs = from.toCharArray();       if (cs[i]!=ch)        cs[i] = ch;       String ns = new String(cs);       if (dict.contains(ns)) {        toRemove.add(ns);        List<String> nl = new ArrayList<>(l);        nl.add(ns);        if (ns.equals(end))         matched.add(nl);        else         newList.add(nl);       }      }     }    }    if (!matched.isEmpty())     return matched;    if (toRemove.isEmpty())     return new ArrayList<List<String>>();    dict.removeAll(toRemove);    list = newList;   }   return new ArrayList<List<String>>();  } } 

结果出现了Memory Limit Exceeded。怎么办呢？忽然想到了对于这种搜索的改进，从start开始的单向搜索可以优化成从start和end两头一起往中间搜索这样的双向搜索形式，理论上可以减少BSF最宽一层的节点数量（代码看起来有点长，但是其实逻辑并不复杂）：

public class Solution {  public List<List<String>> findLadders(String start, String end, Set<String> dict) {   // forward list   List<List<String>> list = new ArrayList<>();   List<String> ll = new ArrayList<>();   ll.add(start);   list.add(ll);   dict.remove(start);   // backward list   List<List<String>> backList = null;   List<List<String>> matched = new ArrayList<>();   while (!dict.isEmpty()) {    // 1. forward bfs    Set<String> toRemove = new HashSet<>();    List<List<String>> newList = new ArrayList<>();    for (List<String> l : list) {     String from = l.get(l.size()-1);     for (int i=0; i<from.length(); i++) {      for (char ch='a'; ch<='z'; ch++) {       char[] cs = from.toCharArray();       if (cs[i]!=ch)        cs[i] = ch;       String ns = new String(cs);       if (dict.contains(ns)) {        toRemove.add(ns);        List<String> nl = new ArrayList<>(l);        nl.add(ns);        if (ns.equals(end))         matched.add(nl);        else         newList.add(nl);       }      }     }    }    if (!matched.isEmpty() || toRemove.isEmpty())     return matched;    dict.removeAll(toRemove);    list = newList;    // 2. backward bfs    if (backList==null) {     backList = new ArrayList<>();     ll = new ArrayList<>();     ll.add(end);     backList.add(ll);     dict.remove(end);    }    newList = new ArrayList<>();    toRemove.clear();    for (List<String> bl : backList) {     String b = bl.get(0);     for (String s : dict) {      if (isNeighbor(b, s)) {       toRemove.add(s);       List<String> nl = new ArrayList<>(bl);       nl.add(0, s);       newList.add(nl);      }     }    }    if (toRemove.isEmpty())     return matched;    dict.removeAll(toRemove);    backList = newList;    // 3. match    for (List<String> l : list) {     for (List<String> bl : backList) {      String s1 = l.get(l.size()-1);      String s2 = bl.get(0);      if (isNeighbor(s1, s2)) {       List<String> nl = new ArrayList<>(l);       nl.addAll(bl);       matched.add(nl);      }     }    }    if (!matched.isEmpty())     return matched;   }   return new ArrayList<List<String>>();  }  private boolean isNeighbor(String s1, String s2) {   boolean dif = false;   for (int i=0; i<s1.length(); i++) {    char c1 = s1.charAt(i);    char c2 = s2.charAt(i);    if (c1!=c2) {     if (!dif)      dif = true;     else      return false;    }   }   return true;  } } 

代码真是复杂不少，遗憾的是，继续Memory Limit Exceeded，服了，这条路看来是走不通了。从网上搜索，有各种解法，都挺复杂的。下面列出的这个方法是从 这个博客 上面摘录下来的，属于思路上相对比较清晰的做法了。整个过程拆成两步，BFS来构造表示单词变化关系的树，DFS来最后搜索路径。从宏观的复杂度上看，比我最原始的做法节约就节约在对路径list的遍历上面，我的做法因为要遍历路径的list，导致循环嵌套多了一层，但是这里使用一个map存放每个节点和下一层的对应关系，省下了这层循环，当然，最后需要额外的DFS来构造这个list。虽说如此，我还是觉得方法不够优雅简洁，如果你有清晰简洁的方法，请告诉我。

public class Solution {  class WordWithLevel {   String word;   int level;    public WordWithLevel(String word, int level) {    this.word = word;    this.level = level;   }  }   private String end;  private ArrayList<ArrayList<String>> result;  private Map<String, List<String>> nextMap;   public ArrayList<ArrayList<String>> findLadders(String start, String end,    HashSet<String> dict) {   result = new ArrayList<ArrayList<String>>();   this.end = end;    // unvisited words set   Set<String> unVisited = new HashSet<String>();   unVisited.addAll(dict);   unVisited.add(start);   unVisited.remove(end);    // used to record the map info of <word : the words of next level>   nextMap = new HashMap<String, List<String>>();   for (String e : unVisited) {    nextMap.put(e, new ArrayList<String>());   }    // BFS to search from the end to start   Queue<WordWithLevel> queue = new LinkedList<WordWithLevel>();   queue.add(new WordWithLevel(end, 0));   boolean found = false;   int finalLevel = Integer.MAX_VALUE;   int currentLevel = 0;   int preLevel = 0;   Set<String> visitedWordsInThisLevel = new HashSet<String>();   while (!queue.isEmpty()) {    WordWithLevel wordWithLevel = queue.poll();    String word = wordWithLevel.word;    currentLevel = wordWithLevel.level;    if (found && currentLevel > finalLevel) {     break;    }    if (currentLevel > preLevel) {     unVisited.removeAll(visitedWordsInThisLevel);    }    preLevel = currentLevel;    char[] wordCharArray = word.toCharArray();    for (int i = 0; i < word.length(); ++i) {     char originalChar = wordCharArray[i];     boolean foundInThisCycle = false;     for (char c = 'a'; c <= 'z'; ++c) {      wordCharArray[i] = c;      String newWord = new String(wordCharArray);      if (c != originalChar && unVisited.contains(newWord)) {       nextMap.get(newWord).add(word);       if (newWord.equals(start)) {        found = true;        finalLevel = currentLevel;        foundInThisCycle = true;        break;       }       if (visitedWordsInThisLevel.add(newWord)) {        queue.add(new WordWithLevel(newWord,          currentLevel + 1));       }      }     }     if (foundInThisCycle) {      break;     }     wordCharArray[i] = originalChar;    }   }    if (found) {    // dfs to get the paths    ArrayList<String> list = new ArrayList<String>();    list.add(start);    getPaths(start, list, finalLevel + 1);   }   return result;  }   private void getPaths(String currentWord, ArrayList<String> list, int level) {   if (currentWord.equals(end)) {    result.add(new ArrayList<String>(list));   } else if (level > 0) {    List<String> parentsSet = nextMap.get(currentWord);    for (String parent : parentsSet) {     list.add(parent);     getPaths(parent, list, level - 1);     list.remove(list.size() - 1);    }   }  } }

Find Minimum in Rotated Sorted Array II

【题目】

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., might become  ).

Find the minimum element.

The array may contain duplicates.

【解答】解这个题目，先简化一下条件，不考虑duplicates存在的情况，那么任意两个元素都不相等，通过比对num[left]、num[mid]和num[right]会得出三种可能的大小关系组合，用具体例子来说就是：

• num[left]
• num[left]num[right]，比如3 4 5 1 2；
• num[left]>num[mid] && num[mid]

在这之后，再考虑存在duplicates的情况。这样就不容易遗留可能性。另外，需要注意两个特殊情况：

• 一种最特殊的情况是num[left]、num[mid]和num[right]三者全部相等，这个时候就完全不知道这个pivot到底在左半支还是右半支，这时候只能left右移并right左移，一点一点缩小范围。所以最坏情况下时间复杂度是n。
• 还有一个要注意的是，当left和right只相差1的时候，mid==left，如果再走到left=mid赋值的分支里面，就会死循环，为了避免这种情况发生，需要处理好这种情况。

public class Solution {  public int findMin(int[] num) {   int left = 0;   int right = num.length-1;   while (left<right-1) {    int mid = (right+left)/2;    if (num[left]num[mid]) {      return num[left];     } else if (num[right]num[mid]) { // 4 5 1 2 3     if (num[mid]num[right]) {      // impossible      throw new RuntimeException("Impossible...");     } else { // num[mid]==num[right]      right = mid;     }    } else {     if (num[right]==num[mid]) {      left++;      right--;     } else {      left = mid;     }    }   }   return Math.min(num[left], num[right]);  } } 

Regular Expression Matching

【题目】 Implement regular expression matching with support for  '.'  and  '*' .

'.' Matches any single character. '*' Matches zero or more of the preceding element.  The matching should cover the entire input string (not partial).  The function prototype should be: bool isMatch(const char *s, const char *p)  Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true

【解答】点号和星号的含义和正则表达式一致。注意"abc".matches(".*")是返回true的，换言之，".*"可以代表任何字符串，空串也可以。我原来的做法是尝试使用在DP中分类讨论的办法，包括分成"a"、".a"、"a*"、".*”这几种情况分别处理，代码写得冗长，做到一半自己都搞晕了。本来想继续沿着DP的思路走下去，但是看到下面的这个做法（来自于 这里 ）以后，我觉得我原来的思路太弱了。下面这个做法是我目前看到的解法最简洁漂亮的代码，整个过程也不需要用额外的空间来存储重复计算的结果。思路是，把各种情况分成这样两种：

• p的第二个字符（p[1]）不是星号，在这种情况下，如果第一个字符p[0]是星号，或者p[0]==s[0]，那就可以继续递归匹配余下的子串，否则返回匹配失败；
• p的第二个字符（p[1]）是星号，在这种情况下，通过一个i来表示".*"或者"a*"管住的那段S子串的结束位置（即s中的子串[0,i]），i之后的子串和p去掉开头的这个".*"或者”a*"后余下的子串继续参与后续的匹配，匹配上了皆大欢喜，匹配不上则令i前进。

public class Solution {  public boolean isMatch(String s, String p) {   if (p.length() == 0)    return s.length() == 0;   if (p.length() == 1 || p.charAt(1) != '*') {    // empty s or unmatch    if (s.length() < 1 || (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)))     return false;    return isMatch(s.substring(1), p.substring(1));   } else {    int i = -1;    // match    while (i < s.length() && (i < 0 || p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))) {     if (isMatch(s.substring(i + 1), p.substring(2)))      return true;     i++;    }    return false;   }  } }