[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于 tricky 的方法。我没有为了这个再更新，就让它们去吧。
以下是 LeetCode 题目解答的最后一部分：Hard 部分。
Text Justification
【题目】Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[ "This is an", "example of text", "justification. " ]
Note: Each word is guaranteed not to exceed L in length.
【解答】主要要把题意理解透彻，几个 corner case 的理解，包括最末一行的处理，还有面对空字符串的处理。遍历的时候，i 从 0 遍历到 words.length，在 i==words.length 的时候处理最末一行的情况。感觉这个题目其实没有太多技巧性，就是需要细心和耐心，把逻辑想清楚。
public class Solution {
public List<String> fullJustify(String[] words, int L) {
List<String> result = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
List<String> list = new ArrayList<String>();
int lenSum = 0;
for (int i = 0; i <= words.length; i++) {
String cur;
if (i == words.length)
cur = "";
else
cur = words[i];
if (lenSum + cur.length() + list.size() > L || i == words.length) {
int slots = list.size() - 1;
int basicSpaces = 0;
if (slots != 0)
basicSpaces = (L - lenSum) / slots;
if (i==words.length)
basicSpaces = 1;
int moreSpaces = L - lenSum;
if (slots != 0 && basicSpaces > 0)
moreSpaces = (L - lenSum) % slots;
if (i==words.length)
moreSpaces = L - lenSum - slots;
// append
for (int j = 0; j < list.size(); j++) {
if (j != 0) {
for (int k = 0; k < basicSpaces; k++)
sb.append(' ');
if (moreSpaces > 0 && i != words.length) {
sb.append(' ');
moreSpaces--;
}
}
sb.append(list.get(j));
}
// trailing spaces
for (int k = 0; k < moreSpaces; k++) {
sb.append(' ');
}
list.clear();
lenSum = 0;
result.add(sb.toString());
sb = new StringBuilder();
}
list.add(cur);
lenSum += cur.length();
}
return result;
}
}
Search in Rotated Sorted Array
【题目】Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
【解答】不知道为什么这道题归为 Hard，其实思路还是很容易找到的。如果是一个单纯的升序排列的数组，那就是二分法查找，现在这个数组可能被 rotate 了，那么还是借由二分法，只不过在找到中间的数了之后，需要比较中间数和最右数（或者最左数），有这样的结论：
- 1. 如果中间数大于最右数，那么最大最小数的分界点在右半支，而左半支严格单调递增，在这种情况下通过比较左半支的首尾两个数，判断目标数在不在左半支内，如果不在，就一定在右半支内。
- 2. 如果中间数小于最右数，那么最大最小数的分界点在左半支，而右半支严格单调递增，在这种情况下通过比较右半支的首尾两个数，判断目标数在不在右半支内，如果不在，就一定在左半支内。
public class Solution {
public int search(int[] A, int target) {
return search(A, target, 0, A.length-1);
}
private int search(int[] A, int target, int start, int end) {
if (start>end)
return -1;
int mid = (end+start)/2;
if (target==A[mid])
return mid;
if (A[end]>=A[mid]) { // the right part is increasing
if (target>A[end] || target<A[mid]) {
return search(A, target, start, mid-1);
} else {
return search(A, target, mid+1, end);
}
} else { // the left part is increasing
if (target<A[start] || target>A[mid]) {
return search(A, target, mid+1, end);
} else {
return search(A, target, start, mid-1);
}
}
}
}
Binary Tree Maximum Path Sum
【题目】Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
【解答】定义一个 maxSinglePath 方法，用来返回以 root 为根的树从根开始存在的最大单向路径（根到某叶子或者根到某分支节点）。再定义一个 pathSum 方法，用来返回以 root 为根时，该树的最大 path sum，在该方法内，调用 maxSinglePath 方法分别获取左子树和右子树的最大单向路径，二者之和再加上当前节点的值为包含当前 root 的最大 path sum，再递归求出左子树的最大 path sum 和右子树的最大 path sum，三者取最大值。
public class Solution {
public int maxPathSum(TreeNode root) {
if (null==root)
return 0;
Map<TreeNode, Integer> map = new HashMap<>();
return pathSum(root, map);
}
private int pathSum(TreeNode root, Map<TreeNode, Integer> map) {
int left = 0;
if (root.left!=null) {
left = maxSinglePath(root.left, map);
if (left<0)
left = 0;
}
int right = 0;
if (root.right!=null) {
right = maxSinglePath(root.right, map);
if (right<0)
right = 0;
}
int current = left + right + root.val;
if (root.left!=null) {
int l = pathSum(root.left, map);
if (l>current)
current = l;
}
if (root.right!=null) {
int r = pathSum(root.right, map);
if (r>current)
current = r;
}
return current;
}
private int maxSinglePath(TreeNode root, Map<TreeNode, Integer> map) {
if (map.containsKey(root))
return map.get(root);
int left = 0;
if (root.left!=null) {
left = maxSinglePath(root.left, map);
if (left<0)
left = 0;
}
int right = 0;
if (root.right!=null) {
right = maxSinglePath(root.right, map);
if (right<0)
right = 0;
}
int maxVal = Math.max(left, right) + root.val;
map.put(root, maxVal);
return maxVal;
}
}
Reverse Nodes in k-Group
【题目】Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
【解答】引入一个伪节点作为头，可以免去对 head 的特殊处理。基本思路是：一个快指针，一个慢指针，平时慢指针不动，快指针往前跑，在二者间距达到 k 时，令 start=slow.next，end=fast，对于 [start,end] 这一段区间的节点指向反向，反向后令 slow.next=end，fast=start。题目不难，小心一点便是。
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode fake = new ListNode(0);
fake.next = head;
ListNode fast = fake;
ListNode slow = fake;
int count = 0;
while (fast!=null) {
if (count==k) {
ListNode start = slow.next;
ListNode end = fast;
fast = end.next;
ListNode n = start;
ListNode next = n.next;
while (n!=end) {
ListNode temp = next.next;
next.next = n;
n = next;
next = temp;
}
slow.next = end;
start.next = fast;
slow = start;
fast = slow;
count=0;
} else {
fast = fast.next;
count++;
}
}
return fake.next;
}
}
Binary Tree Postorder Traversal
【题目】Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
【解答】如果是递归遍历，没有任何难度，也不可能放到 Hard 级别里面来。用非递归方式，需要一个辅助栈，用来存放节点 pop 出来的当前状态。具体说：
- 当前节点不为空，就先遍历左子树，同时当前节点入栈，状态栈入 true；
- 当前节点为空，退栈，如果状态为 true，就遍历右子树，状态栈顶变为 false；
- 当前节点为空，退栈，如果状态为 false，就遍历退栈节点，相应状态元素退栈。
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
Stack<Boolean> status = new Stack<>();
List<Integer> result = new ArrayList<>();
TreeNode node = root;
while (!stack.isEmpty() || node!=null) {
if (null!=node) {
stack.push(node);
status.push(true);
node = node.left;
} else {
node = stack.peek();
boolean flag = status.pop();
if (flag) {
node = node.right;
status.push(false);
} else {
result.add(node.val);
stack.pop();
node = null;
}
}
}
return result;
}
}
Candy
【题目】There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
【解答】最开始我选择的做法是像分析函数曲线一样找拐点，如果知道这条曲线的拐点，比如极大值，那么极大值左侧是递增的，极大值右侧是递减的；极小值左侧递减，右侧递增。这里特别麻烦的地方在于，极小值取值是显然为 1，但极大值的取值取决于极大值两侧单调曲线的长度，要取长的那一侧的最大值。
比如 ratings=[1, 2, 3, 4, 5, 4, 1]，其中 ratings[4] 就是一个极大值，但是取值 candies[4] 取决于 ratings[4] 左右两侧单调曲线的长度，左侧比右侧长，因此要根据左侧来计数取值，在这里 candies[4] 就取 5（如果根据右侧来取值就是 3，那就错了）。还需要考虑一些特殊的 case，比如极大、极小值出现在首尾，这种情况下是只有右侧或者只有左侧单调曲线的。因此这个办法的代码写起来比较复杂。
下面这个办法我也是参考了别人的解法的，两遍遍历，一遍正向，一遍逆向，思路非常清晰：
- 正向遍历的时候，如果发现递增序列，就放置一个从 1 开始依次递增的数，但是，存在这样错误的情况：如果是递减序列的情况呢，这里全放置了 1；
- 那么这个问题就需要通过逆向遍历来消除。
那么这个办法对于我之前办法所说的那个不易处理的问题，通过逆向遍历中的一个关系为且的子判断条件 candies[i]<=candies[i+1] 给巧妙的规避掉了。
public class Solution {
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0)
return 0;
if (ratings.length == 1)
return 1;
int[] candies = new int[ratings.length];
candies[0] = 1;
// forward
for (int i = 1; i < ratings.length; i++) {
// rating: asc
if (ratings[i] > ratings[i - 1])
candies[i] = candies[i - 1] + 1;
else
candies[i] = 1;
}
// backward
for (int i = ratings.length - 2; i >= 0; i--) {
// rating: desc && candy: asc
if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])
candies[i] = candies[i + 1] + 1;
}
int total = 0;
for (int i = 0; i < ratings.length; i++)
total += candies[i];
return total;
}
}
Edit Distance
【题目】Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
【解答】遇到这种求两个东西之间距离的，要么回溯法，要么动态规划。这里就是动态规划，这个题目还是很有代表性的。建立一个 dist 二维数组，注意行、列的长度要分别比 word1 和 word2 的长度多 1，dist[i][j] 用来表示 word1.substring(0,i) 到 word2.substring(0,j) 的距离。因此 dist[i][j] 在 i==0 的时候为 j，在 j==0 的时候为 i。其余的情况，根据 insert、delete 和 replace 三种可能性分类讨论，取三种情况的最小距离。
public class Solution {
public int minDistance(String word1, String word2) {
Integer[][] dist = new Integer[word1.length()+1][word2.length()+1];
return min(word1, word2, word1.length(), word2.length(), dist);
}
private int min(String w1, String w2, int i, int j, Integer[][] dist) {
if (dist[i][j]!=null)
return dist[i][j];
if (i==0) {
dist[i][j] = j;
return j;
} else if (j==0) {
dist[i][j] = i;
return i;
}
char ci = w1.charAt(i-1);
char cj = w2.charAt(j-1);
if (ci==cj) {
dist[i][j] = min(w1, w2, i-1, j-1, dist);
return dist[i][j];
}
int insert = min(w1, w2, i-1, j, dist) + 1;
int replace = min(w1, w2, i-1, j-1, dist) + 1;
int delete = min(w1, w2, i, j-1, dist) + 1;
int result = Math.min(delete, Math.min(insert, replace));
dist[i][j] = result;
return result;
}
}
Recover Binary Search Tree
【题目】Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
【解答】对于 BST，对任一节点，满足左分支上面所有的节点都小于根节点，右分支上面所有的节点都大于根节点，而中序遍历能够保证形成正确的递增序列，因此遍历时能够保证当前节点的大小一定大于前一个节点的大小。这一点是做这道题的基础。
对于其中某两个节点被错误的 swap 了，这里有两种情况可供讨论：
- 两个错误节点是相邻的，比如：0,1,2,3,5,4,6，这种情况中序遍历的整个过程只能发现一次异常节点，在这里是 4，这种情况，需要把异常节点和它前面那个节点调换，即 4 和 5 调换；
- 两个错误节点不相邻，比如：0,1,5,3,4,2,6，这种情况中序遍历的整个过程可以发现两次异常节点，在这里分别为 3 和 2，这种情况下，需要把第一个异常节点的前面那个节点和第二个异常节点调换，即 5 和 2。
掌握这两点规律以后问题就很好解了。下面的解法里面，en 用于存储第一个异常节点，enLast 表示第一个异常节点的前面那个节点。StopTraversalException 的定义其实是可选的，用于在发现第二个异常节点之后直接交换错误值并返回，没必要再往后遍历了。
class StopTraversalException extends RuntimeException {
public StopTraversalException() {
super();
}
}
public class Solution {
private TreeNode en = null;
private TreeNode enLast = null;
private TreeNode last = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
if (null==root)
return;
try {
traverse(root);
} catch (StopTraversalException e) {
return;
}
swap(en, enLast);
}
private void traverse(TreeNode root) {
if (root.left!=null)
traverse(root.left);
if (last.val>root.val) {
if (en==null) {
en = root;
enLast = last;
} else {
swap(enLast, root);
throw new StopTraversalException();
}
}
last = root;
if (root.right!=null)
traverse(root.right);
}
private void swap(TreeNode n1, TreeNode n2) {
int temp = n1.val;
n1.val = n2.val;
n2.val = temp;
}
}
Populating Next Right Pointers in Each Node II
【题目】Follow up for problem “Populating Next Right Pointers in Each Node“.
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
【解答】看起来只是在《Populating Next Right Pointers in Each Node》基础上增加了一个节点可能为空的情况，但是难度其实增加不少。我把原有的递归改成这种从上到下一层一层循环执行的逻辑，我觉得是比较清晰的办法。对于每一层（level），引入一个 fake 节点来帮助掌控每一层的头部，按序构建 next 关联关系。
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null)
return;
TreeLinkNode level = root;
while (level != null) {
TreeLinkNode n = level;
TreeLinkNode fake = new TreeLinkNode(0);
TreeLinkNode child = fake;
while (n != null) {
if (n.left != null) {
child.next = n.left;
child = child.next;
}
if (n.right != null) {
child.next = n.right;
child = child.next;
}
n = n.next;
}
child.next = null;
level = fake.next;
}
}
}
Permutations II
【题目】Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
【解答】大致的思路就是回溯法，但是这里需要注意去重的处理，如果这一点上思路选择不合适的话就会绕很大的圈子。先给 num 数组排序，那么对于任何重复数字的情况，例如 num 为 1,2,2,3,4，其中 2 有重复，假设给这两个 2 分别标号：2-1 和 2-2，如果我可以保证最终输出的序列中，2 的顺序也是一致的，即 2-1 一定出现在 2-2 之前，那么，就恰好去重了。
所以在下面的 build 方法里面的 for 循环中，第二个 continue 的判断条件，就用到了这样的逻辑——如果 num[i]==num[i-1] 且 used[i-1]==false，这表示当有某个数重复出现时，这个序列先用到了后面的那个，这违背了重复数字保序性的要求。
public class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> total = new ArrayList<>();
if (num==null)
return total;
Arrays.sort(num);
boolean[] used = new boolean[num.length];
build(num, used, new ArrayList<Integer>(), total);
return total;
}
private void build (int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> total) {
if (list.size()==nums.length) {
total.add(list);
return;
}
for (int i=0; i<nums.length; i++) {
if (used[i])
continue;
if (i>0 && nums[i]==nums[i-1] && !used[i-1])
continue;
used[i] = true;
List<Integer> l = new ArrayList<>(list);
l.add(nums[i]);
build (nums, used, l, total);
used[i] = false;
}
}
}
Best Time to Buy and Sell Stock III
【题目】Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
【解答】最开始我还是按照《Best Time to Buy and Sell Stock》的思路来解题：那个思路已经可以给出一段区间内的 max profit，保留该方法，当前这道题相当于给出一个切分点 i，在 [0,i] 和 [i,prices.length) 这两段区间内分别求 max profit，取二者之和的最大值。但是在遇到比较长的 case 的时候超时了，所以引入二维数组来缓存计算过的数据，减少重复计算：
public class Solution {
public int maxProfit(int[] prices) {
if (prices.length<=1)
return 0;
mins = new Integer[prices.length][prices.length];
maxs = new Integer[prices.length][prices.length];
int max = 0;
for (int i=0; i<prices.length; i++) {
int left = maxProfit(prices, 0, i+1);
int right = maxProfit(prices, i, prices.length-i);
if (left+right>max)
max = left+right;
}
return max;
}
private Integer[][] mins; // first n days
private Integer[][] maxs; // last n days
private int maxProfit(int[] prices, int offset, int len) {
if (len<=1) {
return 0;
}
if (mins[offset][0]==null)
mins[offset][0] = prices[offset];
if (maxs[offset+len-1][offset+len-1]==null)
maxs[offset+len-1][offset+len-1] = prices[offset+len-1];
// fill max prices, from right to left
for (int i=len-2; i>=0; i--) {
if (maxs[offset+len-1][i]==null) {
if (prices[offset+i]>maxs[offset+len-1][i+1])
maxs[offset+len-1][i] = prices[offset+i];
else
maxs[offset+len-1][i] = maxs[offset+len-1][i+1];
}
}
// fill min prices, and calculate the biggest profit, from left to right
int biggestProfit = 0;
for (int i=1; i<len; i++) {
if (mins[offset][i]==null) {
if (prices[offset+i]<mins[offset][i-1])
mins[offset][i] = prices[offset+i];
else
mins[offset][i] = mins[offset][i-1];
}
int profit = maxs[offset+len-1][i] - mins[offset][i];
if (profit>biggestProfit)
biggestProfit = profit;
}
return biggestProfit;
}
}
可是依然超时。这个思路毕竟也是换汤不换药，n 平方的复杂度。造成这种局面的原因在于，
- 外层循环那个 n 是来自于寻找前半段和后半段的切分点，这一层循环是无论如何都少不了的；
- 里层循环那个 n 则是因为对每次前半段或者后半段自身，要再从后往前寻找最大价格，再从前往后遍历寻找最小价格，并且求出最大收益。
于是换个思路，改进球最大收益的过程，
- 第一遍，从前往后循环对每个 i 的取值计算 [0,i] 的最大收益；
- 第二遍，从后往前循环对每个 i 的取值计算 [i,prices.length) 的最大收益，并根据 profits[i] 的值相加球总收益，记录总收益的最大值。
于是复杂度变成 n 了：
public class Solution {
public int maxProfit(int[] prices) {
if (null == prices || prices.length <= 1)
return 0;
int[] profits = new int[prices.length];
profits[0] = 0;
int minPrice = prices[0], maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
minPrice = Math.min(prices[i - 1], minPrice);
if (maxProfit < prices[i] - minPrice)
maxProfit = prices[i] - minPrice;
profits[i] = maxProfit;
}
int maxPrice = prices[prices.length - 1];
int maxFinalProfit = profits[prices.length - 1];
maxProfit = 0;
for (int i = prices.length - 2; i >= 0; i--) {
maxPrice = Math.max(maxPrice, prices[i + 1]);
if (maxProfit < maxPrice - prices[i])
maxProfit = maxPrice - prices[i];
if (maxFinalProfit < profits[i] + maxProfit)
maxFinalProfit = profits[i] + maxProfit;
}
return maxFinalProfit;
}
}
Palindrome Partitioning II
【题目】Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
【解答】借由《Palindrome Partitioning》的思路，对于给定的区间 [start,end)，先判断是否是回文，如果不是，分别尝试在区间的各个位置截断，判断前半段和后半段是否都是回文。在对一些变态 case 超时以后，分两次加上了两个 cache，isPalindromeCache 和 minCutCache，分别存储判断是否为回文的记录和计算 cut 次数的记录：
public class Solution {
public int minCut(String s) {
Boolean[][] isPalindromeCache = new Boolean[s.length()][s.length()];
Integer[][] minCutCache = new Integer[s.length()][s.length()];
if (isPalindrome(s, 0, s.length(), cache))
return 0;
return minCut(s, 0, s.length(), isPalindromeCache, minCutCache);
}
private int minCut(String s, int start, int end, Boolean[][] isPalindromeCache, Integer[][] minCutCache) {
if (end-start<=1)
return 0;
int min = end-start-1;
for (int i=1; i<end-start-1; i++) {
if (isPalindrome(s, start, start+i, isPalindromeCache)) {
if (isPalindrome(s, start+i, end, isPalindromeCache))
return 1;
int cut = minCut(s, start+i, end, isPalindromeCache)+1;
if (cut<min)
min = cut;
}
}
return min;
}
private boolean isPalindrome(String s, int start, int end, Boolean[][] isPalindromeCache) {
if (isPalindromeCache[start][end-1]!=null)
return isPalindromeCache[start][end-1];
for (int i=start, j=end-1; j>i; j--,i++) {
if (s.charAt(i)!=s.charAt(j))
return false;
}
return true;
}
}
可即便如此，在遇到另外一些变态 case 的时候依然超时，比如这样一个 case：514 个 a，加两个 b，再加 946 个 a。下面这个方法的思路也是从别处借鉴来的：
public class Solution {
public int minCut(String s) {
int len = s.length();
int[] cut = new int[len + 1];
for (int i = 0; i <= len; i++)
cut[i] = len - i;
boolean[][] isPalindrome = new boolean[len][len];
for (int i = len - 1; i &>t;= 0; i--) {
for (int j = i; j < len; j++) {
if (s.charAt(i) == s.charAt(j)
&& (j - i < 2 || isPalindrome[i + 1][j - 1])) {
isPalindrome[i][j] = true;
cut[i] = Math.min(cut[i], cut[j + 1] + 1);
}
}
}
return cut[0] - 1;
}
}
逻辑上看简单多了，但是其实要更不容易想出来。用一个二维数组 isPalindrome 存放是否为回文的状态，两层循环嵌套，i 从后往前，j 从 i 往后遍历，如果 s[i]==s[j]，并且前一个状态，即 isPalindrome[i+1][j-1] 为真，那么 isPalindrome[i][j] 也为真。一维数组 cut 用来存放需要切分的次数，初始为字符串区域的长度。
N-Queens II
【题目】Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
【解答】紧跟着 N-Queens 那道题，思路简直一模一样。不是很理解为啥弄两道差不多的题目。
public class Solution {
private int total = 0;
public int totalNQueens(int n) {
solveNQueens(0, n, new int[n]);
return total;
}
private void solveNQueens(int i, int n, int[] positions) {
if (i == n) {
total++;
} else {
for (int j = 0; j < n; j++) {
positions[i] = j; // row: i, col: j
if (validate(i, positions)) {
solveNQueens(i + 1, n, positions);
}
}
}
}
private boolean validate(int maxRow, int[] positions) {
for (int i = 0; i < maxRow; i++) {
if (positions[i] == positions[maxRow] // same column
|| Math.abs(positions[i] - positions[maxRow]) == maxRow - i) // catercorner line
return false;
}
return true;
}
}
Substring with Concatenation of All Words
【题目】You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
【解答】先把 L 放到一个 map 里面去，key 为单词，value 为该单词在 L 中出现的次数。再遍历 S，以 S 中每个字母为开头时，寻找是否存在满足题目要求的子串：发现单词匹配，就从 dictCopy 里面给这个单词出现的次数减一，如果一切匹配，就不会出现 num==null 或者 num==0 的情况。
public class Solution {
public List<Integer> findSubstring(String S, String[] L) {
Map<String, Integer> dict = new HashMap<>();
for (String l : L) {
if (!dict.containsKey(l)) {
dict.put(l, 0);
}
dict.put(l, dict.get(l)+1);
}
int len = L[0].length();
int lenSum = len*L.length;
List<Integer> list = new ArrayList<>();
traverseS : for (int i=0; i<=S.length()-lenSum; i++) {
Map<String, Integer> dictCopy = new HashMap<>(dict);
for (int j=i; j<i+lenSum; j=j+len) {
String s = S.substring(j, j+len);
Integer num = dictCopy.get(s);
if (num==null || num==0)
continue traverseS;
num--;
dictCopy.put(s, num);
}
list.add(i);
}
return list;
}
}
Sudoku Solver
【题目】Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle…
…and its solution numbers marked in red.
【解答】回溯法，每个可以填写数字的位置挨个试，用 validate 方法来验证当前的填写是否正确，不需要等整个 board 全部填完了再判断，每填写一个数就可以判断了。办法挺死板的，当时想着不行的话再想办法优化，不过居然 AC 了，真是……
public class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) {
if ('.' == board[i][j]) {
for (int k=1; k<=9; ++k) {
board[i][j] = (char)('0'+k);
if (validate(board, i, j) && solve(board))
return true;
board[i][j] = '.';
}
return false;
}
}
}
return true;
}
// x: row, y: col
private boolean validate(char[][] board, int x, int y) {
// col==y
for (int i=0; i<9; i++)
if (i!=x && board[i][y]==board[x][y])
return false;
// row==x
for (int j = 0; j<9; j++)
if (j!=y && board[x][j]==board[x][y])
return false;
// each cube
for (int i=3*(x/3); i<3*(x/3+1); i++)
for (int j=3*(y/3); j<3*(y/3+1); j++)
if (i!=x && j!=y && board[i][j]==board[x][y])
return false;
return true;
}
}
N-Queens
【题目】The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
【解答】这个题目是比较经典的回溯法题目，很多教科书里面都有。根据国际象棋的规则，这里要求任意两个皇后不能在同一行，不能在同一列，不能在同一条对角线上。使用一个 int 数组来存放当前棋盘上皇后的状态，int[i]=j，表示第 i 行上，皇后放在第 j 列，这样天然避免了在同一行情况的出现，也避免了使用二维数组来保存状态；但是不能在同一列和不能在同一条对角线需要每次摆放一个皇后以后立马检查。
public class Solution {
public List<String[]> solveNQueens(int n) {
List<String[]> list = new ArrayList<String[]>();
solveNQueens(0, n, new int[n], list);
return list;
}
private void solveNQueens(int i, int n, int[] positions,
List<String[]> list) {
if (i == n) {
outputToList(n, positions, list);
} else {
for (int j = 0; j < n; j++) {
positions[i] = j; // row: i, col: j
if (validate(i, positions)) {
solveNQueens(i + 1, n, positions, list);
}
}
}
}
private void outputToList(int n, int[] positions, List<String[]> list) {
String[] result = new String[n];
for (int i = 0; i < n; i++) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < n; j++) {
if (j == positions[i])
sb.append('Q');
else
sb.append('.');
}
result[i] = sb.toString();
}
list.add(result);
}
private boolean validate(int maxRow, int[] positions) {
for (int i = 0; i < maxRow; i++) {
if (positions[i] == positions[maxRow] // same column
|| Math.abs(positions[i] - positions[maxRow]) == maxRow - i) // catercorner line
return false;
}
return true;
}
}
Minimum Window Substring
【题目】Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example, S = "ADOBECODEBANC" T = "ABC"
Minimum window is "BANC".
Note: If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
【解答】注意题目要求的复杂度是 n 阶的，因此不能在循环中去匹配变化子串和 T，那样就 n 的平方阶了。可以通过一个有限长的 int 数组来表达这个字符串 T，大致思路如下：
- 双指针，一左一右，[left,right] 这段区域内的子串就是待认定的 window substring；
- 把 T 用一个长度为 128 的 int 数组来表达，下标表示字符的 ascii 码，值表示该字符在 T 中出现的次数；
- 整个流程就是是 right 和 left 分别尝试右移的过程，始终尽量保持 [left,right] 包含 window substring：
- (1) 如果 rightOrLeft 为真，并且 right 能够右移，就右移并判定子串是否包含 T，如果包含就判断是否需要更新 min；如果包含或者干脆就不能右移，把移动的标志位置反。
- (2) 如果 rightOrLeft 为 false，考虑 left 右移，并判定子串是否包含 T，如果包含就判断是否需要更新 min；如果不包含就把移动的标志位置反，让下次迭代去尝试 right 右移。
- 注意处理开头的特殊情况，即初始状态 left==right==0，需要先把 S[0] 放到 source 里面去，避免遗漏。
public class Solution {
public String minWindow(String S, String T) {
int[] target = new int[128];
for (int i=0; i<T.length(); i++) {
target[(int)(T.charAt(i))]++;
}
int left=0;
int right=0;
int[] source = new int[128];
source[(int)(S.charAt(0))]++;
String min = "";
if (T.equals(S.substring(0,1)))
min = S.substring(0,1);
boolean rightOrLeft = true; // true: right, false: left
while (true) {
if (rightOrLeft) {
if (right<S.length()-1) {
right++;
source[(int)(S.charAt(right))]++;
} else {
rightOrLeft = false;
}
if (match(source, target)) {
if ("".equals(min) || min.length()>right-left+1)
min = S.substring(left, right+1);
rightOrLeft = false;
}
} else {
if (left==S.length()-1)
break;
source[(int)(S.charAt(left))]--;
left++;
if (match(source, target)) {
if ("".equals(min) || min.length()>right-left+1)
min = S.substring(left, right+1);
} else {
rightOrLeft = true;
}
} // else
} // while
return min;
}
private boolean match(int[] left, int[] right) {
for (int i=0; i<128; i++) {
if (left[i]<right[i])
return false;
}
return true;
}
}
Merge k Sorted Lists
【题目】Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
【解答】这道题是有一定典型意义的。如果是两个列表归并，那么显然就使用传统归并排序的方法就好了，但是现在是 m 个列表归并，这就意味着，在每一轮归并的迭代中，假使每个列表取一个元素，那么着 m 个元素的大小关系是完全不可知的，原有排好序的 list 特性并没有充分利用，这能优化吗？
进一步考虑，在对刚才说的 m 个元素排序以后，比如说我就知道了最小元素是来自 7 号链表的，那么，我可以想象，最终结果中，次小元素要么在当前这剩下的 m-1 个元素里面，要么就是 7 号链表剩下元素的头部了。要充分利用这个信息，才可以让算法的复杂度降下来。
要不断取得这 m 个元素中最小的，于是我联想到了堆排序（各种排序方法，包括堆排序，我以前在这篇文中总结过）。每次从最小堆中抽走堆顶，接下去就补充被抽走堆顶的 next 元素到堆中，重新恢复最小堆。分析一下复杂度，按照刚才的定义，全部元素是 (m*n)，堆大小是 m，那么整个复杂度就是 m*n(log m)。
在 Java 中，其实已经有封装好堆排序的现成的东西了（这是个死知识），那个东西就是 PriorityQueue：
public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
if (null==lists || lists.isEmpty())
return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.size(), new Comparator<ListNode>(){
@Override
public int compare(ListNode n1, ListNode n2) {
if (n1.val==n2.val)
return 0;
else if (n1.val<n2.val)
return -1;
else
return 1;
}
});
// initialization
for (ListNode n : lists) {
if (n==null)
continue;
queue.add(n);
}
ListNode fakeHead = new ListNode(0);
ListNode current = fakeHead;
while (!queue.isEmpty()) {
ListNode n = queue.poll();
current.next = n;
current = n;
if (n.next!=null)
queue.add(n.next);
}
return fakeHead.next;
}
}
Merge Intervals
【题目】Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
【解答】这题相对来说比较简单。先排序，按照 start 属性来排。之后开始遍历 intervals，如果发现有重叠的 interval，就合并；如果发现非重叠的 interval，放置较靠前的一个到最终的 list 里面去。
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval left, Interval right) {
if (left.start == right.start)
return 0;
else if (left.start < right.start)
return -1;
else
return 1;
}
});
List<Interval> list = new ArrayList<>();
Interval toCompare = null;
for (Interval interval : intervals) {
if (toCompare!=null && interval.end>=toCompare.start && interval.start<=toCompare.end) {
toCompare.start = Math.min(interval.start, toCompare.start);
toCompare.end = Math.max(interval.end, toCompare.end);
} else {
if (toCompare!=null)
list.add(toCompare);
toCompare = interval;
}
}
if (null!=toCompare)
list.add(toCompare);
return list;
}
}
Scramble String
【题目】Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
【解答】终于做到一道 3 维动态规划的题目了。最开始我就是简单的回溯遍历，结果执行超时了，于是想到 DP。cache[i][j][k] 表示的是，s1 以下标 i 为起点，s2 以下标 j 为起点，二者长度都为 k 时，这两个子串是否满足 scramble 关系，即 s1 的 [i,i+k) 和 s2 的 [j,j+k) 是否满足 scramble 关系。
这一点不难想到，并且想到以后就可以落实代码了。但是在写代码判断 scramble 关系的时候，考虑 swap 和非 swap 两种情况，而且很容易写错：
- s1 的 [start1,start1+i) 和 s2 的 [start2,start2+i) 满足 scramble 关系，并且 s1 的 [start1+i,start1+len) 和 s2 的 [start2+i, start2+len) 也满足 scramble 关系，这种情况是两个子串没有发生 swap 的；
- 另一种情况自然就是两个子串发生了 swap，即 s1 的 [start1+len-i,start1+len) 和 s2 的 [start2, start2+i) 满足 scramble 关系，并且 s1 的 [start1,start1+len-i) 和 s2 的 [start2+i,start2+len) 也满足 scrmable 关系。
上面两种情况只需具备其一就返回 true，像这种比较绕的 DP 题目，我觉得写出数学通式是最关键的一步。
public class Solution {
public boolean isScramble(String s1, String s2) {
if (s1.length()!=s2.length())
return false;
// cache[i][j][k]: scramble between s1:[i,i+k) and s2:[j,j+k)
Boolean[][][] cache = new Boolean[s1.length()][s1.length()][s1.length()+1];
return isScramble(s1, s2, 0, 0, s1.length(), cache);
}
private boolean isScramble(String s1, String s2, int start1, int start2, int len, Boolean[][][] cache) {
if (cache[start1][start2][len]!=null)
return cache[start1][start2][len];
// exit
if (len==1) {
cache[start1][start2][len] = s1.charAt(start1)==s2.charAt(start2);
return cache[start1][start2][len];
}
// s1:[start1, start1+i) <=> s2:[start2, start2+i) and s1:[start1+i, start1+len) <=> s2:[start2+i, start2+len)
// or
// s1:[start1+len-i, start1+len) <=> s2:[start2, start2+i) and s1:[start1, start1+len-i) <=> s2:[start2+i, start2+len)
for (int i=1; i<len; i++) {
if (
(isScramble(s1, s2, start1, start2, i, cache) && isScramble(s1, s2, start1+i, start2+i, len-i, cache))
||
(isScramble(s1, s2, start1+len-i, start2, i, cache) && isScramble(s1, s2, start1, start2+i, len-i, cache))
) {
cache[start1][start2][len] = true;
return true;
}
}
cache[start1][start2][len] = false;
return false;
}
}
Trapping Rain Water
【题目】Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
【解答】这道题是 hard 里面相对比较简单的。大致的思路就是，找最长的两根杆子，分别为最长和次长，而两根杆子中间的部分，每个位置都去算距离次长杆子的距离，这些距离累加起来就是这两根杆子中间部分可以 trap 的雨水的量，而对于这两根杆子两侧的部分，继续递归求解。
public class Solution {
public int trap(int[] A) {
return trap(A, 0, A.length-1);
}
// [start, end]
private int trap(int[] A, int start, int end) {
if (start+1>=end)
return 0;
int maxIndex = -1;
int secondMaxIndex = -1;
for (int i=start; i<=end; i++) {
if (secondMaxIndex==-1 || A[i]>A[secondMaxIndex]) {
secondMaxIndex = i;
if (maxIndex==-1 || A[secondMaxIndex]>A[maxIndex]) {
int temp = maxIndex;
maxIndex = secondMaxIndex;
secondMaxIndex = temp;
}
}
}
int left = Math.min(maxIndex, secondMaxIndex);
int right = Math.max(maxIndex, secondMaxIndex);
int leftPart = trap(A, start, left);
int rightPart = trap(A, right, end);
int midPart = 0;
for (int i=left+1; i<right; i++) {
midPart += A[secondMaxIndex] - A[i];
}
return leftPart+midPart+rightPart;
}
}
Median of Two Sorted Arrays
【题目】There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
【解答】首先要明确中位数的概念：在 A 和 B 的总数为奇数时，中位数是中间那个数；总数为偶数时，中位数是中间那两个数的算术平均数。
这道题麻烦的地方在于时间复杂度是 log(m+n)，要得到这种时间复杂度，每个数遍历一遍显然是不可能的。于是就要充分利用好 A 和 B 都是有序的特点，而联想到二分搜索的时间复杂度恰好是 log(n)，所以思路就是看看能不能利用或者借鉴上二分搜索。
再一个如果强化一下条件，假设这里 m==n，那么拿 A 的中位数和 B 的中位数比较，如果 A 的中位数比较大，那么最后我们要求的 A 并 B 的中位数应该在 B 的后半段+A 的前半段里，这样可以一直递归求解。现在 m 不一定等于 n，这个结论也依然成立，每次分别比较 A 和 B 的中位数后可以给 A、B 分别砍掉半支，这样最后求解的复杂度恰好就是 O(log(m+n))。
在求中位数的时候小心坐标运算的时候发生错误，我反正错了 N 次。思路好找，要写对还挺难的。
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
if ((A.length + B.length) % 2 == 0) {
int midLeft = (A.length + B.length) / 2 - 1;
int midRight = (A.length + B.length) / 2;
return (0.0 + find(A, B, midRight, 0, A.length - 1, 0, B.length - 1) + find(
A, B, midLeft, 0, A.length - 1, 0, B.length - 1)) / 2;
} else {
int mid = (A.length + B.length) / 2;
return (double) find(A, B, mid, 0, A.length - 1, 0, B.length - 1);
}
}
private int find(int A[], int B[], int i, int aStart, int aEnd, int bStart,
int bEnd) {
if (aEnd - aStart < 0)
return B[bStart + i];
if (bEnd - bStart < 0)
return A[aStart + i];
if (i == 0)
return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
int aRelativePos = (int) (((0.0 + (aEnd - aStart + 1)) / ((aEnd
- aStart + 1) + (bEnd - bStart + 1))) * i);
int aMid = aRelativePos + aStart;
int bMid = i - aRelativePos - 1 + bStart;
if (A[aMid] > B[bMid]) {
i -= bMid - bStart + 1;
aEnd = aMid;
bStart = bMid + 1;
} else {
i -= aMid - aStart + 1;
bEnd = bMid;
aStart = aMid + 1;
}
return find(A, B, i, aStart, aEnd, bStart, bEnd);
}
}
Maximal Rectangle
【题目】Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
【解答】首先要理解题意，这里说的是要求这个矩形里面包含 1，并且是只包含 1，“rectangle containing all ones”，反正开始我是没有理解出，这句话是表示 “只” 包含 1 的。
比如这样一幅图：
1 0 1 0 1
1 1 1 0 0
0 1 1 0 1
那么这个矩形应该是用下划线标出的区域，因此应该返回 4。
那怎么做呢？先降维思考一下，如果 matrix 只有一维，那就好办了，寻找连续的 1，连续最多的就是最大的值。现在是二维，也可以往一维上面靠，做法就是：从上往下一行一行遍历，每一行的每个元素，都表示和上一行同一列连通（上下都是 1 就表示连通）的累加值。也就是说，上面这个图变成了：
1 0 1 0 1
2 1 2 0 0
0 2 2 0 1
只有上下连通，才会被累加，如果断掉了，就置为 0。
现在，每一行遍历完毕的时候，我拿到该行的结果，就可以去计算截止到该行为止的最大值了。
比如最后这行：
0 2 2 0 1
把这个数组（命名为 acc）画成等价的柱状图就是：
我拿 Excel 草草画的图，但是可见要求最大的矩形应该就是 acc[1] 和 acc[2] 的和，为 4。但是在求最大值的时候，需要按照高度从 1 到 acc 里元素的最大值为上限依次遍历，寻找连续块的最大值。
public class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length==0 || matrix[0].length==0)
return 0;
int[] acc = new int[matrix[0].length];
int max = 0;
for (int i=0; i<matrix.length; i++) {
int singleMax = 0;
for (int j=0; j<matrix[i].length; j++) {
if (matrix[i][j]=='0') {
acc[j] = 0;
} else {
acc[j]++;
if (acc[j]>singleMax)
singleMax = acc[j];
}
}
int newMax = calculateMax(acc, singleMax);
if (newMax>max)
max = newMax;
}
return max;
}
private int calculateMax(int[] acc, int singleMax) {
int max = 0;
for (int i=1; i<=singleMax; i++) {
int accInRow = 0;
for (int j=0; j<acc.length; j++) {
if (acc[j]>=i) {
accInRow += i;
if (accInRow>max)
max = accInRow;
} else {
accInRow = 0;
} // else
} // for j
} // for i
return max;
}
}
AC 了，代码其实并不复杂，但是其实复杂度够高的，达到了 O(x*y*m)，其中 x 和 y 分别表示矩阵的长和宽，m 表示某一行上积累的最大高度（acc 里的最大值）。
当然，网传有更牛逼更简洁的解法，也更不好懂，这有一篇文章提到，我就不贴了。
Max Points on a Line
【题目】Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
【解答】最开始我的做法是，O(n^2) 的复杂度，每取得两个点，就可以列出一个直线方程：y=kx+b，并把该直线方程放到一个 map 里面去，后续出现新的直线的时候都要先到 map 里面去寻找是否能够找到重合的直线，但是值得注意的有两处：
- k 和 b 都要表示成分数，不要使用 double 或者 float，否则可能损失精度，比较两个 float 或者 double 的大小可能是不准确的；
- 在直线垂直于 x 轴的时候，原有方程不存在，直线方程为 x=x0。
不过原始代码却执行超时了。
在此基础上整理一下思路，下面的解法 AC，getCount 方法，是对于给定的两个点 p1、p2，寻找 Point[] 数组里面和 p1、p2 形成的直线斜率相同的点的个数（注意时刻都不要使用真正求斜率的除法，因为那样会引入 double 或者 float 型，丢失精度）：
public class Solution {
public int maxPoints(Point[] points) {
if (points.length <= 1)
return points.length;
int maxCount = 0;
for (int i = 0; i < points.length; i++) {
for (int j = 0; j < points.length; j++) {
if (points[i] == points[j])
continue;
int count = getCount(points, points[i], points[j]);
if (count > maxCount)
maxCount = count;
}
}
return maxCount;
}
public int getCount(Point[] points, Point p1, Point p2) {
int count = 0;
// vertical
if (p1.x == p2.x) {
for (Point p : points) {
if (p.x == p1.x)
count++;
}
return count;
}
// horizontal
if (p1.y == p2.y) {
for (Point p : points) {
if (p.y == p1.y)
count++;
}
return count;
}
for (Point p : points) {
// gradient: (p2.y-p1.y)/(p2.x-p1.x)
if ((p.y - p2.y) * (p1.x - p2.x) == (p1.y - p2.y) * (p.x - p2.x)) {
count++;
}
}
return count;
}
}
LRU Cache
【题目】Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
【解答】这里应用一点小知识，LinkedHashMap 其实已经把这个 LRU 的事情做好了，只要覆写 removeEldestEntry 方法，判断如果大小大过容量，就返回 true。构造方法，需要调用父类构造方法，传入的三个参数分别表示：初始大小、扩容增长因子、访问顺序（accessOrder）。其中第三个参数尤其重要，accessOrder 为 true 时，每次调用 get 方法访问行为发生后，会把最近访问的对象移动到头部，而超出容量移除对象时，是从尾部开始的。
import java.util.LinkedHashMap;
class LRULinkedHashMap extends LinkedHashMap<Integer, Integer> {
private final int capacity;
public LRULinkedHashMap(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry paramEntry) {
if (this.entrySet().size()>capacity)
return true;
return false;
}
}
public class LRUCache {
private LRULinkedHashMap map;
public LRUCache(int capacity) {
this.map = new LRULinkedHashMap(capacity);
}
public int get(int key) {
Integer result = this.map.get(key);
if (null==result)
return -1;
return result;
}
public void set(int key, int value) {
this.map.put(key, value);
}
}
Longest Valid Parentheses
【题目】Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
【解答】这道题也算 hard 里面相对简单的。基本思路是 DP，但是最开始我用递归，从长串往短串方向递归调用，结果一个长 case 让我栈溢出了。于是改成循环，从短串往长串遍历（i 从小到大），而在每次迭代中从右向左寻找包含 s[i] 的合法序列（j 从大到小）：
- 每次循环迭代都拿包含 s[i] 的括号序列和不包含 s[i] 的括号序列（即前一次迭代的结果）比较，取较大值留下来。比如 ()()，i==2 时，s[2] 是 (，结果是 2；i==3 时，s[3] 是)，最长串是 4，结果是 2 和 4 的最大值，为 4。
- 用 rightNum 变量记录目前多余的右括号，需要继续找左括号来匹配。如果 rightNum<0，就要跳出本次迭代，因为左括号太多了，而右括号又必须先于左括号出现（因为 j 从大到小变化），允许合法出现的机会已经错过了；只有当 rightNum 变为 0 时，表示当前的串是一个合法的结果，更新 accumation 为当前串的长度 len。
public class Solution {
public int longestValidParentheses(String s) {
if (s==null)
return 0;
int longest = 0;
for (int i=0; i<s.length(); i++) {
int rightNum = 0;
int len = 0;
int accumulation = 0;
for (int j=i; j>=0; j--) {
char ch = s.charAt(j);
if (ch==')') {
rightNum++;
} else {
rightNum--;
if (rightNum<0)
break;
len += 2;
if (rightNum==0)
accumulation = len;
}
}
if (accumulation>longest)
longest = accumulation;
}
return longest;
}
}
Longest Consecutive Sequence
【题目】Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
【解答】这道题的关键在于时间复杂度要求是 O(n) 的，这就意味着，排序不用想了，而遍历这个数组的时候，还得用常量时间复杂度去做额外的操作。如果拼命去想怎么从原数组里面挨个取出元素来，怎么放到某一个容器里面，在整个数组便利完成之后，要让这个最长序列的结果也得出来的话，就走入死胡同了。原因在于，比如有序列 1,2,3,4 的话，当你 2 先放入容器，4 再放入的时候，很难找到和 2 之间的关联。但是，反过来就不一样了。先把所有的数都一股脑儿倒到一个 set 里面去，然后从中任取一个数，接着这个数开始往大的序列和往小的序列都挨个尝试从这个 set 里面取出来，取到说明有连续串，一直取到这一串数断掉为止。
public class Solution {
public int longestConsecutive(int[] num) {
if (num==null)
return 0;
Set<Integer> total = new HashSet<>();
for (int n : num) {
total.add(n);
}
int max = 0;
while (!total.isEmpty()) {
int n = total.iterator().next();
total.remove(n);
int count = 1;
int i = n;
while (total.remove(++i))
count++;
i = n;
while (total.remove(--i))
count++;
if (count>max)
max = count;
}
return max;
}
}
Copy List with Random Pointer
【题目】A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
【解答】这题比较简单。首先，按照不考虑 random 属性的情况，过一遍这个 list，创建一个新的 list，但是，每过到一个节点的时候，就以< 老节点, 新节点> 这样的组合放到 map 里面去。之后再过第二遍的时候，对于每一个老节点，以及它的 random 属性所指向的节点，都可以在这个 map 里面找到对应的新节点。
对于新建的链表，下面使用了一个 fakeTargetHead 来简化代码，避免 head 的特殊判断。
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode fakeTargetHead = new RandomListNode(0);
RandomListNode src = head;
RandomListNode target = fakeTargetHead;
while (src!=null) {
RandomListNode node = new RandomListNode(src.label);
map.put(src, node);
target.next = node;
src = src.next;
target = target.next;
}
src = head;
while (src!=null) {
if (null!=src.random) {
RandomListNode node = map.get(src);
RandomListNode to = map.get(src.random);
node.random = to;
}
src = src.next;
}
return fakeTargetHead.next;
}
}
Largest Rectangle in Histogram
【题目】Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.
【解答】这个题目可以看作是《Maximal Rectangle》中间的一部分，但是它时间上面的要求，要比那道题高得多。因此我一开始使用解那道题里面的办法来解，就超时了：
public class Solution {
public int largestRectangleArea(int[] height) {
if (height==null)
return 0;
int max = 0;
for (int h : height)
if (h>max)
max = h;
int largest = 0;
for (int i=1; i<=max; i++) {
int total = 0;
for (int h : height) {
if (h>=i) {
total += i;
if (total>largest)
largest = total;
} else {
total = 0;
}
}
}
return largest;
}
}
导致超时的 case 是 [0,0,0,0,0,0,0,0,2147483647]，显然，我让 i 从 1 循环到 2147483674，这太不合理了。于是我想，i 不需要循环那么多，只需要循环 height 数组里面的那几个数就可以了，而 height 数组里面的数是可能有重复的，如果 case 有 1000 个 1 怎么办，其实 i 只需要取一次 1 就可以了，因此引入一个 HashSet 来去重：
public class Solution {
public int largestRectangleArea(int[] height) {
if (height==null)
return 0;
Set<Integer> set = new HashSet<>();
for (int h : height)
if (!set.contains(h))
set.add(h);
int largest = 0;
for (int i : set) {
int total = 0;
for (int h : height) {
if (h>=i) {
total += i;
if (total>largest)
largest = total;
} else {
total = 0;
}
}
}
return largest;
}
}
刚才那个 case 确实过了，但是碰到一个巨长无比的 case 又嗝屁了，归根到底这也是个 n 平方的复杂度。在网上这道题我找到了很多解法，有的解法虽然能 AC，但是只是针对 case 做了优化，换一种类型的 case 其实还是会挂，因此并没有从实际上解决问题，但是，看看下面这个办法（来自这个 blog），大致是思路就是从左往右遍历，用一个栈来存储递增的高度序列，如果发现高度递减，停止入栈，并不断出栈以分别计算以之前栈内存放的每个高度作为最终高度的矩形面积。具体解法刚才的 blog 链接上叙述得非常清楚了，图文并茂。这个办法是非常漂亮的，简洁清晰，而且时间复杂度也要低得多。
public class Solution {
public int largestRectangleArea(int[] height) {
Stack<Integer> stk = new Stack<>();
int i = 0;
int maxArea = 0;
while (i <= height.length) {
int currentHeight = 0;
if (i != height.length)
currentHeight = height[i];
if (stk.empty() || height[stk.peek()] <= currentHeight) {
stk.push(i++);
} else {
int t = stk.pop();
maxArea = Math.max(maxArea, height[t] * (stk.empty() ? i : i - stk.peek() - 1));
}
}
return maxArea;
}
}
Jump Game II
【题目】Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
【解答】这个题目在 hard 的题目里算是简单的。在任意一个位置，都存在着当前 jump 数值可达的范围 [x,range]，还存在着该区间的一系列 A[i]+i 所取的最大值 nextRange，当 i>range 时，更新 range 为原 nextRange，并且 jump 数加一。
public class Solution {
public int jump(int[] A) {
if (A.length == 1)
return 0;
int jump = 0;
int range = 0;
int nextRange = 0;
for (int i = 0; i < A.length; i++) {
if (range < i) {
if (i <= nextRange) {
jump++;
range = nextRange;
} else {
return -1; // unreachable
}
}
if (A[i] + i > nextRange)
nextRange = A[i] + i;
if (i == A.length - 1)
return jump;
}
return -1; // impossible
}
}
Interleaving String
【题目】Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
【解答】这道题给我的第一感觉就是使用回溯法，分别从 s1、s2 和 s3 取一个字符，分别命名为 c1、c2 和 c3，如果 c1==c3 而 c2!=c3，那么这个字符从 s1 取；如果 c2==c3 而 c1!=c3，那么字符从 s2 取。麻烦的是 c1==c3 且 c2==c3 的情况，相当于回溯的路径出现了分支，于是我使用一个 stack 来存放分支。最终回溯的路径会是深度优先遍历一棵二叉树。
class Fork {
int i1;
int i2;
int i3;
public Fork(int i1, int i2, int i3) {
this.i1 = i1;
this.i2 = i2;
this.i3 = i3;
}
}
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length()+s2.length()!=s3.length())
return false;
int i1=0, i2=0, i3=0;
Stack<Fork> stack = new Stack<>();
while ((i1<s1.length() && i2<s2.length()) || !stack.isEmpty()) {
char c1 = 0;
char c2 = 0;
char c3 = 0;
if (i1<s1.length())
c1 = s1.charAt(i1);
if (i2<s2.length())
c2 = s2.charAt(i2);
if (i3<s3.length())
c3 = s3.charAt(i3);
if ( c1==0 || c2==0 || (c1!=c3&&c2!=c3) ) {
if (stack.isEmpty())
return false;
Fork fork = stack.pop();
i1 = fork.i1;
i2 = fork.i2;
i3 = fork.i3;
i2++;
i3++;
continue;
}
if (c1==c3 && c2==c3) {
Fork fork = new Fork(i1,i2,i3);
stack.push(fork);
i1++;
i3++;
} else if (c1==c3) {
i1++;
i3++;
} else {
i2++;
i3++;
}
}
while (i1<s1.length()) {
char c1 = s1.charAt(i1);
char c3 = s3.charAt(i3);
if (c1!=c3)
return false;
i1++;
i3++;
}
while (i2<s2.length()) {
char c2 = s2.charAt(i2);
char c3 = s3.charAt(i3);
if (c2!=c3)
return false;
i2++;
i3++;
}
return true;
}
}
但是很快遇到某 case 的时候超时了，仔细分析了一下这个方法，最好的情况下时间复杂度是 n 阶，最坏的情况下时间复杂度达到了 2 的 n 次方阶。
现在换个思路，不是从前往后，而是从后往前想，假如说 result[i][j] 表示 s1 的前 i 个字符形成的子串和 s2 的前 j 个字符形成的子串能否 interleave 成 s3 的前 i+j 个字符形成的子串，那么就有这样的递推关系：
只要 result[i][j – 1] && s2.charAt(j – 1) == s3.charAt(i + j – 1) 或者 result[i – 1][j] && s1.charAt(i – 1) == s3.charAt(i + j – 1) 有一个为真，result[i][j] 就为真。
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != (s2.length() + s1.length()))
return false;
boolean result[][] = new boolean[s1.length() + 1][s2.length() + 1];
result[0][0] = true;
for (int i = 1; i <= s1.length(); i++)
result[i][0] = result[i - 1][0] && (s1.charAt(i - 1) == s3.charAt(i - 1));
for (int j = 1; j <= s2.length(); j++)
result[0][j] = result[0][j - 1] && (s2.charAt(j - 1) == s3.charAt(j - 1));
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
boolean r = result[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
result[i][j] = r || (result[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
}
}
return result[s1.length()][s2.length()];
}
}
再看一下这个方法的复杂度，稳定在 n 的平方。
Insert Interval
【题目】Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
【解答】循环过程中，分三种情况讨论：
- newInterval 在 interval 的右侧，把左侧的 interval 加入 list；
- newInterval 在 interval 左侧，把左侧的 newInterval 加入 list，把原右侧的 interval 置为新的 newInterval；
- newInterval 和 interval 有重叠，这种情况下，构造一个新的 newInterval，覆盖范围为原有 interval 和 newInterval 的并集。
待循环结束，list 里面添加余下的尚未处理的那个 newInterval（因为它在右侧）。
public class Solution {
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> res = new ArrayList<Interval>();
for (Interval interval : intervals) {
if (interval.end < newInterval.start) { // [1,2] _[3,4]_
res.add(interval);
} else if (interval.start > newInterval.end) { // _[1,2]_ [3,4]
res.add(newInterval);
newInterval = interval;
} else if (interval.end >= newInterval.start || interval.start <= newInterval.end) { // [1,3] _[2,4]_ or _[1,3]_ [2,4]
int start = Math.min(interval.start, newInterval.start);
int end = Math.max(newInterval.end, interval.end);
newInterval = new Interval(start, end);
} else {
// unreachable
}
}
res.add(newInterval);
return res;
}
}
Wildcard Matching
【题目】Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
【解答】看到题目以后，第一反应就是通过一个递归函数来解题：
public class Solution {
public boolean isMatch(String s, String p) {
return isMatch(s, 0, p, 0);
}
private boolean isMatch(String s, int si, String p, int pi) {
if (pi==p.length())
return si==s.length();
char cp = p.charAt(pi);
if (si==s.length()) {
if (cp=='*')
return isMatch(s, si, p, pi+1);
return false;
}
char cs = s.charAt(si);
if (cp=='*') {
for (int i=0; i<s.length()-si; i++) {
if (isMatch(s, si+i, p, pi+1))
return true;
}
return false;
} else if (cp=='?') {
return isMatch(s, si+1, p, pi+1);
} else {
if (cs==cp)
return isMatch(s, si+1, p, pi+1);
return false;
}
}
}
然后，在巨长的 case 上面执行超时了。于是想了想，除了星号（*）以外，其它情况的递归都显然可以免去；而如果遇到星号，要比较星号后面的字符，比如 ababccccdddd 去匹配*d，那么遇到星号以后，要看星号后面那个字符，在这里是 d，去源字符串 s 里面找，如果不是 d 的话直接忽略掉，如果是 d 的话继续递归匹配：
public class Solution {
public boolean isMatch(String s, String p) {
return isMatch(s, 0, p, 0);
}
private boolean isMatch(String s, int si, String p, int pi) {
while (pi<p.length()) {
char cp = p.charAt(pi);
if (si==s.length()) {
if (cp=='*')
pi++;
return false;
}
char cs = s.charAt(si);
if (cp=='*') {
pi++;
int minLen = 0;
while (true) {
if (pi==p.length()) {
if (s.length()-si>=minLen)
return true;
else
return false;
}
char cp2 = p.charAt(pi);
if (cp2=='*') {
minLen = 0;
pi++;
} else if (cp2=='?') {
minLen++;
pi++;
} else {
for (int i=si; i<s.length(); i++) {
if (s.charAt(i)==cp2 && i-si>=minLen && isMatch(s, i+1, p, pi+1))
return true;
}
return false;
}
}
} else if (cp=='?') {
si++;
pi++;
} else {
if (cs==cp) {
si++;
pi++;
}
return false;
}
}
return si==s.length();
}
}
可是，遇到某变态 case 继续超时……于是搞了 N 久，最后可行的办法是，利用一个标识是否遇到星号的变量（asterisk），以及额外的两个标识在星号之后在 s 和 p 出现的指针 sa 和 pa，整个大循环的逻辑是：
- 如果 si 和 pi 指向的字符相等，或者 pi 指向了问号，那么，si++，pi++，这两个是基本指针的前进；
- 如果 pi 指向了星号，把 pi 移到星号之后的那个字符，并且把此时是 si 存为 sa，pi 存为 pa；
- 对于余下的情况，考虑在出现过星号的情况，因为两个字符不相等了，那么星号后面那个字符相应的匹配位置需要在 s 中往后移。
注意：在遇到星号的时候要把 pi 和 si 分别赋给 pa 和 sa，而在有星号出现后的未匹配事件发生时，要把 pa 和 sa 赋回给 pi 和 si（相当于 pa 和 sa 占住位置，pi 和 si 往前试探着前行）；另外，循环完毕后，要判断 p 内还有没有非星号的字符，如果有就匹配失败了。
public class Solution {
public boolean isMatch(String s, String p) {
return isMatch(s, 0, p, 0);
}
private boolean isMatch(String s, int si, String p, int pi) {
boolean asterisk = false;
int sa = 0, pa = 0;
while (si < s.length()) {
if (pi == p.length()) {
if (asterisk) {
sa++;
si = sa;
pi = pa;
continue;
} else {
return false;
}
}
char cp = p.charAt(pi);
char cs = s.charAt(si);
if (cp == '*') {
asterisk = true;
pi++;
pa = pi;
sa = si;
} else if (cp == '?') {
si++;
pi++;
} else {
if (cs == cp) {
si++;
pi++;
} else if (asterisk) {
pi = pa;
sa++;
si = sa;
} else {
return false;
}
}
}
for (int i = pi; i < p.length(); i++) {
if (p.charAt(i) != '*')
return false;
}
return true;
}
}
Distinct Subsequences
【题目】Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
【解答】拿到这样的题目，首先，回溯法遍历所有情况肯定是可以做的，但是那样复杂度太高。为了减小复杂度，很容易考虑到使用动态规划。但是动态规划怎么设计递推关系就很重要了：
- 考虑到 S.length()>=T.length()，那么其中一种递推关系是，假设 f(i) 表示 S 的 [0,i) 子串和 T 形成的 distinct 子串数量，那么如果可以找到 f(i+1) 和 f(i) 之间的递推关系就好解了，这是其中一个思路，写出来的 DP 是一维的；
- 也可以假设 f(i,j) 表示的是 S 的 [0,i) 子串和 T 的 [0,j) 子串，需要寻找 f(i,j) 和 f(i-1,j)、f(i,j-1)、f(i-1,j-1) 这样的递推关系，我采用的是这一条思路：
- 如果 S[i]==T[j]，那么当 S[i] 没出现在 T 里面的时候，f(i,j)=f(i-1,j)，当 S[i] 出现在 T 里面，就有 f(i,j)=f(i-1,j-1)，因此，这种情况下 f(i,j) = f(i-1,j) + f(i-1,j-1)；
- 如果 S[i]!=T[j]，那么显然 S[i] 不能出现在 T 里面，于是 f(i,j) = f(i-1,j)。
注意程序出口，当 j 为 0，即 T 变成了空串，序列数就是 1；反过来，当 S 为空串的时候，T 一定是空串，否则 T 的长度大于 S 的长度了。
public class Solution {
public int numDistinct(String S, String T) {
Integer[][] cache = new Integer[S.length()+1][T.length()+1];
return numDistinct(S, T, S.length(), T.length(), cache);
}
private int numDistinct(String S, String T, int i, int j, Integer[][] cache) {
if (cache[i][j]!=null)
return cache[i][j];
if (i>0) {
char sc = S.charAt(i-1);
char st = 0;
if (j>0)
st = T.charAt(j-1);
int prev = numDistinct(S, T, i-1, j, cache);
if (sc!=st || j==0) {
cache[i][j] = prev;
return prev;
} else {
int total = prev + numDistinct(S, T, i-1, j-1, cache);
cache[i][j] = total;
return total;
}
} else {
if (j==0) {
cache[i][j] = 1;
return 1;
} else {
cache[i][j] = 0;
return 0;
}
}
}
}
可是上的解法在某变态 case 的时候出现了 StackOverflowError，通常这种情况下，如果你的编程语言支持尾递归，那可以考虑把它优化成尾递归的形式，如果不支持（比如 Java），那就干脆尝试把它写成循环（其实下面的代码还是显得啰嗦，还可以继续优化，我留着这样是因为在思考过程中把所有分支情况全部写出来了，是最原始的分类讨论的体现，我觉得看起来直白；而且，空间复杂度上面，是可以从 n 平方降到 n 的，因为 i 是一直在增大，之前的数据没有必要保留，每次这个数组保存的都是当前 i 的迭代数据）：
public class Solution {
public int numDistinct(String S, String T) {
if (T.length()==0)
return 1;
if (S.length()==0)
return 0;
int[][] cache = new int[S.length()][T.length()];
for (int i=0; i<S.length(); i++) {
for (int j=0; j<=i && j<T.length(); j++) {
if (S.charAt(i)!=T.charAt(j)) {
if (i>j) { // i!=0
cache[i][j] = cache[i-1][j];
} else {
cache[i][j] = 0;
}
} else {
if (i>j) {
if (j==0)
cache[i][j] = cache[i-1][j] + 1;
else
cache[i][j] = cache[i-1][j] + cache[i-1][j-1];
} else {
if (i==0)
cache[i][j] = 1;
else
cache[i][j] = cache[i-1][j-1];
}
}
}
}
return cache[S.length()-1][T.length()-1];
}
}
Word Break II
【题目】Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
【解答】动态规划求解。判断给定字符串是否以某单词结尾，如果是，就抠掉该结尾单词，余下子串继续递归判断。
public class Solution {
public List<String> wordBreak(String s, Set<String> dict) {
Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
List<String> defaultList = new ArrayList<String>();
defaultList.add("");
map.put(-1, defaultList);
return getAllPossibleSentences(s, dict, s.length()-1, map);
}
private List<String> getAllPossibleSentences(String s, Set<String> dict, int pos, Map<Integer, List<String>> map){
if (map.containsKey(pos))
return map.get(pos);
String sub = s.substring(0, pos+1);
List<String> list = new ArrayList<String>();
for (String word : dict) {
if (sub.endsWith(word)) {
int firstSegEnd = pos - word.length();
if (firstSegEnd<-1) // no solution found
continue;
List<String> subList = getAllPossibleSentences(s, dict, firstSegEnd, map);
for (String str : subList) {
if ("".equals(str))
list.add(word);
else
list.add(str + " " + word);
}
} // if
}// for
map.put(pos, list)
return list;
}
}
First Missing Positive
【题目】Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
【解答】我开始只注意到了 O(n) 的时间复杂度，于是引入一个 HashSet，把所有数往里一放，最后再从 1 开始累加，并挨个检查在 set 里面有没有，要没有就说明找到那个数了：
public class Solution {
public int firstMissingPositive(int[] A) {
Set<Integer> set = new HashSet<>();
for (int a : A)
set.add(a);
int i = 1;
while (i<=A.length) {
if (!set.contains(i))
return i;
i++;
}
return i;
}
}
但是后来看到题目要求常量的额外空间，那我的这个办法其实是错误的。要记录下这些数，又要常量复杂度，只能考虑能不能重用入参数组 A 了，按理说修改参数里面的东西是不会引入空间复杂度的。
对于数组 A，如果所有的 A[i]==i+1 的话，那么说明这些数正好是从 1 开始的连续正整数序列，但是现在有可能有 0，有负数，而正数序列也可能有重复，有断开的地方……但无论怎样，遍历一遍 A，用交换的办法尽可能把每个数都放到该放的地方去，当然，只有大小不超过 A 长度的正整数才能够找到安居之所。即，把 A[i] 放到 A[A[i]-1] 去。这一遍遍历之后，从头开始数，第一个数值和下标对不上（即 A[i]!=i+1）的那个元素的下标，就是要求的 missing positive。
public class Solution {
public int firstMissingPositive(int[] A) {
Set<Integer> set = new HashSet<>();
for (int a : A)
set.add(a);
int i = 1;
while (i<=A.length) {
if (!set.contains(i))
return i;
i++;
}
return i;
}
}
虽说 AC 了，但是粗看我对其中的时间复杂度是否为 n 阶并不确定，看着一个 for 和一个 while 嵌套的。于是我改成了这样：
public class Solution {
public int firstMissingPositive(int[] A) {
int i=0;
while (i<A.length) {
if (A[i]!=(i+1) && A[i]>=1 && A[i]<=A.length && A[A[i]-1]!=A[i]) {
// swap
int temp = A[i];
A[i] = A[temp-1];
A[temp-1] = temp;
} else {
i++;
}
}
for (i=0; i<A.length; i++) {
if (A[i]!=i+1)
return i+1;
}
return A.length+1;
}
}
看着是少了一层嵌套循环，但是其实呢，做法上面换汤不换药，在每次 swap 发生的时候，i 是不前进的，也就是说，对于 A[i]，swap 一次，把 A[i] 换到该去的地方去了，但是换过来一个别的数，而这个新数因为在 A[i] 上，要继续 swap……直到条件不满足，没有继续 swap 的必要，i 才继续前进。但是仔细分析，由于每个到来到 A[i] 的数都去了它应该去的地方，A[i] 去了新地方以后便不会再被换走，因而复杂度确实为 n。不管是写成上面那种形式还是这种形式。
这道题还是有些有趣的。
Word Ladder II
【题目】Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
【解答】这道题刚拿到手的时候觉得挺简单的，BFS。每一层都去 dict 里面寻找所有的单词，如果二者只差一个字母（isNeighbor），就找到结果了。
public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> list = new ArrayList<>();
List<String> ll = new ArrayList<>();
ll.add(start);
list.add(ll);
dict.remove(start);
while (!dict.isEmpty()) {
Set<String> toRemove = new HashSet<>();
List<List<String>> newList = new ArrayList<>();
List<List<String>> matched = new ArrayList<>();
for (List<String> l : list) {
String from = l.get(l.size()-1);
for (String d : dict) {
if (isNeighbor(from, d)) {
toRemove.add(d);
List<String> nl = new ArrayList<>(l);
nl.add(d);
if (d.equals(end))
matched.add(nl);
else
newList.add(nl);
}
}
}
if (!matched.isEmpty())
return matched;
if (toRemove.isEmpty())
return new ArrayList<List<String>>();
dict.removeAll(toRemove);
list = newList;
}
return new ArrayList<List<String>>();
}
private boolean isNeighbor(String s1, String s2) {
boolean dif = false;
for (int i=0; i<s1.length(); i++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(i);
if (c1!=c2) {
if (!dif)
dif = true;
else
return false;
}
}
return true;
}
}
但是很快遇到某 case 就超时了。于是调整一下角度，对每次待匹配的单词，不是去 dict 里面匹配，而是根据该单词的每个字母，都可以变化成任意一个其它字母的规则，因为那样每次都形成一个新单词，再拿这个新单词到 dict 里面去寻找是否有匹配：
public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> list = new ArrayList<>();
List<String> ll = new ArrayList<>();
ll.add(start);
list.add(ll);
dict.remove(start);
while (!dict.isEmpty()) {
Set<String> toRemove = new HashSet<>();
List<List<String>> newList = new ArrayList<>();
List<List<String>> matched = new ArrayList<>();
for (List<String> l : list) {
String from = l.get(l.size()-1);
for (int i=0; i<from.length(); i++) {
for (char ch='a'; ch<='z'; ch++) {
char[] cs = from.toCharArray();
if (cs[i]!=ch)
cs[i] = ch;
String ns = new String(cs);
if (dict.contains(ns)) {
toRemove.add(ns);
List<String> nl = new ArrayList<>(l);
nl.add(ns);
if (ns.equals(end))
matched.add(nl);
else
newList.add(nl);
}
}
}
}
if (!matched.isEmpty())
return matched;
if (toRemove.isEmpty())
return new ArrayList<List<String>>();
dict.removeAll(toRemove);
list = newList;
}
return new ArrayList<List<String>>();
}
}
结果出现了 Memory Limit Exceeded。怎么办呢？忽然想到了对于这种搜索的改进，从 start 开始的单向搜索可以优化成从 start 和 end 两头一起往中间搜索这样的双向搜索形式，理论上可以减少 BSF 最宽一层的节点数量（代码看起来有点长，但是其实逻辑并不复杂）：
public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
// forward list
List<List<String>> list = new ArrayList<>();
List<String> ll = new ArrayList<>();
ll.add(start);
list.add(ll);
dict.remove(start);
// backward list
List<List<String>> backList = null;
List<List<String>> matched = new ArrayList<>();
while (!dict.isEmpty()) {
// 1. forward bfs
Set<String> toRemove = new HashSet<>();
List<List<String>> newList = new ArrayList<>();
for (List<String> l : list) {
String from = l.get(l.size()-1);
for (int i=0; i<from.length(); i++) {
for (char ch='a'; ch<='z'; ch++) {
char[] cs = from.toCharArray();
if (cs[i]!=ch)
cs[i] = ch;
String ns = new String(cs);
if (dict.contains(ns)) {
toRemove.add(ns);
List<String> nl = new ArrayList<>(l);
nl.add(ns);
if (ns.equals(end))
matched.add(nl);
else
newList.add(nl);
}
}
}
}
if (!matched.isEmpty() || toRemove.isEmpty())
return matched;
dict.removeAll(toRemove);
list = newList;
// 2. backward bfs
if (backList==null) {
backList = new ArrayList<>();
ll = new ArrayList<>();
ll.add(end);
backList.add(ll);
dict.remove(end);
}
newList = new ArrayList<>();
toRemove.clear();
for (List<String> bl : backList) {
String b = bl.get(0);
for (String s : dict) {
if (isNeighbor(b, s)) {
toRemove.add(s);
List<String> nl = new ArrayList<>(bl);
nl.add(0, s);
newList.add(nl);
}
}
}
if (toRemove.isEmpty())
return matched;
dict.removeAll(toRemove);
backList = newList;
// 3. match
for (List<String> l : list) {
for (List<String> bl : backList) {
String s1 = l.get(l.size()-1);
String s2 = bl.get(0);
if (isNeighbor(s1, s2)) {
List<String> nl = new ArrayList<>(l);
nl.addAll(bl);
matched.add(nl);
}
}
}
if (!matched.isEmpty())
return matched;
}
return new ArrayList<List<String>>();
}
private boolean isNeighbor(String s1, String s2) {
boolean dif = false;
for (int i=0; i<s1.length(); i++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(i);
if (c1!=c2) {
if (!dif)
dif = true;
else
return false;
}
}
return true;
}
}
代码真是复杂不少，遗憾的是，继续 Memory Limit Exceeded，服了，这条路看来是走不通了。从网上搜索，有各种解法，都挺复杂的。下面列出的这个方法是从这个博客上面摘录下来的，属于思路上相对比较清晰的做法了。整个过程拆成两步，BFS 来构造表示单词变化关系的树，DFS 来最后搜索路径。从宏观的复杂度上看，比我最原始的做法节约就节约在对路径 list 的遍历上面，我的做法因为要遍历路径的 list，导致循环嵌套多了一层，但是这里使用一个 map 存放每个节点和下一层的对应关系，省下了这层循环，当然，最后需要额外的 DFS 来构造这个 list。虽说如此，我还是觉得方法不够优雅简洁，如果你有清晰简洁的方法，请告诉我。
public class Solution {
class WordWithLevel {
String word;
int level;
public WordWithLevel(String word, int level) {
this.word = word;
this.level = level;
}
}
private String end;
private ArrayList<ArrayList<String>> result;
private Map<String, List<String>> nextMap;
public ArrayList<ArrayList<String>> findLadders(String start, String end,
HashSet<String> dict) {
result = new ArrayList<ArrayList<String>>();
this.end = end;
// unvisited words set
Set<String> unVisited = new HashSet<String>();
unVisited.addAll(dict);
unVisited.add(start);
unVisited.remove(end);
// used to record the map info of <word : the words of next level>
nextMap = new HashMap<String, List<String>>();
for (String e : unVisited) {
nextMap.put(e, new ArrayList<String>());
}
// BFS to search from the end to start
Queue<WordWithLevel> queue = new LinkedList<WordWithLevel>();
queue.add(new WordWithLevel(end, 0));
boolean found = false;
int finalLevel = Integer.MAX_VALUE;
int currentLevel = 0;
int preLevel = 0;
Set<String> visitedWordsInThisLevel = new HashSet<String>();
while (!queue.isEmpty()) {
WordWithLevel wordWithLevel = queue.poll();
String word = wordWithLevel.word;
currentLevel = wordWithLevel.level;
if (found && currentLevel > finalLevel) {
break;
}
if (currentLevel > preLevel) {
unVisited.removeAll(visitedWordsInThisLevel);
}
preLevel = currentLevel;
char[] wordCharArray = word.toCharArray();
for (int i = 0; i < word.length(); ++i) {
char originalChar = wordCharArray[i];
boolean foundInThisCycle = false;
for (char c = 'a'; c <= 'z'; ++c) {
wordCharArray[i] = c;
String newWord = new String(wordCharArray);
if (c != originalChar && unVisited.contains(newWord)) {
nextMap.get(newWord).add(word);
if (newWord.equals(start)) {
found = true;
finalLevel = currentLevel;
foundInThisCycle = true;
break;
}
if (visitedWordsInThisLevel.add(newWord)) {
queue.add(new WordWithLevel(newWord,
currentLevel + 1));
}
}
}
if (foundInThisCycle) {
break;
}
wordCharArray[i] = originalChar;
}
}
if (found) {
// dfs to get the paths
ArrayList<String> list = new ArrayList<String>();
list.add(start);
getPaths(start, list, finalLevel + 1);
}
return result;
}
private void getPaths(String currentWord, ArrayList<String> list, int level) {
if (currentWord.equals(end)) {
result.add(new ArrayList<String>(list));
} else if (level > 0) {
List<String> parentsSet = nextMap.get(currentWord);
for (String parent : parentsSet) {
list.add(parent);
getPaths(parent, list, level - 1);
list.remove(list.size() - 1);
}
}
}
}
Find Minimum in Rotated Sorted Array II
【题目】
Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
【解答】解这个题目，先简化一下条件，不考虑 duplicates 存在的情况，那么任意两个元素都不相等，通过比对 num[left]、num[mid] 和 num[right] 会得出三种可能的大小关系组合，用具体例子来说就是：
- num[left]
- num[left]num[right]，比如 3 4 5 1 2；
- num[left]>num[mid] && num[mid]
在这之后，再考虑存在 duplicates 的情况。这样就不容易遗留可能性。另外，需要注意两个特殊情况：
- 一种最特殊的情况是 num[left]、num[mid] 和 num[right] 三者全部相等，这个时候就完全不知道这个 pivot 到底在左半支还是右半支，这时候只能 left 右移并 right 左移，一点一点缩小范围。所以最坏情况下时间复杂度是 n。
- 还有一个要注意的是，当 left 和 right 只相差 1 的时候，mid==left，如果再走到 left=mid 赋值的分支里面，就会死循环，为了避免这种情况发生，需要处理好这种情况。
public class Solution {
public int findMin(int[] num) {
int left = 0;
int right = num.length-1;
while (left<right-1) {
int mid = (right+left)/2;
if (num[left]num[mid]) {
return num[left];
} else if (num[right]num[mid]) { // 4 5 1 2 3
if (num[mid]num[right]) {
// impossible
throw new RuntimeException("Impossible...");
} else { // num[mid]==num[right]
right = mid;
}
} else {
if (num[right]==num[mid]) {
left++;
right--;
} else {
left = mid;
}
}
}
return Math.min(num[left], num[right]);
}
}
Regular Expression Matching
【题目】Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
【解答】点号和星号的含义和正则表达式一致。注意”abc”.matches(“.*”) 是返回 true 的，换言之，”.*” 可以代表任何字符串，空串也可以。我原来的做法是尝试使用在 DP 中分类讨论的办法，包括分成”a”、”.a”、”a*”、”.*” 这几种情况分别处理，代码写得冗长，做到一半自己都搞晕了。本来想继续沿着 DP 的思路走下去，但是看到下面的这个做法（来自于这里）以后，我觉得我原来的思路太弱了。下面这个做法是我目前看到的解法最简洁漂亮的代码，整个过程也不需要用额外的空间来存储重复计算的结果。思路是，把各种情况分成这样两种：
- p 的第二个字符（p[1]）不是星号，在这种情况下，如果第一个字符 p[0] 是星号，或者 p[0]==s[0]，那就可以继续递归匹配余下的子串，否则返回匹配失败；
- p 的第二个字符（p[1]）是星号，在这种情况下，通过一个 i 来表示”.*” 或者”a*” 管住的那段 S 子串的结束位置（即 s 中的子串 [0,i]），i 之后的子串和 p 去掉开头的这个”.*” 或者”a*” 后余下的子串继续参与后续的匹配，匹配上了皆大欢喜，匹配不上则令 i 前进。
public class Solution {
public boolean isMatch(String s, String p) {
if (p.length() == 0)
return s.length() == 0;
if (p.length() == 1 || p.charAt(1) != '*') {
// empty s or unmatch
if (s.length() < 1 || (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)))
return false;
return isMatch(s.substring(1), p.substring(1));
} else {
int i = -1;
// match
while (i < s.length() && (i < 0 || p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))) {
if (isMatch(s.substring(i + 1), p.substring(2)))
return true;
i++;
}
return false;
}
}
}
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
博主水平不是一般的高
非常感谢！！ 最近在刷题准备校招~ 您的讲解，通俗易懂，非常非常赞~
非常感谢！！ 最近在刷题准备校招~
非常感谢博主，正在学习 java，搜答案找进来的。