[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于 tricky 的方法。我没有为了这个再更新，就让它们去吧。
LeetCode 的题目是不断在更新。还是老规矩，跳过了那些需要付费才能做的题目。下面的解法可能不是最好的，具体问题我们可以讨论。截至目前我解答的全部的 LeetCode 放在了这里。
【题目】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.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
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 ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
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]);
}
}
【题目】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:
- The array is only modifiable by the update function.
- 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 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.
For example:"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
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.
Follow up:
How would you handle overflow for very large input integers?
【解答】在最开始的两个数定了以后，后面就一路计算和检查下去，看是不是 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 (row1, col1) and lower right corner (row2, col2).
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12
Note:
- You may assume that the matrix does not change.
- There are many calls to sumRegion function.
- You may assume that row1 ≤ row2 and col1 ≤ col2.
【解答】这个题是下面《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;
}
}
【题目】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:
- You may assume that the array does not change.
- 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 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.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
【解答】我的方法肯定不是最佳的，因为复杂度是 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;
}
}
【题目】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);
}
}
【题目】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;
}
}
};
【题目】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;
}
}
【题目】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:
- pattern =
"abba", str ="dog cat cat dog"should return true. - pattern =
"abba", str ="dog cat cat fish"should return false. - pattern =
"aaaa", str ="dog cat cat dog"should return false. - 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;
}
}
【题目】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):
- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population..
- 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:
- 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.
- 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;
}
}
【题目】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:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than
O(n2). - 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;
}
}
【题目】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;
}
}
【题目】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:
- You must do this in-place without making a copy of the array.
- 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];
}
}
【题目】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);
}
}
}
}
【题目】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];
}
}
【题目】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;
}
}
【题目】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;
}
}
【题目】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;
}
}
【题目】Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 – 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;
}
}
【题目】Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
【解答】大致是思路就是数组的原地调整，“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;
}
}
【题目】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);
}
}
【题目】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;
}
}
【题目】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:
- The order of the result is not important. So in the above example,
[5, 3]is also correct. - 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};
}
}
【题目】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.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
【解答】公式在维基百科页面这里。
public class Solution {
public int addDigits(int num) {
//https://en.wikipedia.org/wiki/Digital_root
return 1 + (num-1)%9;
}
}
【题目】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;
}
}
【题目】Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.
Note:
You may assume the string contains only lowercase alphabets.
【解答】因为只需要考虑小写字母，那就使用数组就好了，记录每个字母出现的次数。
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;
}
}
【题目】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
}
}
【题目】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.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
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].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.
Follow up:
Could you solve it in linear time?
【解答】滑动窗口内求最大值。解法有几个，但是要求线性时间复杂度的话，引入一个双端队列 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;
}
}
【题目】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].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
【解答】算出的数组要求，第 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;
}
}
【题目】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;
}
}
【题目】Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
【解答】要在 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;
}
}
【题目】Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
【解答】题目看起来似乎不难，不就是有策略地数数嘛，但是做起来还挺难的。下面这个解法最初来自这里，我写成了自己便于理解的版本：
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 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, andis emptyoperations 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();
}
}
【题目】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;
}
}
【题目】Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.
【解答】思路就是利用二叉搜索树的特性，从小到大遍历，找到第 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);
}
}
【题目】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;
}
}
【题目】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;
}
}
【题目】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;
}
}
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
看了您的博文总结的非常好，您的博客非常不错。我也推荐一个程序员必备的搜索博客问答的网站 http://www.itdaan.com 。