LeetCode题目解答——第227到310题

LeetCode的题目是不断在更新。还是老规矩，跳过了那些需要付费才能做的题目。下面的解法可能不是最好的，具体问题我们可以讨论。截至目前我解答的全部的LeetCode放在了这里。

Minimum Height Trees

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

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:

Given n = 4 ,  edges = [[1, 0], [1, 2], [1, 3]]

0         |         1        / /       2   3

return [1]

Example 2:

Given n = 6 ,  edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

0  1  2       / | /         3         |         4         |         5

return [3, 4]

【解答】这个题目如果尝试从根部入手，去遍历各个节点成为根的可能性的话，复杂度就很高了。思路需要倒转一下，从叶子入手，即寻找只有一个邻居的节点，这些节点在在满足最小高度树的情况下，显然是叶子节点，然后把这些叶子砍掉，那么最靠近叶子的那些节点会成为叶子节点，继续砍……直到最后剩下的就是根。

public class Solution {  public List<Integer> findMinHeightTrees(int n, int[][] edges) {   List<Integer> leaves = new ArrayList<Integer>();   if (n == 0)    return leaves;   if (n == 1) {    leaves.add(0);    return leaves;   }    Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();   for (int i = 0; i < n; i++)    map.put(i, new HashSet<Integer>());    // dual way   for (int[] pair : edges) {    map.get(pair[0]).add(pair[1]);    map.get(pair[1]).add(pair[0]);   }    // one leaf   for (int i = 0; i < n; i++) {    if (map.get(i).size() == 1)     leaves.add(i);   }    // when n==2, there is only one level, which are the roots of min height   while (n > 2) {    List<Integer> newLeaves = new ArrayList<Integer>();    for (int leaf : leaves) {     for (int neighbor : map.get(leaf)) {      // dechain      map.get(leaf).remove(neighbor);      map.get(neighbor).remove(leaf);      n--;       if (map.get(neighbor).size() == 1)       newLeaves.add(neighbor);     }    }    leaves = newLeaves;   }    return leaves;  } }

Best Time to Buy and Sell Stock with Cooldown

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

prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]

【解答】“Best Time to Buy and Sell Stock”，也算是经典题了。这个题改变的地方在于，设置了一个cooldown的限制。想了好些办法，下面这个我认为最清晰的解答的思路来源于 这篇文章 。

分别建立buy、sell、rest三个数组，长度都为2，分别表示昨天和今天的情况。根据奇数天和偶数天的不同，数组的第0项和第1项分别代表昨天和今天，以及今天和昨天。这个思路其实很巧妙，因为前一天的“今天”就会变成后一天的“昨天”。在循环中根据规则不断更新这三个状态，每次都尝试选取获益最大的策略，下面的代码注释都写得很清楚了。

public class Solution {  public int maxProfit(int[] prices) {   if (null == prices || prices.length <= 1)    return 0;    int[] buy = new int[] { Integer.MIN_VALUE, Integer.MIN_VALUE };   int[] sell = new int[2];   int[] rest = new int[2];    for (int i = 0; i < prices.length; i++) {    int today = i % 2;    int yesterday = 1 - today;     // keeping yesterday's status vs buying today    buy[today] = Math.max(buy[yesterday], rest[yesterday] - prices[i]);     // selling makes profit    sell[today] = buy[yesterday] + prices[i];     // keeping rest status or selling status    rest[today] = Math.max(rest[yesterday], sell[yesterday]);   }    // check the last day's status   int lastDay = (prices.length - 1) % 2;   return Math.max(sell[lastDay], rest[lastDay]);  } }

Range Sum Query – Mutable

【题目】 Given an integer array  nums , find the sum of the elements between indices  i  and  j  ( i  ≤  j ), inclusive.

The  update(i, val)  function modifies  nums  by updating the element at index  i  to  val .

Example:

Given nums = [1, 3, 5]  sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8

Note:

1. The array is only modifiable by the  update  function.
2. You may assume the number of calls to  update  and  sumRange  function is distributed evenly.

【解答】写的代码看起来有点啰嗦，大致思路是线段树。也就是说，每个节点都存放一个sum，这样在求一段区间的和的时候会比较快；而在更新某一个数的时候，也只需要更新整个树从上到下的一条路径即可。

class Node {     Node parent;     Node left;     Node right;     int startIndex;     int endIndex;     int sum; }  public class NumArray {     private Node treeRoot;      public NumArray(int[] nums) {         if (nums!=null && nums.length!=0) {             this.treeRoot = new Node();             buildTree(this.treeRoot, nums, 0, nums.length-1);         }     }      private int buildTree(Node root, int[] nums, int startIndex, int endIndex) {         root.startIndex = startIndex;         root.endIndex = endIndex;                  if (startIndex==endIndex) {             root.sum = nums[startIndex];             return root.sum;         }                  // left: [startIndex, mid], right: [mid+1, endIndex]         int mid = (startIndex+endIndex)/2;                  Node left = new Node();         root.left = left;         int sumLeft = buildTree(left, nums, startIndex, mid);                  Node right = new Node();         root.right = right;         int sumRight = buildTree(right, nums, mid+1, endIndex);                  int sum = sumLeft+sumRight;         root.sum = sum;                  return sum;     }      void update(int i, int val) {         updateTree(i, val, this.treeRoot);     }          private int updateTree(int index, int val, Node root) {         if (root.startIndex==root.endIndex) {             int change = val - root.sum;             root.sum = val;             return change;         }                  int mid = (root.startIndex+root.endIndex)/2;         int change;         if (index<=mid)             change = updateTree(index, val, root.left);         else             change = updateTree(index, val, root.right);                  root.sum += change;                  return change;     }      public int sumRange(int i, int j) {         return sumRangeInTree(i, j, this.treeRoot);     }          private int sumRangeInTree(int i, int j, Node root) {         if (root.startIndex==root.endIndex || (i<=root.startIndex && j>=root.endIndex))             return root.sum;                  int mid = (root.startIndex+root.endIndex)/2;         int sum = 0;         if (i<=mid && j>=root.startIndex)             sum += sumRangeInTree(i, j, root.left);         if (j>=mid+1 && i<=root.endIndex)             sum += sumRangeInTree(i, j, root.right);                      return sum;     } }

Additive Number

【题目】 Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199"  is also an additive number, the additive sequence is:  1, 99, 100, 199 .

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence  cannot have leading zeros, so sequence  1, 2, 03 or  1, 02, 3 is invalid.

Given a string containing only digits '0'-'9' , write a function to determine if it’s an additive number.

【解答】在最开始的两个数定了以后，后面就一路计算和检查下去，看是不是additive number就好了。因此在最开始使用两层for循环去遍历前两个数（整型）的各种可能的组合。

public class Solution {     private int MAX_LEN = String.valueOf(Integer.MAX_VALUE).length();          public boolean isAdditiveNumber(String num) {         for (int i=0; i<MAX_LEN && i<num.length(); i++) {             for (int j=i+1; j-(i+1)<MAX_LEN && j<num.length(); j++) {                 // first number: [0,i], second number: [i+1,j]                                  String firstStr = num.substring(0, i+1);                 if (firstStr.startsWith("0") && firstStr.length()>1)                     continue;                 long first = Long.parseLong(firstStr);                                  String secondStr = num.substring(i+1, j+1);                 if (secondStr.startsWith("0") && secondStr.length()>1)                     continue;                 long second = Long.parseLong(secondStr);                                  if (first > Integer.MAX_VALUE || second > Integer.MAX_VALUE)                     continue;                                  if (isAdditiveNumber(first, second, num.substring(j+1)))                     return true;             }         }                  return false;     }          private boolean isAdditiveNumber(long first, long second, String num) {         long sum = first + second;                  String sumStr = String.valueOf(sum);         if (!num.startsWith(sumStr))             return false;         if (num.equals(sumStr))             return true;                  String rest = num.substring(sumStr.length());         return isAdditiveNumber(second, sum, rest);     } }

Range Sum Query 2D – Immutable

【题目】 Given a 2D matrix  matrix , find the sum of the elements inside the rectangle defined by its upper left corner ( row 1,  col 1) and lower right corner ( row 2,  col 2).

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) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to  sumRegion  function.
3. You may assume that  row 1 ≤  row 2 and  col 1 ≤  col 2.

【解答】这个题是下面《Range Sum Query – Immutable》的演化版本。思路类似，建立一个二维数组：sum[i][j]表示从[0,0]到[i,j]围成的矩形内数的和。

public class NumMatrix {      /**      * sum[i][j]: sum from [0,0] to [i,j]      */     private int[][] sum;      public NumMatrix(int[][] matrix) {         if (null==matrix || matrix.length==0 || matrix[0].length==0) {             sum = new int[][]{};             return;         }                  sum = new int[matrix.length][matrix[0].length];                  for (int i=0; i<matrix.length; i++) {             for (int j=0; j<matrix[0].length; j++) {                 if (i==0) {                     if (j==0)                         sum[i][j] = matrix[0][0];                     else                         sum[i][j] = sum[i][j-1] + matrix[i][j];                 } else {                     if (j==0)                         sum[i][j] = matrix[i][j] + sum[i-1][j];                     else                         sum[i][j] = sum[i-1][j] + sum[i][j-1] + matrix[i][j] - sum[i-1][j-1];                 }             }         }     }      public int sumRegion(int row1, int col1, int row2, int col2) {         int left = 0;         if (col1>0)             left = sum[row2][col1-1];                  int top = 0;         if (row1>0)             top = sum[row1-1][col2];                  int leftTop = 0;         if (row1>0 && col1>0)             leftTop = sum[row1-1][col1-1];                  return sum[row2][col2] - left - top + leftTop;     } }

Range Sum Query – Immutable

【题目】 Given an integer array  nums , find the sum of the elements between indices  i  and  j  ( i  ≤  j ), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]  sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3

Note:

1. You may assume that the array does not change.
2. There are many calls to  sumRange  function.

【解答】题目很简单，使用一个数组，sums[i]表示从头到i这一串数的和。sumRange时间复杂度是常数阶的。

public class NumArray {     private int[] sums;          public NumArray(int[] nums) {         sums = new int[nums.length];         int sum = 0;         for (int i=0; i<nums.length; i++) {             sum += nums[i];             sums[i] = sum;         }     }      public int sumRange(int i, int j) {         int toMinus = 0;         if (i>0)             toMinus = sums[i-1];         return sums[j] - toMinus;     } }

Remove Invalid Parentheses

【题目】 Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and  ) .

Examples:

"()())()" -> ["()()()", "(())()"] "(a)())()" -> ["(a)()()", "(a())()"] ")(" -> [""]

【解答】其实这个题目不难，基本思路就是穷举遍历。先尝试remove零个，再一个，再两个，再三个……每次都调用isValid方法来判定是否valid。

public class Solution {     public List<String> removeInvalidParentheses(String s) {         List<String> list = new ArrayList<>();         Set<String> set = new HashSet<>();         set.add(s);                  while (list.isEmpty()) {             Set<String> newSet = new HashSet<>();             for (String ss : set) {                 if (isValid(ss)) {                     list.add(ss);                     continue;                 }                                  newSet.addAll(removeOneLetter(ss));             }                          set = newSet;         }                  return list;     }          private boolean isValid(String s) {         int count=0;         for (int i=0; i<s.length(); i++) {             char ch = s.charAt(i);             if (ch=='(')                 count++;             else if (ch==')')                 count--;                          if (count<0)                 return false;         }                  return count==0;     }          private Set<String> removeOneLetter(String s) {         Set<String> set = new HashSet<>();         if (s.length()==1) {             set.add("");             return set;         }                  for (int i=0; i<s.length(); i++)             set.add(s.substring(0, i) + s.substring(i+1));                  return set;     } }

Longest Increasing Subsequence

【题目】 Given an unsorted array of integers, find the length of longest increasing subsequence.

Your algorithm should run in O( n 2 ) complexity.

Follow up: Could you improve it to O( n log  n ) time complexity?

【解答】我的方法肯定不是最佳的，因为复杂度是n平方。思路是动态规划，cache[x]表示以nums[x]结尾的串的最长递增子序列的长度。

public class Solution {     public int lengthOfLIS(int[] nums) {         // O(n^2) solution                  if (null==nums || nums.length==0)             return 0;                  // cache[x] means the longest increasing subsequence which is ended with nums[x]         int[] cache = new int[nums.length];         int max = 1;                  for (int i=0; i<nums.length; i++) {             cache[i] = 1;                          for (int j=0; j<=i; j++) {                 // if nums[i] is the last number and nums[j] is the number before the last in the subsequence                 if (nums[i]>nums[j]) {                     cache[i] = Math.max(cache[i], cache[j]+1);                     max = Math.max(max, cache[i]);                 }             }         }                  return max;     } }

Bulls and Cows

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

For example:

Secret number:  "1807" Friend's guess: "7810"

Hint:  1  bull and  3  cows. (The bull is  8 , the cows are  0 ,  1  and  7 .)

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. In the above example, your function should return  "1A3B" .

Please note that both secret number and friend’s guess may contain duplicate digits, for example:

Secret number:  "1123" Friend's guess: "0111"

In this case, the 1st  1  in friend’s guess is a bull, the 2nd or 3rd  1  is a cow, and your function should return  "1A1B" .

You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

【解答】题目不难，使用一个长度为10的数组来存放特定数字的出现次数。

public class Solution {     public String getHint(String secret, String guess) {         int[] map = new int[10];         int A=0, B=0;                  // for A         for (int i=0; i<secret.length(); i++) {             int sn = secret.charAt(i) - '0';             int gn = guess.charAt(i)  - '0';                          if (sn==gn)                 A++;             else                 map[sn]++;         }                  // for B         for (int i=0; i<secret.length(); i++) {             int sn = secret.charAt(i) - '0';             int gn = guess.charAt(i)  - '0';                          if (sn!=gn && map[gn]>0) {                 B++;                 map[gn]--;             }         }                  return A + "A" + B + "B";     } }

Serialize and Deserialize Binary Tree

【题目】 Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

1    / /   2   3      / /     4   5

as  "[1,2,3,null,null,4,5]" , just the same as  how LeetCode OJ serializes a binary tree . You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.  

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

【解答】有很多方法序列化和反序列化。我选择了一种相对比较简单，时间复杂度也能接受的。使用BSF来遍历，并且每一个空的位置使用一个特殊符号来表示（“n”）。

public class Codec {      // Encodes a tree to a single string.     public String serialize(TreeNode root) {         if (root==null)             return "";                  // BSF         List<TreeNode> level = new ArrayList<>();         level.add(root);                  String data = iterateForSerialization(level, "");         return data;     }          private String iterateForSerialization(List<TreeNode> level, String data) {         List<TreeNode> nextLevel = new ArrayList<>();         boolean allNull = true;         String newData = "";         for (TreeNode node : level) {             if (node==null) {                 newData += "n,";             } else {                 allNull = false;                                  newData += node.val + ",";                                  nextLevel.add(node.left);                 nextLevel.add(node.right);             }         }                  if (!allNull) {             data = data + newData;             data = iterateForSerialization(nextLevel, data);         }                  return data;     }      // Decodes your encoded data to tree.     public TreeNode deserialize(String data) {         if (null==data || data.length()==0)             return null;                  String[] vals = data.split(",");         TreeNode root = new TreeNode(Integer.parseInt(vals[0]));         List<TreeNode> level = new ArrayList<>();         level.add(root);                  iterateForDeserialization(vals, 1, level);                  return root;     }          private void iterateForDeserialization(String[] vals, int index, List<TreeNode> level) {         if (vals.length<=index)             return;                  List<TreeNode> nextLevel = new ArrayList<>();         for (TreeNode node : level) {             if ("n".equals(vals[index])) {                 index++;             } else {                 TreeNode left = new TreeNode(Integer.parseInt(vals[index]));                 node.left = left;                                  nextLevel.add(left);                 index++;             }                          if ("n".equals(vals[index])) {                 index++;             } else {                 TreeNode right = new TreeNode(Integer.parseInt(vals[index]));                 node.right = right;                                  nextLevel.add(right);                 index++;             }         }                  iterateForDeserialization(vals, index, nextLevel);     } }

Find Median from Data Stream

【题目】 Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: 

[2,3,4] , the median is  3

[2,3] , the median is  (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) – Add a integer number from the data stream to the data structure.
• double findMedian() – Return the median of all elements so far.

For example:

add(1) add(2) findMedian() -> 1.5 add(3) findMedian() -> 2

【解答】搞两个堆，一个最大堆，一个最小堆。大体的思路就是让最小堆存放所有数据中偏大的那一半，而让最大堆存放所有数据中偏小的那一半。再设置一个median，如果所有数据总数为偶数，这个median就为null，相当于没用，求中位数的时候只需要两个堆的root拿出来求平均即可；如果所有数据总数为奇数，那么这个median就放置中位数。每次添加新数的时候，只需要在最大堆的root、最小堆的root和median这三个数中间比较就好，把最大的放到最小堆去（上半区），把最小的放到最大堆去（下半区）。

这种情况下，findMedian复杂度是常数阶，而addNum则是log(n)。

class MedianFinder {     private Queue<Integer> smallPartHeap = new PriorityQueue<Integer>(10, new Comparator<Integer>(){         @Override         public int compare(Integer left, Integer right) {             return -(new Integer(left).compareTo(right));         }     });     private Queue<Integer> bigPartHeap = new PriorityQueue<Integer>();          /**      * null when even numbers, non-null when odd numbers      */     private Integer median;      // Adds a number into the data structure.     public void addNum(int num) {         if (median==null) {             Integer high = bigPartHeap.poll();             Integer low = smallPartHeap.poll();             if (high==null && low==null) {                 median = num;             } else {                 if (high<num) {                     int temp = num;                     num = high;                     high = temp;                 } else if (num<low) {                     int temp = num;                     num = low;                     low = temp;                 }                                  bigPartHeap.add(high);                 smallPartHeap.add(low);                 median = num;             }         } else {             if (median>num) {                 bigPartHeap.add(median);                 smallPartHeap.add(num);             } else {                 bigPartHeap.add(num);                 smallPartHeap.add(median);             }                          median = null;         }     }      // Returns the median of current data stream     public double findMedian() {         // even         if (median==null) {             Integer high = bigPartHeap.peek();             Integer low = smallPartHeap.peek();                          return ( (double)high + (double)low )/2;         }         // odd         else {             return (double)median;         }     } };

Nim Game

【题目】 You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

【解答】这个其实是个数学问题。

• 如果只有1块石头，你全拿走，赢了；
• 如果只有2块石头，你全拿走，赢了；
• 如果只有3块石头，你全拿走，赢了；
• 如果只有4块石头，你无论拿多少块，对方都可以把剩下的收走，你一定会输；
• 如果有5块石头，如果你拿1块，相当于让对方面对只剩4块石头从头开始拿的问题，那么对方一定会输；
• 如果有6块石头、如果你拿2块，相当于让对方面对只剩4块石头从头开始拿的问题，那么对方一定会输；
• 如果有7块石头、如果你拿3块，相当于让对方面对只剩4块石头从头开始拿的问题，那么对方一定会输；
• 如果有8块石头，无论你怎么拿，对方都可以再拿让问题变成让你面对只剩四块石头从头开始拿的问题，那么你一定会输
• ……

写到这里，问题已经很清楚了，只要石头不是4的倍数，你就能赢。

public class Solution {     public boolean canWinNim(int n) {         return n%4!=0;     } }

Word Pattern

【题目】 Given a  pattern  and a string  str , find if  str  follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in  pattern and a  non-empty word in  str .

Examples:

1. pattern =  "abba" , str =  "dog cat cat dog"  should return true.
2. pattern =  "abba" , str =  "dog cat cat fish"  should return false.
3. pattern =  "aaaa" , str =  "dog cat cat dog"  should return false.
4. pattern =  "abba" , str =  "dog dog dog dog"  should return false.

Notes:

You may assume pattern contains only lowercase letters, and  str contains lowercase letters separated by a single space.

【解答】准备两个map，一个从pattern字符到表示的实际字符串，一个则是反过来。在遍历pattern串的时候，先尝试去寻找以前有没有遇到过，如果遇到过了就很简单，直接校验，要保证和以前所代表的字符串意义一致；如果没有，就要检查当前代表的实际字符是否曾经被别的pattern串所代表。这个过程就是保证pattern字符到实际字符串的一对一匹配，既要充分，又要必要。

public class Solution {     public boolean wordPattern(String pattern, String str) {         if (str.length()==0) {             return pattern.length()==0;         }                  String[] tokens = str.split(" ");         Map<Character, String> patToActual = new HashMap<>();         Map<String, Character> actualToPat = new HashMap<>();         if (pattern.length()!=tokens.length)             return false;                  for (int i=0; i<pattern.length(); i++) {             char pat = pattern.charAt(i);             String actual = patToActual.get(pat);             if (actual==null) {                 if (null!=actualToPat.get(tokens[i]))                     return false;                                  patToActual.put(pat, tokens[i]);                 actualToPat.put(tokens[i], pat);             } else {                 if (!tokens[i].equals(actual))                     return false;             }         }                  return true;     } }

Game of Life

【题目】 According to the  Wikipedia’s article : “The  Game of Life , also known simply as  Life , is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with  m by  n cells, each cell has an initial state  live (1) or  dead (0). Each cell interacts with its  eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up : 

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

【解答】状态转换的问题，把代码逻辑想清楚再写。这类题算法本身不难，也没什么变态case，关键是代码逻辑要规划清楚。

设置了四种状态：1：live，0：dead，-1：live要变成dead（状态变化已经考虑过了，不要重复考虑）和-2：dead要变成live（同前）。第一阶段处理完成以后，1和0都应该已经不存在了。第二阶段再一遍循环把-1变成0，把-2变成1。

public class Solution {     public void gameOfLife(int[][] board) {         if (board==null || board.length==0 || board[0].length==0)             return;                  // 1: live,         // 0: dead,         // -1: live to dead;         // -2: dead to live         for (int i=0; i<board.length; i++) {             for (int j=0; j<board[0].length; j++) {                 int count = countNeighbors(board, i, j);                                  // rule 1                 if (count<2 && board[i][j]==1)                     board[i][j] = -1;                                  // rule 2                                  // rule 3                 else if (count > 3 && board[i][j]==1)                     board[i][j] = -1;                                  // rule 4                 else if (count == 3 && board[i][j]==0)                     board[i][j] = -2;             } // for j         } // for i                  // flip         for (int i=0; i<board.length; i++) {             for (int j=0; j<board[0].length; j++) {                 if (board[i][j]==-1)                     board[i][j] = 0;                 else if (board[i][j]==-2)                     board[i][j] = 1;             }         }     }          private int countNeighbors (int[][] board, int i, int j) {         int count = 0;                  count += isLive(board, i-1, j);         count += isLive(board, i+1, j);         count += isLive(board, i, j-1);         count += isLive(board, i, j+1);         count += isLive(board, i-1, j-1);         count += isLive(board, i+1, j-1);         count += isLive(board, i-1, j+1);         count += isLive(board, i+1, j+1);                  return count;     }          private int isLive (int[][] board, int i, int j) {         if (i<0 || i>=board.length || j<0 || j>=board[0].length)             return 0;                  if (board[i][j]==1 || board[i][j]==-1)             return 1;                  return 0;     } }

Find the Duplicate Number

【题目】 Given an array  nums  containing  n  + 1 integers where each integer is between 1 and  n  (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You  must not  modify the array (assume the array is read only).
2. You must use only constant,  O (1) extra space.
3. Your runtime complexity should be less than  O(n2) .
4. There is only one duplicate number in the array, but it could be repeated more than once.

【解答】我最先想到的是排序（下面代码中注释的部分），排好了自然就清楚了。但是题目要求数组不能变，额外空间还要求O(1)，排序就不行了。还是要充分利用题目中的条件：1~n的数正好各占一坑，但是还多出一个数。

准备左右各一指针，在指针范围内，寻找中间那个数的位置，然后数比这个中间数小的元素个数，正常情况下这个数出来的数应该等于这个中间元素的值，但是也有可能多1，这就说明这个多出来的数在这小的半段，反之则是在大的这半段。反复使用如此的方法最后就可以找到这个多出来的数。

public class Solution {     // public int findDuplicate(int[] nums) {     //     int[] copyNums = nums.clone();     //     Arrays.sort(copyNums);              //     for (int i=0; i<copyNums.length; i++) {     //         if (i!=0 && copyNums[i]==copyNums[i-1])     //             return copyNums[i];     //     }              //     return -1; // unreachable     // }          public int findDuplicate(int[] nums) {         int small = 1, large = nums.length - 1;         while (small < large) {             int mid = small + (large - small) / 2;             // mid is the average or the largest value smaller than average                          int count = 0;             for (int num : nums) {                 if (num <= mid)                     count++;             }              if (count <= mid) // dup is on the second half                 small = mid + 1;             else // dup is on the first half                 large = mid;         }          return small;     } }

Peeking Iterator

【题目】 Given an Iterator class interface with methods:  next()  and  hasNext() , design and implement a PeekingIterator that support the  peek()  operation — it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3] .

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling  next() after that  still return 2.

You call next() the final time and it returns 3, the last element. Calling  hasNext() after that should return false.

【解答】这个问题不难，思路就是要“多取一个数”，把这个数暂存到某个地方，这样调用peek的时候，就可以直接查看这个数返回。注意考虑边界情形。

// Java Iterator interface reference: // https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html class PeekingIterator implements Iterator<Integer> {     private Iterator<Integer> iterator = null;     private Integer current = null;       public PeekingIterator(Iterator<Integer> iterator) {      this.iterator = iterator;      if (iterator.hasNext())          this.current = iterator.next();  }      // Returns the next element in the iteration without advancing the iterator.  public Integer peek() {         return current;  }   // hasNext() and next() should behave the same as in the Iterator interface.  // Override them if needed.  @Override  public Integer next() {      Integer result = this.current;      if (iterator.hasNext())          this.current = iterator.next();      else          this.current = null;            return result;  }   @Override  public boolean hasNext() {      // actually there's a bug here, if there's a null element, hasNext returns false but it should not      return this.current != null;  } }

Move Zeroes

【题目】 Given an array  nums , write a function to move all  0 ‘s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12] , after calling your function,  nums should be  [1, 3, 12, 0, 0] .

Note :

1. You must do this  in-place  without making a copy of the array.
2. Minimize the total number of operations.

【解答】这个问题比较简单，swap大法就好了。从前往后，双指针，一个（left）只在发生交换以后才前进，另一个（right）指向待考察元素，每次都单步加一往后走。当right指向的数不为零的时候，就让它和left指向的数交换。这样就保证不为零的数尽可能地往前放，那零就放在尾部了。

public class Solution {     public void moveZeroes(int[] nums) {         if (nums==null || nums.length==0)             return;                  int left=0, right=0;         while (right<nums.length) {             if (nums[right] != 0) {                 swap(nums, left, right);                 left++;             }                          right++;         }     }          private void swap(int[] nums, int left, int right) {         if (left==right)             return;                  nums[left] ^= nums[right];         nums[right] ^= nums[left];         nums[left] ^= nums[right];     } }

Expression Add Operators

【题目】 Given a string that contains only digits  0-9  and a target value, return all possibilities to add  binary  operators (not unary)  + ,  - , or  *  between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> []

【解答】原则上好像没有什么特别简约的办法，还是需要遍历各种可能性。下面这个方法的思路是从讨论区里面借鉴而来的，也是我认为比较清晰简洁的。每次得到一个字符串的时候，遍历所有可以添加符号的位置并添加符号，加减最好处理，但是乘法需要先复原前面多算了的加法（如果是减法则是看作加上了一个负数，因此还是加法），以保证乘法的高优先级。

有没有不需要添加符号的情况？有，比如一进来就比较result是不是等于target，如果相等，而且余下要处理的num为空，就不用往下进行了。

注意两点，一个是溢出的可能，要使用long型；一个是要过滤掉leading zero的数。

public class Solution {     public List<String> addOperators(String num, int target) {         List<String> list = new ArrayList<>();         eval(num, (long) target, "", 0, 0, list);          return list;     }      private void eval(String num, long target, String item, long result, long prev, List<String> list) {         // hit         if (result == target && num.length() == 0) {             list.add(item);             return;         }          for (int i = 1; i <= num.length(); i++) {             String val = num.substring(0, i);             // leading 0             if (val.startsWith("0") && val.length() > 1)                 return;              long current = Long.parseLong(val);             String next = num.substring(i);              // not the leading number             if (item.length() != 0) {                 eval(next, target, item + '+' + current, result + current, current, list);                 eval(next, target, item + '-' + current, result - current, -current, list);                 eval(next, target, item + '*' + current, (result - prev) + prev * current, prev * current, list);             } else {                 eval(next, target, val, current, current, list);             }          }     } }

Perfect Squares

【题目】 Given a positive integer  n , find the least number of perfect square numbers (for example,  1, 4, 9, 16, ... ) which sum to  n .

For example, given n =  12 , return  3 because  12 = 4 + 4 + 4 ; given  n =  13 , return  2 because  13 = 4 + 9 .

【解答】使用一个cache数组：cache[i]表示数i可以最少拆成多少个平方数之和。有了这一条思路以后，就一马平川了。

public class Solution {     public int numSquares(int n) {         if (n<0)             return -1;         if (n==0)             return 0;                  Integer[] cache = new Integer[n+1];         cache[0] = 0;                  for (int i=1; i<=n; i++) {             for (int j=1; Math.pow(j,2)<=i; j++) {                 int times = cache[i-(int)(Math.pow(j,2))] + 1;                 if (cache[i]==null)                     cache[i] = times;                 else                     cache[i] = Math.min(times, cache[i]);             }         }                  return cache[n];     } }

First Bad Version

【题目】 You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions  [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether  version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

【解答】一看就知道大概是要用二分法来找这个位置，但是这里有个陷阱，就是在n为最大整型数的时候，left+right会溢出，所以引入long型来解决这个问题。

public class Solution extends VersionControl {     public int firstBadVersion(int n) {         long left = 1, right = n;         while (left<right) {             long middle = (right + left) / 2;             if (super.isBadVersion((int)middle))                 right = middle;             else                 left = middle + 1;         }                  return (int)right;     } }

H-Index II

【题目】 Follow up  for  H-Index : What if the  citations  array is sorted in ascending order? Could you optimize your algorithm?

【解答】能否优化的问题。可以利用有序性下的二分查找把时间复杂度降到log(n)。

public class Solution {     public int hIndex(int[] citations) {         if (citations==null || citations.length==0)             return 0;                  int left=0, right=citations.length-1;         // using left+1 rather than left to avoid indefinite loop         while (left+1 < right) {             int mid = (left+right)/2;             if (citations[mid] >= citations.length-mid) {                 right = mid;             } else {                 left = mid;             }         }                  // right itself doesn't satisfy the requirement         if (citations[right] < citations.length-right)             return 0;                      // special case, left satisfy the requirement         if (citations[left] >= citations.length-left)             right = left;                  return citations.length-right;     } }

H-Index

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

For example, given citations = [3, 0, 6, 1, 5] , which 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, his h-index is  3 .

Note : If there are several possible values for  h , the maximum one is taken as the h-index.

【解答】我偷了个懒，排序一下，然后就从地位开始遍历，一旦发现不符题意的，就跳出。

public class Solution {     public int hIndex(int[] citations) {         Arrays.sort(citations);                  int i=0;         for (; i<citations.length; i++) {             if (citations[citations.length-i-1] < i+1)                 break;         }                  return i;     } }

Integer to English Words

【题目】 Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2 31  - 1.

For example,

123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand Three Hundred Forty Five" 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

【解答】这种就是“坑题”，题目看着没啥难度，但是要一遍做对很难。无非就是各种case。思路和特殊情况如下：

• 由低位到高位，三位三位地划分，这样会比较好处理。
• 空格的处理要注意，很多地方需要trim。
• “零”的情况的处理。

// a lot of "trim" public class Solution {     private final String[] DIGITS = new String[]{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine",         "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};     private final String[] DECADES = new String[]{null, null, "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};     private final String[] UNITS = new String[]{"", "Thousand", "Million", "Billion"};          public String numberToWords(int num) {         String result = "";                  for (int i=0; i<UNITS.length; i++) {             int threeDigits = num%1000;             num = num/1000;             if (threeDigits!=0)                 result = threeDigitsToWords(threeDigits, UNITS[i]).trim() + " " + result.trim();                          if (num==0)                 break;         }                  if ("".equals(result))             result = "Zero";                  return result.trim();     }          private String threeDigitsToWords(int threeDigits, String unit) {         String result = "";                  int twoDigits = threeDigits%100;         if (twoDigits!=0) {             if (twoDigits<20)                 result = DIGITS[twoDigits];             else                 result = DECADES[twoDigits/10] + " " + DIGITS[twoDigits%10];         }                  int hundred = threeDigits/100;         if (hundred!=0) {             result = DIGITS[hundred] + " Hundred " + result.trim();         }                  return result.trim() + " " + unit;     } }

Missing Number

【题目】 Given an array containing  n  distinct numbers taken from  0, 1, 2, ..., n , find the one that is missing from the array.

【解答】大致是思路就是数组的原地调整，“swap大法”，这个方法很典型，也很常用。

遍历的时候，没到一个位置，就把当前这个位置上的当前值放到它该去的地方，比如2,1,3，第一个位置下标是0，元素是2，那么它该去这个数组的末尾，因此第一次swap发生，变成了：3,1,2。这样数组的元素全部过一遍以后，可以保证大部分元素都呆到了它该呆的位置，除了元素n，这个数特别，是最大的一个，没地方呆，要单独创建一个变量n来放置它。这一遍过完数组以后，再过一遍数组，检查每一个位置，如果array[i]!=i的话，说明这个位置的元素就是丢失的那个。

public class Solution {     public int missingNumber(int[] nums) {         int n = -1;         int temp = 0, pos = 0;                  for (int i=0; i<nums.length;) {             if (nums[i]==i || nums[i]==-1) {                 i++;                 continue;             } else if (nums[i]==nums.length) {                 // swap                 temp = n;                 n = nums.length;                 nums[i] = temp;             } else {                 // swap                 pos = nums[i];                 temp = nums[pos];                 nums[pos] = pos;                 nums[i] = temp;             }         }                  if (n==-1)             return nums.length;         for (int i=0; i<nums.length; i++) {             if (nums[i]==-1)                 return i;         }                  // unreachable         return -1;     } }

Ugly Number II

【题目】 Write a program to find the  n -th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5 . For example,  1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first  10 ugly numbers.

Note that 1 is typically treated as an ugly number.

【解答】下面这个解答很清楚，是来自于LeetCode的一个 讨论帖 。基本原理就像是找第N个质数一样，填表法。但是填表也有技巧。a、b、c分别用来表示用来乘以2、3、5的三趟序列的下标，最开始都是0，每次都找这三个位置最小的一个元素作为整个Ugly Number序列的下一个。而a、b、c都是一点一点增加的，因此不会错过任何一个符合要求的元素。

public class Solution {     /**      * https://leetcode.com/discuss/55304/java-easy-understand-o-n-solution      *      * a, b, c stands for the next number to multiply 2 or 3 or 5 respectively      * for example, c always stands for the index of number series starting from 1 and each element will multiply 5:      * 1,      * 1*5,      * 2*5,      * 3*5,      * 4*5,      * 5*5,      * 6*5,      * 8*5,      * 9*5      * ...      *      */     public int nthUglyNumber(int n) {         if (n<=0) return 0;         int a=0,b=0,c=0;         List<Integer> table = new ArrayList<Integer>();         table.add(1);         while (table.size()<n) {             int next_val = Math.min(table.get(a)*2,Math.min(table.get(b)*3,table.get(c)*5));             table.add(next_val);             if (table.get(a)*2==next_val) a++;             if (table.get(b)*3==next_val) b++;             if (table.get(c)*5==next_val) c++;         }         return table.get(table.size()-1);     } }

Ugly Number

【题目】 Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5 . For example,  6, 8 are ugly while  14 is not ugly since it includes another prime factor  7 .

Note that 1 is typically treated as an ugly number.

【解答】不断地去尝试除以2、3、5，如果发现都无法整除，而且还比1大，那么显然就含有非2、3、5的因子，这就是Ugly Number。

public class Solution {     public boolean isUgly(int num) {         if (num<=0)             return false;                      while (num!=1) {             if (num%2==0)                 num = num/2;             else if (num%3==0)                 num = num/3;             else if (num%5==0)                 num = num/5;             else                 return false;         }                  return true;     } }

Single Number III

【题目】 Given an array of numbers  nums , in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5] , return  [3, 5] .

Note :

1. The order of the result is not important. So in the above example,  [5, 3]  is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

【解答】如果是只有一个数只出现一次，那可以用异或大法来解决，但是现在有两个数，就要动点脑筋了。

• 首先，使用异或大法可以找得到这两个数异或以后的值（非零），这个值取名为xor；
• 其次，假如说我们有一个掩码mask，能够给数分类，让每个数都去和这个掩码进行与操作，得出两种结果（两个组），并且，使得这两个特殊的数，分别落在这两种结果里面，那么，就可以对么个group分别进行异或大法来得出结果了。

现在来考虑一下怎么构造这个掩码。

看前面说的那个值xor，如果xor大于0，说明符号位是0，那么这两个特殊的数是同号的；反之则是异号的：

• 先考虑异号的情况，这种情况最好处理，我只要令掩码为Integer.MIN_VALUE，即“负零”——符号位为1，其它位都为0，那么，我肯定可以保证两个异号的数去与这个掩码的时候，会落到不同的结果里面——负数与上掩码会得到Integer.MIN_VALUE，而正数或零与上掩码会得到0；
• 在考虑同号的情况，这种情况要动点小脑筋：不断拿xor去除以2，直到发现除不尽位置，这个时候说明在第i位上是1，也就是说在这一位上面这两个数是不同的，那么就构造一个每一位上全为0，但是第i位上为1的数作为掩码，这个掩码可以保证在和那两个数分别进行与运算的时候，会得到不同的结果，一个是0，一个不为0（第i位上为1）。

好了，有了这个掩码，就可以把两个数分别扔到两个组里，再对每个组内部使用异或大法，就能得出每个组内特殊的那个数，这两个组的特殊数合起来就是所求。这个题目还是很有意思的。

public class Solution {     public int[] singleNumber(int[] nums) {         if (nums==null || nums.length==0)             return new int[]{};         if(nums.length==1)             return new int[]{ nums[0] };                  // get the xor result of the two single numbers         int xor = 0;         for (int num : nums)             xor ^= num;                  // divide the numbers into two groups, get the mask to calculate which group will each number be put in         int mask = 0;         if (xor==0) {             return new int[]{};         } else if (xor>0) {             for (int i=1; i<32; i++) {                 int remainder = xor%2;                 if (remainder>0) {                     mask = 1 << (i-1);                     break;                 }                                  xor = xor/2;             }         } else {             mask = Integer.MIN_VALUE;         }                  // num1 is the xor result for group 1, and num2 is for group2         int num1 = 0;         int num2 = 0;         for (int num : nums) {             int group = num & mask;             if (group==0)                 num1 ^= num;             else                 num2 ^= num;         }                  return new int[]{num1, num2};     } }

Add Digits

【题目】 Given a non-negative integer  num , repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38 , the process is like:  3 + 8 = 11 ,  1 + 1 = 2 . Since  2 has only one digit, return it.

【解答】公式在 维基百科页面 这里。

public class Solution {     public int addDigits(int num) {         //https://en.wikipedia.org/wiki/Digital_root         return 1 + (num-1)%9;     } }

Binary Tree Paths

【题目】 Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1  /   / 2     3  /   5

All root-to-leaf paths are:

["1->2->5", "1->3"]

【解答】递归遍历就可以，每个节点都把左子树和右子树的递归结果merge起来。

public class Solution {     public List<String> binaryTreePaths(TreeNode root) {         List<String> result = new ArrayList<>();         if (null==root)             return result;                  result.add("");         return traverse(root, result);     }          private List<String> traverse(TreeNode root, List<String> list) {         List<String> newList = new ArrayList<>();         for (String item : list) {             if ("".equals(item))                 item = root.val + "";             else                 item += "->" + root.val;                          newList.add(item);         }                  if (root.left==null && root.right==null)             return newList;                  List<String> result = new ArrayList<>();         if (root.left!=null)             result.addAll(traverse(root.left, newList));         if (root.right!=null)             result.addAll(traverse(root.right, newList));                      return result;     } }

Valid Anagram

【题目】 Given two strings  s  and  t , write a function to determine if  t  is an anagram of  s .

【解答】因为只需要考虑小写字母，那就使用数组就好了，记录每个字母出现的次数。

public class Solution {     public boolean isAnagram(String s, String t) {         int[] count = new int[26];                  for (int i=0; i<s.length(); i++) {             char ch = s.charAt(i);             count[ch-'a']++;         }                  for (int i=0; i<t.length(); i++) {             char ch = t.charAt(i);             count[ch-'a']--;         }                  for (int i=0; i<26; i++) {             if (count[i]!=0)                 return false;         }                  return true;     } }

Different Ways to Add Parentheses

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

((2-1)-1) = 0 (2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

【解答】每次对input的字符遍历的时候，只要遇到符号，就依据它把input切成左半边和右半边，左右半边各递归求解，再把左右解集合放一起进行运算。需要考虑特殊情况，如果input不包含符号，就是一个纯数。

public class Solution {     private static List<Character> OPERATORS = new ArrayList<>();     static {         OPERATORS.add('+');         OPERATORS.add('-');         OPERATORS.add('*');     }          public List<Integer> diffWaysToCompute(String input) {         List<Integer> list = new ArrayList<>();         if (input==null || input.length()==0)             return list;                      for (int i=0; i<input.length(); i++) {             char ch = input.charAt(i);             if (OPERATORS.contains(ch)) {                 List<Integer> lefts = diffWaysToCompute(input.substring(0, i));                 List<Integer> rights = diffWaysToCompute(input.substring(i+1));                                  for (int left : lefts) {                     for (int right : rights) {                         if (ch=='+')                             list.add(left+right);                         else if(ch=='-')                             list.add(left-right);                         else                             list.add(left*right);                     }                 }                              }         }                  // this is a pure number         if (list.isEmpty())             list.add(Integer.parseInt(input));                      return list;     } }

Search a 2D Matrix II

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

For 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 .

【解答】大致思路是从左上角开始蔓延查找，因为从上到下和从左到右都是依次增大的，因此这个方向可以由每一步和当前数的比较来获知。另外，需要使用一个状态map来记录这个位置是不是来过了。开始我写了一个方法使用递归查找，但是超时了：

private boolean search(int[][] matrix, int target, int i, int j, boolean[][] visited) {     if (i<0 || i>=matrix.length || j<0 || j>=matrix[0].length || visited[i][j])         return false;       if (matrix[i][j]==target)         return true;       if (matrix[i][j]>target) {         visited[i][j] = true;         return false;     }       return search(matrix, target, i+1, j, visited) || search(matrix, target, i, j+1, visited); }

于是使用循环，使用一个栈来记录路径，使得走不通往回退的时候能找到位置：

class Node {     int i;     int j;          public Node(int i, int j) {         this.i = i;         this.j = j;     } } public class Solution {     public boolean searchMatrix(int[][] matrix, int target) {         if (matrix==null || matrix.length==0 || matrix[0].length==0)             return false;                      Stack<Node> stack = new Stack<>();         boolean visited[][] = new boolean[matrix.length][matrix[0].length];         int i=0, j=0;         while (true) {             if (matrix[i][j]==target)                 return true;                          if (matrix[i][j]>target) {                 visited[i][j] = true;                              if (!stack.isEmpty()) {                     Node back = stack.pop();                                          i = back.i;                     j = back.j;                                          continue;                 } else {                     return false;                 }             }                          // matrix[i][j] < target             if (i+1<matrix.length && !visited[i+1][j]) {                 stack.push(new Node(i, j));                                  i++;                 continue;             } else if (j+1<matrix[0].length && !visited[i][j+1]) {                 stack.push(new Node(i, j));                                  j++;                 continue;             } else {                 visited[i][j] = true;                                  if (!stack.isEmpty()) {                     Node back = stack.pop();                                          i = back.i;                     j = back.j;                                          continue;                 } else {                     return false;                 }             }                      } // while     } }

Sliding Window Maximum

【题目】 Given an array  nums , there is a sliding window of size  k  which is moving from the very left of the array to the very right. You can only see the  k  numbers in the window. Each time the sliding window moves right by one position.

Window position                Max ---------------               ----- [1  3  -1] -3  5  3  6  7       3  1 [3  -1  -3] 5  3  6  7       3  1  3 [-1  -3  5] 3  6  7       5  1  3  -1 [-3  5  3] 6  7       5  1  3  -1  -3 [5  3  6] 7       6  1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7] .

【解答】滑动窗口内求最大值。解法有几个，但是要求线性时间复杂度的话，引入一个双端队列deque来表示这个窗口内的元素。从deque头部（题中窗口的右侧）进元素，从deque的尾部（题中窗口的左侧）出元素。出元素比较简单，但是进元素需要保持deque始终递减：

为什么要保持递减？

• 因为如果出现递增，假设deque[i] < deque[i+1]，在求窗口最大值的时候，这里的deque[i]就成了废物，因为从这个递增出现开始，无论串口往右移动多少格，deque[i+1]的存在一定会令deque[i]无法成为最大值；
• 反之，递减的情况下，如果deque[i] > deque[i+1]，那么虽然deque[i+1]小，通常情况下无法成为最大值，但是存在这样一种可能，当窗口右移到某个位置的时候，deque[i]已经因为位置的关系被迫移出窗口，那么deque[I+1]就可能成为新窗口的最大值。

理解这一点是关键。

class Item {     public int index;     public int value;     public Item(int index, int value) {         this.index = index;         this.value = value;     } }  public class Solution {     public int[] maxSlidingWindow(int[] nums, int k) {         if (k==0)             return new int[]{};                  Deque<Item> deque = new LinkedList<>();         for (int i=0; i<k; i++) {             // keep it descending             while (!deque.isEmpty()) {                 if (deque.getLast().value <= nums[i])                     deque.removeLast();                 else                     break;             }                              deque.add(new Item(i, nums[i]));         }                  List<Integer> maxList = new ArrayList<>();         maxList.add(deque.getFirst().value);                  for (int i=k; i<nums.length; i++) {             int max = move(deque, nums, i, k);             maxList.add(max);         }                  int[] rets = new int[maxList.size()];         for (int i=0; i<rets.length; i++) {             rets[i] = maxList.get(i);         }                  return rets;     }          private int move(Deque<Item> deque, int[] nums, int i, int k) {         if (deque.getFirst().index == i-k)             deque.removeFirst();                  while (!deque.isEmpty()) {             if (deque.getLast().value <= nums[i])                 deque.removeLast();             else                 break;         }                  deque.add(new Item(i, nums[i]));                  return deque.getFirst().value;     } }

Product of Array Except Self

【题目】 Given an array of  n  integers where  n  > 1,  nums , return an array  output  such that  output[i]  is equal to the product of all the elements of  nums  except  nums[i] .

Solve it without division and in O( n ).

For example, given [1,2,3,4] , return  [24,12,8,6] .

【解答】算出的数组要求，第i个等于原数组除去第i个元素以外全部的乘积。很容易想到的一点就是，我可以拿个数存放所有数的乘积，然后要求第i个结果的时候，拿这个乘积除以nums[i]就好。但是需要考虑两个特殊情况：

• 乘积可能溢出；
• 除以0的情况。

public class Solution {     public int[] productExceptSelf(int[] nums) {         int[] ret = new int[nums.length];          long product = 1;         Integer zeroPos = null;         for (int i=0; i<nums.length; i++) {             if (nums[i]==0) {                 if (zeroPos!=null) {                     return ret;                 } else {                     zeroPos = i;                     continue;                 }             }                          product *= nums[i];         }                  if (zeroPos!=null) {             ret[zeroPos] = (int)(product);             return ret;         }                  for (int i=0; i<nums.length; i++) {             ret[i] = (int)(product/nums[i]);         }         return ret;     } }

Delete Node in a Linked List

【题目】 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value  3 , the linked list should become  1 -> 2 -> 4 after calling your function.

【解答】这个没啥好说的：

public class Solution {     public void deleteNode(ListNode node) {         node.val = node.next.val;         node.next = node.next.next;     } }

Lowest Common Ancestor of a Binary Tree

【题目】 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 v and w as the lowest node in T that has both v and w as descendants (where we allow  a node to be a descendant of itself ).”

_______3______        /              /     ___5__          ___1__    /      /        /      /    6      _2       0       8          /  /          7   4

For example, the lowest common ancestor (LCA) of nodes 5 and  1 is  3 . Another example is LCA of nodes  5 and  4 is  5 , since a node can be a descendant of itself according to the LCA definition.

【解答】找二叉树的最小共同祖先。思路就是判断当前root的left和right是不是p或者q的祖先，如果left和right分别是p和q，或者是q和p的祖先，那么显然p和q分布在两侧，最小共同祖先就是root；如果p和q分布在同侧，比如左侧，那么返回之前递归检查左侧分支的结果。也就是说，说是找祖先，其实是利用递归找从祖先开始，分别延伸到p和q的路径。

public class Solution {     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {         if (root==null || p==null || q==null)             return null;                  if (p==root || q==root)             return root;                  TreeNode left = lowestCommonAncestor(root.left, p, q);         TreeNode right = lowestCommonAncestor(root.right, p, q);                  if (left!=null && right!=null)             return root;         else if (left!=null)             return left;         else if (right!=null)             return right;         else             return null;     } }

Lowest Common Ancestor of a Binary Search Tree

【题目】 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia : “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow  a node to be a descendant of itself ).”

_______6______        /              /     ___2__          ___8__    /      /        /      /    0      _4       7       9          /  /          3   5

For example, the lowest common ancestor (LCA) of nodes 2 and  8 is  6 . Another example is LCA of nodes  2 and  4 is  2 , since a node can be a descendant of itself according to the LCA definition.

【解答】二叉搜索树的最小共同祖先，比二叉树条件更强。从root开始，考虑三种情形：

• 自己就是p或q；
• p和q一个比自己大，一个比自己小，那么自己就是最小共同祖先；
• p和q都比自己大，或者都比自己小，利用二叉搜索树的特性，递归判断左右两个分支。

public class Solution {     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {         if (p==root)             return p;         if (q==root)             return q;                  if (p.val<root.val && q.val<root.val)             return lowestCommonAncestor(root.left, p, q);                      if (p.val>root.val && q.val>root.val)             return lowestCommonAncestor(root.right, p, q);                  return root;     } }

Palindrome Linked List

【题目】 Given a singly linked list, determine if it is a palindrome.

【解答】要在O(n)时间复杂度内，还要常量空间复杂度内完成，基本思路就是，找到整个链表的中点，然后把后半截反转，这样的话就可以从中间往两边逐个节点比较了。这个思路其实有一定代表性。

public class Solution {     public boolean isPalindrome(ListNode head) {         if (head==null || head.next==null)             return true;                  int count = 0;         ListNode n = head;         while (n!=null) {             count++;             n = n.next;         }                  int mid = count/2;         ListNode tail = null;         if (count%2==0) { // even             count = 1;             n = head;             while (count<mid) {                 n = n.next;                 count++;             }                          if (n!=null)                 tail = reverse(n.next);         } else { // odd             count = 1;             n = head;             while (count<=mid) {                 n = n.next;                 count++;             }                          if (n!=null)                 tail = reverse(n.next);         }                  count = 1;         while (count<=mid) {             if (head.val!=tail.val)                 return false;                              head = head.next;             tail = tail.next;                          count++;         }                  return true;     }          private ListNode reverse(ListNode head) {         if (head.next==null)             return head;                  ListNode last = null;         ListNode first = head;         ListNode second = first.next;         while (second.next!=null) {             first.next = last;                          ListNode newSecond = second.next;             second.next = first;                          last = first;             first = second;             second = newSecond;         }                  second.next = first;         first.next = last;                  return second;     } }

Number of Digit One

【题目】 Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

【解答】题目看起来似乎不难，不就是有策略地数数嘛，但是做起来还挺难的。下面这个解法最初来自 这里 ，我写成了自己便于理解的版本：

public class Solution {   public int countDigitOne(int n) {     if (n <= 0)       return 0;     if (n < 10)       return 1;      // example: 2077     int length = String.valueOf(n).length(); // 4     int base = (int) (Math.pow(10, length - 1)); // 1000     int coefficient = n / base; // 2     int remainder = n % base; // 77          // part 1     int highest; // total highest digit one count     if (coefficient == 1)       highest = n - base + 1;     else       highest = base;          // part 2     int lower = countDigitOne(base - 1); // 0~999     lower = lower * coefficient; // 0~1999          // part 3     int rest = countDigitOne(remainder); // 77      return lower + highest + rest;   } }

基本思路是这样的，对于任意n，比如2077，求解可以分成三个部分：

• part 1：最高位（千位）的1的个数，为1000，分别来自1000到1999这1000个数的千位；
• part 2：0~999的递归求解，得到的结果，再乘以系数2，就得到了从0~1999的全部解答；
• part 3：余下从2000到2077中，千位的1已经计算，余下的出现1的数量，递归求解。

Implement Queue using Stacks

【题目】 Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Notes:

• You must use  only  standard operations of a stack — which means only  push to top ,  peek/pop from top ,  size , and  is empty  operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

【解答】要拿栈来实现队列。基本思路就是准备两个栈，无论是push还是pop，都需要把栈反转。因此需要两个栈互相倒腾。

class MyQueue {     private Stack<Integer> head = new Stack<>();     private Stack<Integer> tail = new Stack<>();          // Push element x to the back of queue.     public void push(int x) {         if (!head.isEmpty()) {             while (!head.isEmpty()) {                 tail.push(head.pop());             }         }                  tail.push(x);     }      // Removes the element from in front of queue.     public void pop() {         if (head.isEmpty()) {             while (!tail.isEmpty()) {                 head.push(tail.pop());             }         }                  head.pop();     }      // Get the front element.     public int peek() {         if (head.isEmpty()) {             while (!tail.isEmpty()) {                 head.push(tail.pop());             }         }                  return head.peek();     }      // Return whether the queue is empty.     public boolean empty() {         return head.isEmpty() && tail.isEmpty();     } }

Power of Two

【题目】 Given an integer, write a function to determine if it is a power of two.

【解答】不断除以二就好：

public class Solution {     public boolean isPowerOfTwo(int n) {         if (n<=0)             return false;                  while (n!=1) {             if (n%2>0)                 return false;             n = n/2;         }                  return true;     } }

Kth Smallest Element in a BST

【题目】 Given a binary search tree, write a function  kthSmallest  to find the  k th smallest element in it.

【解答】思路就是利用二叉搜索树的特性，从小到大遍历，找到第k个的时候抛出带有所求值的异常：

class KthSmallestFoundException extends RuntimeException {     public KthSmallestFoundException(int val) {         super();         this.val = val;     }     int val; } public class Solution {     public int kthSmallest(TreeNode root, int k) {         try {             traverse(root, k, 0);         } catch(KthSmallestFoundException e) {             return e.val;         }                  return 0; // unreachable     }               private int traverse(TreeNode root, int k, int accu) {         if (null==root)             return accu;                  accu = traverse(root.left, k, accu);         accu ++; // the root                  if (accu==k)             throw new KthSmallestFoundException(root.val);                  return traverse(root.right, k, accu);     } }

Majority Element II

【题目】 Given an integer array of size  n , find all elements that appear more than  ⌊ n/3 ⌋  times. The algorithm should run in linear time and in O(1) space.

【解答】题目很短，但是做起来并不容易，因为要求线性复杂度，还要求O(1)的空间复杂度。

这道题我纠结了很久，思路大致靠谱，但是最后还是参考了一个解法才解出来，原因就在于我尝试一遍循环搞定，这就走入不归路了——线性复杂度，需要两遍循环。大致思路如下：

• 假设自己两只手，每只手要么空着，要么只拿一种牌（数）。
• 第一遍循环：来一张牌的时候，如果有一只手空着，或者已经有一只手有这种牌了，就把那张牌放手里；
• 否则，左右手各丢任意一张牌。
• 到最后，左右手剩下的牌就是满足条件的那两种。
• 再来一遍循环统计这两者分别有多少张就好了。

public class Solution {   public List<Integer> majorityElement(int[] nums) {     int count1 = 0, count2 = 0;     int num1 = 0, num2 = 0;      // get the most two numbers     for (int num : nums) {       if (count1 == 0 || num == num1) {         count1++;         num1 = num;       } else if (count2 == 0 || num == num2) {         count2++;         num2 = num;       } else {         count1--;         count2--;       }     }      // count how many the most two numbers are     count1 = 0;     count2 = 0;     for (int n : nums) {       if (n == num1)         count1++;       else if (n == num2)         count2++;     }      List<Integer> result = new ArrayList<Integer>();     if (count1 > nums.length / 3)       result.add(num1);     if (count2 > nums.length / 3)       result.add(num2);          return result;   } }

Summary Ranges

【题目】 Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7] , return  ["0->2","4->5","7"].

【解答】题目不难。在遍历的过程中需要三个变量，num表示当前数，prev表示前一个数，start表示出现range的时候，range的起始位置。循环结束后，如果还有没有处理的range，不要遗漏。

注意，如果使用Integer的话，不要直接和int/Integer比较，要转成int以后再比。

代码如下：

public class Solution {     public List<String> summaryRanges(int[] nums) {         List<String> list = new ArrayList<>();         if (null==nums)             return list;                  Integer prev = null;         Integer start = null;                  for (int num : nums) {             if (prev==null) {                 prev = num;                 start = num;             }             else if (prev.intValue()+1==num) {                 prev = num;             }             else {                 // don't use prev==start !!                 if (prev.intValue()==start.intValue())                     list.add(start + "");                 else                     list.add(start + "->" + prev);                                  prev = num;                 start = num;             }         }                  if (prev!=null) {             // don't use prev==start !!             if (prev.intValue()==start.intValue())                 list.add(start + "");             else                 list.add(start + "->" + prev);         }                  return list;     } }

Basic Calculator II

【题目】 Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers,  + ,  - ,  * ,  / operators and empty spaces  . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5

Note: Do not use the  eval built-in library function.

【解答】和Basic Calculator相比，这里没有括号的出现，这样栈就可以不用了，但是依然需要处理优先级的问题。因此我定义变量num1、num2，符号op1、op2，在计算的过程中，最多还会涉及到临时变量num，他们之间具备如下关系：

• 遍历的过程中，如果遇到数字才考虑计算，如果遇到加减乘除的符号，只储存下来。如果遇到符号就开始考虑计算就会搞得很复杂。
• 如果某次出现加减法，num1和num2就是用来存放这样两个数的，为什么不直接计算？因为考虑到它的优先级比乘除法低，所以先放着，不计算，而op1就是用来存放加号或者减号的。如果出现连续加减法，那就需要计算，但是最后一步加减法不要算。比如3+2-3*4，就把3+2-3计算成为5-3，num1为5，num2为3，op1为减号。
• 如果某次出现乘除法，就直接计算。
• 循环结束后，如果还有余下的加减法没有计算，不要遗漏。

public class Solution {     public int calculate(String s) {         int i=0;         char op1 = 0;         char op2 = 0;         Integer num1 = null;         Integer num2 = null;                  // num1 (op1) num2 (op2) num         while (i<s.length()) {             char ch = s.charAt(i);                          // number             if (ch>='0' && ch<='9') {                 int j = i+1;                 while (true) {                     if (j==s.length())                         break;                                          char chDigit = s.charAt(j);                     if (chDigit>='0' && chDigit<='9')                         j++;                     else                         break;                 }                 int num = Integer.parseInt(s.substring(i, j));                                  if (num1==null) {                     num1 = num;                 } else if (num2==null) {                     if (op1=='*' || op1=='/') {                         num1 = calc(op1, num1, num);                         op1 = 0;                     } else {                         num2 = num;                     }                 } else {                     num2 = calc(op2, num2, num);                     op2 = 0;                 }                                  i = j;                 continue;             }             else if (ch=='*' || ch=='/') {                 if (op1==0)                     op1 = ch;                 else                     op2 = ch;             } else if (ch=='+' || ch=='-') {                 if (op1==0) {                     op1 = ch;                 } else {                     num1 = calc(op1, num1, num2);                     num2 = null;                     op1 = ch;                 }             } else {                 i++;                 continue;             }                          i++;         }                  if (op1!=0)             return calc(op1, num1, num2);                  return num1;     }          private int calc(char op, int num1, int num2) {         if (op=='+')             return num1+num2;         if (op=='-')             return num1-num2;         if (op=='*')             return num1*num2;         return num1/num2;     } }