从第 416 到第 460 题，跳过了需要付费的题目。付费的题目会单独放在一篇里面。
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:
- Each of the array element will not exceed 100.
- 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.
【解答】要划分数组成两个部分，这两个部分各自的和相等。
其实这道题可以问 k 个部分，两个部分是一个强化了的条件。整个数组的和（sum）是可以很容易得到的，那么分成两个部分，每个部分的和（sum/2）也就可以很容易得到了。于是这道题就变成了，能不能从数组中找出一些数，使之和为 sum/2？搜索求解即可。
求解期间做一点小优化，创建一个<index, <target, partitionable>> 这样的结构，表示源数组的下标 index 开始往后到底的这一段，能否存在一个子数组，使得和为 target。
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, <target, partitionable>>
Map<Integer, Map<Integer, Boolean>> cache = new HashMap<>();
return canPartition(nums, cache, target, 0);
}
private boolean canPartition(int[] nums, Map<Integer, Map<Integer, Boolean>> cache, int target, int index) {
if (index == nums.length)
return target == 0;
if (!cache.containsKey(index)) {
cache.put(index, new HashMap<>());
}
Map<Integer, Boolean> 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:
- The order of returned grid coordinates does not matter.
- 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<int[]> pacificAtlantic(int[][] matrix) {
if (matrix == null)
throw new IllegalArgumentException();
List<int[]> 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];
Queue pacificQueue = new LinkedList<>();
// 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];
Queue atlanticQueue = new LinkedList<>();
// 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) {
result.add(new int[] {i, j});
}
}
}
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))
queue.add(new Point(p.x-1, p.y));
if (this.mark(matrix, p.x, p.y, p.x, p.y-1, reachable))
queue.add(new Point(p.x, p.y-1));
if (this.mark(matrix, p.x, p.y, p.x+1, p.y, reachable))
queue.add(new Point(p.x+1, p.y));
if (this.mark(matrix, p.x, p.y, p.x, p.y+1, reachable))
queue.add(new Point(p.x, p.y+1));
}
}
private boolean mark(int[][] matrix, int x, int y, int nx, int ny, Boolean[][] reachable) {
if (nx<0 || ny<0 || nx>=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) orNx1(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.
Follow up:
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 上的数值。
一行一行遍历，每一行中从左往右遍历。对于每一个点，如果左侧和上方都不是 X，那就认为这是一艘新的 battleship。
class Solution {
public int countBattleships(char[][] board) {
int count = 0;
for (int i=0; i<board.length; i++) {
for (int j=0; j<board[0].length; j++) { if (board[i][j]=='.') continue; if (j>0 && board[i][j-1]=='X') continue;
if (i>0 && board[i-1][j]=='X') continue;
count++;
}
}
return count;
}
}
Strong Password Checker
【题目】A password is considered strong if below conditions are all met:
- It has at least 6 characters and at most 20 characters.
- It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
- 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.
【解答】规则很容易理解：
- 6~20 个字符；
- 必须包含小写字符、大写字符和数字；
- 不能包含连续三个相同字符。
但是困难的地方在于，题目不是问一个字符串是否符合条件，而是要求怎样通过最少的增删改来使得密码符合规则。题目类似于求编辑距离，只不过编辑距离只有一头（源字符串）确定，另一头是不确定的。如果只有一个规则，也会简单一些，三个规则混到一起，互相影响，使得题目非常困难。
挣扎了一段时间，就去讨论区看解答去了：
class Solution {
public int strongPasswordChecker(String s) {
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 < arr.length && over_len > 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 < arr.length; i++) { if (arr[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, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
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 的最大值。
既然是 O(n) 时间，排序什么的就别想了。拿到手感觉没有什么思路，要去找全部的 XOR 结果暴力解法需要 n 平方的复杂度。再有一点，我觉得可以从高位往低位一位一位去分析，而每一位都是独立的，且优先级有着明确的区别。比如数值部分的最高位在 XOR 能得到 1，总共有 x 种组合，那么在分析次高位的时候，只需要考虑这 x 种中，寻找能够得到 XOR 结果为 1 的即可。但是思路再往下，又不太好继续了。
下面的思路借鉴自讨论区的一个解法。现在 Medium 的题目居然也需要看解答了，叹气。
class Solution {
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for (int i = 31; i >= 0; i--){
// part 1:
// prefix mask
mask = mask | (1 << i);
// prefix set
Set set = new HashSet<>();
for (int num : nums){
set.add(num & mask);
}
// part 2:
int tmp = max | (1 << i);
for (int prefix : set){
if(set.contains(tmp ^ prefix)) {
max = tmp;
break;
}
}
}
return max;
}
}
我把思路整理了一下来说明上述代码。求解需要利用一个特性：若 a ^ b = c, a ^ c = b。循环体内的代码说明：
- 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:
- Input contains only lowercase English letters.
- 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.
- Input length is less than 50,000.
Example 1:
Input: "owoztneoer" Output: "012"
Example 2:
Input: "fviefuro" Output: "45"
【解答】要从无序的英文字母串还原到数字。
考虑个数字的英文所包含字母的特性。比如说字母 z，就只可能在 zero 中出现，因此很容易就找到了 zero 的个数。有一些并不是 unique 的，比如 seven，每个字母都可能在别的英文数中出现，但是 s 只能再 six 和 seven 中出现，因此一旦知道了 six，把 s 的次数减去 six 的次数，就可以得到 seven 的次数了。
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<Character, Integer> 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 ktimes. 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 104.
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 的问题，一下就豁然开朗了：
- 假设说有一个 sliding window，从左慢慢往右划，不断调整左右边界：左边吐出 char，右边吃进 char；
- 这个 window 里面的不同 char 各有多少个，通过一个 map 来记录；
- 这个 window 的左边界所对应的 char 作为所考察的 repeating char，在左边界固定的基础上不断右移右边界，记录 window 的最大值，如果其他 char 的数量超过了 k，那么需要右移左边界，吐出一个之前的 repeating char。
这类字符串寻找连续子串的问题，都可以考虑 sliding window 的方法。使用 sliding window 的一个好处有这么两个：
- 窗口内字符排列或数量增量变化。无论移动左侧还是右侧窗口边沿，都只变化一个字符。
- 窗口的左侧或者右侧固定，从而简化问题。像这道题就是总是考虑窗口左侧的 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; i<26; i++) {
if (i!=base) {
replacementCount += counters[i];
}
}
if (replacementCount>k) {
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());
}
}
Construct Quad Tree
【题目】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 val. isLeaf 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.
Your task is to use a quad tree to represent a given grid. The following example may help you understand the problem better:
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:
Nis less than1000and guaranteened to be a power of 2.- If you want to know more about the quad tree, you can refer to its wiki.
【解答】构造 Quad Tree。
没有太多可以说的。递归判断并合并节点，形成 quad tree。
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:
- The depth of the tree is at most
1000. - The total number of nodes is at most
5000.
【解答】没有太多可以说的。循环内按层遍历就好。
class Solution {
public List<List> levelOrder(Node root) {
List<List> result = new ArrayList<>();
if (root==null)
return result;
Queue level = new LinkedList<>();
level.add(root);
while (!level.isEmpty()) {
Queue nextLevel = new LinkedList<>();
List list = new ArrayList<>();
for (Node node : level) {
list.add(node.val);
if (node.children != null)
nextLevel.addAll(node.children);
}
result.add(list);
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:
【解答】要把多层的双向链表压平。
大致思路上应该说没有什么难的，但是细节处理的坑比较多。源链表节点的 next 始终要放到 stack 里面去，然后再看 child，如果 child 不为空，直接从 stack 里面取下一个节点；如果为空，则优先使用 child 为下一个节点。
在选中下一个节点之后，再重新链接的过程中，注意覆盖节点的所有 field，包括 next、prev、child。
class Solution {
public Node flatten(Node head) {
if (head==null)
return null;
Stack stack = new Stack<>();
Node cur = head;
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;
}
}
// link current to next
cur.child = null;
next.prev = cur;
cur.next = next;
cur = next;
}
return head;
}
}
All O`one Data Structure
【题目】Implement a data structure supporting the following operations:
- 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.
- 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.
- GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string
"". - 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。
有了这样的思路以后，建立一个 Item 元素，作为 value，里面需要存放前一个节点、后一个节点，实际取值，以及 key set。这里的前一个、后一个节点是用来保序用的。建立的 head 和 tail 是用于包住 value 形成的有序串，简化计算用的。
class Item {
public int value;
public Item next;
public Item prev;
public Set keys = new HashSet<>();;
}
class AllOne {
private Map<String, Item> map = new HashMap<>();
private Item head = new Item();
private Item tail = new Item();
/** Initialize your data structure here. */
public AllOne() {
this.head.next = this.tail;
this.tail.prev = this.head;
// dummy head and dummy tail
this.head.value = Integer.MIN_VALUE;
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);
next.keys.add(key);
} else {
// there is no item for newValue, create one
Item newItem = new Item();
newItem.value = newValue;
newItem.keys.add(key);
this.link(currentItem, newItem);
this.link(newItem, next);
map.put(key, newItem);
}
// remove the node if there's no key mapped to its value
if (currentItem.keys.isEmpty()) {
this.link(currentItem.prev, currentItem.next);
}
} else { // it's a new key
if (this.head.next.value == 1) {
// the item for new key (value==1) is already existed
this.head.next.keys.add(key);
map.put(key, this.head.next);
} else {
// new item needed
Item next = this.head.next;
Item newItem = new Item();
newItem.value = 1;
newItem.keys.add(key);
this.link(this.head, newItem);
this.link(newItem, next);
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()) {
this.link(prev, currentItem.next);
}
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) {
prev.keys.add(key);
this.map.put(key, prev);
return;
}
// there is no item for newValue, create one
Item newItem = new Item();
newItem.value = newValue;
newItem.keys.add(key);
Item next = prev.next;
this.link(prev, newItem);
this.link(newItem, next);
map.put(key, newItem);
}
/** Returns one of the keys with maximal value. */
public String getMaxKey() {
if (this.head.next == this.tail)
return "";
return this.tail.prev.keys.iterator().next();
}
/** Returns one of the keys with Minimal value. */
public String getMinKey() {
if (this.head.next == this.tail)
return "";
return this.head.next.keys.iterator().next();
}
}
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:
- Starting point is assumed to be valid, so it might not be included in the bank.
- If multiple mutations are needed, all mutations during in the sequence must be valid.
- 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<>();
current.add(start);
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
newCurrent.add(b);
} else {
newBank.add(b);
}
}
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:
- You may assume the interval’s end point is always bigger than its start point.
- 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 无重叠。
一开始，觉得这道题应该比较简单，扫描线问题嘛。上来先排序，完毕之后从左往右扫一遍——这也算是常规思路了。于是我把 intervals 按照 start 排序，然后尝试从中拿掉某些。结果超时了，于是使用一个二维数组优化，内存使用又超了：
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;
}
}
现在换一个角度，反过来想，如果是从零开始，找尽量多的无重叠 interval 呢？把搜索问题变成构造问题。
考虑排序，可根据什么排呢？二者是很不一样的。用 end 来排序，而不是 start：
- 如果按照 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:
- You may assume the interval’s end point is always bigger than its start point.
- 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 在它的右边。
肯定不能死算。仔细想一下，其实对每个 interval 我只关心它的右边界，和剩余所有 interval 的左边界。
如果它的右边界确定的时候，要找所有比它小的左边界，这就是一个典型的使用 TreeMap 的问题——key 是所有 interval 的左边界；value 是源数组中的 index。
class Solution {
public int[] findRightInterval(Interval[] intervals) {
if (intervals == null)
throw new IllegalArgumentException();
TreeMap<Integer, Integer> 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<Integer, Integer> 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<>();
newList.add(root.val);
for (int num : list) {
int added = num + root.val;
newList.add(added);
if (added==sum) total++;
}
int left = travel(root.left, newList, sum);
int right = travel(root.right, newList, sum);
total += left;
total += right;
return total;
}
}
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<Character, Integer> 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<Character, Integer> 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()) {
result.add(left);
// 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 ≤ 109.
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 小的那一个。
老实说，这一类题我是不太擅长做的。尝试了几种思路都没有发现特别好的解法。在讨论区我找到了我认为最清晰的解法，而且这种解法对于类似的这种问题有一定启发意义。大致思路是使用引入十叉数，因为每一个数字的后面，最多可能有从 0 到 9 这十个可能。于是从根往叶子方向一层一层遍历，直到找到第 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;
}
}
说明，从根节点开始往下一层一次统计，curr 指向当前节点，如果 curr 和 curr+1 之间的 steps 小于 k，那 curr 就在当前层前进；否则，curr 下潜到下一层去，这种情况下 k 需要-1 因为原节点已经遍历过了。
关于 steps 的计算（calSteps）：考虑边界情况，n2 和 n+1 二者中小的那个区减掉 n1，这里的+1 主要是考虑要把 n 这个数也算进去。
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.
【解答】要求硬币组成的楼梯形状的层数，不完整的层要舍弃。
我觉得是一个数学问题。第一层是有 1 枚硬币，第 x 层最多有 x 枚，等差数列，那么最多一共有 (1+x)*x/2 枚，这个数必须要大于等于 n，这是个一元二次方程，拿求根公式解一下就好。
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) 的时间复杂度，这就意味着一般的搜索和排序之类方法的都可以靠边站了 。
利用这些数范围的特性，在找一个数的时候，把这个数 x 减去 1 作为一个 index，让数组在该 index 上的数取负数，如果发现该数已经是负数了，那就说明这个数 x 就是重复的数。
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
List result = new LinkedList<>();
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
result.add(index + 1);
} 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.
Follow up:
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:
- All characters have an ASCII value in
[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<chars.length) {
if (fast==chars.length || chars[fast]!=chars[slow]) {
// recording always starts with the char
chars[recording++] = chars[slow];
if (fast-slow > 1) {
String num = "" + (fast-slow);
for (char n : num.toCharArray())
chars[recording++] = n;
}
slow = fast;
}
fast++;
}
return recording;
}
}
Add Two Numbers II
【题目】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.
Follow up:
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
【解答】两个用链表表示的数相加。常规操作，包括 fake/dummy head，进位符号的处理等等。
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));
ListNode dummyHead = new ListNode(0);
cur = dummyHead;
while (!res.isEmpty()) {
cur.next = res.pop();
cur = cur.next;
}
return dummyHead.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 (P0, P1, …, Pk) such that 0 ≤ P0 < P1 < … < Pk < N.
A subsequence slice (P0, P1, …, Pk) of array A is called arithmetic if the sequence A[P0], A[P1], …, A[Pk-1], A[Pk] 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 -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-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]
【解答】我最开始的思路是动态规划，划分成子问题。每个子问题是：
对于所有从 index 为 i 开始的 subsequence，在 interval 是 k 的情况下，解集用 c[i][k] 来表示，这个解集合我不需要知道具体内容，但我需要知道每个 subsequence 在包含特定个元素个数 p 的情况下个有多少种可能。那么对于一个新的 index j 且 j<i，考察 A[j] 和 A[i]:
A[j]-A[i] 为新的 interval，寻求解集 c[j][A[j]-A[i]]。看起来这个方法似乎是可以走得通的，但是明显无论从实现层面还是时间复杂度层面都过高了。为了缓存已得到的结果，我需要建立一个这样的数据结构来避开重复计算：Map<Integer, Map<Integer, Map<Integer, Integer>>>，含义是：<start_index, <interval, <sub_seq_len, count>>。因此这是一个三维的动态规划，我们一般只做一维到二维，而三维的话一般有更好的解决办法。[后记：其实第三维 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<Integer, Integer>[] 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.MIN_VALUE || 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 的距离。
基本思路很简单，遍历每一个点，并以之为 i，再以它到所有其他点距离的平方为 key，放到 map 里面去，value 为统计该距离出现的次数。
之后对于 map 中的每组 entry，value 的个数就表示了在选定 i 的情况下，有多少组距离相等，如果它是 x 的话，那么 x*(x-1) 就意味着有多少种组合。（我在注释里面列出了排列组合的两个基本公式，也是它的本质由来）
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<Integer, Integer> 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);
}
return total;
}
// 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)
result.add(i+1);
}
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:
- Search for a node to remove.
- 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
Another valid answer is [5,2,6,null,4,null,7].
5
/ \
2 6
\ \
4 7
【解答】要从一棵 BST 上面删除一个节点。分成几种情况考虑：
如果要删除的节点在左子树，递归调用左子树；
右子树同理；
最麻烦的是删除根节点，删掉了之后，如果原本有左子树，那就从左子树取最大的节点放到根上；反之，从右子树取最小的节点放到根上（不需要实际的节点替换，替换节点的数值即可）。
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root==null) return null;
if (key<root.val) {
root.left = this.deleteNode(root.left, key);
return root;
}
if (key>root.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<Character, Item> 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);
list.add(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 104 balloons.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. 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<Point> el = new ArrayList<>(points.length);
for (int[] point : points) {
Point p = new Point(point[0], point[1]);
el.add(p);
}
Collections.sort(el, new Comparator<Point>() {
@Override
public int compare(Point left, Point right) {
return left.end - right.end;
}
});
int index = 0;
int count = 0;
Integer rangeStart = null;
while (index<el.size()) {
Point point = el.get(index);
if (rangeStart==null || point.start>rangeStart) {
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);
return total;
}
}
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 -228 to 228 – 1 and the result is guaranteed to be at most 231 – 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<Integer, Integer> 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);
}
}
return total;
}
}
【题目】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 gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, 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 a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. 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].
【解答】要寻找一串数中是否存在 “小-大-中” 这样的模式。
这道题看起来似乎不难，却让我思考了很长时间。最开始的想法是，看起来是一道引入双指针，创建几个 O(1) 的变量，从左到右简单扫描一遍，就可以得到结果的题目。后来越想越发现不是这样的，并且如果只使用 O(1) 的变量，似乎是无法解答的。因为对于这道题中 ai、aj、ak 三个变量的寻找，在拿到候选的 aj 的时候，ai 和 ak 使用不同的组合，aj 有可行和不可行这样不同的可能，因此为了遍历 ai 和 ak 不同的组合而形成的可能性，需要使用至少 O(n) 的空间来创建一个类似数组的结构。
这个空间就是使用 stack 来实现，而这个 stack 存放的是 ak 的候选。从右往左扫描，考虑到 i、j、k 三个变数，ai 在 aj 的左侧，aj 在 ak 的左侧，因此扫描遍历到的数：
- 首先考虑能不能成为 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:
- -1000 ≤ nums[i] ≤ 1000
- nums[i] ≠ 0
- 1 ≤ nums.length ≤ 5000
Follow up:
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<Integer> forwardIndices = new HashSet<>();
Set<Integer> 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) {
forwardIndices.add(originalItem);
backwardIndices.add(originalItem);
continue;
}
Integer item = originalItem;
if (forward)
forwardIndices.add(originalItem);
else
backwardIndices.add(originalItem);
while (true) {
item = this.getNextIndex(nums, item);
if (item.equals(originalItem))
return true;
if (forward) {
if (nums[item]<=0 || forwardIndices.contains(item))
break;
forwardIndices.add(item);
} else {
if (nums[item]>=0 || backwardIndices.contains(item))
break;
backwardIndices.add(item);
}
}
}
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:
- A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
- After a pig has instantly finished drinking buckets, there has to be a cool down time of m minutes. During this time, only observation is allowed and no feedings at all.
- Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).
【解答】1000 个桶，只有一个桶里面有毒。如果猪喝了毒药，15 分钟内死掉。问要在 1 小时内找到哪个桶，最少需要多少头猪。
这道题貌似是一道数学题，也许在很久以前在一本数学有关的书上见过。一个小时，如果把喝的水分成 5 部分，每部分都混合起来让猪喝，可以喝+观察 4 次，但是可以得出 5 部分的结果，因为 4 次如果死了分别可以代表该次喝的水有毒，如果没死则按照排除法，得知剩下那一部分有毒。一头猪的存活情况，代表了 5 种可能，这就像是 5 进制，那么两头猪就可以表示 5^5=25 种，所以题中例子要求的是 5^x >= 1000，求 x 的最小值。用这样的算法推广可以得到：
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.
Follow up:
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(2); // returns -1 (not found) cache.get(3); // returns 3. cache.put(4, 4); // evicts key 1. cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4
【解答】LFU 的缓存设计。
和 LRU 类似，思路是使用一个普通 map 来处理 key-value 映射的问题，但是为了能够根据使用频率来淘汰元素，就引入了有序的链表，这样在访问的时候位置可能会发生邻近的移动。思路基本上没有什么特殊的，但是实现起来比较啰嗦。很遗憾下面这个解停在巨长的一个 test case，还不是超时，而是结果错误，这个 case 的步骤是如此之长，1000+的操作步骤，大概前 2/3 这段代码的执行是没问题的，之后不一致，我很难去分析原因了。
class LFUCache2 {
private Map<Integer, Item> 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();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
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) {
Item item = dummyHead.next;
map.remove(item.key);
item.key = key;
item.value = value;
item.frequence = 1;
map.put(key, item);
this.moveForwardForSameFrequence(item);
} else {
Item current = dummyHead.next;
Item item = new Item(key, value, 1);
dummyHead.next = item;
current.prev = item;
item.prev = dummyHead;
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;
}
}
我也看了讨论区高票的解法，对 LinkedHashSet 使用很合适，把根据访问频率挪位置等等操作都简化了。主要思路：
三个 HashMap：
- 第一个是最常规的，存放 LFUCache 的 key 和 value；
- 第二个存放 key 和频率（出现次数）；
- 那么余下的问题是怎么实现淘汰机制，即在有 map 以外的 key 到来的时候，找到最近最不使用的 key 来，于是第三个使用的是一个值为 LinkedHashSet 的 map，这个 map 的 key 是前面提到的出现次数，而把实际的外部看起来的 LFUCache 的 key 放到了这个 LinkedHashSet 里面。
在淘汰机制触发的时候，就看到 LinkedHashSet 优于普通 HashSet 的好处了——数据是存放在它内部的一个 LinkedList 里面的，因而是严格有序的。这个 list 上面所有的数，对应的 count 都是一致的，添加的时候总是在尾部添加，而淘汰的时候总是从头部淘汰，这就像是一个队列。那为什么不直接使用 LinkedList，而要使用 LinkedHashSet 呢？这就要用到 Set 的机制，当添加的元素已经在 Set 内存在了，就要把它挪到队尾，而不是添加重复元素。
除了以上三个 map，还需要一个 int min，用来记录最小的 count，因为淘汰首先要找到当前最小的 count，其次才在属于同一个 count 的 LinkedHashSet 里面找出需要淘汰的那个 key。
class LFUCache {
HashMap<Integer, Integer> vals;
HashMap<Integer, Integer> counts;
HashMap<Integer, LinkedHashSet<Integer>> lists;
int cap;
int min = -1;
public LFUCache(int capacity) {
cap = capacity;
vals = new HashMap<>();
counts = new HashMap<>();
lists = new HashMap<>();
lists.put(1, new LinkedHashSet<>());
}
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))
lists.put(count+1, new LinkedHashSet<>());
lists.get(count+1).add(key);
return vals.get(key);
}
public void put(int key, int value) {
if(cap<=0)
return;
if(vals.containsKey(key)) {
vals.put(key, value);
get(key);
return;
}
if(vals.size() >= 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;
lists.get(1).add(key);
}
}
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》