[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于 tricky 的方法。我没有为了这个再更新，就让它们去吧。
以下是 LeetCode 题目中 Medium 部分的上半部分，点击表格中的名称进入题目和解答。我计划把 LeetCode 我的解答分成四个部分发上来，这是第二部分。做这些题目收获还是挺大的。
Divide Two Integers
【题目】Divide two integers without using multiplication, division and mod operator.
【解答】不能用乘除和取模，但是还是可以用加减和左移的嘛，第一遍循环先找到最高位，看到底要左移多少；第二遍循环从最高位开始，不断除以 2 的幂。
有一些需要特殊考虑的 case，比如说：
- 符号问题；
- 整型溢出问题，使用 Math.abs 方法要当心，如果数值是-2147483648 的话，由于溢出的关系，取绝对值的结果还是它自己，所以在取绝对值之前先给转成了 long；
- 2 的 x 次方，就左移 x 位好了，但是当 x=0 需要特殊处理。
public class Solution {
public int divide(int dividend, int divisor) {
boolean sign = (dividend < 0 && divisor < 0)
|| (dividend >= 0 && divisor >= 0);
long dividendL = Math.abs((long)dividend);
long divisorL = Math.abs((long)divisor);
int res = 0;
int move = 0;
while (true) {
if ((divisorL << move) > dividendL) { // found the highest digit
break;
}
move++;
} // while
long temp = dividendL;
for (int i = move - 1; i >= 0; i--) {
long newDivisor = divisorL << i;
if (temp - newDivisor < 0)
continue;
temp -= newDivisor;
if (i == 0)
res += 1;
else
res += 2 << (i - 1);
}
if (!sign)
res = -res;
return res;
}
}
3Sum
【题目】Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
【解答】首先要排序，排序之后就可以利用数规律的排列简化计算。由于要求最终结果是 0，最开始我的办法是分为 0、负数和正数来讨论，结果写出了答案，却很复杂。但是实际上并不需要考虑 0 这个特殊值，其实给定任意一个数，都有类似的做法：使用双指针，一个 left，一个 right，前者从最左侧开始，只能向右移动；后者相反，从最右侧开始，只能向左移动。如果 sum 大于目标值，那么 right 左移；如果 sum 小于目标值，那么 left 右移。
从 0 推广到任意数是如此计算，从三个数推广到四个数还是如此计算。
另外，需要注意去重，可以利用一个 HashSet 来去重，也可以在每次指针移动之后比较最新值和前一个值，如果一样就跳过：
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
List<List<Integer>> list = new ArrayList<>();
if (num.length<3)
return list;
Arrays.sort(num);
for (int i=0; i<num.length-2; i++) {
if(i!=0 && num[i]==num[i-1])
continue;
int left = i+1;
int right = num.length-1;
while (left<right) {
if (left>i+1 && num[left]==num[left-1]) {
left++;
continue;
}
if (right<num.length-2 && num[right]==num[right+1]) {
right--;
continue;
}
int sum = num[i] + num[left] + num[right];
if (sum==0) {
List<Integer> item = new ArrayList<>();
item.add(num[i]);
item.add(num[left]);
item.add(num[right]);
list.add(item);
left++;
right--;
} else if (sum>0) {
right--;
} else {
left++;
}
} // while
} // for
return list;
}
}
Evaluate Reverse Polish Notation
【题目】Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
【解答】就是逆波兰式求解，利用一个栈可以搞定。注意从栈里面 pop 出来的时候，先出来那个是运算符右边的数，再出来的才是左边的：
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (token.matches("[+-]{0,1}\\d+")) {
stack.push(Integer.parseInt(token));
} else {
int right = stack.pop();
int left = stack.pop();
int result;
if ("+".equals(token))
result = left + right;
else if ("-".equals(token))
result = left - right;
else if ("*".equals(token))
result = left * right;
else
result = left / right;
stack.push(result);
}
}
if (stack.isEmpty())
return 0;
return stack.pop();
}
}
Find Minimum 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).
Find the minimum element.
You may assume no duplicate exists in the array.
【解答】就是挨个遍历，复杂度也只有 n 阶，但是还是可以利用类似二分法来找到最小值。通过二分的时候，最左值与中间值大小的比较，有这么两种情况：
- 最左值≤中间值，这意味着要么最左值就是最小值，要么最小值在右半边；
- 最左值> 中间值，这意味着最大最小值都在左半边。
public class Solution {
public int findMin(int[] num) {
if (num.length==0)
return num[0];
int left=0;
int right=num.length-1;
int min = Integer.MAX_VALUE;
while (left<right) {
int mid = (left+right)/2;
if (left==mid)
break;
// 3 4 5 6 2, left part is equal or ascending, so for this part num[left] is the smallest
if(num[left]<=num[mid]) {
if (num[left]<min)
min = num[left];
left= mid+1;
}
// 5 6 1 2 3, both min and max value are in left part
else {
if (num[mid]<min)
min = num[mid];
right = mid-1;
}
}
if (num[right]<min)
min = num[right];
if (num[left]<min)
min = num[left];
return min;
}
}
Word Search
【题目】Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[ ["ABCE"], ["SFCS"], ["ADEE"] ]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
【解答】这个题目很像贪吃蛇，找一条路径，并且不能碰到自己，类似这种找路径的问题，包括迷宫之类的，都可以考虑回溯法解决。回溯法基本上就这几个步骤：
- 找出发点；
- 按约定选一个方向前进，当前位置入栈；
- 没有路了就后退，出栈；
- 按约定寻找下一个方向前进。
如果是递归的回溯法，这个栈可以免去，递归工作栈来代替。这道题使用一个二维数组 used 来存放位置是否走过的信息，参数 from 的取值 1、2、3、4 分别表示从上方、左边、下方、右边来到当前位置，这样在寻找下一个位置的时候，过来的路线直接跳过。下面的解答需要注意的地方是，在每个位置，递归调用 exist 方法前，要把下一个位置的状态（现场）保存下来，等到调用完毕之后，要恢复现场。
public class Solution {
public boolean exist(char[][] board, String word) {
if (word.length() == 0)
return true;
for (int i = 0; i < board.length; i++)
for (int j = 0; j < board[0].length; j++)
if (word.charAt(0) == board[i][j]
&& exist(board, word, 0, i, j,
new boolean[board.length][board[0].length], 0))
return true;
return false;
}
private boolean exist(char[][] board, String word, int pos, int i, int j,
boolean[][] used, int from) {
if (pos == word.length())
return true;
if (used[i][j] || board[i][j] != word.charAt(pos))
return false;
// for special case, {{'a'}}, "a"
if (pos == word.length() - 1)
return true;
// mark it used
used[i][j] = true;
boolean temp;
// up
if (i > 0 && from != 1) {
temp = used[i - 1][j];
if (exist(board, word, pos + 1, i - 1, j, used, 3))
return true;
used[i - 1][j] = temp; // roll back
}
// left
if (j > 0 && from != 2) {
temp = used[i][j - 1];
if (exist(board, word, pos + 1, i, j - 1, used, 4))
return true;
used[i][j - 1] = temp; // roll back
}
// down
if (i < board.length - 1 && from != 3) {
temp = used[i + 1][j];
if (exist(board, word, pos + 1, i + 1, j, used, 1))
return true;
used[i + 1][j] = temp; // roll back
}
// right
if (j < board[0].length - 1 && from != 4) {
temp = used[i][j + 1];
if (exist(board, word, pos + 1, i, j + 1, used, 2))
return true;
used[i][j + 1] = temp; // roll back
}
return false;
}
}
Word Ladder
【题目】Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
【解答】这个题目看起来是要找一条 path，使得可以从 start 走到 end，再看发现其实是一个关于广度优先搜索的题目：
- 这棵树从 start 开始，每一个在词典里面的词如果变化一个字母，派生成的那个新词还在词典里面，那就可以看做那个新词就是老词的一个子节点；
- 这棵树一层一层往下生长，每生长一层，距离就要+1；
- 每找到一个在词典里的词，就要把它从词典里面删掉，这样可以保证词典里面每一个词出现在这棵树上的时候，距离都是尽可能小的；
- 直到发现 end 在新长出来的叶子节点里面，就算找到了；
- 如果词典里面都没词了还没找到，那就说明不存在这样的路径。
具体代码需要注意的地方包括，如果对一个普通的 HashSet/HashMap 元素遍历的期间，对其 add 一个新元素，会抛出 java.util.ConcurrentModificationException，所以这个问题需要避免：
class Node {
public String word;
public int distance;
public Node(String word, int distance) {
this.word = word;
this.distance = distance;
}
}
public class Solution {
public int ladderLength(String start, String end, Set<String> dict) {
if (start.equals(end))
return 1;
Set<Node> set = new HashSet<Node>();
set.add(new Node(start, 1));
while (!dict.isEmpty()) {
// use newSet to avoid java.util.ConcurrentModificationException
Set<Node> newSet = new HashSet<Node>();
for (Node node : set) {
for (int i = 0; i < node.word.length(); i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
char[] arr = node.word.toCharArray();
arr[i] = ch;
String newWord = new String(arr);
if (end.equals(newWord))
return node.distance + 1;
if (dict.contains(newWord)) {
dict.remove(newWord);
newSet.add(new Node(newWord, node.distance + 1));
}
} // for: 'a'~'z'
} // for: word[i]
} // for: nodes
if (newSet.isEmpty())
return 0;
set = newSet;
} // while
return 0;
}
}
另外，我还找到了一个更快一些的办法，是从 start 和 end 两边搜索，因为一棵树越接近根的地方越小，在生长的时候每一层的叶子节点的循环次数就越小，具体分析在这篇文章里（下图来自该文章）：
Flatten Binary Tree to Linked List
【题目】Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
【解答】观察一下规律，其实就是先序遍历：
public class Solution {
public void flatten(TreeNode root) {
if (root != null)
traverse(root);
}
private TreeNode traverse(TreeNode root) {
TreeNode right = root.right;
TreeNode left = root.left;
TreeNode tail = root;
root.left = null;
root.right = null;
if (null != left) {
root.right = left;
tail = traverse(left);
}
if (null != right) {
tail.right = right;
tail = traverse(root.right);
}
tail.left = null;
tail.right = null;
return tail;
}
}
Gas Station
【题目】There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
【解答】这道题我一开始看到，很快就写出来了，提交了，也提示 Accepted，但是复杂度是 n 平方的：
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for (int start=0; start<gas.length; start++) {
int g = 0;
int i = start;
boolean flag = false;
do {
if (flag && i==start)
return start;
flag = true;
g += gas[i];
g -= cost[i];
if (i==gas.length-1)
i=0;
else
i++;
} while (g>=0);
}
return -1;
}
}
但是，我老婆看了我的答案说，人家可是用 O(n) 来做的。
那，这还能再优化么？
回过头来看一下问题，冠冕堂皇地搞了一个 gas 数组，又搞了一个 cost 数组，其实，对于环上的每一个点 i 而言，我关心的只有 gas[i]-cost[i] 而已，我把它定义为 diff[i]。
1. 显而易见的一点是，假设 sum(p,q) 表示从 diff[p] 到 diff[q] 这些项求和，那么如果 p 为 0，q 为 n-1，即所有的数之和如果小于零的话，sum(0, n-1) = ∑diff[i]<0（i∈[0, n-1]），根本是无法做到有一点让轿车跑一圈的。
那么对于这个和大于 0 的情况，如何找到这一个出发点呢？
2. 这个出发点假设是 k 的话，我可以说，那么对于 k 前面的任意一点 p，sum(p,k-1) 必须满足 sum(p,k-1)<0，否则的话，一定可以从 [p,k-1] 中找到一点，作为新的出发点，这个出发点可以使得也一样可以成功绕一圈，而注意到题中提示，“The solution is guaranteed to be unique.”，既然只有一个解，那么这个点就只能不存在了。所以可以得到：对于 k 前面的任意一点 p，sum(p,k-1) 必须满足 sum(p,k-1)<0，现在取 p=0，即所有的 sum(0,k-1) 全部小于零。
3. 再来看 k 后面的情况，对于 k 后面的任意一点 q，一定有 sum(k+1,q)≥0，否则的话，从 k+1 到 q 就走不了了。
有了上面 1~3 点的分析，有点绕，但是想清楚了代码就很简单了：
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0;
int sum = 0;
int start = 0;
for (int i=0; i<gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
sum += diff;
if (sum<0) {
sum = 0;
start = i+1;
}
}
if (total<0)
return -1;
return start;
}
}
Generate Parentheses
【题目】Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
【解答】有几种方法可以解这道题，我觉得最容易理解的方式是这样，以自然的方式，从左到右写出这一堆括号来，每次下笔都有两种选择，要么写左括号，要么写右括号，具体说，每一次下笔都必须满足这样的条件：
- 写过的左括号次数必须小于 n，那就可以写左括号；
- 写过的右括号次数必须小于 n，并且也小于左括号次数，那就可以写右括号。
写成代码就是：
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
append(n, 0, 0, "", list);
return list;
}
private void append(int n, int left, int right, String s, List<String> list) {
if (left==n && right==n) {
list.add(s);
return;
}
if (left<n) {
append(n, left+1, right, s+'(', list);
}
if (right<n && left>right) {
append(n, left, right+1, s+')', list);
}
}
}
当然，也有其它的解法，比如说，考虑递推式，在 n=k 的时候，我有一个括号的序列合集，现在当 n=k+1 的时候，我要给这堆括号的序列合集里面加上一组新的括号，可以用动态规划来解，但是这样的解法要复杂一些。
Gray Code
【题目】The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0 01 - 1 11 - 3 10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
【解答】格雷码，先去读了读维基百科，在注意到它的生成规则具备镜像特性以后，问题就好办了：
public class Solution {
public List<Integer> grayCode(int n) {
if (n==0){
List<Integer> list = new ArrayList<Integer>();
list.add(0);
return list;
}
List<String> list = strGrayCode(n);
return convert(list);
}
private List<Integer> convert(List<String> list){
List<Integer> ret = new ArrayList<Integer>();
for (String str : list) {
int sum = 0;
for (int i=0; i<str.length(); i++) {
char bit = str.charAt(i);
if (bit=='1')
sum += 1<<(str.length()-1-i); //Math.pow(2, x);
}
ret.add(sum);
}
return ret;
}
private List<String> strGrayCode(int n) {
if (n==1) {
List<String> list = new ArrayList<String>();
list.add("0");
list.add("1");
return list;
}
List<String> list = strGrayCode(n-1);
List<String> newList = new ArrayList<String>();
for (int i=0; i<list.size() ;i++) {
newList.add("0"+list.get(i));
}
for (int i=list.size()-1; i>=0 ;i--) {
newList.add("1"+list.get(i));
}
return newList;
}
}
Word Break
【题目】Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
【解答】动态规划，对于字符串 [0,i) 取子串，如果子串 [0,k) 存在解，而 [k,i) 又在字典里面的话，那么 [0,i) 就是有解的：
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
// boolean 数组 mem[i] 表示 [0,i) 是否存在通路（0<=i<=str.length）
boolean[] mem = new boolean[s.length()+1];
mem[0] = true;
// mem[i] = {所有 mem[k] && ([k,i)∈dict) 中只要有一个为 true，就为 true}（其中 0<=k<i）
for (int i=0; i<=s.length(); i++) {
for (int k=0; k<i; k++) {
String str = s.substring(k, i);
mem[i] = mem[k] && dict.contains(str);
if (mem[i])
break;
}
}
return mem[s.length()];
}
}
Validate Binary Search Tree
【题目】Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
【解答】递归检查。对每一个节点都尝试寻找左孩子的最小值作为以该节点为根的树的最小值；对每一个节点都尝试寻找右孩子的最大值作为以该节点为根的树的最大值。对于非法的 BST，也没有必要继续执行下去了，抛出 InvalidBSTException 异常。使用异常机制就可以免去定义一个表示非法 BST 的特殊返回值来特殊处理。
class InvalidBSTException extends RuntimeException {
}
public class Solution {
public boolean isValidBST(TreeNode root) {
if (null==root)
return true;
try {
validateBST(root);
} catch (InvalidBSTException e) {
return false;
}
return true;
}
private int maxValueOfValidBST(TreeNode root) {
validateBST(root);
if (root.right!=null) {
return maxValueOfValidBST(root.right);
}
return root.val;
}
private int minValueOfValidBST(TreeNode root) {
validateBST(root);
if (root.left!=null) {
return minValueOfValidBST(root.left);
}
return root.val;
}
private void validateBST(TreeNode root) {
if (root.left!=null) {
int maxLeft = maxValueOfValidBST(root.left);
if (maxLeft>=root.val)
throw new InvalidBSTException();
}
if (root.right!=null) {
int minRight = minValueOfValidBST(root.right);
if (minRight<=root.val)
throw new InvalidBSTException();
}
}
}
Insertion Sort List
【题目】Sort a linked list using insertion sort.
【解答】引入一个假的哨兵节点，放在头上，这样每次在插入节点的时候，就不需要单独判断新插入的那个节点是不是 head，代码简单一些：
public class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode fakeHead = new ListNode(Integer.MIN_VALUE);
ListNode cur = head;
while (cur!=null) {
ListNode next = cur.next;
insert(fakeHead, cur);
cur = next;
}
return fakeHead.next;
}
private void insert(ListNode fakeHead, ListNode cur) {
ListNode node = fakeHead;
while (node.next!=null && node.next.val<cur.val)
node = node.next;
cur.next = node.next;
node.next = cur;
}
}
Integer to Roman
【题目】Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
【解答】刚开始我想寻找罗马数字的规则，罗马数字计数法讨厌的地方在于，有的数的表示不是通过 “加”，而是通过 “减” 来实现的，比如 4，是 5-1：IV。最后代码需要考虑字符串生长的方向，写得很复杂，还有些 case 是错误的。
重新在草稿上写了一些罗马数字，发现这些 “减” 的情况极其有限，说白了，就只有 4（IV）、9（IX）、40（XL）、90（XC）、400（CD）和 900（CM），这几个特殊情况，再加上罗马字母本身的字符，就足以枚举出从 1 到 3999 所有的情况了：
public class Solution {
public String intToRoman(int num) {
Map<Integer, String> map = new HashMap<>();
map.put(1, "I");
map.put(4, "IV");
map.put(5, "V");
map.put(9, "IX");
map.put(10, "X");
map.put(40, "XL");
map.put(50, "L");
map.put(90, "XC");
map.put(100, "C");
map.put(400, "CD");
map.put(500, "D");
map.put(900, "CM");
map.put(1000, "M");
int enums[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String result = "";
for (int i=0; i<enums.length; i++) {
int quotient = num/enums[i];
num = num%enums[i];
for(int j=1; j<=quotient; j++)
result += map.get(enums[i]);
}
return result;
}
}
代码一下子很简单，有豁然开朗的感觉。所以，数学题目做多了也会把一些简单的问题复杂化。要去根据数的大小分类，考虑情况讨论就陷进去了。
4Sum
【题目】Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
【解答】其实有了前面 3Sum 的基础，这道题就很好做了，只不过在 3Sum 的基础上外面多套一层循环而已：
public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
List<List<Integer>> list = new ArrayList<List<Integer>>();
for (int i = 0; i <= num.length - 3; i++) {
if (i != 0 && num[i] == num[i-1])
continue;
for (int j = i + 1; j <= num.length - 2; j++) {
if (j != i + 1 && num[j] == num[j-1])
continue;
int left = j + 1, right = num.length - 1;
while (left < right) {
if (left != j + 1 && num[left] == num[left-1]) {
left++;
continue;
}
if (right != num.length - 1 && num[right] == num[right+1]) {
right--;
continue;
}
int sum = num[i] + num[j] + num[left] + num[right];
if (sum == target) {
List<Integer> item = new ArrayList<Integer>();
item.add(num[i]);
item.add(num[j]);
item.add(num[left]);
item.add(num[right]);
list.add(item);
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
} // while
} // for:j
} // for: i
return list;
}
}
Jump Game
【题目】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.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
【解答】这题看起来很容易，我最开始的思路是建立一个用作 DP 的 reachable 数组，然后从 A 的最左侧开始遍历，对于 A 中每一个元素，所代表的能遍历到的后面的元素全部把 reachable 全部置为 true，但是遇到 A 很大的某一个变态 case 的时候，执行超时了。
所以就着这个思路改进一下，其实对于每一个可达的 A 中的元素来说，都可以唯一确定一个下一步可以达到的最大的范围，如果这个最大范围包含了 A 数组的末尾，那就返回 true：
public class Solution {
public boolean canJump(int[] A) {
int end = 0;
for (int i=0; i<A.length; i++) {
if (i>end)
continue;
if (A[i]+i > end)
end = A[i]+i;
if (end>=A.length-1)
return true;
}
return false;
}
}
Add Two Numbers
【题目】You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
【解答】处理好进位就好了：
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode n1 = l1;
ListNode n2 = l2;
ListNode head = null;
ListNode result = null;
while (n1!=null || n2!=null) {
int sum = carry;
if (n1!=null) {
sum += n1.val;
n1 = n1.next;
}
if (n2!=null) {
sum += n2.val;
n2 = n2.next;
}
if (sum/10>0)
carry = 1;
else
carry = 0;
sum = sum % 10;
ListNode item = new ListNode(sum);
if (result==null) {
head = item;
}
else {
result.next = item;
}
result = item;
}
if (carry!=0)
result.next = new ListNode(1);
return head;
}
}
Anagrams
【题目】Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
【解答】Anagram——我也是查到的含义，anagram 是一个中文里没有的概念（因为中文由字、而非字母组成），指一个单词、短语或句子经过字母重组后产生出来的另一个单词，短语或句子。比如，won 是 now 的 anagram，satin 是 stain 的 anagram，a net 是 neat 的 anagram。
知道这个以后，只要保证同样字母组成的词语能够被放到一起统计就好了，引入一个 HashMap，让每个词里面的字符数组按照字母顺序重新排好序，这构成的新词就可以拿来当做 key 了：
public class Solution {
public List<String> anagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] arr = str.toCharArray();
Arrays.sort(arr);
String s = new String(arr);
if (!map.containsKey(s))
map.put(s, new ArrayList<String>());
map.get(s).add(str);
}
List<String> list = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : map.entrySet()) {
if (entry.getValue().size()>1) {
list.addAll(entry.getValue());
}
}
return list;
}
}
Decode Ways
【题目】A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
【解答】用一个数组来帮助 DP，区分两位数表示的字母和一位数表示的字母这两种可能性：
public class Solution {
public int numDecodings(String s) {
if (null==s || "".equals(s))
return 0;
int[] arr = new int[s.length()];
int prev = '0';
for (int i=0; i<s.length(); i++) {
int ch = s.charAt(i);
int count = 0;
// two digits
int num = 10*(prev-'0') + (ch-'0');
int c = 'A'+num-1;
int prevC = 'A'+(prev-'0')-1;
if (c>='A' && c<='Z' && prevC>='A' && prevC<='Z') {
if (i>1)
count += arr[i-2];
else if(i==1)
count += 1;
}
// one digit
c = 'A'+(ch-'0')-1;
if (c>='A' && c<='Z') {
if (i>0)
count += arr[i-1];
else
count += 1;
}
if (count==0)
return 0;
arr[i] = count;
prev = ch;
}
return arr[s.length()-1];
}
}
Letter Combinations of a Phone Number
【题目】Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
【解答】注意入参为空字符串的情况，还有电话上面按键 1 这两个特殊的情况的处理就好了：
public class Solution {
public List<String> letterCombinations(String digits) {
List<char[]> list = new ArrayList<>();
list.add(new char[]{' '});
list.add(new char[]{});
list.add(new char[]{'a','b','c'});
list.add(new char[]{'d','e','f'});
list.add(new char[]{'g','h','i'});
list.add(new char[]{'j','k','l'});
list.add(new char[]{'m','n','o'});
list.add(new char[]{'p','q','r','s'});
list.add(new char[]{'t','u','v'});
list.add(new char[]{'w','x','y','z'});
List<String> ret = new ArrayList<>();
ret.add("");
return build(ret, list, digits, 0);
}
private List<String> build(List<String> ret, List<char[]> list, String digits, int pos) {
if (pos==digits.length())
return ret;
int num = digits.charAt(pos) - '0';
char[] chs = list.get(num);
if (chs.length==0)
return ret;
List<String> newRet = new ArrayList<>();
for (char c : chs) {
for (String str : ret) {
newRet.add(str+c);
}
}
return build(newRet, list, digits, pos+1);
}
}
Linked List Cycle
【题目】Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
【解答】准备一个快指针和一个慢指针，慢指针每次走一步，快指针每次走两步，如果他们俩碰上，那就存在环；如果走完了也没碰上，那就不存在环：
public class Solution {
public boolean hasCycle(ListNode head) {
if(null==head)
return false;
ListNode first = head, second = head;
while (true) {
if(null==first.next || null==first.next.next)
return false;
first = first.next.next;
second = second.next;
if(first==second)
return true;
}
}
}
Linked List Cycle II
【题目】Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
【解答】问题基于 Linked List Cycle，快慢两个指针的模式依然保留。下面这个复杂度低，比较好的解法来自水中的鱼的这篇博客，具体原理其中已经说得非常清楚了。大致的思路，如果在图上画一画，会清楚起来：
- 快指针每次走两步，慢指针每次走一步，快慢两个指针第一次碰面以后，让慢指针退回起点；
- 然后快指针和慢指针每次都走一步，它们碰面的地方，就是这个环的入口。
public class Solution {
public ListNode detectCycle(ListNode head) {
if (null==head)
return null;
ListNode x = head;
ListNode y = head;
do {
x = x.next;
y = y.next;
if (y==null)
return null;
y = y.next;
if (y==null)
return null;
} while (x!=y);
// found the cycle begin point
// special case, the whole list is a cycle
if (head==x)
return head;
x = head;
do {
x = x.next;
y = y.next;
} while (x!=y);
return x;
}
}
Best Time to Buy and Sell Stock
【题目】Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
【解答】一买一卖，求最大差价。这里有一个隐含条件，就是买必须发生在卖之前，因此这一段时间内，找一个切分点，使得后半段的最大值减去前半段的最小值这个差最大。因此在填最大值表的时候，要从右往左；而填最小值表的时候，要从左往右：
public class Solution {
public int maxProfit(int[] prices) {
if (prices.length<=1) {
return 0;
}
Integer[] mins = new Integer[prices.length]; // first n days
Integer[] maxs = new Integer[prices.length]; // last n days
mins[0] = prices[0];
maxs[prices.length-1] = prices[prices.length-1];
// fill max prices, from right to left
for (int i=prices.length-2; i>=0; i--) {
if (prices[i]>maxs[i+1])
maxs[i] = prices[i];
else
maxs[i] = maxs[i+1];
}
// fill min prices, and calculate the biggest profit, from left to right
int biggestProfit = 0;
for (int i=1; i<prices.length; i++) {
if (prices[i]<mins[i-1])
mins[i] = prices[i];
else
mins[i] = mins[i-1];
int profit = maxs[i] - mins[i];
if (profit>biggestProfit)
biggestProfit = profit;
}
return biggestProfit;
}
}
Unique Paths II
【题目】Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0] ]
The total number of unique paths is 2.
Note: m and n will be at most 100.
【解答】有了前面一道 Unique Paths 的求解，这道题就简单多了。这个问题是那个问题的加强，面对的是存在若干路障的情况。我还是利用动态规划求解，需要注意的是路障设在起点和终点这两个特殊的情况：
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid.length==0 || obstacleGrid[0].length==0 || obstacleGrid[0][0]==1 || obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1]==1)
return 0;
Integer[][] visited = new Integer[obstacleGrid.length][obstacleGrid[0].length];
return traverse(0, 0, obstacleGrid, visited);
}
private int traverse(int i, int j, int[][] obstacleGrid, Integer[][] visited) {
if (i==obstacleGrid.length-1 && j==obstacleGrid[0].length-1)
return 1;
int count = 0;
if (i<obstacleGrid.length-1 && obstacleGrid[i+1][j]==0) {
Integer val = visited[i+1][j];
if (val==null) {
val = traverse(i+1, j, obstacleGrid, visited);
visited[i+1][j] = val;
}
count += val;
}
if (j<obstacleGrid[0].length-1 && obstacleGrid[i][j+1]==0) {
Integer val = visited[i][j+1];
if (val==null) {
val = traverse(i, j+1, obstacleGrid, visited);
visited[i][j+1] = val;
}
count += val;
}
return count;
}
}
Longest Palindromic Substring
【题目】Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
【解答】求最长回文子串。下面的解法是 O(n*n) 的，最容易想到和写出来，注意需要考虑到奇数对称（比如 aba）和偶数对称（比如 abba）这两种情况。除此之外还有两种复杂度更低的解法，后续可以专门总结一下：
- 早就听说这个问题有 O(n) 的解法，后来查了一下叫做 Manacher 算法，我是看着这篇博客理解的。
- 还有一种思路上也很容易理解的解法是把字符串翻转，再把原字符串和翻转后的字符串分别建立后缀树，在对每一个字符视作回文中心，到两个后缀树中去寻找最长的共同前缀。我原以为这种解法也是 O(n*n) 的，但是其实建立后缀树有 O(n) 的办法，所以这个方法的复杂度也可以是 O(n) 的。
public class Solution {
public String longestPalindrome(String s) {
String sub = "";
for (int i=0; i<s.length(); i++) {
int j;
// odd
for (j=0; i-j>=0 && i+j<s.length(); j++) {
if (s.charAt(i-j)==s.charAt(i+j)) {
if (j*2+1>sub.length())
sub = s.substring(i-j, i+j+1);
} else {
break;
}
}
// even
for (j=0; i-j>=0 && i+1+j<s.length(); j++) {
if (s.charAt(i-j)==s.charAt(i+j+1)) {
if ((j+1)*2>sub.length())
sub = s.substring(i-j, i+j+2);
} else {
break;
}
}
}
return sub;
}
}
Longest Substring Without Repeating Characters
【题目】Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
【解答】大致思路是用两个指针，快指针用来一直向前探路，慢指针用来标注这个最长子串的起始位置；再引入一个 map，key 存放字符，value 存放字符位置，一旦发现快指针的字符在 map 中存在，就说明找到了一个疑似最大子串，可以和积累的最大值进行比较。
第一遍实现的时候执行超时了，原因是在下面代码的 map.containsKey(ch) 为真的时候，我直接把 map 清空，再把 fast 放到 newSlow 的下一个的位置，这会导致从 slow 到 newSlow 这一段重复比较，所以我做了优化——在这种情况下把 slow 到 newSlow 的记录从 map 中清掉即可：
public class Solution {
public int lengthOfLongestSubstring(String s) {
int slow = 0;
int fast = 0;
int max = 0;
Map<Character, Integer> map = new HashMap<>();
while (fast<s.length()) {
char ch = s.charAt(fast);
if (fast==slow) {
map.put(ch, fast);
fast++;
continue;
}
if (map.containsKey(ch)) {
max = Math.max(max, fast-slow);
// remove the chars ∈ [slow, newSlow)
int newSlow = map.get(ch) + 1;
for (int i=slow; i<newSlow; i++) {
map.remove(s.charAt(i));
}
slow = newSlow;
} else {
map.put(ch, fast);
fast++;
}
}
return Math.max(max, fast-slow);
}
}
Unique Paths
【题目】A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
【解答】前面做了几道回溯法的题目以后，这道题我一开始也用单纯的回溯法，但是最后超时了。再看了看题目，其实可以引入动态规划，用一个 Integer 的数组来记录位置 (i,j) 上面路径的数量，避免重复计算，其中初始值为 null 表示尚未计算：
public class Solution {
public int uniquePaths(int m, int n) {
if (m<=0 || n<=0)
return 0;
Integer[][] visited = new Integer[m][n];
return traverse(0, 0, m, n, visited);
}
private int traverse(int i, int j, int m, int n, Integer[][] visited) {
if (i==m-1 && j==n-1)
return 1;
int count = 0;
if (i<m-1) {
Integer val = visited[i+1][j];
if (val==null) {
val = traverse(i+1, j, m, n, visited);
visited[i+1][j] = val;
}
count += val;
}
if (j<n-1) {
Integer val = visited[i][j+1];
if (val==null) {
val = traverse(i, j+1, m, n, visited);
visited[i][j+1] = val;
}
count += val;
}
return count;
}
}
但是，就这道题而言，其实有更优雅的办法来解决，就是利用排列组合的特性：
观察从左上角到右下角的各条路径，它们都有个共同的特点，向右走的步数都是一样的（stepRight = m-1 步），向下走的步数也都是一样的（stepDown = n-1 步），总步数 stepAll = stepRight + stepDown——因此问题就变成了一个组合问题，即从 stepAll 的总步数里面，选出 stepRight 步来，共有几种选择的方法——C(stepAll, stepRight) = C(m+n-2, m-1)。然后再根据组合公式 C(a,b) = a!/(b!*(a-b)!) 求解。
Unique Binary Search Trees II
【题目】Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
【解答】在下面那道 Unique Binary Search Trees 的基础上，这题就好做了。每次选定一个根元素，然后把所有左子树的可能和右子树的可能结合起来，放到结果里面去：
public class Solution {
public List<TreeNode> generateTrees(int n) {
if (n==0) {
List<TreeNode> list = new ArrayList<>();
list.add(null);
return list;
}
return generateTreesByNumberRange(1, n);
}
private List<TreeNode> generateTreesByNumberRange(int start, int end) {
List<TreeNode> list = new ArrayList<>();
if (start==end) {
list.add(new TreeNode(start));
return list;
}
for (int i=start; i<=end; i++) {
List<TreeNode> left = null;
if (i!=start) {
left = generateTreesByNumberRange(start, i-1);
}
List<TreeNode> right = null;
if (i!=end) {
right = generateTreesByNumberRange(i+1, end);
}
if (left==null) {
for (TreeNode node : right) {
TreeNode root = new TreeNode(i);
root.right = node;
list.add(root);
}
} else if (right==null) {
for (TreeNode node : left) {
TreeNode root = new TreeNode(i);
root.left = node;
list.add(root);
}
} else {
for (TreeNode n1 : left) {
for (TreeNode n2 : right) {
TreeNode root = new TreeNode(i);
root.left = n1;
root.right = n2;
list.add(root);
}
} // for
} // else
} // for
return list;
}
}
Unique Binary Search Trees
【题目】Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
【解答】二叉搜索树的每一个节点都满足：如果有左孩子，那么左孩子小于自己；如果有右孩子，那么右孩子小于自己。假设 f(n) 表示有多少棵树，利用动态规划：
- 当 n=0，就一棵树（空树）；
- 当 n=1，就一棵树；
- 当 n=2，f(2) = 左子树 f(0)*右子数 f(1) + 左子树 f(1)*右子数 f(0)，即根节点可以取第一个数，也可以取第二个数，总数就是这两种情况相加；
- ……
- 当 n=i，f(i) = Σ total(k)*total(i-1-k)，其中 k=0..i-1。
有了这样的递推式就可以写代码了：
class Node {
public Node left;
public Node right;
public int value;
}
public class Solution {
public int numTrees(int n) {
if(n<0)
throw new IllegalArgumentException();
int[] total = new int[n+1];
total[0]=total[1]=1;
for(int i=2; i<=n; i++){
for(int k=0; k<i; k++)
total[i] += total[k]*total[i-1-k];
}
return total[n];
}
}
Two Sum
【题目】Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
【解答】我觉得至少有两个常见的思路：
一个是先排序，然后利用双指针，一个从小头开始右移，一个从大头开始左移，直到找到和 target 匹配的位置为止，这和 3 sum、4 sum 的做法是一致的；
另一个思路是，不用排序了，把这堆数放到 HashMap 里面去，其中 key 是这个数的值，value 是下标，然后把原数组中的每一个数都去找它的补，使得它加上它的补等于目标值，如果这个补在 HashMap 里面，就匹配上了：
public class Solution {
public int[] twoSum(int[] numbers, int target) {
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
for (int i=0;i<numbers.length;i++) {
map.put(numbers[i], i);
}
for (int i=0;i<numbers.length;i++) {
int dif = target-numbers[i];
Integer index = map.get(dif);
if (index!=null && i!=index) {
if (index>i)
return new int[]{i+1,index+1};
else
return new int[]{index+1,i+1};
}
}
return null;
}
}
Convert Sorted List to Binary Search Tree
【题目】Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
【解答】有了前面的 Convert Sorted Array List to Binary Search Tree 那道题的启发，总的思路就是，把这个 LinkedList 先放到一个 ArrayList 里面去，然后和那道题的解法就一样了：
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (null==head)
return null;
List<TreeNode> list = new ArrayList<>();
ListNode node = head;
while(node!=null) {
TreeNode n = new TreeNode(node.val);
list.add(n);
node = node.next;
}
return buildTree(0, list.size()-1, list);
}
private TreeNode buildTree(int start, int end, List<TreeNode> list) {
int mid = (start+end)/2;
TreeNode root = list.get(mid);
if (start<=mid-1)
root.left = buildTree(start, mid-1, list);
if (end>=mid+1)
root.right = buildTree(mid+1, end, list);
return root;
}
}
Maximum Product Subarray
【题目】Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
【解答】有了前面的 Maximum Subarray 的提示，这道题就简单多了。方法类似，但是这里求的最值是乘积，所以需要考虑，如果有两个比较大的负数，乘起来是有可能成为最大值的，所以每次存储前一次结果的时候，不仅要存正的最大值，还要存负的最小值：
public class Solution {
public int maxProduct(int[] A) {
int max = Integer.MIN_VALUE;
int negative = 1;
int positive = 1;
for (int a : A) {
int n1 = negative*a;
int n2 = positive*a;
int n3 = a;
positive = Math.max(n1, n2);
positive = Math.max(positive, n3);
negative = Math.min(n1, n2);
negative = Math.min(negative, n3);
max = Math.max(max, positive);
}
return max;
}
}
Maximum Subarray
【题目】Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
【解答】假设 f(i) 表示区间 [0,i] 内，以 A[i] 结尾的子串的最大值，那可以找到从 f(i) 到 f(i+1) 的递推关系：
- 如果 A[i+1]+f(i)>0，那么 f(i+1)=A[i+1]+f(i)，因为 f(i+1) 要以 A[i+1] 结尾；
- 但是如果 A[i+1]+f(i)<0，那我可以扔掉这个子串，也就是说，就是一个空串（””）的和 0 都比这个子串的 sum 大。
public class Solution {
public int maxSubArray(int[] A) {
if (null==A)
throw new IllegalArgumentException();
int max = Integer.MIN_VALUE;
int sum = 0;
// think about every maximum subarray ended with i
for (int i : A) {
sum += i;
// keep it
if(sum>max)
max = sum;
// deprecate it, the worst case: every member in A are negative, then the result is 0
if(sum<0)
sum = 0;
}
return max;
}
}
Triangle
【题目】Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
【解答】一层一层从上往下遍历，用一个 List 来存放最值串：
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
List<Integer> mins = new ArrayList<>();
int minTotal = Integer.MAX_VALUE;
for (int index=0; index<triangle.size(); index++) {
List<Integer> list = triangle.get(index);
List<Integer> newMins = new ArrayList<>();
for (int i=0; i<list.size(); i++) {
int left = Integer.MAX_VALUE;
if (i!=0)
left = mins.get(i-1) + list.get(i);
int right = Integer.MAX_VALUE;
if (i!=list.size()-1)
right = mins.get(i) + list.get(i);
int min;
if (list.size()==1)
min = list.get(0);
else
min = left<right? left : right;
if (index==triangle.size()-1) {
if (minTotal>min)
minTotal = min;
}
else {
newMins.add(min);
}
}
mins = newMins;
}
return minTotal;
}
}
Best Time to Buy and Sell Stock II
【题目】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). However, 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 的基础上，但是其实要简单得多。每次在买之前，必须先卖掉，那就意味着，其中的任意时间，只要明天的价格高于今天，那今天买明天卖一定是最划算的：
public class Solution {
public int maxProfit(int[] prices) {
int total = 0;
if(prices.length==0 || prices.length==1)
return 0;
for (int i=0; i<prices.length-1; i++)
if(prices[i+1]-prices[i]>0)
total += prices[i+1]-prices[i];
return total;
}
}
Swap Nodes in Pairs
【题目】Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
【解答】三个指针，第一个占住位置，后两个指向的元素交换一下。需要注意边界上的处理：
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode first = null;
ListNode second = head;
ListNode third = head.next;
while(third!=null) {
ListNode x = swap(second, third);
if (first==null)
head = x;
else
first.next = x;
ListNode temp = second;
second = third;
third = temp;
if (third.next==null)
return head;
else {
first = third;
third = third.next.next;
second = second.next.next;
}
}
return head;
}
private ListNode swap(ListNode second, ListNode third) {
second.next = third.next;
third.next = second;
return third;
}
}
Convert Sorted Array to Binary Search Tree
【题目】Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
【解答】找整个有序序列的中点，把中点作为最大的根，然后对左、右两个子序列分别递归执行构造树的过程：
public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
if(num==null)
return null;
return buildTree(num, 0, num.length-1);
}
private TreeNode buildTree(int[] num, int start, int end) {
if (end<start)
return null;
int mid = (start+end)/2;
TreeNode root = new TreeNode(num[mid]);
root.left = buildTree(num, start, mid-1);
root.right = buildTree(num, mid+1, end);
return root;
}
}
Container With Most Water
【题目】Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
【解答】求最大体积的公式很容易写：V = Max( Min(height[j], height[i])*(j-i) )，但硬算复杂度就是 n 的平方，但是考虑到体积是由 (j-i) 和短木板的乘积得到的，因此在短木板确定的情况下，另一条木板再长也没用。使用左右两个双指针对向移动来遍历：
public class Solution {
// V = Max( Min(height[j], height[i])*(j-i) )
public int maxArea(int[] height) {
int max = 0;
int i=0, j=height.length-1;
while (i<j) {
max = Math.max(Math.min(height[j],height[i])*(j-i), max);
if (height[i]>height[j])
j--;
else
i++;
}
return max;
}
}
Minimum Path Sum
【题目】Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
【解答】和前面 Jump Game 那道题的思路差不多，动态规划求解，从终点开始往起点推：
public class Solution {
public int minPathSum(int[][] grid) {
int[][] visited = new int[grid.length][grid[0].length];
return min(grid, visited, grid.length-1, grid[0].length-1);
}
private int min(int[][] grid, int[][]visited, int i, int j){
if(i==0 && j==0)
return grid[0][0];
int min = Integer.MAX_VALUE;
if(i>0) {
int val;
if(visited[i-1][j]>0)
val = visited[i-1][j] + grid[i][j];
else
val = min(grid, visited, i-1, j) + grid[i][j];
min = Math.min(val, min);
}
if(j>0) {
int val;
if(visited[i][j-1]>0)
val = visited[i][j-1] + grid[i][j];
else
val = min(grid, visited, i, j-1) + grid[i][j];
min = Math.min(val, min);
}
visited[i][j] = min;
return min;
}
}
Surrounded Regions
【题目】Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X X O O X X X O X X O X X
After running your function, the board should be:
X X X X X X X X X X X X X O X X
【解答】这道题我刚拿到的时候想，就是要找连通关系嘛，所以最开始的做法是用一个 m*n 的表格记录每个点访问的状态，包括：
- 未考察状态
- 正在考察周边元素时的 pending 状态
- 元素为’O’ 且不需要 flip
- 元素为’O’ 且需要 flip
- 元素为’X’（这种状态处理起来最简单，也可以不记录）
然后尝试递归求解，但是很快就栈溢出了——，我看了一下导致溢出的那个 case，全部都是’O’，这也难怪了，用这种方法每一次遇到’O’ 都无法确定，必须递归调用检查周边的’O’，而所有的’O’ 都连通，因此直到所有的’O’ 都遍历到为止，根本无法确定其中任何一个’O’ 是需要 flip 的。
我想了一下，对于这种极端的 case，用递归求解的话肯定会爆栈的。只能用循环求解。另一方面，题目中有这样一个隐含的规律：
如果’O’ 的区域和整个 board 的边界连通，那么该区域就是不可 flip 的；反之，则是需要 flip 的。
所以，我的新办法的思路基本上是这样：
- 先找整个 board 的边界，以边界上那些’O’ 作为起点，放到一个 ArrayList 里面去，且置它的初始游标位置为 0；
- 每次循环遍历这个 ArrayList，但不需要全部遍历，而是从游标处开始，一直遍历到 ArrayList 的结尾，对每一个元素，也就是上一次存储的’O’，找其中的每个’O’ 的周边：
- 如果周边为’X’，无视；
- 如果周边为’O’，但已经被访问过（在这个 ArrayList 里面存在），也无视；
- 如果周边为’O’，且没有被访问过，把这个’O’ 元素加到这个 ArrayList 里面。
如此进行，直到最后一次没有元素添加进来，这样，这个 ArrayList 里面剩下的元素，都是无法被 flip 的元素了，那么整个 board 里面余下的’O’ 都是要被 flip 的。
但是，这整个过程里面需要经常判断某元素是否在这个 ArrayList 里面，为了节约这一步的开销，引入一个 HashSet，用来判断这个存在性。另外，在 set 中比较元素的时候，由于是自定义的元素 Item，需要覆写它的 equals 和 hashCode 方法，使得相同 i、j 坐标的元素可以落到一个 hash 桶里面执行比较：
class Item {
public static int UP = 1;
public static int LEFT = 2;
public static int DOWN = 3;
public static int RIGHT = 4;
public int from; // UP, LEFT, DOWN, RIGHT
public int i;
public int j;
public Item(int i, int j, int from) {
this.i = i;
this.j = j;
this.from = from;
}
@Override
public boolean equals(Object obj) {
Item item = (Item) obj;
return item.i == i && item.j == j;
}
@Override
public int hashCode() {
return i + j;
}
}
public class Solution {
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
// max row index and max column index
int maxR = board.length - 1;
int maxC = board[0].length - 1;
List<Item> list = new ArrayList<Item>();
int cursor = 0;
Set<Item> set = new HashSet<Item>();
// left/right edge
for (int i = 0; i <= maxR; i++) {
if (board[i][0] == 'O') {
Item item = new Item(i, 0, Item.LEFT);
if (!set.contains(item)) {
list.add(item);
set.add(item);
}
}
if (board[i][maxC] == 'O') {
Item item = new Item(i, maxC, Item.RIGHT);
if (!set.contains(item)) {
list.add(item);
set.add(item);
}
}
}
// top/bottom
for (int j = 0; j <= maxC; j++) {
if (board[0][j] == 'O') {
Item item = new Item(0, j, Item.UP);
if (!set.contains(item)) {
list.add(item);
set.add(item);
}
}
if (board[maxR][j] == 'O') {
Item item = new Item(maxR, j, Item.DOWN);
if (!set.contains(item)) {
list.add(item);
set.add(item);
}
}
}
while (cursor < list.size()) {
Item item = list.get(cursor);
cursor++;
int i = item.i;
int j = item.j;
// up
if (item.from != Item.UP && i > 0 && board[i - 1][j] == 'O') {
Item newItem = new Item(i - 1, j, Item.DOWN);
if (!set.contains(newItem)) {
list.add(newItem);
set.add(newItem);
}
}
// left
if (item.from != Item.LEFT && j > 0 && board[i][j - 1] == 'O') {
Item newItem = new Item(i, j - 1, Item.RIGHT);
if (!set.contains(newItem)) {
list.add(newItem);
set.add(newItem);
}
}
// down
if (item.from != Item.DOWN && i < maxR && board[i + 1][j] == 'O') {
Item newItem = new Item(i + 1, j, Item.UP);
if (!set.contains(newItem)) {
list.add(newItem);
set.add(newItem);
}
}
// right
if (item.from != Item.RIGHT && j < maxC && board[i][j + 1] == 'O') {
Item newItem = new Item(i, j + 1, Item.LEFT);
if (!set.contains(newItem)) {
list.add(newItem);
set.add(newItem);
}
}
}
// flip
for (int i = 0; i <= maxR; i++) {
for (int j = 0; j <= maxC; j++) {
Item item = new Item(i, j, 0);
if (!set.contains(item))
board[i][j] = 'X';
}
}
}
}
【2014-11-16】更新：其实这个 List 和这个 Set 都是可以免去的，对于状态的标记，只需要在原有的 board 数组上操作就可以了，对于’X’ 无变化，对于需要 flip 的’O’，直接翻转，对于不需要翻转的’O’，可以暂时置为’N’ 标记，等遍历完成以后，最后再把’N’ 统一回置为’O’。
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
add two numbers , 进位没有加上去
你好，“Maximum Product Subarray” 这道题似乎有个小 bug，如果输入 array 全都是负数，-1,-2,-3.-4，结果应该是 24，但似乎不太对哦。
就是 24 啊