# LeetCode 题目解答—— 第 416 到 460 题

 416 Partition Equal Subset Sum 40.0% Medium 417 Pacific Atlantic Water Flow 36.9% Medium 419 Battleships in a Board 65.2% Medium 420 Strong Password Checker 17.9% Hard 421 Maximum XOR of Two Numbers in an Array 50.5% Medium 423 Reconstruct Original Digits from English 45.4% Medium 424 Longest Repeating Character Replacement 43.8% Medium 427 55.0% Easy 429 N-ary Tree Level Order Traversal 58.5% Easy 430 Flatten a Multilevel Doubly Linked List 40.9% Medium 432 All Oone Data Structure 29.0% Hard 433 Minimum Genetic Mutation 37.5% Medium 434 Number of Segments in a String 36.7% Easy 435 Non-overlapping Intervals 41.4% Medium 436 42.4% Medium 437 42.1% Easy 438 Find All Anagrams in a String 36.7% Easy 440 K-th Smallest in Lexicographical Order 26.3% Hard 441 37.6% Easy 442 Find All Duplicates in an Array 60.1% Medium 443 37.0% Easy 445 49.5% Medium 446 Arithmetic Slices II – Subsequence 29.9% Hard 447 49.4% Easy 448 Find All Numbers Disappeared in an Array 52.9% Easy 449 Serialize and Deserialize BST 46.1% Medium 450 39.4% Medium 451 Sort Characters By Frequency 55.8% Medium 452 Minimum Number of Arrows to Burst Balloons 46.2% Medium 453 Minimum Moves to Equal Array Elements 49.1% Easy 454 50.4% Medium 455 48.3% Easy 456 27.4% Medium 457 27.5% Medium 458 45.3% Hard 459 Repeated Substring Pattern 39.7% Easy 460 28.6% Hard

Partition Equal Subset Sum

【题目】Given a  non-empty array containing  only positive integers , find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

【解答】要划分数组成两个部分，这两个部分各自的和相等。

class Solution {
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0)
throw new IllegalArgumentException();

int total = 0;
for (int num : nums) {
total += num;
}

if (total % 2 == 1)
return false;

int target = total / 2;
// <index, >
Map<Integer, Map> cache = new HashMap();

return canPartition(nums, cache, target, 0);
}

private boolean canPartition(int[] nums, Map<Integer, Map> cache, int target, int index) {
if (index == nums.length)
return target == 0;

if (!cache.containsKey(index)) {
cache.put(index, new HashMap());
}
Map subMap = cache.get(index);
if (subMap.containsKey(target))
return subMap.get(target);

// current is not selected
boolean partitionable = canPartition(nums, cache, target, index + 1);
subMap.put(target, partitionable);
if (partitionable) {
subMap.put(target, true);
return true;
}

// current is selected
if (nums[index] <= target) {
partitionable = canPartition(nums, cache, target - nums[index], index + 1);
}

return partitionable;
}
}

Pacific Atlantic Water Flow

【题目】Given an  m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

1. The order of returned grid coordinates does not matter.
2. Both  m  and  n  are less than 150.

Example:

Given the following 5x5 matrix:

Pacific ~   ~   ~   ~   ~
~  1   2   2   3  (5) *
~  3   2   3  (4) (4) *
~  2   4  (5)  3   1  *
~ (6) (7)  1   4   5  *
~ (5)  1   1   2   4  *
*   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

【解答】太平洋在左上方，大西洋在右下方，要寻找二者的分界线。

class Solution {
public List pacificAtlantic(int[][] matrix) {
if (matrix == null)
throw new IllegalArgumentException();

List result = new ArrayList();
if (matrix.length==0 || matrix[0].length==0)
return result;

// null: undetermined, true: reachable, false: unreachable
Boolean[][] pacificReachable = new Boolean[matrix.length][matrix[0].length];
// top row
for (int j=0; j<matrix[0].length; j++) {
pacificReachable[0][j] = true;
pacificQueue.offer(new Point(0, j));
}
// left column
for (int i=0; i<matrix.length; i++) {
pacificReachable[i][0] = true;
pacificQueue.offer(new Point(i, 0));
}
// find all the nodes pacific water flow can reach
iterate(matrix, pacificQueue, pacificReachable);

Boolean[][] atlanticReachable = new Boolean[matrix.length][matrix[0].length];
// bottom row
for (int j=0; j<matrix[0].length; j++) {
atlanticReachable[matrix.length-1][j] = true;
atlanticQueue.offer(new Point(matrix.length-1, j));
}
// right column
for (int i=0; i<matrix.length; i++) {
atlanticReachable[i][matrix[0].length-1] = true;
atlanticQueue.offer(new Point(i, matrix[0].length-1));
}
iterate(matrix, atlanticQueue, atlanticReachable);

for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[0].length; j++) {
if (pacificReachable[i][j] == Boolean.TRUE && atlanticReachable[i][j] == Boolean.TRUE) {
}
}
}

return result;
}

private void iterate(int[][] matrix, Queue queue, Boolean[][] reachable) {
while (!queue.isEmpty()) {
Point p = queue.poll();

if (this.mark(matrix, p.x, p.y, p.x-1, p.y, reachable))
if (this.mark(matrix, p.x, p.y, p.x, p.y-1, reachable))
if (this.mark(matrix, p.x, p.y, p.x+1, p.y, reachable))
if (this.mark(matrix, p.x, p.y, p.x, p.y+1, reachable))
}
}

private boolean mark(int[][] matrix, int x, int y, int nx, int ny, Boolean[][] reachable) {
if (nx<0 || ny=matrix.length || ny>=matrix[0].length || reachable[nx][ny] != null)
return false;

if (matrix[x][y] <= matrix[nx][ny]) {
reachable[nx][ny] = true;
return true;
}

return false;
}
}

class Point {
public int x;
public int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}

Battleships in a Board

【题目】Given an 2D board, count how many battleships are in it. The battleships are represented with  'X' s, empty slots are represented with  '.' s. You may assume the following rules:

• You receive a valid board, made of only battleships or empty slots.
• Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape  1xN  (1 row, N columns) or  Nx1  (N rows, 1 column), where N can be of any size.
• At least one horizontal or vertical cell separates between two battleships – there are no adjacent battleships.

Example:

X..X
...X
...X

In the above board there are 2 battleships.

Invalid Example:

...X
XXXX
...X

This is an invalid board that you will not receive – as battleships will always have a cell separating between them.

Could you do it in  one-pass , using only  O(1) extra memory and  without modifying the value of the board?

【解答】要数有多少 battleship，并且要求使用 O(1) 的空间复杂度，还不能修改 board 上的数值。

class Solution {
public int countBattleships(char[][] board) {
int count = 0;

for (int i=0; i<board.length; i++) {
for (int j=0; j0 && board[i][j-1]=='X') continue;
if (i>0 && board[i-1][j]=='X') continue;
count++;
}
}

return count;
}
}

【题目】A password is considered strong if below conditions are all met:

1. It has at least 6 characters and at most 20 characters.
2. It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
3. It must NOT contain three repeating characters in a row (“…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met).

Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.

Insertion, deletion or replace of any one character are all considered as one change.

【解答】规则很容易理解：

1. 6~20 个字符；
2. 必须包含小写字符、大写字符和数字；
3. 不能包含连续三个相同字符。

class Solution {
int res = 0, a = 1, A = 1, d = 1;
char[] carr = s.toCharArray();
int[] arr = new int[carr.length];

for (int i = 0; i < arr.length;) {
if (Character.isLowerCase(carr[i])) a = 0;
if (Character.isUpperCase(carr[i])) A = 0;
if (Character.isDigit(carr[i])) d = 0;

int j = i;
while (i < carr.length && carr[i] == carr[j]) i++;
arr[j] = i - j;
}

int total_missing = (a + A + d);

if (arr.length < 6) {
res += total_missing + Math.max(0, 6 - (arr.length + total_missing));

} else {
int over_len = Math.max(arr.length - 20, 0), left_over = 0;
res += over_len;

for (int k = 1; k < 3; k++) {
for (int i = 0; i  0; i++) {
if (arr[i] < 3 || arr[i] % 3 != (k - 1)) continue;
arr[i] -= Math.min(over_len, k);
over_len -= k;
}
}

for (int i = 0; i = 3 && over_len > 0) {
int need = arr[i] - 2;
arr[i] -= over_len;
over_len -= need;
}

if (arr[i] >= 3) left_over += arr[i] / 3;
}

res += Math.max(total_missing, left_over);
}

return res;
}
}

Maximum XOR of Two Numbers in an Array

【题目】Given a  non-empty array of numbers, a 0 , a 1 , a 2 , … , a n-1 , where 0 ≤ a i < 2 31 .

Find the maximum result of a i XOR a j , where 0 ≤  ijn .

Could you do this in O( n ) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

【解答】要在 O(n) 时间内找两个数 XOR 的最大值。

class Solution {
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for (int i = 31; i >= 0; i--){
// part 1:
// prefix set
Set set = new HashSet();
for (int num : nums){
}

// part 2:
int tmp = max | (1 << i);
for (int prefix : set){
if(set.contains(tmp ^ prefix)) {
max = tmp;
break;
}
}
}
return max;
}
}

• part 1：利用 mask 来取所有数的 prefix，第一次一个最高位，第二次为两个最高位，第三次为三个最高位…… 这些 prefix 组成一个 set。
• part 2：现在假设第 n 次迭代所得到的最大值是 max，那么考虑第 n+1 次迭代：假设新确定的那一位是 1，那么设这个数为 tmp，然后把 tmp 和所有 prefix 进行 XOR 操作，如果得到的数还在这个 prefix set 里面，根据前面提到的特性，说明有两个 prefix 进行 XOR 以后可以得到这个 tmp，那么这个 tmp 就是新的最大值 max，否则这一位只能是 0，那么 max 不变。

Reconstruct Original Digits from English

【题目】Given a  non-empty string containing an out-of-order English representation of digits  0-9 , output the digits in ascending order.

Note:

1. Input contains only lowercase English letters.
2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.
3. Input length is less than 50,000.

Example 1:

Input: "owoztneoer"

Output: "012"

Example 2:

Input: "fviefuro"

Output: "45"

【解答】要从无序的英文字母串还原到数字。

class Solution {
public String originalDigits(String s) {
// unique:
// zero
// 'z' => 0
// two
// 'w' => 2
// four
// 'u' => 4
// six
// 'x' => 6
// eight
// 'g' => 8

// not unique:
// seven = 's' - '6'
// 's' => 7
// five = 'v' - '7'
// 'v' => 5
// one = 'o' - '0' - '2' - '4'
// 'o' => 1
// three = 'h' - 8
// 'h' => 3
// nine = 'i' - '6' - '8' - '5'
// 'i' => 9

Map countMap = new HashMap();
for (int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
if (!countMap.containsKey(ch))
countMap.put(ch, 0);
countMap.put(ch, countMap.get(ch) + 1);
}

int[] digits = new int[10];
Integer count = countMap.get('z');
if (count != null) {
digits[0] = count;
}
count = countMap.get('w');
if (count != null) {
digits[2] = count;
}
count = countMap.get('u');
if (count != null) {
digits[4] = count;
}
count = countMap.get('x');
if (count != null) {
digits[6] = count;
}
count = countMap.get('g');
if (count != null) {
digits[8] = count;
}

count = countMap.get('s');
if (count != null) {
digits[7] = count - digits[6];
}
count = countMap.get('v');
if (count != null) {
digits[5] = count - digits[7];
}
count = countMap.get('o');
if (count != null) {
digits[1] = count - digits[0] - digits[2] - digits[4];
}
count = countMap.get('h');
if (count != null) {
digits[3] = count - digits[8];
}
count = countMap.get('i');
if (count != null) {
digits[9] = count - digits[6] - digits[8] - digits[5];
}

StringBuilder sb = new StringBuilder();
for (int i=0; i<digits.length; i++) {
for (int j=0; j<digits[i]; j++)
sb.append(i);
}
return sb.toString();
}
}

Longest Repeating Character Replacement

【题目】Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most  k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:

Both the string’s length and  k will not exceed 10 4 .

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

【解答】要求在字符串 s 中替换字符 k 次，得到最长的连续字符子串。

• 假设说有一个 sliding window，从左慢慢往右划，不断调整左右边界：左边吐出 char，右边吃进 char；
• 这个 window 里面的不同 char 各有多少个，通过一个 map 来记录；
• 这个 window 的左边界所对应的 char 作为所考察的 repeating char，在左边界固定的基础上不断右移右边界，记录 window 的最大值，如果其他 char 的数量超过了 k，那么需要右移左边界，吐出一个之前的 repeating char。

1. 窗口内字符排列或数量增量变化。无论移动左侧还是右侧窗口边沿，都只变化一个字符。
2. 窗口的左侧或者右侧固定，从而简化问题。像这道题就是总是考虑窗口左侧的 char 为 repeating char。
class Solution {
public int characterReplacement(String s, int k) {
if (s==null || k<0)
throw new IllegalArgumentException();
if (s.length()==0)
return 0;

int left=0, right=0;
int max = 1;

char[] counters = new char[26];
counters[s.charAt(0) - 'A']++;

while (right<s.length()) {
int base = s.charAt(left) - 'A';
int replacementCount = 0;
for (int i=0; ik) {
counters[base]--;
left++;
} else {
int newSize = right-left+1;
max = Math.max(max, newSize);
right++;
if (right<s.length()) {
counters[s.charAt(right) - 'A']++;
} else {
// special case: there are still change chances left
max = Math.max(max, newSize + k - replacementCount);
}
}
}

// never exceeds the length of s
return Math.min(max, s.length());
}
}

【题目】We want to use quad trees to store an  N x N boolean grid. Each cell in the grid can only be true or false. The root node represents the whole grid. For each node, it will be subdivided into four children nodes  until the values in the region it represents are all the same .

Each node has another two boolean attributes : isLeaf and  valisLeaf is true if and only if the node is a leaf node. The  val attribute for a leaf node contains the value of the region it represents.

Given the 8 x 8 grid below, we want to construct the corresponding quad tree:

It can be divided according to the definition above:

The corresponding quad tree should be as following, where each node is represented as a (isLeaf, val) pair.

For the non-leaf nodes, val can be arbitrary, so it is represented as  * .

#### Note:

1. N  is less than  1000  and guaranteened to be a power of 2.
2. If you want to know more about the quad tree, you can refer to its  wiki .

class Solution {
public Node construct(int[][] grid) {
if (grid==null || grid.length==0 || grid.length!=grid[0].length)
throw new IllegalArgumentException();

return this.construct(grid, 0, 0, grid.length);
}

private Node construct(int[][] grid, int x, int y, int w) {
if (w==1) {
return new Node(grid[x][y]!=0, true, null, null, null, null);
}

Node topLeft = this.construct(grid, x, y, w/2);
Node topRight = this.construct(grid, x, y+w/2, w/2);
Node bottomLeft = this.construct(grid, x+w/2, y, w/2);
Node bottomRight = this.construct(grid, x+w/2, y+w/2, w/2);

// all leaves and equal, merge
if (topLeft.isLeaf &&
topRight.isLeaf &&
bottomLeft.isLeaf &&
bottomRight.isLeaf &&
topLeft.val == topRight.val &&
topLeft.val == bottomLeft.val &&
topLeft.val == bottomRight.val
) {
return new Node(topLeft.val, true, null, null, null, null);
}

// otherwise create a sub tree
return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
}
}

N-ary Tree Level Order Traversal

【题目】

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

We should return its level order traversal:

[
[1],
[3,2,4],
[5,6]
]

Note:

【解答】没有太多可以说的。循环内按层遍历就好。

class Solution {
public List levelOrder(Node root) {
List result = new ArrayList();
if (root==null)
return result;

while (!level.isEmpty()) {
List list = new ArrayList();
for (Node node : level) {
if (node.children != null)
}
level = nextLevel;
}

return result;
}
}

Flatten a Multilevel Doubly Linked List

【题目】You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

#### Example:

Input:
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

#### Explanation for the above example:

Given the following multilevel doubly linked list:

We should return the following flattened doubly linked list:

【解答】要把多层的双向链表压平。

class Solution {
return null;

Stack stack = new Stack();
while (true) {
// always push the next node to stack
if (cur.next != null)
stack.push(cur.next);

Node next = cur.child;
if (next == null) {
// make child as the next, but if child is null, pop the next from stack
if (!stack.isEmpty()) {
next = stack.pop();
} else {
cur.child = null;
cur.next = null;
break;
}
}

cur.child = null;
next.prev = cur;
cur.next = next;

cur = next;
}

}
}

All Oone Data Structure

【题目】Implement a data structure supporting the following operations:

1. Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a  non-empty  string.
2. Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a  non-empty  string.
3. GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string  "" .
4. GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string  "" .

Challenge: Perform all these in O(1) time complexity.

【解答】实现一个数据结构，加一、减一，获取最大值的 key 和最小值的 key，都是 O(1) 的时间复杂度。

• 要 O(1)，根据 key 去取 value 的，无非就两种数据结构，一个是 HashMap，一个是数组（下标访问）。
• 如果有根据 key 取 value，那就需要从 key 到 value 的映射；如果有根据 value 取 key，那就需要 value 到 key 的映射。
• 这道题看起来需要两者：
• 根据 key 要获取 value 对象，从而进行 inc 和 dec 的操作；
• 根据 value 的大小情况，来找到对象并返回相应的 key。
• 要能 O(1) 得到最大值和最小值，肯定不能在需要的时候去现找，那就需要在平时维护一个有序列表，一头最大，一头最小。这个列表的大小比较实际只靠 value，具体这个 value 有多少个 key 对应并不重要。因而这个序号并不是 key 根据 value 的值实际的序号，而是互不重复的 value 进行比较得到的序号。
• 在 inc 和 dec 的时候，由于变化只有 1，位置调整于是也只有 1。这就是为什么要根据互不重复的 value 来排序的原因，这样的情况一定能保证调整的幅度不超过 1。

class Item {
public int value;
public Item next;
public Item prev;
public Set keys = new HashSet();;
}
class AllOne {

private Map map = new HashMap();
private Item head = new Item();
private Item tail = new Item();

/** Initialize your data structure here. */
public AllOne() {
// dummy head and dummy tail
this.tail.value = Integer.MAX_VALUE;
}

private void link(Item left, Item right) {
left.next = right;
right.prev = left;
}

/** Inserts a new key  with value 1. Or increments an existing key by 1. */
public void inc(String key) {
Item currentItem = this.map.get(key);
if (currentItem != null) { // it's an existing key
currentItem.keys.remove(key);
int newValue = currentItem.value + 1;
Item next = currentItem.next;
if (next.value == newValue) {
// the item for the newValue is already existed
map.put(key, next);
} else {
// there is no item for newValue, create one
Item newItem = new Item();
newItem.value = newValue;

map.put(key, newItem);
}

// remove the node if there's no key mapped to its value
if (currentItem.keys.isEmpty()) {
}
} else { // it's a new key
// the item for new key (value==1) is already existed
} else {
// new item needed
Item newItem = new Item();
newItem.value = 1;

map.put(key, newItem);
}
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
Item currentItem = this.map.get(key);
if (currentItem == null)
return;

Item prev = currentItem.prev;
currentItem.keys.remove(key);
// remove the item if no key mapped to it
if (currentItem.keys.isEmpty()) {
}

if (currentItem.value == 1) {
this.map.remove(key);
return;
}

int newValue = currentItem.value - 1;
// there's already an item existed for newValue
if (prev.value == newValue) {
this.map.put(key, prev);
return;
}

// there is no item for newValue, create one
Item newItem = new Item();
newItem.value = newValue;

Item next = prev.next;

map.put(key, newItem);
}

/** Returns one of the keys with maximal value. */
public String getMaxKey() {
return "";
return this.tail.prev.keys.iterator().next();
}

/** Returns one of the keys with Minimal value. */
public String getMinKey() {
return "";
}
}

Minimum Genetic Mutation

【题目】A gene string can be represented by an 8-character long string, with choices from  "A""C""G""T" .

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" ->  "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

1. Starting point is assumed to be valid, so it might not be included in the bank.
2. If multiple mutations are needed, all mutations during in the sequence must be valid.
3. You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

【解答】维护一个当前考察的字符串集合和一个字典，每次都拿当前字符串去和字典里的所有候选字符串比较，如果只差 1，就把候选从字典里面拿出来，更新到当前考察的字符串集合中。直到发现解，或者字典为空，或者在最近一次比较中没有发现任何匹配，就表示算法已经结束。

class Solution {
public int minMutation(String start, String end, String[] bank) {
if (start==null || end==null || bank==null)
throw new IllegalArgumentException();
if (start.equals(end))
return 0;
if (start.length() != end.length() || bank.length==0)
return -1;

Set bankSet = new HashSet(Arrays.asList(bank));
Set current = new HashSet();

int count = 0;
while (!current.isEmpty() && !bankSet.isEmpty()) {
count++;
Set newCurrent = new HashSet();
for (String cur : current) {
Set newBank = new HashSet();
for (String b : bankSet) {
if (this.diffOne(cur, b)) {
if (b.equals(end))
return count;
else
} else {
}
}
bankSet = newBank;
}
current = newCurrent;
}

return -1;
}

private boolean diffOne(String left, String right) {
if (left.length() != right.length())
return false;

boolean changed = false;
for (int i=0; i<left.length(); i++) {
if (left.charAt(i) != right.charAt(i)) {
if (changed)
return false;
else
changed = true;
}
}

return true;
}
}

Number of Segments in a String

【题目】Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable  characters.

Example:

Input: "Hello, my name is John"
Output: 5

【解答】常规题。没有太多可说的，注意一些特殊 case 是否被覆盖到，比如首尾空格。

class Solution {
public int countSegments(String s) {
boolean isSpace = true;
int count = 0;
for (int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
if (ch!=' ' && isSpace) {
isSpace = false;
} else if (ch==' ' && !isSpace) {
count++;
isSpace = true;
}
}

if (!isSpace)
count++;

return count;
}
}

Non-overlapping Intervals

【题目】Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

1. You may assume the interval’s end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

【解答】要求去掉最少的 interval 使得剩余的 interval 无重叠。

class Solution {
public int eraseOverlapIntervals(Interval[] intervals) {
Arrays.sort(intervals, new Comparator(){
@Override
public int compare(Interval left, Interval right) {
if (left.start != right.start)
return left.start - right.start;
// this is to make sure when start is same, we can always remove the left one and keep the right one as the right one is shorter
return right.end - left.end;
}
});

Integer[][] cache = new Integer[intervals.length][intervals.length];
return this.cal(intervals, 0, -1, cache);
}

private int cal(Interval[] intervals, int index, int last, Integer[][] cache) {
if (index >= intervals.length)
return 0;

if (last!=-1 && cache[index][last] != null)
return cache[index][last];

int count = 0;
for (int i=index; i<intervals.length; i++) {
Interval interval = intervals[i];

if (last==-1) {
last = i;
} else if (intervals[last].start == interval.start) {
count++;
last = i;
} else if (intervals[last].end <= interval.start) {
// no overlapping
last = i;
} else {
// it's the most complicated case as we don't know which should be removed: "last" or "i"
int c1 = this.cal(intervals, i+1, last, cache);
int c2 = this.cal(intervals, i+1, i, cache);
count++;
count += Math.min(c1, c2);
break;
}
}

cache[index][last] = count;
return count;
}
}

• 如果按照 start 排序，从左到右扫描的过程中，start 大或者小并不代表该 interval 是否应该被选中，因为需要考虑几个重叠 interval 之间覆盖的竞争关系。对右侧的 interval 来说，和不同的左侧 interval 产生重叠，但 start 更大不代表这个重叠范围更大或者更小。因此单纯按照 start 排序没有意义。
• 而如果按照 end 排序，从小到大扫描的时候，只要发现重叠就只需要忽略后扫描到的，而根本不需要考虑 start 在哪里。因为对于右侧的 interval 来说，左侧元素的 start 在哪里不重要，重要的是 end 在哪里，end 才是决定了重叠部分右边界位置的因素。我们当然希望这个右边界越靠左越好，因此我们在扫描的过程中，尽可能留下先遇到的 end。
class Solution {
public int eraseOverlapIntervals(Interval[] intervals) {
Arrays.sort(intervals, new Comparator(){
@Override
public int compare(Interval left, Interval right) {
return left.end - right.end;
}
});

int count = 0;
Interval last = null;
for (Interval interval : intervals) {
// intervals are sorted by "end"
if (last==null || interval.start >= last.end) {
last = interval;
count++;
}
}

return intervals.length - count;
}
}

Find Right Interval

【题目】Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

1. You may assume the interval’s end point is always bigger than its start point.
2. You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

【解答】对于每个 interval，要找有多少 interval 在它的右边。

class Solution {
public int[] findRightInterval(Interval[] intervals) {
if (intervals == null)
throw new IllegalArgumentException();

TreeMap map = new TreeMap();
for (int i=0; i<intervals.length; i++) {
Interval interval = intervals[i];
map.put(interval.start, i);
}

int[] result = new int[intervals.length];
for (int i=0; i<intervals.length; i++) {
Interval interval = intervals[i];
Map.Entry entry = map.ceilingEntry(interval.end);
if (entry==null)
result[i] = -1;
else
result[i] = entry.getValue();
}

return result;
}
}

Path Sum III

【题目】You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/  \
5   -3
/ \    \
3   2   11
/ \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

【解答】递归求解。但是在递归的过程中，不需要记录每个解分别是由那几个数累加起来的，但是需要记录都可以得到哪些和，不需要去重。因为不同的节点加起来可以得到同样的和，但是实际是算作不同的解。

class Solution {
public int pathSum(TreeNode root, int sum) {
if (root==null) return 0;
return travel(root, new ArrayList(), sum);
}

private int travel(TreeNode root, List list, int sum) {
if (root==null) return 0;

int total = 0;
if (root.val == sum) total++;

List newList = new ArrayList();
for (int num : list) {
int added = num + root.val;
}

int left = travel(root.left, newList, sum);
int right = travel(root.right, newList, sum);

total += left;
total += right;

}
}

Find All Anagrams in a String

【题目】Given a string  s and a  non-empty string  p , find all the start indices of  p ‘s anagrams in  s .

Strings consists of lowercase English letters only and the length of both strings s and  p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

【解答】要找成为 anagram 的子串，基本上最直接的方法就是使用滑动窗口了。而且是个固定大小的滑动窗口。我当时的做法不是特别好，虽然也解出来了，但没有充分利用固定大小这个特性，于是代码写得有些啰嗦。

class Solution {
private void updateMap(Map charMap, char ch, int count) {
if (count==0)
charMap.remove(ch);
else
charMap.put(ch, count);
}

public List findAnagrams(String s, String p) {
if (s==null || p==null || p.length()==0)
throw new IllegalArgumentException();

List result = new ArrayList();
if (s.length()==0)
return result;

Map charMap = new HashMap();
for (int i=0; i<p.length(); i++) {
char ch = p.charAt(i);
int count = charMap.getOrDefault(ch, 0);
charMap.put(ch, ++count);
}

int left=0, right=0;
while (right<s.length()) {
// always load s[right] at the beginning of each iteration
char cr = s.charAt(right);
int count = charMap.getOrDefault(cr, 0) - 1;
this.updateMap(charMap, cr, count);

// anagram found
if (charMap.isEmpty()) {
// move both boundaries
charMap.put(s.charAt(left), 1);
left++;
right++;
continue;
}

// now try moving left only, and break the loop when:
// the amount of cr is matched, or left moves beyond right (no matches found)
while (charMap.getOrDefault(cr, 0)==-1 && left<=right) {
char cl = s.charAt(left++);
count = charMap.getOrDefault(cl, 0) + 1;
this.updateMap(charMap, cl, count);
}

right++;
}

return result;
}
}

K-th Smallest in Lexicographical Order

【题目】Given integers  n and  k , find the lexicographically k-th smallest integer in the range from  1 to  n .

Note: 1 ≤ k ≤ n ≤ 10 9 .

Example:

Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

【解答】要找从 1 到 n 这连续的数中，第 k 小的那一个。

class Solution {
public int findKthNumber(int n, int k) {
int curr = 1;
k = k - 1;
while (k > 0) {
int steps = calSteps(n, curr, curr + 1);
if (steps <= k) {
curr += 1;
k -= steps;
} else {
curr *= 10;
k -= 1;
}
}
return curr;
}

/**
* how many steps from n1 to n2
*/
public int calSteps(int n, long n1, long n2) {
int steps = 0;
while (n1 <= n) {
steps += Math.min(n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return steps;
}
}

Arranging Coins

【题目】You have a total of  n coins that you want to form in a staircase shape, where every  k -th row must have exactly  k coins.

Given n , find the total number of  full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

【解答】要求硬币组成的楼梯形状的层数，不完整的层要舍弃。

class Solution {
public int arrangeCoins(int n) {
// (1 + x) * x / 2 >= n
// so x^2 + x - 2n >= 0
// [-b±(b^2-4ac)^(1/2)]/(2a)
// avoid overflow
double result = (-1 + Math.sqrt(1 - 4*(-2*(double)n))) / 2;
return (int) result;
}
}

Find All Duplicates in an Array

【题目】Given an array of integers, 1 ≤ a[i] ≤  n ( n = size of array), some elements appear  twice and others appear  once .

Find all the elements that appear twice in this array.

Could you do it without extra space and in O( n ) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

【解答】要从大小为 1~n 的长度为 n 数组中找出出现了两次的数，而且要 O(1) 的空间和 O(n) 的时间复杂度，这就意味着一般的搜索和排序之类方法的都可以靠边站了 。

class Solution {
public List findDuplicates(int[] nums) {
if (null==nums)
throw new IllegalArgumentException();

// to save as much space as possible LinkedList is used, not ArrayList
for (int i=0; i<nums.length; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index]<0) { // if it's already <0 this is the second time to be hit
} else {
nums[index] = -nums[index];
}
}

return result;
}
}

String Compression

【题目】Given an array of characters, compress it  in-place .

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array  in-place , return the new length of the array.

Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

[35, 126]
1 <= len(chars) <= 1000


【解答】字符串压缩。快慢双指针方式求解。

class Solution {
public int compress(char[] chars) {
if (chars==null)
throw new IllegalArgumentException();
if (chars.length==0)
return 0;

// slow / fast: the star/end of the consecutive sub char array
// recording: the pointer recording char + number
int slow=0, fast=0, recording=0;
while (slow 1) {
String num = "" + (fast-slow);
for (char n : num.toCharArray())
chars[recording++] = n;
}
slow = fast;
}

fast++;
}

return recording;
}
}

【题目】You are given two  non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1==null || l2==null)
throw new IllegalArgumentException();

Stack s1 = new Stack();
Stack s2 = new Stack();

ListNode cur = l1;
while (cur!=null) {
s1.push(cur);
cur = cur.next;
}
cur = l2;
while (cur!=null) {
s2.push(cur);
cur = cur.next;
}

Stack res = new Stack();
boolean carry = false;
while (!s1.isEmpty() || !s2.isEmpty()) {
ListNode l = s1.isEmpty() ? null : s1.pop();
ListNode r = s2.isEmpty() ? null : s2.pop();
int lv = l==null ? 0 : l.val;
int rv = r==null ? 0 : r.val;
int sum = lv + rv;
if (carry)
sum++;

if (sum>=10) {
sum -= 10;
carry = true;
} else {
carry = false;
}

res.push(new ListNode(sum));
}
if (carry)
res.push(new ListNode(1));

while (!res.isEmpty()) {
cur.next = res.pop();
cur = cur.next;
}

}
}

Arithmetic Slices II – Subsequence

【题目】A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P 0 , P 1 , …, P k ) such that 0 ≤ P 0 < P 1 < … < P k < N.

A subsequence slice (P 0 , P 1 , …, P k ) of array A is called arithmetic if the sequence A[P 0 ], A[P 1 ], …, A[P k-1 ], A[P k ] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -2 31 and 2 31 -1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 2 31 -1.

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

【解答】我最开始的思路是动态规划，划分成子问题。每个子问题是：

A[j]-A[i] 为新的 interval，寻求解集 c[j][A[j]-A[i]]。看起来这个方法似乎是可以走得通的，但是明显无论从实现层面还是时间复杂度层面都过高了。为了缓存已得到的结果，我需要建立一个这样的数据结构来避开重复计算：Map<Integer, Map<Integer, Map>>，含义是：<start_index, <interval, >。因此这是一个三维的动态规划，我们一般只做一维到二维，而三维的话一般有更好的解决办法。[后记：其实第三维 sub_seq_len 应该是不需要的，当时的想法有点问题。]

• 对于任意 0<=j<i<A.length, A[j] 和 A[i] 之间的差是 d，那么：map[i][d] 表示：以 A[i] 结尾的这些 subsequence 且元素两两差值为 d 的情况下，这样的这些 subsequence 有多少个。
• 这样在每次迭代中，先对于当前的元素 A[i] 拿到当前的值 c1=map[i][d]，再看它前面的元素 A[j]，拿到它的值 c2=map[j][d]，对于 map[i][d] 来说，新的值就是 c1+c2+1，这里面的“+1”是因为这个新的这些 subsequence：A[j],A[i]；
• 在考虑总数的时候，每次都把 c2 加进去，因为 c2 来自于前一个元素 A[j] 的统计，这些 subsequence 们最少也有两个元素，现在各自再加上一个 A[i] 就都成为了合法的结果（至少三个元素）。
class Solution {
public int numberOfArithmeticSlices(int[] A) {
if (A==null)
throw new IllegalArgumentException();

int res = 0;
Map[] map = new Map[A.length];

for (int i = 0; i < A.length; i++) {
map[i] = new HashMap(i);

for (int j = 0; j < i; j++) {
long diff = (long)A[i] - A[j];
if (diff  Integer.MAX_VALUE) continue;

int d = (int)diff;
int c1 = map[i].getOrDefault(d, 0);
int c2 = map[j].getOrDefault(d, 0);
res += c2;
map[i].put(d, c1 + c2 + 1);
}
}

return res;
}
}

Number of Boomerangs

【题目】Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:

[[0,0],[1,0],[2,0]]

Output:

2

Explanation:

The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

【解答】i 到 j 的距离必须等于 i 到 k 的距离。

class Solution {
public int numberOfBoomerangs(int[][] points) {
if (points==null)
throw new IllegalArgumentException();

int total = 0;
for (int i=0; i<points.length; i++) {
int[] point = points[i];
// point is chosen as the center (first element of the tri-tuple)
// key: distance^2, value: count
Map map = new HashMap();
for (int j=0; j<points.length; j++) {
int[] p = points[j];
if (point==p)
continue;

int distance = (int) (Math.pow(point[0]-p[0], 2) + Math.pow(point[1]-p[1], 2));
int count = map.getOrDefault(distance, 0);
map.put(distance, ++count);
}

for (int count : map.values())
total += this.perm(count);
}

}

// Permutation: P(m, n) = n! / (n-m)!
// Combination: C(m, n) = P(m, n) / m! = n! / ((n-m)!*m!)
private int perm(int count) {
// here m=2, so C(m, n) = n * (n-1);
return count * (count-1);
}
}

Find All Numbers Disappeared in an Array

【题目】Given an array of integers where 1 ≤ a[i] ≤  n ( n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n ] inclusive that do not appear in this array.

Could you do it without extra space and in O( n ) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

【解答】应该算是常规题了。把每个数都尝试换到它应该去的位置，完毕之后，扫一遍看哪些位置上的数和 index 不匹配（index 应当等于 n-1）。

class Solution {
public List findDisappearedNumbers(int[] nums) {
if (nums==null)
throw new IllegalArgumentException();

int i=0;
while (i<nums.length) {
int currentVal = nums[i];
int indexShouldBe = nums[i]-1;
if (indexShouldBe != i) {
if (nums[indexShouldBe] != currentVal) {
swap(nums, i, indexShouldBe);
continue;
}
}

i++;
}

List result = new ArrayList();
for (i=0; i<nums.length; i++) {
if (nums[i]-1 != i)
}

return result;
}

private void swap(int[] nums, int i, int j) {
if (i==j)
return;

int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

Serialize and Deserialize BST

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

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

The encoded string should be as compact as possible.

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

【解答】要把一棵 BST 序列化和反序列化。

public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root==null)
return "";

// pre-order traversal
String result = "" + root.val;
if (root.left!=null)
result += "," + serialize(root.left);
if (root.right!=null)
result += "," + serialize(root.right);

return result;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length()==0)
return null;

String[] arr = data.split(",");
int[] tokens = new int[arr.length];
for (int i=0; i<arr.length; i++)
tokens[i] = Integer.parseInt(arr[i]);
return deserialize(tokens, 0, tokens.length-1);
}

private TreeNode deserialize(int[] tokens, int start, int end) {
TreeNode root = new TreeNode(tokens[start]);
Integer left = null;
Integer right = null;
for (int i=start+1; i<=end; i++) {
if (tokens[i]root.val && right==null) {
right = i;
break;
}
}

if (left!=null)
root.left = right==null ? deserialize(tokens, left, end) : deserialize(tokens, left, right-1);
if (right!=null)
root.right = deserialize(tokens, right, end);

return root;
}
}

Delete Node in a BST

【题目】Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

5
/ \
3   6
/ \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

5
/ \
4   6
/     \
2       7

5
/ \
2   6
\   \
4   7

【解答】要从一棵 BST 上面删除一个节点。分成几种情况考虑：

class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root==null) return null;
if (keyroot.val) {
root.right = this.deleteNode(root.right, key);
return root;
}
if (root.left==null && root.right==null) return null;
if (root.left==null) return root.right;
if (root.right==null) return root.left;

TreeNode smallest = this.getSmallest(root.right);
root.val = smallest.val;
root.right = deleteNode(root.right, smallest.val);
return root;
}

private TreeNode getSmallest(TreeNode node){
while(node.left != null){
node = node.left;
}
return node;
}
}

Sort Characters By Frequency

【题目】Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

【解答】按照字符的出现频率排序。常规题目，使用一个 map 来统计次数，然后实现比较接口来排序。

class Solution {
public String frequencySort(String s) {
if (s==null) throw new IllegalArgumentException();

Map map = new HashMap();
List list = new ArrayList();
for (int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
if (!map.containsKey(ch)) {
Item item = new Item(ch, 1);
map.put(ch, item);
} else {
Item item = map.get(ch);
item.count = item.count + 1;
}
}

Collections.sort(list);
StringBuilder sb = new StringBuilder();
for (Item item : list) {
for (int i=1; i<=item.count; i++) {
sb.append(item.ch);
}
}
return sb.toString();
}
}

class Item implements Comparable {
public char ch;
public int count;

public Item(char ch, int count) {
this.ch = ch;
this.count = count;
}

@Override
public int compareTo(Item that) {
return that.count - this.count;
}
}

Minimum Number of Arrows to Burst Balloons

【题目】There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 10 4 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x start and x end bursts by an arrow shot at x if x start ≤ x ≤ x end . There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

【解答】要寻找看起来还是某种扫描线问题。在从左往右扫描的过程中，既然要尽量使得射出的箭少，那就要尽量到不得不射箭的时候再出手，即到最先出现的未打爆气球右边沿再射出箭，而这一箭要打爆其中所有碰到的气球。反复如此操作。（既然要考察右边沿，因此排序的时候必须按照 end，而不是 start 来排序。）

class Solution {
public int findMinArrowShots(int[][] points) {
if (points==null)
throw new IllegalArgumentException();

List el = new ArrayList(points.length);
for (int[] point : points) {
Point p = new Point(point[0], point[1]);
}

Collections.sort(el, new Comparator() {
@Override
public int compare(Point left, Point right) {
return left.end - right.end;
}
});

int index = 0;
int count = 0;
Integer rangeStart = null;
while (indexrangeStart) {
rangeStart = point.end; // keep the range start as far as possible
count++;
}

index++;
}

return count;
}
}

class Point {
public int start;
public int end;
public Point(int start, int end) {
this.start = start;
this.end = end;
}
}

Minimum Moves to Equal Array Elements

【题目】Given a  non-empty integer array of size  n , find the minimum number of moves required to make all array elements equal, where a move is incrementing  n – 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

【解答】每次只能移动 n-1 个元素且移动的方法是+1，要尽量让所有元素靠拢，那本质上其实意味着每次只能移动一个元素且移动方法是-1。这样，只需要找到其中的最小数，然后累加所有其他数和最小值的差值即可。顺便提一句，如果题目修改一下，移动的方法可以是+1 也可以是-1，那就不是找最小数，而是找中位数了。

class Solution {
public int minMoves(int[] nums) {
Integer min = null;
for (int num : nums) {
if (min==null || num<min)
min = num;
}

int total = 0;
for (int num : nums)
total += (num-min);

}
}

4Sum II

【题目】Given four lists A, B, C, D of integer values, compute how many tuples  (i, j, k, l) there are such that  A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2 28 to 2 28 – 1 and the result is guaranteed to be at most 2 31 – 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

【解答】四个数组，各取一个数，要求加起来为 0。似乎没有特别好的办法，死算肯定嵌套层数太多，时间复杂度可以到 n 的四次方。于是，折中的方法是，A 和 B 嵌套，找出两两配对所有的和的出现次数；再拿 C 和 D 嵌套，找出两两配对所有和的出现次数。再把这两个结果合并考察，找到加起来结果为 0 的组合。整体时间复杂度为 n 的平方，空间复杂度也为 n 的平方。

class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
if (A==null || B==null || C==null || D==null)
throw new IllegalArgumentException();

Map sumMap = new HashMap();
for (int a : A) {
for (int b : B) {
int count = sumMap.getOrDefault(a+b, 0);
count++;
sumMap.put(a+b, count);
}
}

int total = 0;
for (int c : C) {
for (int d : D) {
total += sumMap.getOrDefault(-(c+d), 0);
}
}

}
}

【题目】Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g i , which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s j . If s j >= g i , we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:

You may assume the greed factor is always positive.

You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

【解答】分饼干问题。

class Solution {
public int findContentChildren(int[] g, int[] s) {
if (g==null || s==null)
throw new IllegalArgumentException();
if (g.length==0 || s.length==0)
return 0;

Arrays.sort(g);
Arrays.sort(s);

int gi = 0, si = 0;
int count = 0;
while (gi<g.length && si<s.length) {
if (g[gi]<=s[si]) {
count++;
gi++;
si++;
} else {
si++;
}
}

return count;
}
}

132 Pattern

【题目】Given a sequence of n integers a 1 , a 2 , …, a n , a 132 pattern is a subsequence a i , a j , a k such that  ijk and a i < a k < a j . Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

【解答】要寻找一串数中是否存在“小-大-中”这样的模式。

• 首先考虑能不能成为 ai，如果能，那就返回结果，因为 ai<ak，而 ak<aj 是已经存在了的；
• 如果不能，那把它列为 aj 的候选，要求 aj 必须>ak；
• 如果再不能，那就把它列为 ak 的候选，此处没有要求。
class Solution {
public boolean find132pattern(int[] nums) {
if (nums==null) throw new IllegalArgumentException();
if (nums.length<3) return false;

Integer num2 = null;
Stack stack = new Stack();
for (int i=nums.length-1; i>=0; i--) {
int num1 = nums[i];
// check the case if num1 can be ai -
// if num1 is smaller than num2 we find the result
if (num2!=null && num1<num2)
return true;

// so num1 can't be ai, let's check if num1 can be aj -
// if so the numbers in the stack must be smaller than num1 because ak < aj
// if there are multiple we only keep the last one because:
// to match ai<ak<aj, since ak is smaller than aj, we want ak to be as largest as possible
while (!stack.isEmpty() && stack.peek()<num1)
num2 = stack.pop();

// so num1 can't be aj either, let num1 be an ak candidate -
stack.push(num1);
}

return false;
}
}

Circular Array Loop

【题目】

You are given a circular array  nums of positive and negative integers. If a number  k at an index is positive, then move forward  k steps. Conversely, if it’s negative (- k ), move backward  k steps. Since the array is circular, you may assume that the last element’s next element is the first element, and the first element’s previous element is the last element.

Determine if there is a loop (or a cycle) in nums . A cycle must start and end at the same index and the cycle’s length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

Example 1:

Input: [2,-1,1,2,2]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.

Example 2:

Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.

Example 3:

Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.

Note:

1. -1000 ≤ nums[i] ≤ 1000
2. nums[i] ≠ 0
3. 1 ≤ nums.length ≤ 5000

Could you solve it in O(n) time complexity and  O(1) extra space complexity?

【解答】我解是解出来了，但是属于基础解法，并没有做到上面 Follow Up 中要求的复杂度。思路是，每一个元素都尝试作为循环的开头，使用 set 来标记运行轨迹，同时也建立一个 boolean 型的变量来标记当前尝试是正向还是逆向。一旦发现遇到遍历过的元素，表示这次尝试失败；如果遇到起始元素，返回 true。

class Solution {
public boolean circularArrayLoop(int[] nums) {
if (nums==null) throw new IllegalArgumentException();
if (nums.length==0 || nums.length==1) return false;

for (int i=0; i<nums.length; i++) {
Set forwardIndices = new HashSet();
Set backwardIndices = new HashSet();
Integer originalItem = i;
boolean forward = nums[originalItem] > 0;
if (nums[originalItem] == 0)
continue;
if (forward && forwardIndices.contains(originalItem))
continue;
if (!forward && backwardIndices.contains(originalItem))
continue;

if (this.getNextIndex(nums, i)==i) {
continue;
}

Integer item = originalItem;
if (forward)
else

while (true) {
item = this.getNextIndex(nums, item);
if (item.equals(originalItem))
return true;

if (forward) {
if (nums[item]=0 || backwardIndices.contains(item))
break;
}
}
}

return false;
}

private int getNextIndex(int[] nums, int index) {
index = nums[index] + index;
while (index >= nums.length) {
index -= nums.length;
}
while (index < 0) {
index += nums.length;
}
return index;
}
}

Poor Pigs

【题目】There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?

Answer this question, and write an algorithm for the general case.

General case:

If there are n buckets and a pig drinking poison will die within  m minutes, how many pigs ( x ) you need to figure out the  poisonous bucket within  p minutes? There is exactly one bucket with poison.

#### Note:

1. A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
2. After a pig has instantly finished drinking buckets, there has to be a  cool down time  of  minutes. During this time, only observation is allowed and no feedings at all.
3. Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

【解答】1000 个桶，只有一个桶里面有毒。如果猪喝了毒药，15 分钟内死掉。问要在 1 小时内找到哪个桶，最少需要多少头猪。

class Solution {
public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
long rounds = minutesToTest / minutesToDie + 1;
// rounds ^ pigs >= buckets
long pigs = 0;
while (Math.pow(rounds, pigs)<buckets) {
pigs++;
}

return (int) pigs;
}
}

Repeated Substring Pattern

【题目】Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

【解答】要判断一个字符串是否有多个子字符串拼接而成。使用最直白的做法，考虑每一个字符为重复串开始的位置进行递归，如果字符串全部遍历完毕，而又没有多余的字符，就返回 true。

class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s==null)
throw new IllegalArgumentException();

if (s.length()<2)
return false;

for (int len=1; len<=s.length()-len; len++) {
if (s.length() % len == 0) {
int start = len;
boolean matched = true;
while (start<s.length()) {
if (!this.check(s, len, start)) {
matched = false;
break;
}
start += len;
}
if (matched)
return true;
}
}

return false;
}

private boolean check(String s, int len, int start) {
int i=0;
while (i<len) {
if (s.charAt(i) != s.charAt(start + i))
return false;
i++;
}
return true;
}
}

LFU Cache

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

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) – Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least  recently used key would be evicted.

Could you do both operations in  O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(3);       // returns 3
cache.get(4);       // returns 4

【解答】LFU 的缓存设计。

class LFUCache2 {
private Map map = new HashMap();
private Item dummyHead = new Item(0, 0, -1); // the list is sorted ascendingly
private Item dummyTail = new Item(0, 0, Integer.MAX_VALUE);
private int size = 0;
private int capacity;

public LFUCache2(int capacity) {
if (capacity<0) throw new IllegalArgumentException();
this.capacity = capacity;
}

public int get(int key) {
if (!map.containsKey(key))
return -1;

Item item = map.get(key);
int returnValue = item.value;
item.frequence = item.frequence + 1;
while (item.next != null && item.next.frequence<=item.frequence) {
this.swapWithNext(item);
item = item.next;
}

return returnValue;
}

public void put(int key, int value) {
if (capacity==0)
return;

if (map.containsKey(key)) {
Item item = map.get(key);
item.value = value;
item.frequence = item.frequence + 1;

this.moveForwardForSameFrequence(item);

return;
}

if (size == this.capacity) {
map.remove(item.key);

item.key = key;
item.value = value;
item.frequence = 1;

map.put(key, item);

this.moveForwardForSameFrequence(item);
} else {
Item item = new Item(key, value, 1);

current.prev = item;

item.next = current;

this.moveForwardForSameFrequence(item);

map.put(key, item);
size++;
}
}

private void moveForwardForSameFrequence(Item item) {
while (item.next.frequence<=item.frequence) {
this.swapWithNext(item);
}
}

private void swapWithNext(Item l) {
Item r = l.next;
Item prev = l.prev;
Item next = r.next;

prev.next = r;
next.prev = l;

l.next = next;
l.prev = r;

r.next = l;
r.prev = prev;
}
}

class Item {
public Integer key;
public Integer value;
public Integer frequence;
public Item next;
public Item prev;
public Item(Integer key, Integer value, Integer frequence) {
this.key = key;
this.value = value;
this.frequence = frequence;
this.next = null;
this.prev = null;
}
}

• 第一个是最常规的，存放 LFUCache 的 key 和 value；
• 第二个存放 key 和频率（出现次数）；
• 那么余下的问题是怎么实现淘汰机制，即在有 map 以外的 key 到来的时候，找到最近最不使用的 key 来，于是第三个使用的是一个值为 LinkedHashSet 的 map，这个 map 的 key 是前面提到的出现次数，而把实际的外部看起来的 LFUCache 的 key 放到了这个 LinkedHashSet 里面。

class LFUCache {
HashMap vals;
HashMap counts;
int cap;
int min = -1;
public LFUCache(int capacity) {
cap = capacity;
vals = new HashMap();
counts = new HashMap();
lists = new HashMap();
}

public int get(int key) {
if(!vals.containsKey(key))
return -1;
int count = counts.get(key);
counts.put(key, count+1);
lists.get(count).remove(key);
if(count==min && lists.get(count).size()==0)
min++;
if(!lists.containsKey(count+1))
return vals.get(key);
}

public void put(int key, int value) {
if(cap= cap) {
int evit = lists.get(min).iterator().next();
lists.get(min).remove(evit);
vals.remove(evit);
}
vals.put(key, value);
counts.put(key, 1);
min = 1;
}