- 2019-11-02
- 2019-11-03
- 2019-11-04
- 2019-11-06
- 2019-11-10
- 2019-11-11
- 2019-11-13
- 2019-11-14
- 2019-11-17
- 2019-11-18
- 2019-11-20
- 2019-11-24
- 2019-11-30

# 2019-11-02

## 539. Minimum Time Difference

### Description

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list. Example 1: Input: [“23:59”,”00:00”] Output: 1 Note: The number of time points in the given list is at least 2 and won’t exceed 20000. The input time is legal and ranges from 00:00 to 23:59.

### Solution

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public int findMinDifference(List<String> timePoints) {
int[] times = new int[timePoints.size()];
int count = 0;
for (String time : timePoints) {
times[count++] = convert(time);
}
Arrays.sort(times);
int min = Integer.MAX_VALUE;
for(int i = 0;i<times.length-1;i++){
min = Math.min(min,times[i+1]-times[i]);
}
min = Math.min(min,Math.abs(times[0]+24*60-times[times.length-1]));
return min;
}
private int convert(String time) {
//use split will cause time waste.
//since you know the format, can call them directly.
int hour = 10 * (time.charAt(0) - '0') + (time.charAt(1) - '0');
int minute = 10 * (time.charAt(3) - '0') + (time.charAt(4) - '0');
return hour * 60 + minute;
}
}
```

## 24. Swap Nodes in Pairs

### Description

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

### Solution

```
/**
* Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = dummy.next;
while (cur != null && cur.next != null) {
ListNode sec = cur.next;
cur.next = sec.next;
sec.next = cur;
pre.next = sec;
pre = cur;
cur = cur.next;
}
return dummy.next;
}
}
```

## 71. Simplify Path

### Description

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

```
Example 1:
Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:
Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:
Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Example 4:
Input: "/a/./b/../../c/"
Output: "/c"
Example 5:
Input: "/a/../../b/../c//.//"
Output: "/c"
Example 6:
Input: "/a//b////c/d//././/.."
Output: "/a/b/c"
```

### Solution

```
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new LinkedList<>();
for (String s : path.split("/")) {
if (s.equals("..")) {
//use poll() can avoid empty with pop()
stack.poll();
} else if (!s.equals("") && !s.equals(".")) {
stack.push(s);
}
}
StringBuilder sb = new StringBuilder();
if (stack.size() == 0) {
return "/";
}
while (stack.size() != 0) {
sb.append("/").append(stack.pollLast());
}
return sb.toString();
}
}
```

# 2019-11-03

## 173. Binary Search Tree Iterator

### Description

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

```
Example:
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // return 3
iterator.next(); // return 7
iterator.hasNext(); // return true
iterator.next(); // return 9
iterator.hasNext(); // return true
iterator.next(); // return 15
iterator.hasNext(); // return true
iterator.next(); // return 20
iterator.hasNext(); // return false
```

Note:

next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree. You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

### Solution

```
import java.util.Stack;
/**
* Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
* right; TreeNode(int x) { val = x; } }
*/
class BSTIterator {
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<>();
pushAll(root);
}
/**
* @return the next smallest number
*/
public int next() {
TreeNode cur = stack.pop();
//next node will always on its right.
pushAll(cur.right);
return cur.val;
}
private void pushAll(TreeNode root) {
while (root != null) {
stack.push(root);
root = root.left;
}
}
/**
* @return whether we have a next smallest number
*/
public boolean hasNext() {
return !stack.isEmpty();
}
}
/**
* Your BSTIterator object will be instantiated and called as such: BSTIterator obj = new
* BSTIterator(root); int param_1 = obj.next(); boolean param_2 = obj.hasNext();
*/
```

## 328. Odd Even Linked List

### Description

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

```
Example 1:
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
```

Note:

The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on …

### Solution

```
/**
* Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int
* x) { val = x; } }
*/
class Solution {
//We just need to form a linked list of all odd nodes(X) and another linked list of all even nodes(Y). Afterwards, we link Y to the end of X, and return the head of X.
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
```

## 304. Range Sum Query 2D - Immutable

### Description

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

```
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
```

Note: You may assume that the matrix does not change. There are many calls to sumRegion function. You may assume that row1 ≤ row2 and col1 ≤ col2.

### Solution

```
class NumMatrix {
int[][] sum;
public NumMatrix(int[][] matrix) {
int Y = matrix.length;
//how to handle null matrix or matrix of size 0;
if(Y==0) return;
int X = matrix[0].length;
sum = new int[Y][X];
sum[0][0] = matrix[0][0];
for (int x = 1; x < X; x++) {
sum[0][x] = sum[0][x - 1] + matrix[0][x];
}
for (int y = 1; y < Y; y++) {
sum[y][0] = sum[y - 1][0] + matrix[y][0];
}
for (int y = 1; y < Y; y++) {
for (int x = 1; x < X; x++) {
sum[y][x] = matrix[y][x] + sum[y - 1][x] + sum[y][x - 1] - sum[y - 1][x - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if (col1 - 1 < 0 && row1 - 1 < 0) {
return sum[row2][col2];
}
if (col1 - 1 < 0) {
return sum[row2][col2] + -sum[row1 - 1][col2];
}
if (row1 - 1 < 0) {
return sum[row2][col2] + -sum[row2][col1 - 1];
}
return sum[row2][col2] + sum[row1 - 1][col1 - 1] - sum[row1 - 1][col2] - sum[row2][col1 - 1];
}
}
/**
* Your NumMatrix object will be instantiated and called as such: NumMatrix obj = new
* NumMatrix(matrix); int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
```

## 698. Partition to K Equal Sum Subsets

### Description

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16. 0 < nums[i] < 10000.

### Solution

```
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int num:nums)sum += num;
//sum cannot be divided by k then there's no way to split.
if(k <= 0 || sum%k != 0)return false;
int[] visited = new int[nums.length];
return canPartition(nums, visited, 0, k, 0, 0, sum/k);
}
public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target){
//already found k-1 subsets then the rest is guarenteed to have sum k
if(k==1)return true;
//found a subset, and looking for next subset.
//start from 0 to end, and look in the rest unvisited element.
if(cur_sum == target && cur_num>0)return canPartition(nums, visited, 0, k-1, 0, 0, target);
//will skip the loop and save lots of time.
if(cur_sum>target) return false;
for(int i = start_index; i<nums.length; i++){
if(visited[i] == 0){
visited[i] = 1;
if(canPartition(nums, visited, i+1, k, cur_sum + nums[i], cur_num++, target))return true;
visited[i] = 0;
}
}
return false;
}
}
```

## 179. Largest Number

### Description

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2] Output: “210” Example 2:

Input: [3,30,34,5,9] Output: “9534330” Note: The result may be very large, so you need to return a string instead of an integer.

### Solution

```
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0)
return "";
String[] s_nums = new String[nums.length];
for (int i = 0; i < nums.length; i++)
s_nums[i] = String.valueOf(nums[i]);
//compare by string but not integer.
Comparator<String> comp = new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String s1 =o1 + o2;
String s2 = o2 + o1;
return s2.compareTo(s1);
}
};
Arrays.sort(s_nums,comp);
if(s_nums[0].charAt(0) == '0')
return "0";
StringBuilder sb =new StringBuilder();
for(String s: s_nums){
sb.append(s);
}
return sb.toString();
}
}
```

# 2019-11-04

## 277. Find the Celebrity

### Description

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

```
Example 1:
Input: graph = [
[1,1,0],
[0,1,0],
[1,1,1]
]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.
Example 2:
Input: graph = [
[1,0,1],
[1,1,0],
[0,1,1]
]
Output: -1
Explanation: There is no celebrity.
```

Note:

The directed graph is represented as an adjacency matrix, which is an n x n matrix where a[i][j] = 1 means person i knows person j while a[i][j] = 0 means the contrary. Remember that you won’t have direct access to the adjacency matrix.

### Solution

```
/* The knows API is defined in the parent class Relation.
boolean knows(int a, int b); */
//no need build a graph and implement topological sort.
public class Solution extends Relation {
public int findCelebrity(int n) {
int candidate = 0;
for (int i = 1; i < n; i++) {
if(knows(candidate,i)) candidate = i;
}
for(int i = 0;i<n;i++){
if(i !=candidate && (knows(candidate,i) || !knows(i,candidate)))
return -1;
}
return candidate;
}
}
```

## 211. Add and Search Word - Data structure design

### Description

Design a data structure that supports the following two operations:

void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

```
Example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
```

### Solution

```
class WordDictionary {
private class Node {
Node[] alpha;
boolean isEnd;
public Node() {
alpha = new Node[26];
isEnd = false;
}
}
Node root;
/**
* Initialize your data structure here.
*/
public WordDictionary() {
root = new Node();
}
/**
* Adds a word into the data structure.
*/
public void addWord(String word) {
char[] c_list = word.toCharArray();
Node cur = root;
for (char c : c_list) {
if (cur.alpha[c - 'a'] == null) {
cur.alpha[c - 'a'] = new Node();
}
cur = cur.alpha[c - 'a'];
}
cur.isEnd = true;
}
/**
* Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
*/
public boolean search(String word) {
return searchUtil(word.toCharArray(), 0, root);
}
//main idea is when met a '.', use for loop to check.
private boolean searchUtil(char[] word, int idx, Node cur) {
if (idx == word.length) {
return cur.isEnd;
}
if (word[idx] != '.') {
return cur.alpha[word[idx] - 'a'] != null && searchUtil(word, idx + 1, cur.alpha[word[idx] - 'a']);
} else {
for (int i = 0; i < 26; i++) {
if (cur.alpha[i] != null) {
if(searchUtil(word,idx+1,cur.alpha[i])){
return true;
}
}
}
}
return false;
}
}
/**
* Your WordDictionary object will be instantiated and called as such: WordDictionary obj = new WordDictionary(); obj.addWord(word); boolean param_2 =
* obj.search(word);
*/
```

# 2019-11-06

## 166. Fraction to Recurring Decimal

### Description

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:

Input: numerator = 1, denominator = 2 Output: “0.5” Example 2:

Input: numerator = 2, denominator = 1 Output: “2” Example 3:

Input: numerator = 2, denominator = 3 Output: “0.(6)”

### Solution

```
import java.util.HashMap;
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
if ((numerator > 0) ^ (denominator > 0)) {
sb.append("-");
}
long num = Math.abs((long) numerator);
long den = Math.abs((long) denominator);
sb.append(num / den);
num %= den;
if (num == 0)
return sb.toString();
sb.append(".");
HashMap<Long, Integer> map = new HashMap<>();
map.put(num, sb.length());
//num 是个余数，如果这个余数出现过，那就会出现循环，就可以在这里结束。
while (num != 0) {
num *= 10;
sb.append(num / den);
num %= den;
if (map.containsKey(num)) {
int idx = map.get(num);
//map记录了余数出现的位置，插入左括号。
sb.insert(idx, "(");
sb.append(")");
return sb.toString();
} else {
map.put(num, sb.length());
}
}
return sb.toString();
}
}
```

# 2019-11-10

## 1041. Robot Bounded In Circle

### Description

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

“G”: go straight 1 unit; “L”: turn 90 degrees to the left; “R”: turn 90 degress to the right. The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

```
Example 1:
Input: "GGLLGG"
Output: true
Explanation:
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
Example 2:
Input: "GG"
Output: false
Explanation:
The robot moves north indefinitely.
Example 3:
Input: "GL"
Output: true
Explanation:
The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
```

Note:

1 <= instructions.length <= 100 instructions[i] is in {‘G’, ‘L’, ‘R’}

### Solution

```
class Solution {
//(x,y) is the location of chopper.
//d[i] is the direction he is facing.
//i = (i + 1) % 4 will turn right
//i = (i + 3) % 4 will turn left
Check the final status after instructions.
public boolean isRobotBounded(String instructions) {
int[][] dirs = new int[][][[0, 1], [1, 0], [0, -1], [-1, 0]];
int x = 0, y = 0;
int dir = 0;
//if at the end of instruction, the robot does not face north,
//then it will go back with 4 insc.
for (char c : instructions.toCharArray()) {
if (c == 'R') {
dir = (dir + 1) % 4;
} else if (c == 'L') {
dir = (dir + 3) % 4;
} else {
x += dirs[dir][0];
y += dirs[dir][1];
}
}
return (x == 0 && y == 0) || dir != 0;
}
}
```

## 1052. Grumpy Bookstore Owner

### Description

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

```
Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
```

Note:

1 <= X <= customers.length == grumpy.length <= 20000 0 <= customers[i] <= 1000 0 <= grumpy[i] <= 1

### Solution

```
class Solution {
//sliding window to count max.
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int len = customers.length;
int sum = 0;
int sum_grumpy = 0;
for (int i = 0; i < len; i++) {
if (grumpy[i] == 0) {
sum += customers[i];
customers[i] = 0;
} else {
sum_grumpy += customers[i];
}
}
if (len <= X) {
return sum_grumpy + sum;
}
sum_grumpy = 0;
int max_time = Integer.MIN_VALUE;
for (int i = 0; i < X; i++) {
sum_grumpy += customers[i];
}
max_time = Math.max(sum_grumpy,max_time);
for (int i = 1; i < len - X +1; i++) {
sum_grumpy -= customers[i-1] ;
sum_grumpy += customers[i+X-1];
max_time = Math.max(sum_grumpy,max_time);
}
return sum+max_time;
}
}
```

### Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

```
Example:
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
```

### Solution

```
import java.util.ArrayList;
import java.util.List;
class Solution {
List<List<String>> res;
List<String> currLst;
public List<List<String>> partition(String s) {
res = new ArrayList<>();
currLst = new ArrayList<>();
helper(s,0);
return res;
}
private void helper(String s, int left){
if(left >= s.length() && currLst.size()!=0){
res.add(new ArrayList<>(currLst));
return;
}
for(int i = left; i<s.length();i++){
if(isPalindrome(s,left,i)){
if(i == left){
currLst.add(Character.toString(s.charAt(i)));
}else{
currLst.add(s.substring(left,i+1));
}
helper(s,i+1);
currLst.remove(currLst.size()-1);
}
}
}
private boolean isPalindrome(String str, int l, int r){
if(l==r) return true;
while(l<r){
if(str.charAt(l)!=str.charAt(r)) return false;
l++;r--;
}
return true;
}
}
```

# 2019-11-11

## 1130. Minimum Cost Tree From Leaf Values

### Description

Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children; The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.) The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively. Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

```
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees. The first has non-leaf node sum 36, and the second has non-leaf node sum 32.
24 24
/ \ / \
12 4 6 8
/ \ / \
6 2 2 4
Constraints:
2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).
```

### Solution

```
class Solution {
public int mctFromLeafValues(int[] arr) {
int len = arr.length;
int[][] dp = new int[len][len];
int[][] localMax = new int[len][len];
for (int i = 0; i < len; i++) {
int localmax = 0;
for (int j = i; j < len; j++) {
if (arr[j] > localmax) {
localmax = arr[j];
}
localMax[i][j] = localmax;
}
}
for (int j = 1; j < len; j++) {
for (int i = j-1; i>=0;i--) {
dp[i][j] = Integer.MAX_VALUE;
if (j == i + 1) {
dp[i][j] = arr[i] * arr[j];
} else {
for(int k = i;k<j;k++){
//dp[i][j] is the sum of non-leaves node in range i and j.
//add up left and right tree, then add the production of max leaf node in left and right.
int temp = dp[i][k] + dp[k+1][j] + localMax[i][k]*localMax[k+1][j];
dp[i][j] = Math.min(dp[i][j],temp);
}
}
}
}
return dp[0][len-1];
}
}
```

## 1091. Shortest Path in Binary Matrix

### Description

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, …, C_k such that:

Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner) C_1 is at location (0, 0) (ie. has value grid[0][0]) C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1]) If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0). Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

```
Example 1:
Input: [[0,1],[1,0]]
Output: 2
Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
```

Note:

1 <= grid.length == grid[0].length <= 100 grid[r][c] is 0 or 1

### Solution

```
//Simple BFS
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}
int X = grid[0].length;
int Y = grid.length;
if (grid[0][0] == 1 || grid[Y - 1][X - 1] == 1) {
return -1;
}
int res = 1;
boolean[][] visited = new boolean[Y][X];
int[][] dirs = new int[][][[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0});
while (!queue.isEmpty()) {
Queue<int[]> queue_temp = new LinkedList<>();
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == Y - 1 && cur[1] == X - 1) {
return res;
}
for (int dir = 0; dir < 8; dir++) {
int nextX = cur[0] + dirs[dir][0];
int nextY = cur[1] + dirs[dir][1];
if (nextX >= 0 && nextX < X && nextY >= 0 && nextY < Y &&
!visited[nextX][nextY] && grid[nextX][nextY] == 0) {
visited[nextX][nextY] = true;
queue_temp.offer(new int[]{nextX,nextY});
}
}
}
queue = queue_temp;
res++;
}
return -1;
}
}
```

## 957. Prison Cells After N Days

### Description

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied. Otherwise, it becomes vacant. (Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

```
Example 1:
Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation:
The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
Example 2:
Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]
```

Note:

cells.length == 8 cells[i] is in {0, 1} 1 <= N <= 10^9

### Solution

```
class Solution {
public int[] prisonAfterNDays(int[] cells, int N) {
Map<String, Integer> seen = new HashMap<>();
while (N > 0) {
int[] cellsNext = new int[8];
for(int i = 1;i<7;i++){
cellsNext[i] = cells[i-1]==cells[i+1]?1:0;
}
seen.put(Arrays.toString(cells),N--);
cells = cellsNext;
String cells_str = Arrays.toString(cells);
//met before,and the loop size is {seen.get(cells_str)-N}
if(seen.containsKey(cells_str)){
N %= (seen.get(cells_str)-N);
}
}
return cells;
}
}
```

# 2019-11-13

## 636. Exclusive Time of Functions

### Description

On a single threaded CPU, we execute some functions. Each function has a unique id between 0 and N-1.

We store logs in timestamp order that describe when a function is entered or exited.

Each log is a string with this format: “{function_id}:{“start” | “end”}:{timestamp}”. For example, “0:start:3” means the function with id 0 started at the beginning of timestamp 3. “1:end:2” means the function with id 1 ended at the end of timestamp 2. |

A function’s exclusive time is the number of units of time spent in this function. Note that this does not include any recursive calls to child functions.

The CPU is single threaded which means that only one function is being executed at a given time unit.

Return the exclusive time of each function, sorted by their function id.

```
Example 1:
Input:
n = 2
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3, 4]
Explanation:
Function 0 starts at the beginning of time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 1 starts at the beginning of time 2, executes 4 units of time and ends at time 5.
Function 0 is running again at the beginning of time 6, and also ends at the end of time 6, thus executing for 1 unit of time.
So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.
```

Note:

1 <= n <= 100 Two functions won’t start or end at the same time. Functions will always log when they exit.

### Solution

```
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[n];
int prevTime = 0;
for(String log :logs){
String[] logArray = log.split(":");
int idx = Integer.parseInt(logArray[0]);
int curTime = Integer.parseInt(logArray[2]);
if(!stack.isEmpty()){
res[stack.peek()] += curTime- prevTime;
}
prevTime = curTime;
if("start".equals(logArray[1])){
stack.push(idx);
}else {
//why plus 1?
//at the end, this one second belongs to current function.
//i.e. method 1 start from 2 , end at 5, occupy 2,3,4,5 total 4 sec.
//so prevTime will also increase one at the end of 5 which is start of 6.
res[stack.pop()] ++;
prevTime++;
}
}
return res;
}
}
```

## 909. Snakes and Ladders

### Description

```
On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows:
You start on square 1 of the board (which is always in the last row and first column). Each move, starting from square x, consists of the following:
You choose a destination square S with number x+1, x+2, x+3, x+4, x+5, or x+6, provided this number is <= N*N.
(This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations, regardless of the size of the board.)
If S has a snake or ladder, you move to the destination of that snake or ladder. Otherwise, you move to S.
A board square on row r and column c has a "snake or ladder" if board[r][c] != -1. The destination of that snake or ladder is board[r][c].
Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving. (For example, if the board is `[[4,-1],[-1,3]]`, and on the first move your destination square is `2`, then you finish your first move at `3`, because you do not continue moving to `4`.)
Return the least number of moves required to reach square N*N. If it is not possible, return -1.
Example 1:
Input: [
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation:
At the beginning, you start at square 1 [at row 5, column 0].
You decide to move to square 2, and must take the ladder to square 15.
You then decide to move to square 17 (row 3, column 5), and must take the snake to square 13.
You then decide to move to square 14, and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
It can be shown that you need at least 4 moves to reach the N*N-th square, so the answer is 4.
Note:
2 <= board.length = board[0].length <= 20
board[i][j] is between 1 and N*N or is equal to -1.
The board square with number 1 has no snake or ladder.
The board square with number N*N has no snake or ladder.
```

### Solution

```
class Solution {
public int snakesAndLadders(int[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return -1;
}
int N = board.length;
int target = N * N;
boolean[] visited = new boolean[N * N + 1];
visited[1] = true;
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
int step = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int cur = queue.poll();
for (int j = 1; j <= 6; j++) {
int[] pos = numToPos(cur + j, N);
int next;
if (board[pos[0]][pos[1]] == -1) {
next = cur + j;
} else {
next = board[pos[0]][pos[1]];
}
if (next == target) {
return step;
}
//should mark next as visited.
//otherwise consider this:
//[1, 1, -1]
//[1, 1, 1]
//[-1,1, 1]
//it will cause infinent loop if not do so.
if(!visited[next]){
queue.offer(next);
visited[next] = true;
}
}
}
step++;
}
return -1;
}
private int posToNum(int[] pos, int n) {
int row = n - 1 - pos[0];
int col = row % 2 == 0 ? pos[1] + 1 : n - pos[1];
return row * n + col;
}
private int[] numToPos(int target, int n) {
int row = (target - 1) / n;
int col = (target - 1) % n;
int x = n - 1 - row;
int y = row % 2 == 0 ? col : n - 1 - col;
return new int[]{x, y};
}
}
```

## 875. Koko Eating Bananas

### Description

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

```
Example 1:
Input: piles = [3,6,7,11], H = 8
Output: 4
Example 2:
Input: piles = [30,11,23,4,20], H = 5
Output: 30
Example 3:
Input: piles = [30,11,23,4,20], H = 6
Output: 23
```

Note:

1 <= piles.length <= 10^4 piles.length <= H <= 10^9 1 <= piles[i] <= 10^9

### Solution

```
import java.util.Arrays;
class Solution {
public int minEatingSpeed(int[] piles, int H) {
int maxPile = Arrays.stream(piles).max().getAsInt();
int low = 1, high = maxPile;
//binary search if they can finish, if not, then increase K.
while(low<=high){
int mid = low + (high-low)/2;
if(!canEatAll(piles,mid,H)){
low = mid+1;
}else{
high = mid-1;
}
}
return low;
}
private boolean canEatAll(int[] piles, int K, int H){
int sum = 0;
for(int num:piles){
sum += num/K;
if(num%K != 0){
sum++;
}
}
return sum <= H;
}
}
```

# 2019-11-14

## 609. Find Duplicate File in System

### Description

Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths.

A group of duplicate files consists of at least two files that have exactly the same content.

A single directory info string in the input list has the following format:

“root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content)”

It means there are n files (f1.txt, f2.txt … fn.txt with content f1_content, f2_content … fn_content, respectively) in directory root/d1/d2/…/dm. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of group of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

“directory_path/file_name.txt”

```
Example 1:
Input:
["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]
Output:
[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
```

Note:

No order is required for the final output. You may assume the directory name, file name and file content only has letters and digits, and the length of file content is in the range of [1,50]. The number of files given is in the range of [1,20000]. You may assume no files or directories share the same name in the same directory. You may assume each given directory info represents a unique directory. Directory path and file info are separated by a single blank space.

Follow-up beyond contest: Imagine you are given a real file system, how will you search files? DFS or BFS? If the file content is very large (GB level), how will you modify your solution? If you can only read the file by 1kb each time, how will you modify your solution? What is the time complexity of your modified solution? What is the most time-consuming part and memory consuming part of it? How to optimize? How to make sure the duplicated files you find are not false positive?

### Solution

```
class Solution {
public List<List<String>> findDuplicate(String[] paths) {
List<List<String>> res = new ArrayList<>();
int len = paths.length;
if(len == 0) return res;
Map<String, Set<String>> map = new HashMap<>();
for(String path: paths){
String[] strs = path.split(" ");
for(int i = 1;i<strs.length;i++){
int idx = strs[i].indexOf("(");
String fileName = strs[0] + "/" + strs[i].substring(0,idx);
String content = strs[i].substring(idx);
Set<String> fileNames = map.getOrDefault(content,new HashSet<>());
fileNames.add(fileName);
map.put(content,fileNames);
}
}
for (String key : map.keySet()) {
if (map.get(key).size() > 1) {
res.add(new ArrayList<String>(map.get(key)));
}
}
return res;
}
}
```

### Follow-up

Question-1: Imagine you are given a real file system, how will you search files? DFS or BFS?

Answer: core idea: DFS Reason: if depth of directory is not too deeper, which is suitable to use DFS, comparing with BFS.

```
import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.attribute.BasicFileAttributes;
import java.security.MessageDigest;
import java.math.BigInteger;
class Directory {
List<Directory> subDirectories;
List<File> files;
}
public static String makeHashQuick(File file) {
try {
FileInputStream fileInput = new FileInputStream(file);
byte[] data = new byte[(int) file.length()];
fileInput.read(data);
fileInput.close();
MessageDigest md = MessageDigest.getInstance("MD5");
String fileHash = new BigInteger(1, md.digest(data)).toString(16);
return fileHash;
} catch (IOException e) {
throw new RuntimeException("can't read file: " + file.getAbsolutePath(), e);
}
}
public static void findDuplicatedFilesByMD5FromFile(Map<String, List<String>> lists, File file) {
String fileHash = makeHashQuick(file)
List<String> list = lists.get(fileHash);
if (list==null) {
list = new LinkedList<String>();
lists.put(fileHash, list);
}
list.add(file.getAbsolutePath());
}
public static void findDuplicatedFilesByMD5(Map<String, List<String>> lists, Directory dir) {
for (File file: dir.files) {
findDuplicatedFilesByMD5FromFile(lists, file);
}
for (Directory curDir: dir.subDirectories) {
findDuplicatedFilesByMD5(lists, curDir);
}
}
public static List<List<String>> storeDuplicateFiles(Directory dir) {
List<List<String>> ret = new ArrayList<List<String>>();
Map<String, List<String>> listsByMD5 = new HashMap<String, List<String>>();
findDuplicatedFilesByMD5(listsByMD5, dir);
for (List<String> list: listsByMD5) {
if (list.size()>1) {
ret.add(list);
}
}
return ret;
}
```

Question-2: If the file content is very large (GB level), how will you modify your solution?

Answer: core idea: make use of meta data, like file size before really reading large content. Two steps: DFS to map each size to a set of paths that have that size: Map<Integer, Set> For each size, if there are more than 2 files there, compute hashCode of every file by MD5, if any files with the same size have the same hash, then they are identical files: Map<String, Set>, mapping each hash to the Set of filepaths+filenames. This hash id’s are very very big, so we use the Java library BigInteger.

```
public static void findDuplicatedFilesBySizeFromFile(Map<Integer, List<String>> lists, File file) {
try {
Path filePath = Paths.get(file.getAbsolutePath());
BasicFileAttributes attr = Files.readAttributes(filePath, BasicFileAttributes.class);
int size = attr.size();
List<String> list = lists.get(size);
if (list==null) {
list = new LinkedList<String>();
lists.put(size, list);
}
list.add(file.getAbsolutePath());
} catch (IOException e) {
throw new RuntimeException("can't read file attributes: " + file.getAbsolutePath(), e);
}
}
public static void findDuplicatedFilesBySize(Map<Integer, List<String>> lists, Directory dir) {
for (File file: dir.files) {
findDuplicatedFilesBySizeFromFile(lists, file);
}
for (Directory curDir: dir.subDirectories) {
findDuplicatedFilesBySize(lists, curDir);
}
}
public static List<List<String>> storeDuplicateFiles(Directory dir) {
List<List<String>> ret = new ArrayList<List<String>>();
Map<Integer, List<String>> listsBySize = new HashMap<Integer, List<String>>();
findDuplicatedFilesBySize(listsBySize, dir);
Map<String, List<String>> listsByMD5 = new HashMap<String, List<String>>)();
for (List<String> list: listsBySize) {
if (list.size()>1) {
for (String fileName: list) {
findDuplicatedFilesByMD5FromFile(listsByMD5, new File(fileName));
}
}
}
for (List<String> list: listsByMD5) {
if (list.size()>1) {
ret.add(list);
}
}
return ret;
}
```

To optimize Step-2. In GFS, it stores large file in multiple “chunks” (one chunk is 64KB). we have meta data, including the file size, file name and index of different chunks along with each chunk’s checkSum(the xor for the content). For step-2, we just compare each file’s checkSum. Disadvantage: there might be flase positive duplicates, because two different files might share the same checkSum. Question-3: If you can only read the file by 1kb each time, how will you modify your solution?

Answer: makeHashQuick Function is quick but memory hungry, might likely to run with java -Xmx2G or the likely to increase heap space if RAM avaliable. we might need to play with the size defined by “buffSize” to make memory efficient.

```
import java.io.RandomAccessFile;
public static String makeHashLean(File infile) {
RandomAccessFile file = new RandomAccessFile(infile, "r");
int buffSize = 1024;
byte[] buffer = new byte[buffSize];
// calculate the hash of the whole file
long offset = file.length();
long read = 0;
int unitsize;
while(read<offset) {
unitsize = (int) (((offset-read)>=buffSize)?buffSize:(offset-read));
file.read(buffer, 0, unitsize);
md.update(buffer, 0, unitsize);
read += unitsize;
}
file.close();
String hash = new BigInteger(1, md.digest()).toString(16);
return hash;
}
```

Question-4: What is the time complexity of your modified solution? What is the most time-consuming part and memory consuming part of it? How to optimize?

Answer: hashing part is the most time-consuming and memory consuming. optimize as above mentioned, but also introduce false positive issue. Question-5: How to make sure the duplicated files you find are not false positive?

Answer: Question-2-Answer-1 will avoid it. We need to compare the content chunk by chunk when we find two “duplicates” using checkSum.

In preparing for my Dropbox interview, I came across this problem and really wanted to find the ideas behind the follow up questions (as these were the questions that the interviewer was most interested in, not the code itself). Since this is the only post with the follow up discussion, i’ll comment here! @yujun gave a great solution above and I just wanted to add a bit more to help future interviewees.

To find duplicate files, given input of String array is quite easy. Loop through each String and keep a HashMap of Strings to Set/Collection of Strings: mapping the contents of each file to a set of paths with filename concatenated.

For me, instead of given a list of paths, I was given a Directory and asked to return List of List of duplicate files for all under it. I chose to represent a Directory like:

```
class Directory{
List<Directory> subDirectories;
List<File> files;
}
```

Given a directory, you are asked how you can find duplicate files given very large files. The idea here is that you cannot store contents in memory, so you need to store the file contents in disk. So you can hash each file content and store the hash as a metadata field for each file. Then as you perform your search, store the hash instead the file’s contents in memory. So the idea is you can do a DFS through the root directory and create a HashMap<String, Set

(Note: You can choose BFS / DFS to traverse the Path. I chose DFS as it is more memory efficient and quicker to code up.)

Follow Up: This is great, but it requires you to compute the hash for every single file once, which can be expensive for large files. Is there anyway you can avoid computing the hash for a file?

One approach is to also **maintain a metadata field for each file’s size on disk**. Then you can take a 2 pass approach:

**DFS to map each size to a set of paths that have that size**
For each size, if there are more than 2 files there, compute hash of every file, if any files with the same size have the same hash, then they are identical files.
This way, you only compute hashes if you have multiple files with the same size. So when you do a DFS, you can create a HashMap<Integer, Set

## 419. Battleships in a Board

### Description

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.
```

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

### Solution

```
/*
There are three rules to tell if a cell is a 'head':
The cell is a 'X' (board[i][j] == 'X')
No left side neighbor, or the left neighbor is a '.' (i == 0 || board[i - 1][j] == '.')
No right side neighbor, or the right neighbor is a '.' (j == 0 || board[i][j - 1] == '.')
*/
class Solution {
public int countBattleships(char[][] board) {
int count = 0;
if(board==null || board.length==0 || board[0].length==0){
return count;
}
for(int i = 0;i<board.length;i++){
for(int j = 0;j<board[0].length;j++){
if(board[i][j]=='X' && (i==0 || board[i-1][j]=='.') && (j==0 || board[i][j-1]=='.')){
count++;
}
}
}
return count;
}
}
```

## 280. Wiggle Sort

### Description

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….

Example:

```
Input: nums = [3,5,2,1,6,4]
Output: One possible answer is [3,5,1,6,2,4]
```

### Solution

```
class Solution {
//greedy.
//if odd, should have
//i-1 <= i
//if even, should have
//i-1 >= i
//for example, for i is odd:
//if i-1 <= i, then no need to swap.
//if i-1 > i:
//already known i-2 >= i-1 > i
//swap, then i-2 > i, i< i-1, wiggled.
public void wiggleSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {\
if (i % 2 == 0) {
if (nums[i - 1] < nums[i]) {
swap(i - 1, i, nums);
}
}else if(nums[i-1]>nums[i]){
swap(i-1,i,nums);
}
}
}
private void swap(int i, int j, int[] nums) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```

# 2019-11-17

## 416. Partition Equal Subset Sum

### Description

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.
```

### Solution

```
/*
This problem is essentially let us to find whether there are several numbers in a set which are able to sum to a specific value (in this problem, the value is sum/2).
Actually, this is a 0/1 knapsack problem, for each number, we can pick it or not. Let us assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers. If we can pick such a series of numbers from 0-i whose sum is j, dp[i][j] is true, otherwise it is false.
Base case: dp[0][0] is true; (zero number consists of sum 0 is true)
Transition function: For each number, if we don't pick it, dp[i][j] = dp[i-1][j], which means if the first i-1 elements has made it to j, dp[i][j] would also make it to j (we can just ignore nums[i]). If we pick nums[i]. dp[i][j] = dp[i-1][j-nums[i]], which represents that j is composed of the current value nums[i] and the remaining composed of other previous numbers. Thus, the transition function is dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
============solution2===============
dp[i] : if sum i can be reached.
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]] => dp[i] = dp[i] || dp[i-num]
*/
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int num:nums){
sum += num;
}
if(sum %2 != 0){
return false;
}
sum /= 2;
boolean[] dp = new boolean[sum +1];
for(int num: nums){
for(int i = sum;i>=num;i--){
dp[i] = dp[i] || dp[i-num];
}
}
return dp[sum];
}
}
```

## 130. Surrounded Regions

### Description

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

```
Example:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
```

### Solution

```
visit from board and turn all adjacenet cell to R, and remaining cell is X, turn R to O, that is all.
class Solution {
int[][] dirs = new int[][][[1, 0], [-1, 0], [0, 1], [0, -1]];
int X, Y;
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
X = board[0].length;
Y = board.length;
boolean[][] visited = new boolean[Y][X];
for (int i = 0; i < Y; i++) {
if (board[i][0] == 'O') {
helper(0, i, board, visited);
}
if (board[i][X - 1] == 'O') {
helper(X - 1, i, board, visited);
}
}
for (int i = 1; i < X - 1; i++) {
if (board[0][i] == 'O') {
helper(i, 0, board, visited);
}
if (board[Y - 1][i] == 'O') {
helper(i, Y - 1, board, visited);
}
}
for(int x = 0;x<X;x++){
for(int y = 0;y<Y;y++){
if(board[y][x]=='O'){
board[y][x]='X';
}
if(board[y][x]=='R'){
board[y][x]='O';
}
}
}
}
private void helper(int x, int y, char[][] board, boolean[][] visited) {
board[y][x] = 'R';
visited[y][x] = true;
for (int[] dir : dirs) {
int next_x = x + dir[0];
int next_y = y + dir[1];
if (next_x >= 0 && next_x < X && next_y >= 0 && next_y < Y && !visited[next_y][next_x] && board[next_y][next_x] == 'O') {
helper(next_x, next_y, board, visited);
}
}
}
}
```

## 523. Continuous Subarray Sum

### Description

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.

```
Example 1:
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Example 2:
Input: [23, 2, 6, 4, 7], k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
```

Note:

The length of the array won’t exceed 10,000. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

### Solution

```
/*
For e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42] and the remainders are [5,1,1,5,0]. We got remainder 5 at index 0 and at index 3. That means, in between these two indexes we must have added a number which is multiple of the k.
*/
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();;
//find a solution when met same %.
int runningSum = 0;
for (int i=0;i<nums.length;i++) {
runningSum += nums[i];
if (k != 0) runningSum %= k;
Integer prev = map.get(runningSum);
if (prev != null) {
if (i - prev > 1) return true;
}
else map.put(runningSum, i);
}
return false;
}
```

## 1055. Shortest Way to Form String

### Description

From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions).

Given two strings source and target, return the minimum number of subsequences of source such that their concatenation equals target. If the task is impossible, return -1.

```
Example 1:
Input: source = "abc", target = "abcbc"
Output: 2
Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".
Example 2:
Input: source = "abc", target = "acdbc"
Output: -1
Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target string.
Example 3:
Input: source = "xyz", target = "xzyxz"
Output: 3
Explanation: The target string can be constructed as follows "xz" + "y" + "xz".
```

Constraints:

Both the source and target strings consist of only lowercase English letters from “a”-“z”. The lengths of source and target string are between 1 and 1000.

### Solution

first opinion is that we can use two pointer , one iterate src, another iterate tar. for each tar char, we move j until src[j] == tar[i], if j == src.length, res++, j = 0; in this solution, we greedy match as many chars from src to tar as possible which can lead mininum use of src. and we can build a set to save all the char in src, if there exists a char from tar which not exists in set, return -1.

```
public int shortestWay(String source, String target) {
char[] cs = source.toCharArray(), ts = target.toCharArray();
boolean[] map = new boolean[26];
for (int i = 0; i < cs.length; i++)
map[cs[i] - 'a'] = true;
int j = 0, res = 1;
for (int i = 0; i < ts.length; i++,j++) {
if (!map[ts[i] - 'a']) return -1;
while (j < cs.length && cs[j] != ts[i]) {
j++;
}
if (j == cs.length) {
j = -1;
res++;
i--;
}
}
return res;
}
```

follow up 1: yes, correct. could u implement it with O 1 space, which mean without set. okay. without set, we need a way to make sure there is a char which not in src. we can iterate src completely. if the j not move, then we can return -1.

```
public int shortestWay(String source, String target) {
char[] cs = source.toCharArray(), ts = target.toCharArray();
int res = 0;
for (int i = 0; i < ts.length; ) {
int oriI = i;
for (int j = 0; j < cs.length; j++) {
if (i < ts.length && cs[j] == ts[i])
i++;
}
if (i == oriI) return -1;
res++;
}
return res;
}
```

follow up 2: fine. what’s the time complexity for above solutions. O(MN). could u make it better? the time complexity is better than O (MN), should be O(logM * N) or O (N) to find a logM way, it is easy to think of binary search. for each char in tar, we need loop from j to end, to find a char same as tar[i]. we can build a map which key is from ‘a’ -> ‘z’, the value is idx for this char in src. because idx is add from small to big. when we iterate tar[i], we can easily to find the tar[i]’s idx list. to search is there a idx is larger or equal than j+1. it is logM. and we have N char in tar, so the time complexity is N * logM the time is to build the map is O(M);

```
public int shortestWay(String source, String target) {
char[] cs = source.toCharArray(), ts = target.toCharArray();
int res = 1;
List<Integer>[] idx = new List[26];
for (int i = 0; i < 26; i++) idx[i] = new ArrayList<>();
for (int i = 0; i < cs.length; i++) idx[cs[i] - 'a'].add(i);
int j = 0;
for (int i = 0; i < ts.length; ) {
List<Integer> tar = idx[ts[i] - 'a'];
if (tar.isEmpty()) return -1;
int k = Collections.binarySearch(tar,j);
if (k < 0) k = -k - 1;
if (k == tar.size()) {
res++;
j = 0;
} else {
j = tar.get(k) + 1;
i++;
}
}
return res;
}
```

follow up 3: great. could u improve it more? so we have to think a solution which is O(N), how should we use O(1) to know the next J pos? maybe we can use more to save time. in binary search solution we will have a map like a ->{1,3,7,16} (total src length is 20), so we need binary search. if we can flatten them, i mean for each pos in 20 length, we just save the next idx, we can use O 1 to find the next J. a -> {1,1,3,3,7,7,7,7,16,16,16,16,16,16,16,16,16,0,0,0} for example if now j is 4, we can just check map[4] = 7; we know 7 pos have an ‘a’, so next j will be 7 + 1. if now j is 17, we get map[17] = 0, we know there is no more j after. so j = 0, res++; the time complexity is O (N) , and build the map cost 26 * M

```
public int shortestWay(String source, String target) {
char[] cs = source.toCharArray(), ts = target.toCharArray();
int[][] idx = new int[26][cs.length];
for (int i = 0; i < cs.length; i++) idx[cs[i] - 'a'][i] = i + 1;
for (int i = 0; i < 26; i++) {
for (int j = cs.length - 1, pre = 0; j >= 0; j--) {
if (idx[i][j] == 0) idx[i][j] = pre;
else pre = idx[i][j];
}
}
int res = 1, j = 0;
for (int i = 0; i < ts.length; i++) {
if (j == cs.length) {
j = 0;
res++;
}
if (idx[ts[i] - 'a'][0] == 0) return -1;
j = idx[ts[i] - 'a'][j];
if (j == 0 ) {
res++;
i--;
}
}
return res;
}
```

follow up 4: cool, if we assume which can copy a array to another array with 26 length in constant time. could u implement it with O(M + N) it sounds like we need switch the map from [26][src.length] to [src.length][26]. and we also need to use O 1 time to know what’s next j position. now we are in the 2rd idx (j = 1), so tar[i] = ‘a’ we should save the map[1][‘a’] the next position of j. if we are in the last idx, i think the map should be all 0, except the last tar char. for example the char is ‘a’ so the map for it is [last+1,0,0,…,0] how about last -1 idx, if the tar[last - 1] is same as tar[last], we just update it , [last - 1 + 1, 0….0] if is not same. we can update a 0 with last - 1 + 1

```
public int shortestWay(String source, String target) {
char[] cs = source.toCharArray(), ts = target.toCharArray();
int[][] idx = new int[cs.length][26];
idx[cs.length - 1][cs[cs.length - 1] - 'a'] = cs.length;
for (int i = cs.length - 2; i >= 0; i--) {
idx[i] = Arrays.copyOf(idx[i + 1],26);
idx[i][cs[i] - 'a'] = i + 1;
}
int j = 0, res = 1;
for (int i = 0; i < ts.length; i++) {
if (j == cs.length) {
j = 0;
res++;
}
j = idx[j][ts[i] - 'a'];
if (idx[0][ts[i] - 'a'] == 0) return -1;
if (j == 0) {
res++;
i--;
}
}
return res;
}
```

## 353. Design Snake Game

### Description

Design a Snake game that is played on a device with screen size = width x height. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0,0) with length = 1 unit.

You are given a list of food’s positions in row-column order. When a snake eats the food, its length and the game’s score both increase by 1.

Each food appears one by one on the screen. For example, the second food will not appear until the first food was eaten by the snake.

When a food does appear on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

```
Example:
Given width = 3, height = 2, and food = [[1,2],[0,1]].
Snake snake = new Snake(width, height, food);
Initially the snake appears at position (0,0) and the food at (1,2).
|S| | |
| | |F|
snake.move("R"); -> Returns 0
| |S| |
| | |F|
snake.move("D"); -> Returns 0
| | | |
| |S|F|
snake.move("R"); -> Returns 1 (Snake eats the first food and right after that, the second food appears at (0,1) )
| |F| |
| |S|S|
snake.move("U"); -> Returns 1
| |F|S|
| | |S|
snake.move("L"); -> Returns 2 (Snake eats the second food)
| |S|S|
| | |S|
snake.move("U"); -> Returns -1 (Game over because snake collides with border)
```

### Solution

```
//use Integer to store position info to avoid using board[][]
class SnakeGame {
/** Initialize your data structure here.
@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0].
**/
Set<Integer> set; // this copy is good for fast loop-up for eating body case
Deque<Integer> body; // this copy is good for updating tail
int score;
int[][] food;
int foodIndex;
int width;
int height;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
set = new HashSet<>();
set.add(0); //intially at [0][0]
body = new LinkedList<>();
body.offerLast(0);
}
/** Moves the snake.
@param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
@return The game's score after the move. Return -1 if game over.
Game over when snake crosses the screen boundary or bites its body. */
public int move(String direction) {
if (score == -1) {
return -1;
}
int rowHead = body.peekFirst() / width;
int colHead = body.peekFirst() % width;
switch (direction) {
case "U" : rowHead--;
break;
case "D" : rowHead++;
break;
case "L" : colHead--;
break;
default : colHead++;
}
int head = rowHead * width + colHead;
set.remove(body.peekLast()); // new head is legal to be in old tail's position, remove from set temporarily
if (rowHead < 0 || rowHead == height || colHead < 0 || colHead == width || set.contains(head)) {
return score = -1;
}
// add head for case2 and case3
set.add(head);
body.offerFirst(head);
//case2: eating food, keep tail, add head
if (foodIndex < food.length && rowHead == food[foodIndex][0] && colHead == food[foodIndex][1]) {
set.add(body.peekLast()); // old tail does not change, so add it back to set
foodIndex++;
return ++score;
}
//case3: normal move, remove tail, add head
body.pollLast();
return score;
}
}
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/
```

# 2019-11-18

## 945. Minimum Increment to Make Array Unique

### Description

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

```
Example 1:
Input: [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].
Example 2:
Input: [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.
```

Note: 0 <= A.length <= 40000 0 <= A[i] < 40000

### Solution

```
class Solution {
public int minIncrementForUnique(int[] A) {
int require = 0, incSum = 0;
Arrays.sort(A);
for(int num:A){
incSum += Math.max(require-num,0);
require = Math.max(require,num)+1;
}
return incSum;
}
}
```

## 390. Elimination Game

### Description

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input: n = 9, 1 2 3 4 5 6 7 8 9 2 4 6 8 2 6 6

Output: 6

### Solution

```
/*
from Left:
even: head + step;
odd: head + step;
from right:
even: head;
odd: head + step;
remaining /= 2, no matter even or odd.
when remaining is 1, head is the answer.
*/
class Solution {
public int lastRemaining(int n) {
int head = 1, step = 1, remaining = n;
boolean isLeft = true;
while (remaining != 1) {
if(isLeft || remaining%2 != 0){
head += step;
}
step *= 2;
remaining /= 2;
isLeft = !isLeft;
}
return head;
}
}
```

## 797. All Paths From Source to Target

### Description

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

```
Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0--->1
| |
v v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
```

Note:

The number of nodes in the graph will be in the range [2, 15]. You can print different paths in any order, but you should keep the order of nodes inside one path. Accepted

### Solution

```
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> tempPath = new ArrayList<>();
tempPath.add(0);
dfs(graph,0,tempPath,res);
return res;
}
public void dfs(int[][] graph, int node, List<Integer> tempPath, List<List<Integer>> res) {
if(node == graph.length-1){
res.add(new ArrayList<>(tempPath));
return;
}
for(int nextNode : graph[node]){
tempPath.add(nextNode);
dfs(graph,nextNode,tempPath,res);
tempPath.remove(tempPath.size()-1);
}
}
}
```

# 2019-11-20

## 953. Verifying an Alien Dictionary

### Description

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

```
Example 1:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
Example 2:
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.
Example 3:
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).
```

Constraints:

1 <= words.length <= 100 1 <= words[i].length <= 20 order.length == 26 All characters in words[i] and order are English lowercase letters.

### Solution

```
import java.util.HashMap;
import java.util.Map;
class Solution {
public boolean isAlienSorted(String[] words, String order) {
Map<Character,Integer> orderMap = new HashMap<>();
for(int i = 0;i<order.length();i++){
orderMap.put(order.charAt(i),i);
}
for(int i = 1;i<words.length;i++){
if(!bigger(words[i],words[i-1],orderMap)){
return false;
}
}
return true;
}
//compare two string, start from the first non-equal char to compare.
//if all prefix is same, then the longer one is bigger.
private boolean bigger(String word1, String word2, Map<Character,Integer> order){
int len1 = word1.length();
int len2 = word2.length();
for(int i=0;i<Math.min(len1,len2);i++){
if(word1.charAt(i)!=word2.charAt(i)){
return order.get(word1.charAt(i))>order.get(word2.charAt(i));
}
}
return len1 >len2;
}
}
```

# 2019-11-24

## 215. Kth Largest Element in an Array

### Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

```
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
```

Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.

### Solution

```
class Solution {
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int lo = 0;
int hi = nums.length-1;
while(lo<hi){
int j = partition(nums,lo,hi);
if(j<k){
lo = j+1;
}else if(j>k){
hi = j -1;
}else{
break;
}
}
return nums[k];
}
//most important part using exchange instead of using extra space.
private int partition(int[] nums, int lo, int hi) {
int i = lo;
int j = hi + 1;
while (true) {
//use lo as flag.
//find two element that at wrong position;
//i is larger than flag, j is smaller than flag.
//swap them.
while (i < hi && nums[++i] < nums[lo]);
while (j > lo && nums[--j] > nums[lo]);
if (i >= j) {
break;
}
exch(nums,i,j);
}
//now j is actually smaller than flag.
exch(nums,j,lo);
return j;
}
private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
```

# 2019-11-30

## 443. String Compression

### Description

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.

### Solution

```
class Solution {
public int compress(char[] chars) {
int len = chars.length;
int idx = 0, indexAns = 0;
while(idx < len){
char cur = chars[idx];
int count = 0;
//loop over to count.
while(idx < len && chars[idx]==cur){
idx++;
count++;
}
chars[indexAns++] = cur;
//if the count has two digit need to take care.
if(count != 1){
for(char c: String.valueOf(count).toCharArray()){
chars[indexAns++] = c;
}
}
}
return indexAns;
}
}
```

## 572. Subtree of Another Tree

### Description

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

```
Example 1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
```

### Solution

```
/**
* Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if(s == null) return false;
if (isSame(s, t)) {
return true;
}
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSame(TreeNode s, TreeNode t) {
//bottom condition.
if (s == null && t == null) {
return true;
}
//early stop.
if (s == null || t == null) {
return false;
}
if (s.val != t.val) {
return false;
}
return isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
```

## 680. Valid Palindrome II

### Description

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

```
Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
```

Note: The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

### Solution

```
class Solution {
public boolean validPalindrome(String s) {
int l = -1;int r = s.length();
while(++l < --r){
if(s.charAt(l) != s.charAt(r)){
//char at l and r are different
//if met a pair that does not match, there are two situation:
//1. skip l and try the rest.so it will rethink r so l->r+1
//2. skip r and try the rest.so it will rethink l so l-1->r
return isPalindrome(s,l,r+1) || isPalindrome(s,l-1,r);
}
}
return true;
}
private boolean isPalindrome(String s, int l, int r) {
while (++l < --r) {
if (s.charAt(l) != s.charAt(r)) {
return false;
}
}
return true;
}
}
```