# 2020-07-01

## 311. Sparse Matrix Multiplication

### Description

Given two sparse matrices A and B, return the result of AB.

You may assume that A’s column number is equal to B’s row number.

``````Example:

Input:

A = [
[ 1, 0, 0],
[-1, 0, 3]
]

B = [
[ 7, 0, 0 ],
[ 0, 0, 0 ],
[ 0, 0, 1 ]
]

Output:

|  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
| 0 0 1 |

Constraints:

1 <= A.length, B.length <= 100
1 <= A[i].length, B[i].length <= 100
-100 <= A[i][j], B[i][j] <= 100
``````

### Solution

``````public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int m = A.length, n = A[0].length, nB = B[0].length;
int[][] C = new int[m][nB];

for(int i = 0; i < m; i++) {
for(int k = 0; k < n; k++) {
if (A[i][k] != 0) {
for (int j = 0; j < nB; j++) {
if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
}
}
}
}
return C;
}
}
``````

## 1344. Angle Between Hands of a Clock

### Description

Given two numbers, hour and minutes. Return the smaller angle (in degrees) formed between the hour and the minute hand.

``````Example 1:

Input: hour = 12, minutes = 30
Output: 165

Example 2:

Input: hour = 3, minutes = 30
Output: 75
Example 3:

Input: hour = 3, minutes = 15
Output: 7.5
Example 4:

Input: hour = 4, minutes = 50
Output: 155
Example 5:

Input: hour = 12, minutes = 0
Output: 0

Constraints:

1 <= hour <= 12
0 <= minutes <= 59
Answers within 10^-5 of the actual value will be accepted as correct.
``````

### Solution

``````public double angleClock(int hour, int minutes) {
//in case hour is 12, down to actually 0
hour%=12;
//distance from 0 to hour clock / total distance for the whole circle.
double hourPercentage = (hour + minutes/60.0D)/12.0D;
double minutePercentage = minutes/60.0D;
double diff = Math.abs(hourPercentage-minutePercentage);
//min is to find the smaller angle -> 270 will down to 90.
return 360 * Math.min(diff,1-diff);
}
``````

### Description

Given a url startUrl and an interface HtmlParser, implement a Multi-threaded web crawler to crawl all links that are under the same hostname as startUrl.

Return all urls obtained by your web crawler in any order.

Start from the page: startUrl Call HtmlParser.getUrls(url) to get all urls from a webpage of given url. Do not crawl the same link twice. Explore only the links that are under the same hostname as startUrl.

As shown in the example url above, the hostname is example.org. For simplicity sake, you may assume all urls use http protocol without any port specified. For example, the urls http://leetcode.com/problems and http://leetcode.com/contest are under the same hostname, while urls http://example.org/test and http://example.com/abc are not under the same hostname.

The HtmlParser interface is defined as such:

``````interface HtmlParser {
// Return a list of all urls from a webpage of given url.
// This is a blocking call, that means it will do HTTP request and return when this request is finished.
public List<String> getUrls(String url);
}
``````

Note that getUrls(String url) simulates performing a HTTP request. You can treat it as a blocking function call which waits for a HTTP request to finish. It is guaranteed that getUrls(String url) will return the urls within 15ms. Single-threaded solutions will exceed the time limit so, can your multi-threaded web crawler do better?

Below are two examples explaining the functionality of the problem, for custom testing purposes you’ll have three variables urls, edges and startUrl. Notice that you will only have access to startUrl in your code, while urls and edges are not directly accessible to you in code.

Assume we have 10,000 nodes and 1 billion URLs to crawl. We will deploy the same software onto each node. The software can know about all the nodes. We have to minimize communication between machines and make sure each node does equal amount of work. How would your web crawler design change? What if one node fails or does not work? How do you know when the crawler is done?

``````Example 1:

Input:
urls = [
"http://news.yahoo.com",
"http://news.yahoo.com/news",
"http://news.yahoo.com/news/topics/",
"http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
"http://news.yahoo.com",
"http://news.yahoo.com/news",
"http://news.yahoo.com/news/topics/",
"http://news.yahoo.com/us"
]
Example 2:

Input:
urls = [
"http://news.yahoo.com",
"http://news.yahoo.com/news",
"http://news.yahoo.com/news/topics/",
]
edges = [[0,2],[2,1],[3,2],[3,1],[3,0]]
Explanation: The startUrl links to all other pages that do not share the same hostname.

Constraints:

1 <= urls.length <= 1000
1 <= urls[i].length <= 300
startUrl is one of the urls.
Hostname label must be from 1 to 63 characters long, including the dots, may contain only the ASCII letters from 'a' to 'z', digits from '0' to '9' and the hyphen-minus character ('-').
The hostname may not start or end with the hyphen-minus character ('-').
See:  https://en.wikipedia.org/wiki/Hostname#Restrictions_on_valid_hostnames
You may assume there're no duplicates in url library.
``````

### Solution

``````class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {

// find hostname
int index = startUrl.indexOf('/', 7);
String hostname = (index != -1) ? startUrl.substring(0, index) : startUrl;

Crawler crawler = new Crawler(startUrl, hostname, htmlParser);
crawler.map = new ConcurrentHashMap<>(); // reset result as static property belongs to class, it will go through all of the test cases
crawler.result = crawler.map.newKeySet();

return new ArrayList<>(crawler.result);
}
}

class Crawler implements Runnable {
String startUrl;
String hostname;
HtmlParser htmlParser;
public static ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
public static Set<String> result = map.newKeySet();

public Crawler(String startUrl, String hostname, HtmlParser htmlParser) {
this.startUrl = startUrl;
this.hostname = hostname;
this.htmlParser = htmlParser;
}

@Override
public void run() {
if (this.startUrl.startsWith(hostname) && !this.result.contains(this.startUrl)) {
for (String s : htmlParser.getUrls(startUrl)) {
if(result.contains(s)) continue;
Crawler crawler = new Crawler(s, hostname, htmlParser);
}
}
}
}

try {
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}

``````

Stream Method

``````class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String hostname = getHostname(startUrl);

Set<String> visited = ConcurrentHashMap.newKeySet();

return crawl(startUrl, htmlParser, hostname, visited)
.collect(Collectors.toList());
}

private Stream<String> crawl(String startUrl, HtmlParser htmlParser, String hostname, Set<String> visited) {
Stream<String> stream = htmlParser.getUrls(startUrl)
.parallelStream()
.filter(url -> isSameHostname(url, hostname))
.flatMap(url -> crawl(url, htmlParser, hostname, visited));

return Stream.concat(Stream.of(startUrl), stream);
}

private String getHostname(String url) {
int idx = url.indexOf('/', 7);
return (idx != -1) ? url.substring(0, idx) : url;
}

private boolean isSameHostname(String url, String hostname) {
if (!url.startsWith(hostname)) {
return false;
}
return url.length() == hostname.length() || url.charAt(hostname.length()) == '/';
}
}
``````

## 284. Peeking Iterator

### Description

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation – it essentially peek() at the element that will be returned by the next call to next().

``````Example:

Assume that the iterator is initialized to the beginning of the list: [1,2,3].

Call next() gets you 1, the first element in the list.
Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.
You call next() the final time and it returns 3, the last element.
Calling hasNext() after that should return false.

Follow up: How would you extend your design to be generic and work with all types, not just integer?
``````

### Solution

``````class PeekingIterator implements Iterator<Integer> {

Integer next;
Iterator<Integer> iterator;

public PeekingIterator(Iterator<Integer> iterator) {
// initialize any member here.
this.iterator = iterator;
if (this.iterator.hasNext()) {
this.next = this.iterator.next();
} else {
this.next = null;
}
}

// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
return next;
}

// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
Integer temp = next;
if (iterator.hasNext()) {
this.next = iterator.next();
} else {
this.next = null;
}
return temp;
}

@Override
public boolean hasNext() {
return next != null;
}
}
``````

## 532. K-diff Pairs in an Array

### Description

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

``````Example 1:
Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).
Note:
The pairs (i, j) and (j, i) count as the same pair.
The length of the array won't exceed 10,000.
All the integers in the given input belong to the range: [-1e7, 1e7].
``````

### Solution

``````class Solution {

public int findPairs(int[] nums, int k) {
if(k<0)return 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0)+1);
}
int count = 0;
if (k == 0) {
for (int num : map.keySet()) {
if (map.get(num) != 1) {
count++;
}
}
return count;
}
for (int num : map.keySet()) {
if (map.containsKey(num + k)) {
count++;
}
}
return count;
}
}
``````

# 2020-07-02

## 460. LFU Cache

### Description

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.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

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(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(3);       // returns 3
cache.get(4);       // returns 4
``````

### Solution

``````public class LFUCache {

private int min;

private final int capacity;
private final HashMap<Integer, Integer> keyToVal;
private final HashMap<Integer, Integer> keyToCount;

public LFUCache(int capacity) {
this.min = -1;
this.capacity = capacity;
this.keyToVal = new HashMap<>();
this.keyToCount = new HashMap<>();
this.countToLRUKeys = new HashMap<>();
}

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

int count = keyToCount.get(key);
countToLRUKeys.get(count).remove(key); // remove key from current count (since we will inc count)
if (count == min && countToLRUKeys.get(count).size() == 0) min++; // nothing in the current min bucket

putCount(key, count + 1);
return keyToVal.get(key);
}

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

if (keyToVal.containsKey(key)) {
keyToVal.put(key, value); // update key's value
get(key); // update key's count
return;
}

if (keyToVal.size() >= capacity)
evict(countToLRUKeys.get(min).iterator().next()); // evict LRU from this min count bucket

min = 1;
putCount(key, min); // adding new key and count
keyToVal.put(key, value); // adding new key and value
}

private void evict(int key) {
countToLRUKeys.get(min).remove(key);
keyToVal.remove(key);
}

private void putCount(int key, int count) {
keyToCount.put(key, count);
}
}
``````

## 395. Longest Substring with At Least K Repeating Characters

### Description

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

``````Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
``````

### Solution

``````/**
loop over 1->26 so find the max length with:
h:[1,26] and k so that
the length has h unique char and all char repeat at least k times.
*/
class Solution {
public int longestSubstring(String s, int k) {
char[] str = s.toCharArray();
int[] count = new int[26];
int maxLen = 0;
int strLen = str.length;
//count the number of unique character
int charCount=0;
for(char c:str){
if(count[c-'a']++==0){
charCount++;
}
}
//only need to loop from 1 to charCount since it's the max unique char can reach.
for (int h = 1; h <= charCount; h++) {
count = new int[26];
int i = 0, j = 0, unique = 0, noLessThanK = 0;
while (j < strLen) {
if (unique <= h) {
int idx = str[j] - 'a';
if (count[idx] == 0) {
unique++;
}
count[idx]++;
if (count[idx] == k) {
noLessThanK++;
}
j++;
} else {
int idx = str[i] - 'a';
if (count[idx] == k) {
noLessThanK--;
}
count[idx]--;
if (count[idx] == 0) {
unique--;
}
i++;
}
//because after update and make it valid, i or j will +1.
//so the actual lenth for valid str is j-i.
if (h == unique && h == noLessThanK) {
maxLen = Math.max(maxLen, j - i);
}
}
}

return maxLen;
}
}

``````

### Description

Write a program that outputs the string representation of numbers from 1 to n, however:

If the number is divisible by 3, output “fizz”. If the number is divisible by 5, output “buzz”. If the number is divisible by both 3 and 5, output “fizzbuzz”. For example, for n = 15, we output: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz.

``````Suppose you are given the following code:

class FizzBuzz {
public FizzBuzz(int n) { ... }               // constructor
public void fizz(printFizz) { ... }          // only output "fizz"
public void buzz(printBuzz) { ... }          // only output "buzz"
public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
public void number(printNumber) { ... }      // only output the numbers
}
Implement a multithreaded version of FizzBuzz with four threads. The same instance of FizzBuzz will be passed to four different threads:

Thread A will call fizz() to check for divisibility of 3 and outputs fizz.
Thread B will call buzz() to check for divisibility of 5 and outputs buzz.
Thread C will call fizzbuzz() to check for divisibility of 3 and 5 and outputs fizzbuzz.
Thread D will call number() which should only output the numbers.
``````

### Solution

``````class FizzBuzz {
private int n;
private int num = 1;

public FizzBuzz(int n) {
this.n = n;
}

public synchronized void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while (num <= n) {
if (num % 15 == 0) {
printFizzBuzz.run();
num++;
//notifyAll will let the other thread to stop wait and continue;
notifyAll();
} else {
wait();
}
}
}

public synchronized void fizz(Runnable printFizz) throws InterruptedException {
while (num <= n) {
if (num % 3 == 0 && num % 5 != 0) {
printFizz.run();
num++;
notifyAll();
} else {
wait();
}
}
}

public synchronized void buzz(Runnable printBuzz) throws InterruptedException {
while (num <= n) {
if (num % 3 != 0 && num % 5 == 0) {
printBuzz.run();
num++;
notifyAll();
} else {
wait();
}
}
}

public synchronized void number(IntConsumer printNumber) throws InterruptedException {
while (num <= n) {
if (num % 3 != 0 && num % 5 != 0) {
printNumber.accept(num);
num++;
notifyAll();
} else {
wait();
}
}
}
}

``````

CycleBarrier

``````import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.function.IntConsumer;

class FizzBuzz {

private int n;

CyclicBarrier cyclicBarrier;

public FizzBuzz(int n) {
this.n = n;
cyclicBarrier = new CyclicBarrier(4);
}

public  void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
try {
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) {
printFizzBuzz.run();
}
cyclicBarrier.await();
}
} catch (
BrokenBarrierException e) {
}
}

public  void fizz(Runnable printFizz) throws InterruptedException {
try {
for (int i = 1; i <= n; i++) {
if (i % 3 == 0 && i % 5 != 0) {
printFizz.run();
}
cyclicBarrier.await();
}
} catch (BrokenBarrierException e) {
}
}

public  void buzz(Runnable printBuzz) throws InterruptedException {
try {
for (int i = 1; i <= n; i++) {
if (i % 3 != 0 && i % 5 == 0) {
printBuzz.run();
}
cyclicBarrier.await();
}
} catch (BrokenBarrierException e) {
}
}

public  void number(IntConsumer printNumber) throws InterruptedException {
try {
for (int i = 1; i <= n; i++) {
if (i % 3 != 0 && i % 5 != 0) {
printNumber.accept(i);
}
cyclicBarrier.await();
}
} catch (
BrokenBarrierException e) {
}

}
}

``````

## 1326. Minimum Number of Taps to Open to Water a Garden

### Description

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, …, n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

``````
Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]
Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.
Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3
Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2
Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100
``````

### Solution

``````/**
dp[i] is the min taps needed to water first i gardens

*/
class Solution {
public int minTaps(int n, int[] ranges) {
int[] dp = new int[n+1];
Arrays.fill(dp,n+3);
//dp[0] = [0] as we need no tap to water nothing.
dp[0]= 0 ;
for(int i = 0;i<=n;i++){
int k = ranges[i];
int start = Math.max(0,i-k+1);
int end = Math.min(i+k,n);
int pre = dp[Math.max(0,i-k)] + 1;
for(int j = start;j<=end;j++){
//if we put a tap at i, then j is watered
//so to water j, either dp[j] which it's alreadyed watered by previous tap
//or watered by i so the total number is dp[i-k] + 1.
dp[j] = Math.min(dp[j],pre);
}
}

//if dp[n] is larger than n+3, means at least one garden does not get watered.
return dp[n]<n+3?dp[n]:-1;
}
}
``````

## 935. Knight Dialer

### Description

A chess knight can move as indicated in the chess diagram below:

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops. Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

``````Example 1:

Input: 1
Output: 10
Example 2:

Input: 2
Output: 20
Example 3:

Input: 3
Output: 46

Note:

1 <= N <= 5000
``````

### Solution

``````
class Solution {

int[][] memo;
int[][] jump;
final static int MOD = 1000000007;

public int knightDialer(int N) {
memo = new int[10][N + 1];
jump = new int[][][[4, 6], [6, 8], [7, 9], [4, 8], [3, 9, 0], [], [1, 7, 0], [2, 6], [1, 3], [2, 4}};
for (int i = 0; i < 10; i++) {
memo[i][1] = 1;
}
int sum = 0;
for (int i = 0; i < 10; i++) {
sum = (sum + getNumber(i, N)) % MOD;
}
return sum;
}

private int getNumber(int start, int N) {
if (memo[start][N] != 0) {
return memo[start][N];
}
int sum = 0;
for (int next : jump[start]) {
sum = (sum + getNumber(next, N - 1)) % MOD;
}
memo[start][N] = sum;
return sum;
}
}
``````

# 2020-07-06

## 428. Serialize and Deserialize N-ary Tree

### Description

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 an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure.

``````For example, you may serialize the following 3-ary tree

as [1 [3[5 6] 2 4]]. Note that this is just an example, you do not necessarily need to follow this format.

Or you can follow LeetCode's level order traversal serialization format, where each group of children is separated by the null value.

For example, the above tree may be serialized as [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14].

You do not necessarily need to follow the above suggested formats, there are many more different formats that work so please be creative and come up with different approaches yourself.

Constraints:

The height of the n-ary tree is less than or equal to 1000
The total number of nodes is between [0, 10^4]
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
``````

### Solution

``````class Codec {

// Encodes a tree to a single string.
public String serialize(Node root) {
if (root == null) {
return "";
}
buildString(root, list);
return String.join(",", list);
}

public void buildString(Node root, List<String> list) {
if (root.children == null) {
return;
}
for (Node child : root.children) {
buildString(child, list);
}
}

// Decodes your encoded data to tree.
public Node deserialize(String data) {
if (data.isEmpty()) {
return null;
}
Queue<String> queue = new ArrayDeque<String>(Arrays.asList(data.split(",")));
return deserializeHelper(queue);
}

public Node deserializeHelper(Queue<String> queue) {
Node root = new Node();
root.val = Integer.parseInt(queue.poll());
int size = Integer.parseInt(queue.poll());
root.children = new ArrayList<Node>(size);
for (int i = 0; i < size; i++) {
}

return root;
}
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

``````

## 437. Path Sum III

### Description

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

### Solution

``````//same idea as find sum array. using pre sum.
class Solution {

public int pathSum(TreeNode root, int sum) {
if(root==null){
return 0;
}
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
return helper(root, map, 0, sum);
}

public int helper(TreeNode root, HashMap<Integer, Integer> map, int curSum, int sum) {
//current sum from root to this node.
curSum += root.val;
//find count of array sum to sum.
// cur-sum + sum  = cur
int res = map.getOrDefault(curSum - sum,0);
//put current sum into array.
map.put(curSum,map.getOrDefault(curSum,0)+1);
if(root.left!=null){
res += helper(root.left,map,curSum,sum);
}
if(root.right!=null){
res += helper(root.right,map,curSum,sum);
}
//need to remove because will go for different node.
map.put(curSum,map.get(curSum)-1);
return res;
}
}
``````

## 1396. Design Underground System

### Description

Implement the class UndergroundSystem that supports three methods:

``````1. checkIn(int id, string stationName, int t)

A customer with id card equal to id, gets in the station stationName at time t.
A customer can only be checked into one place at a time.
2. checkOut(int id, string stationName, int t)

A customer with id card equal to id, gets out from the station stationName at time t.
3. getAverageTime(string startStation, string endStation)

Returns the average time to travel between the startStation and the endStation.
The average time is computed from all the previous traveling from startStation to endStation that happened directly.
Call to getAverageTime is always valid.
You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.00000. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.00000. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.00000
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.00000
Example 2:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkIn(2, "Leyton", 21);

Constraints:

There will be at most 20000 operations.
1 <= id, t <= 10^6
All strings consist of uppercase, lowercase English letters and digits.
1 <= stationName.length <= 10
Answers within 10^-5 of the actual value will be accepted as correct.
``````

### Solution

``````//straightforward storing all information using hashmaps.
class UndergroundSystem {

HashMap<Integer,String> traveling;
HashMap<Integer,Integer> checkinTime;
HashMap<String,Double> time;
HashMap<String,Integer> timeCount;

public UndergroundSystem() {
traveling = new HashMap<>();
checkinTime = new HashMap<>();
timeCount = new HashMap<>();
time = new HashMap<>();
}

public void checkIn(int id, String stationName, int t) {
traveling.put(id,stationName);
checkinTime.put(id,t);
}

public void checkOut(int id, String stationName, int t) {
String start = traveling.get(id);
int startTime = checkinTime.get(id);
String interval = start+" "+stationName;
int timeInterval = t-startTime;
int count = timeCount.getOrDefault(interval,0);
Double average = (time.getOrDefault(interval,0.0D)*count+timeInterval) / (count+1);
timeCount.put(interval,count+1);
time.put(interval,average);
}

public double getAverageTime(String startStation, String endStation) {
String interval = startStation+" "+endStation;
return time.get(interval);
}
}
``````

## 286. Walls and Gates

### Description

You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle. 0 - A gate. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

``````Example:

Given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
0  -1 INF INF
After running your function, the 2D grid should be:

3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4
``````

### Solution

``````class Solution {

int[][] dirs = new int[][][[0, 1], [0, -1], [-1, 0], [1, 0]];

public void wallsAndGates(int[][] rooms) {
if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
return;
}
int rowLen = rooms.length;
int colLen = rooms[0].length;
//start from any gates to find min distance.
for (int row = 0; row < rowLen; row++) {
for (int col = 0; col < colLen; col++) {
if (rooms[row][col] == 0) {
helper(rooms, 0, row, col);
}
}
}
}

public void helper(int[][] rooms, int distance, int row, int col) {
rooms[row][col] = distance;
for (int[] dir : dirs) {
int new_row = row + dir[0];
int new_col = col + dir[1];
//no need to check visited cause have condition rooms[new_row][new_col] > rooms[row][col]
//if visited, then this condition will never meet.
if (new_row >= 0 && new_row < rooms.length && new_col >= 0 && new_col < rooms[new_row].length
&& rooms[new_row][new_col] != -1 && rooms[new_row][new_col] > rooms[row][col]) {
helper(rooms, distance + 1, new_row, new_col);
}
}
}
}

``````

## 540. Single Element in a Sorted Array

### Description

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

``````
Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5

``````

### Solution

``````/**
1,1,2,3,3,4,4,8,8
0,1,2,3,4,5,6,7,8
E,O,N,O,E,O,E,O,E
pair will transfer from Even,Odd to Odd,Even after the single number.
Use Binary search to find.
*/
class Solution {
public int singleNonDuplicate(int[] nums) {
int len = nums.length;
int start = 0, end = nums.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
//if mid is valid
if (mid - 1 >= 0 && mid + 1 < len && nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) {
return nums[mid];
} else if ((mid + 1 < len && nums[mid] == nums[mid + 1] && mid % 2 == 0) || (mid - 1 >= 0 && nums[mid] == nums[mid - 1] && mid % 2 != 0)) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return nums[start];
}
}

``````

# 2020-07-07

## 1293. Shortest Path in a Grid with Obstacles Elimination

### Description

Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

``````Example 1:

Input:
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

Example 2:

Input:
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 1
Output: -1
Explanation:
We need to eliminate at least two obstacles to find such a walk.

Constraints:

grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0
``````

### Solution

``````class Solution {
int[][] dirs = new int[][][[0, 1], [0, -1], [1, 0], [-1, 0]];

public int shortestPath(int[][] grid, int k) {
int n = grid.length;
int m = grid[0].length;
boolean[][][] visited = new boolean[n][m][k + 1];
visited[0][0][0] = true;
q.offer(new int[]{0, 0, k});
int res = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] info = q.poll();
int r = info[0], c = info[1], curK = info[2];
if (r == n - 1 && c == m - 1) {
return res;
}
for (int[] dir : dirs) {
int nextR = dir[0] + r;
int nextC = dir[1] + c;
int nextK = curK;
if (nextR >= 0 && nextR < n && nextC >= 0 && nextC < m) {
//use a elimination.
if (grid[nextR][nextC] == 1) {
nextK--;
}
//if only there remains elimination can go through next.
if (nextK >= 0 && !visited[nextR][nextC][nextK]) {
visited[nextR][nextC][nextK] = true;
q.offer(new int[]{nextR, nextC, nextK});
}
}
}
}
res++;
}
return -1;
}
}
``````

## 658. Find K Closest Elements

### Description

Given a sorted array arr, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

``````Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Constraints:

1 <= k <= arr.length
1 <= arr.length <= 10^4
Absolute value of elements in the array and x will not exceed 104
``````

### Solution

``````import java.util.*;

class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
//use deque so no need to sort again.
//find the position where
int idx = Arrays.binarySearch(arr, x);
int len = arr.length;
if (idx < 0) {
idx = -idx - 1;
}

int left = idx - 1;
int right = idx;
int size = 0;

while (left >= 0 && right < len && size < k) {
if (x - arr[left] <= arr[right] - x) {
} else if (x - arr[left] > arr[right] - x) {
}
size++;
}
while (left >= 0 && size < k) {
size++;
}

while (right < len && size < k) {
size++;
}

return (List)res;

}
}
``````

Another way using binary search

``````/**
Explanation
Assume we are taking A[i] ~ A[i + k -1].
We can binary research i
We compare the distance between x - A[mid] and A[mid + k] - x

@vincent_gui listed the following cases:
Assume A[mid] ~ A[mid + k] is sliding window

case 1: x - A[mid] < A[mid + k] - x, need to move window go left
-------x----A[mid]-----------------A[mid + k]----------

case 2: x - A[mid] < A[mid + k] - x, need to move window go left again
-------A[mid]----x-----------------A[mid + k]----------

case 3: x - A[mid] > A[mid + k] - x, need to move window go right
-------A[mid]------------------x---A[mid + k]----------

case 4: x - A[mid] > A[mid + k] - x, need to move window go right
-------A[mid]---------------------A[mid + k]----x------

If x - A[mid] > A[mid + k] - x,
it means A[mid + 1] ~ A[mid + k] is better than A[mid] ~ A[mid + k - 1],
and we have mid smaller than the right i.
So assign left = mid + 1.

Important
Note that, you SHOULD NOT compare the absolute value of abs(x - A[mid]) and abs(A[mid + k] - x).
It fails at cases like A = [1,1,2,2,2,2,2,3,3], x = 3, k = 3
*/
public List<Integer> findClosestElements(int[] A, int k, int x) {
int left = 0, right = A.length - k;
while (left < right) {
int mid = (left + right) / 2;
if (x - A[mid] > A[mid + k] - x)
left = mid + 1;
else
right = mid;
}

return Arrays.stream(A, left, left + k).boxed().collect(Collectors.toList());
}

``````

## 836. Rectangle Overlap

### Description

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two (axis-aligned) rectangles, return whether they overlap.

``````Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true
Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false
Notes:

Both rectangles rec1 and rec2 are lists of 4 integers.
All coordinates in rectangles will be between -10^9 and 10^9.
``````

### Solution

``````//consider the situation two are not overlaped:
//2 is on top of 1 -> rec2[1] >= rec1[3]
//2 is on bottom of 1 -> rec2[3] <= rec1[1]
//2 is on left of 1 -> rec2[2] <= rec1[0]
//2 is on right of 1 -> rec2[0] >= rec1[2]

//otherwise they are overlaped.
class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
if (rec2[1] >= rec1[3] || rec2[3] <= rec1[1] || rec2[2] <= rec1[0] || rec2[0] >= rec1[2]) {
return false;
}
return true;
}
}
``````

## 1239. Maximum Length of a Concatenated String with Unique Characters

### Description

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

``````Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.
Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".
Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Constraints:

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lower case English letters.
``````

### Solution

``````import java.util.*;

class Solution {
int result;

public int maxLength(List<String> arr) {
result = 0;
if (arr == null || arr.size() == 0) {
return 0;
}
dfs(arr, "", 0);
return result;
}

private void dfs(List<String> arr, String path, int idx) {
boolean isUnique = isUniqueChars(path);
if (isUnique) {
result = Math.max(path.length(), result);
}

if (idx == arr.size() || !isUnique) {
return;
}

for (int i = idx; i < arr.size(); i++) {
dfs(arr, path + arr.get(i), i + 1);
}

}

//Effeicient way to check if the string is unique.
private boolean isUniqueChars(String str) {

// An integer to store presence/absence
// of 26 characters using its 32 bits.
int checker = 0;

for (int i = 0; i < str.length(); ++i) {
int val = (str.charAt(i) - 'a');

// If bit corresponding to current
if ((checker & (1 << val)) > 0)
return false;

// set bit in checker
checker |= (1 << val);
}

return true;
}
}

``````

# 2020-07-08

## 57. Insert Interval

### Description

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

``````Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
``````

### Solution

``````/**
* Find the first overlapped interval, keep merging until all overlaped intervals are merged.
*/
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int i=0;
int len = intervals.length;
List<int[]> res = new ArrayList<>();
//skip all intervals that's not overlapped.
while(i<len && intervals[i][1] <newInterval[0]) {
}
//keep merging.
while(i<len && intervals[i][0]<=newInterval[1]){
newInterval = new int[]{Math.min(intervals[i][0], newInterval[0]), Math.max(intervals[i][1], newInterval[1])};
i++;
}
while(i<len){
}
return res.toArray(new int[res.size()][]);
}
}
``````

## 243. Shortest Word Distance

### Description

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

``````Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
``````

### Solution

``````class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
int p1 = -1, p2 = -1, minDist = Integer.MAX_VALUE;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
p1 = i;
if (p2 != -1) {
//no need to do comparision everytime
//only when
minDist = Math.min(minDist, Math.abs(p1 - p2));
}
}

if (words[i].equals(word2)) {
p2 = i;
if (p1 != -1) {
minDist = Math.min(minDist, Math.abs(p1 - p2));
}
}
}
return minDist;
}
}
``````

## 1328. Break a Palindrome

### Description

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome.

After doing so, return the final string. If there is no way to do so, return the empty string.

``````Example 1:

Input: palindrome = "abccba"
Output: "aaccba"
Example 2:

Input: palindrome = "a"
Output: ""

Constraints:

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.
``````

### Solution

``````/**
two situation:
1. all a -> if len == 1 then it's impossible, otherwise replace the last char with 'b'
2. not all a -> replace the first non a char with a and return.
*/
class Solution {
public String breakPalindrome(String palindrome) {
char[] charArr = palindrome.toCharArray();
int len = charArr.length;
for (int i = 0; i < len / 2; i++) {
if (charArr[i] != 'a') {
charArr[i] = 'a';
return String.valueOf(charArr);
}
}
if (len == 1) {
return "";
} else {
charArr[len - 1] = 'b';
return String.valueOf(charArr);
}
}
}

``````

## 490. The Maze

### Description

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball’s start position, the destination and the maze, determine whether the ball could stop at the destination.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

``````Example 1:

Input 1: a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)

Output: true

Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
``````

``````Example 2:

Input 1: a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (3, 2)

Output: false

Explanation: There is no way for the ball to stop at the destination.
``````

``````Note:

There is only one ball and one destination in the maze.
Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
``````

### Solution

``````/**
Main idea is the same BFS except
*/
class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
if (maze == null || maze.length == 0 || maze[0].length == 0) {
return false;
}
int rowLen = maze.length;
int colLen = maze[0].length;
int[][] dirs = new int[][[0, 1], [0, -1], [1, 0], [-1, 0]];
Queue<int[]> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[rowLen][colLen];
visited[start[0]][start[1]] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] dir : dirs) {
int next_row = cur[0];
int next_col = cur[1];
//the ball keeps rolling until hit a wall.
while (next_row >= 0 && next_row < rowLen && next_col >= 0 && next_col < colLen && maze[next_row][next_col] == 0) {
next_row += dir[0];
next_col += dir[1];
}
next_row -= dir[0];
next_col -= dir[1];
if (visited[next_row][next_col]) continue;
visited[next_row][next_col] = true;
if (next_row == destination[0] && next_col == destination[1]) {
return true;
}
}
}
return false;
}

}

``````

## 270. Closest Binary Search Tree Value

### Description

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

``````Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

4
/ \
2   5
/ \
1   3

Output: 4
``````

### Solution

``````class Solution {

public int closestValue(TreeNode root, double target) {
int res = root.val;
TreeNode cur = root;
while (cur != null) {
//must calc everytime or if use a double to store, will overflow.
if (Math.abs(target - cur.val) < Math.abs(target - res)) {
res = cur.val;
//early stop, if the diff is less than 0.5, no other interger can achieve less diff.
if(Math.abs(target - cur.val)<=0.5){
break;
}
}
if (target > cur.val) {
cur = cur.right;
} else {
cur = cur.left;
}
}

return res;
}
}

``````

## 1283. Find the Smallest Divisor Given a Threshold

### Description

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

``````Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
Example 2:

Input: nums = [2,3,5,7,11], threshold = 11
Output: 3
Example 3:

Input: nums = [19], threshold = 5
Output: 4

Constraints:

1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6
``````

### Solution

``````import java.util.Arrays;

class Solution {

public int smallestDivisor(int[] nums, int threshold) {
int max = 0;
for(int num:nums){
max  = Math.max(max,num);
}
int left = 1, right = max;
while(left<right){
int mid = left+(right-left)/2;
int sum = getSum(nums,mid);
if(sum > threshold){
left = mid+1;
}else{
right = mid;
}
}
return left;
}

public int getSum(int[] nums, int div) {
int sum = 0;
for (int num : nums) {
//Math.ceil() also works but way slower.
sum += (num+div-1)/div;
}
return sum;
}
}

``````

## 703. Kth Largest Element in a Stream

### Description

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

``````Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
Note:
You may assume that nums' length ≥ k-1 and k ≥ 1.
``````

### Solution

``````/**
No need to store all numbers, just the first k largest.

*/
class KthLargest {

PriorityQueue<Integer> pq;
int capacity;
public KthLargest(int k, int[] nums) {
this.capacity = k;
this.pq = new PriorityQueue<>(k);
for(int num:nums){
}
}

if(pq.size()<capacity){
pq.offer(val);
//if the current smallest one is larger than or equal to val, means no need to update
//cause the number will update order laster than K, k largest will not be updated
}else if(pq.peek() < val){
pq.poll();
pq.offer(val);
}

return pq.peek();
}
}

/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
*/

``````

## 168. Excel Sheet Column Title

### Description

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

``````For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
Example 1:

Input: 1
Output: "A"
Example 2:

Input: 28
Output: "AB"
Example 3:

Input: 701
Output: "ZY"
``````

### Solution

``````/**
Special case: BA->52, AB->28, AAA->703
*/
public class Solution {

public String convertToTitle(int n) {
StringBuilder result = new StringBuilder();

while(n>0){
//handle the situation where n == 26;
n--;
result.append( (char)('A' + n % 26));
n /= 26;
}

return result.reverse().toString();
}
}

``````

# 2020-07-09

## 815. Bus Routes

### Description

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

``````Example:
Input:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation:
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
``````

### Solution

``````/**
Store the information for a certain stop, which buses go through that stop.
then for a certain stop, we can take all possible buses
and go to all possible stops reachable by these buses.

*/
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
HashSet<Integer> visited = new HashSet<>();
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
int ret = 0;

if (S==T) return 0;

//Use map to store buses go through a stop.
for(int i = 0; i < routes.length; i++){
for(int j = 0; j < routes[i].length; j++){
ArrayList<Integer> buses = map.getOrDefault(routes[i][j], new ArrayList<>());
map.put(routes[i][j], buses);
}
}

q.offer(S);
//loop over level size.
while (!q.isEmpty()) {
int len = q.size();
ret++;
for (int i = 0; i < len; i++) {
int cur = q.poll();
//find all buses I can take from this stop.
ArrayList<Integer> buses = map.get(cur);
for (int bus: buses) {
if (visited.contains(bus)) continue;
//if I take this bus, push all stops I get reach.
for (int j = 0; j < routes[bus].length; j++) {
//skip the current one.
if(routes[bus][j]==cur)continue;
if (routes[bus][j] == T) return ret;
q.offer(routes[bus][j]);
}
}
}
}
return -1;
}
}
``````

## 205. Isomorphic Strings

### Description

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

``````Example 1:

Input: s = "egg", t = "add"
Output: true
Example 2:

Input: s = "foo", t = "bar"
Output: false
Example 3:

Input: s = "paper", t = "title"
Output: true
Note:
You may assume both s and t have the same length.
``````

### Solution

``````/**
No two characters may map to the same character but a character may map to itself.
So need to store whether the char has been mapped to.
*/
class Solution {
public boolean isIsomorphic(String s, String t) {
int[] map = new int[256];
int[] mapped =new int[256];
int len = s.length();
for (int i = 0; i < len; i++) {
if (map[s.charAt(i)]!=0) {
if (map[s.charAt(i)] != t.charAt(i)) {
return false;
}
} else if (mapped[t.charAt(i)]!=0) {
return false;
}else{
map[s.charAt(i)] = t.charAt(i);
mapped[t.charAt(i)] = 1;
}
}
return true;
}
}
``````

## 450. Delete Node in a BST

### Description

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

5
/ \
2   6
\   \
4   7
``````

### Solution

``````/**
Recursively find the node that has the same value as the key, while setting the left/right nodes equal to the returned subtree
Once the node is found, have to handle the below 4 cases
node doesn't have left or right - return null
node only has left subtree- return the left subtree
node only has right subtree- return the right subtree
node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null){
return null;
}
//key exist on left part, change root.left
if(root.val > key){
root.left = deleteNode(root.left,key);
}else if(root.val < key){
//else change root.right
root.right = deleteNode(root.right,key);
}else{
//if this is the one to be deleted
//no child, delete and return null.
if(root.left==null && root.right==null){
return null;
}
if(root.left==null){
return root.right;
}
if(root.right==null){
return root.left;
}

//find the min node on right tree.
TreeNode min = findMin(root.right);
//change the current one value woth min value.
root.val = min.val;
//recursivly delete min value on the right tree.
root.right = deleteNode(root.right,min.val);
}
return root;
}

private TreeNode findMin(TreeNode root){
while(root.left!=null){
root = root.left;
}
return root;
}
}

``````

# 2020-07-10

## 758. Bold Words in String

### Description

``````Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between <b> and </b> tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "a<b>abc</b>d". Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Constraints:

words has length in range [0, 50].
words[i] has length in range [1, 10].
S has length in range [0, 500].
All characters in words[i] and S are lowercase letters.
``````

### Solution

``````/**
Find intervals, merge it, than insert into StringBuilder

*/
class Solution {
public String boldWords(String[] words, String S) {

}

}

``````

Or Use a array to store if this char should be bolded

``````public String boldWords(String[] words, String S) {
boolean[] bold = new boolean[S.length() + 1];
for (String w : words) {
int start = S.indexOf(w, 0);
while (start != -1) {
Arrays.fill(bold, start, start + w.length(), true);
start = S.indexOf(w, start + 1);
}
}
StringBuilder r = new StringBuilder().append(bold[0] ? "<b>" : "");
for (int i = 0; i < bold.length - 1; i++) {
r.append(S.charAt(i));
if (!bold[i] && bold[i + 1]) r.append("<b>");
else if (bold[i] && !bold[i + 1]) r.append("</b>");
}
return r.toString();
}

``````

## 678. Valid Parenthesis String

### Description

``````Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
An empty string is also valid.
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
Note:
The string size will be in the range [1, 100].
``````

### Solution

``````/**
cmin, cmax is the number of opening we are waiting to close.
cmax assume all * as ( so it's max.
cmin assume all * as ) so it's min.
but cmin will always be larger or equal to 0 cause otherwise the current string is invalid.
so in order to make it valid, cmin = Math.max(cmin,0)

if while looping, cmax is smaller than 0, means there's no way the current string is valid.

at the end, we have to make sure no opening are waiting to be closed, that is cmin == 0.
*/
class Solution {
public boolean checkValidString(String s) {
int cmin = 0, cmax = 0;
for (int i = 0; i < s.length(); i++) {
char cur = s.charAt(i);
if (cur == '(') {
cmin++;
cmax++;
} else if (cur == ')') {
cmax--;
cmin = Math.max(--cmin, 0);
} else {
cmax++;
cmin = Math.max(--cmin, 0);
}
if (cmax < 0) {
return false;
}
}

return cmin == 0;
}
}
``````

# 2020-07-12

## 611. Valid Triangle Number

### Description

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

``````Example 1:
Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
Note:
The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].
``````

### Solution

``````import java.util.Arrays;

class Solution {
public int triangleNumber(int[] nums) {
//sort the nums first, so only need to check condition 1 + 2 < 3
Arrays.sort(nums);
int i = 0;
//skip 0 as it never make a valid triangle.
while (i < nums.length) {
if (nums[i] != 0) {
break;
}
i++;
}
int count = 0;
while (i <= nums.length - 3) {
//try every possible number after nums[i]
for (int j = i + 1; j <= nums.length - 2; j++) {
int key = nums[i] + nums[j] - 1;
//find the position of last valid third number.
int idx = Arrays.binarySearch(nums, j + 1, nums.length, key);
if (idx < 0) {
idx = -idx - 2;
}
//binary search does not guarantee it's the last one.
//need to move to last idx of valid number.
while (idx < nums.length && nums[i] + nums[j] > nums[idx]) {
idx++;
}
//all numbers from j to idx-1 is valid
count += idx - j - 1;
}
i++;
}
return count;
}
}
``````

## 83. Remove Duplicates from Sorted List

### Description

Given a sorted linked list, delete all duplicates such that each element appear only once.

``````Example 1:

Input: 1->1->2
Output: 1->2
Example 2:

Input: 1->1->2->3->3
Output: 1->2->3
``````

### Solution

``````/**
Keep search next node until next val.
*/
class Solution {

}
ListNode pre = null;
while(cur != null){
pre = cur;
while(cur!=null && cur.val==pre.val){
cur = cur.next;
}
pre.next = cur;
pre = pre.next;
}
}
}

``````

## 844. Backspace String Compare

### Description

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

``````Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".
Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
Note:

1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.
``````

### Solution

``````class Solution {
public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1;
int j = T.length() - 1;
int back = 0;
while (true) {
back = 0;
//find the first char that will exist in the result.
while (i >= 0 && (back > 0 || S.charAt(i) == '#')) {
back += S.charAt(i) == '#' ? 1 : -1;
i--;
}

back = 0;
//find the first char that will exist in the result.
while (j >= 0 && (back > 0 || T.charAt(j) == '#')) {
back += T.charAt(j) == '#' ? 1 : -1;
j--;
}

//compare them.
if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
i--;
j--;
} else {
break;
}
}
return i == -1 && j == -1;
}
}
``````

## 40. Combination Sum II

### Description

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

``````Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
``````

### Solution

``````class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//key point: sort first.
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
dfs(candidates,0,target,new ArrayList<>(),res);
return res;
}

private void dfs(int[] candidates, int idx, int runningSum, List<Integer> temp, List<List<Integer>> res){
if(runningSum<=0){
if(runningSum==0){
}
return;
}
for(int i = idx;i<candidates.length;i++){
//key point to prevent dup:
//for a certain number, it can only appear at position idx once.
//but if we put num at idx, we still have chance to put num at idx+1 by dfs(i+1)
if(i > idx && candidates[i-1]==candidates[i]){
continue;
}
dfs(candidates, i+1,runningSum-candidates[i],temp, res);
temp.remove(temp.size()-1);
}
}

public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.combinationSum2(new int[]{10,1,2,7,6,1,5},8));
}
}

``````

## 249. Group Shifted Strings

### Description

Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

``````"abc" -> "bcd" -> ... -> "xyz"
Given a list of non-empty strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

Example:

Input: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Output:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
``````

### Solution

``````/**
Left align to set first char as 'a'
so the string with the same pattern will align to the same string.
*/
class Solution {

public List<List<String>> groupStrings(String[] strings) {
HashMap<String, List<String>> map = new HashMap<>();
for (String str : strings) {
String temp = aligns(str);
map.putIfAbsent(temp, new ArrayList<>());
}
List<List<String>> res = new ArrayList<>();
for (String key : map.keySet()) {
}
return res;
}

private String aligns(String str) {
char[] strArr = str.toCharArray();
int shift = strArr[0] - 'a';
for (int i = 0; i < strArr.length; i++) {
//"ba" -> az"
//handle a - 1 = z circle.
int diff = (strArr[i] - 'a' - shift + 26) % 26;
strArr[i] = (char) (diff + 'a');
}
return String.valueOf(strArr);
}
}

``````

## 1032. Stream of Characters

### Description

Implement the StreamChecker class as follows:

StreamChecker(words): Constructor, init the data structure with the given words. query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

``````Example:

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
streamChecker.query('a');          // return false
streamChecker.query('b');          // return false
streamChecker.query('c');          // return false
streamChecker.query('d');          // return true, because 'cd' is in the wordlist
streamChecker.query('e');          // return false
streamChecker.query('f');          // return true, because 'f' is in the wordlist
streamChecker.query('g');          // return false
streamChecker.query('h');          // return false
streamChecker.query('i');          // return false
streamChecker.query('j');          // return false
streamChecker.query('k');          // return false
streamChecker.query('l');          // return true, because 'kl' is in the wordlist

Note:

1 <= words.length <= 2000
1 <= words[i].length <= 2000
Words will only consist of lowercase English letters.
Queries will only consist of lowercase English letters.
The number of queries is at most 40000.
``````

### Solution

``````/**
Store words reversly.
*/
class StreamChecker {

class TrieNode {
boolean isWord;
TrieNode[] next = new TrieNode[26];
}

TrieNode root = new TrieNode();
StringBuilder sb = new StringBuilder();

public StreamChecker(String[] words) {
createTrie(words);
}

public boolean query(char letter) {
sb.append(letter);
TrieNode node = root;
for (int i = sb.length() - 1; i >= 0 && node != null; i--) {
char c = sb.charAt(i);
node = node.next[c - 'a'];
if (node != null && node.isWord) {
return true;
}
}
return false;
}

private void createTrie(String[] words) {
for (String s : words) {
TrieNode node = root;
int len = s.length();
for (int i = len - 1; i >= 0; i--) {
char c = s.charAt(i);
if (node.next[c - 'a'] == null) {
node.next[c - 'a'] = new TrieNode();
}
node = node.next[c - 'a'];
}
node.isWord = true;
}
}
}
``````

## 117. Populating Next Right Pointers in Each Node II

### Description

Given a binary tree

``````struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

You may only use constant extra space.
Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

The number of nodes in the given tree is less than 6000.
-100 <= node.val <= 100
``````

### Solution

1. Level traversal using Queue

2. Use pre to store information

``````class Solution {
public Node connect(Node root) {
Node nextLeft = root;
while (nextLeft != null) {
Node cur = nextLeft;
Node pre = null;
nextLeft = null;
while (cur != null) {
if (cur.left != null) {
if (nextLeft == null) {
nextLeft = cur.left;
}
if (pre != null) {
pre.next = cur.left;
pre = pre.next;
} else {
pre = cur.left;
}
}

if (cur.right != null) {
if (nextLeft == null) {
nextLeft = cur.right;
}
if (pre != null) {
pre.next = cur.right;
pre = pre.next;
} else {
pre = cur.right;
}
}

cur = cur.next;
}
}
return root;
}
}

``````

## 112. Path Sum

### Description

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

``````Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
``````

### Solution

``````class Solution {

public boolean hasPathSum(TreeNode root, int sum) {
return hasPathSumHelper(root, sum, 0);
}

public boolean hasPathSumHelper(TreeNode root, int target, int runningSum) {
if(root==null){
return false;
}
runningSum += root.val;
//the only condition which is true
if (root.left == null && root.right == null && target == runningSum) {
return true;
}
boolean res = false;
if (root.left != null) {
res = hasPathSumHelper(root.left, target, runningSum);
}
if (root.right != null) {
res |= hasPathSumHelper(root.right, target, runningSum);
}
return res;

}
}
``````

# 2020-07-13

## 1116. Print Zero Even Odd

### Description

Suppose you are given the following code:

``````class ZeroEvenOdd {
public ZeroEvenOdd(int n) { ... }      // constructor
public void zero(printNumber) { ... }  // only output 0's
public void even(printNumber) { ... }  // only output even numbers
public void odd(printNumber) { ... }   // only output odd numbers
}
The same instance of ZeroEvenOdd will be passed to three different threads:

Thread A will call zero() which should only output 0's.
Thread B will call even() which should only ouput even numbers.
Thread C will call odd() which should only output odd numbers.
Each of the threads is given a printNumber method to output an integer. Modify the given program to output the series 010203040506... where the length of the series must be 2n.

Example 1:

Input: n = 2
Output: "0102"
Explanation: There are three threads being fired asynchronously. One of them calls zero(), the other calls even(), and the last one calls odd(). "0102" is the correct output.
Example 2:

Input: n = 5
Output: "0102030405"
``````

### Solution

``````class ZeroEvenOdd {

private int n;

public ZeroEvenOdd(int n) {
this.n = n;
}

CyclicBarrier cyclicBarrier = new CyclicBarrier(3);
Semaphore semaphore = new Semaphore(0);

// printNumber.accept(x) outputs "x", where x is an integer.
public void zero(IntConsumer printNumber) throws InterruptedException {
try {
for (int i = 1; i <= n; i++) {
printNumber.accept(0);
semaphore.release();
cyclicBarrier.await();
}
} catch (BrokenBarrierException ignored) {
}
}

public void even(IntConsumer printNumber) throws InterruptedException {
try {
for (int i = 1; i <= n; i++) {
if (i % 2 == 0) {
semaphore.acquire();
printNumber.accept(i);
}
cyclicBarrier.await();
}
} catch (BrokenBarrierException ignored) {
}
}

public void odd(IntConsumer printNumber) throws InterruptedException {
try {
for (int i = 1; i <= n; i++) {
if (i % 2 != 0) {
semaphore.acquire();
printNumber.accept(i);
}
cyclicBarrier.await();
}
} catch (BrokenBarrierException ignored) {
}
}
}

``````

## 934. Shortest Bridge

### Description

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

``````Example 1:

Input: A = [[0,1],[1,0]]
Output: 1
Example 2:

Input: A = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Example 3:

Input: A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Constraints:

2 <= A.length == A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1
``````

### Solution

1.Find a island and use BFS to expand island one level each step until met a 1. so the steps are the min bridge length.

``````class Solution {

int[][] dirs = new int[][][[0, 1], [0, -1], [1, 0], [-1, 0]];

public int shortestBridge(int[][] A) {
boolean found = false;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[i].length; j++) {
if (!found) {
if (A[i][j] == 1) {
findBoarder(A, queue, i, j);
found = true;
}
} else {
break;
}
}
}

int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int s = 0; s < size; s++) {
int[] cur = queue.poll();
for (int[] dir : dirs) {
int i = cur[0] + dir[0];
int j = cur[1] + dir[1];
if (i >= 0 && j >= 0 && i < A.length && j < A[i].length && A[i][j] != -1) {
if (A[i][j] == 1) {
return step;
}
queue.offer(new int[]{i, j});
A[i][j] = -1;
}
}
}
step++;
}
return -1;

}

private void findBoarder(int[][] A, Queue<int[]> boarder, int i, int j) {
boolean isBoarder = false;
A[i][j] = -1;
for (int[] dir : dirs) {
int next_i = i + dir[0];
int next_j = j + dir[1];
if (next_i >= 0 && next_i < A.length && next_j >= 0 && next_j < A[next_i].length) {
if (A[next_i][next_j] == 0) {
isBoarder = true;
continue;
}
if (A[next_i][next_j] == 1) {
findBoarder(A, boarder, next_i, next_j);
}
}
}

if (isBoarder) {
}
}

}
``````

## 489. Robot Room Cleaner

### Design

Given a robot cleaner in a room modeled as a grid.

Each cell in the grid can be empty or blocked.

The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.

When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

Design an algorithm to clean the entire room using only the 4 given APIs shown below.

``````interface Robot {
// returns true if next cell is open and robot moves into the cell.
// returns false if next cell is obstacle and robot stays on the current cell.
boolean move();

// Robot will stay on the same cell after calling turnLeft/turnRight.
// Each turn will be 90 degrees.
void turnLeft();
void turnRight();

// Clean the current cell.
void clean();
}
Example:

Input:
room = [
[1,1,1,1,1,0,1,1],
[1,1,1,1,1,0,1,1],
[1,0,1,1,1,1,1,1],
[0,0,0,1,0,0,0,0],
[1,1,1,1,1,1,1,1]
],
row = 1,
col = 3

Explanation:
All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.
Notes:

The input is only given to initialize the room and the robot's position internally. You must solve this problem "blindfolded". In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot's position.
The robot's initial position will always be in an accessible cell.
The initial direction of the robot will be facing up.
All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
Assume all four edges of the grid are all surrounded by wall.
``````

### Solution

``````/**
search the room by DFS
search all four directions, go there, dfs, then go back.
*/
class Solution {

public void cleanRoom(Robot robot) {
// A number can be added to each visited cell
// use string to identify the class
Set<String> set = new HashSet<>();
int cur_dir = 0;
// 0: up, 90: right, 180: down, 270: left
backtrack(robot, set, 0, 0, 0);
}

public void backtrack(Robot robot, Set<String> set, int i,
int j, int cur_dir) {
String tmp = i + " " + j;
if (set.contains(tmp)) {
return;
}

robot.clean();

for (int n = 0; n < 4; n++) {
// the robot can to four directions, we use right turn
if (robot.move()) {
// can go directly. Find the (x, y) for the next cell based on current direction
int x = i, y = j;
switch (cur_dir) {
case 0:
// go up, reduce i
x = i - 1;
break;
case 90:
// go right
y = j + 1;
break;
case 180:
// go down
x = i + 1;
break;
case 270:
// go left
y = j - 1;
break;
default:
break;
}

backtrack(robot, set, x, y, cur_dir);
// go back to the starting position
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnRight();
robot.turnRight();

}
// turn to next direction
robot.turnRight();
cur_dir = (cur_dir + 90) % 360;
}

}
}
``````

## 453. Minimum Moves to Equal Array Elements

### Description

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

### Solution

``````/**
let's define sum as the sum of all the numbers, before any moves; minNum as the min number int the list; n is the length of the list;

After, say m moves, we get all the numbers as x , and we will get the following equation

sum + m * (n - 1) = x * n
and actually,

x = minNum + m
This part may be a little confusing, but @shijungg explained very well. let me explain a little again. it comes from two observations:

the minum number will always be minum until it reachs the final number, because every move, other numbers (besides the max) will be increamented too;
from above, we can get, the minum number will be incremented in every move. So, if the final number is x, it would be minNum + moves;
and finally, we will get

sum - minNum * n = m
This is just a math calculation.
*/
class Solution {
public int minMoves(int[] nums) {
return IntStream.of(nums).sum() - nums.length * IntStream.of(nums).min().getAsInt();
}
}
``````

## 670. Maximum Swap

### Description

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

``````Example 1:
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973
Output: 9973
Explanation: No swap.
Note:
The given number is in the range [0, 108]
``````

### Solution

``````class Solution {

public int maximumSwap(int num) {
int[] buckets = new int[10];
char[] arr = String.valueOf(num).toCharArray();
//record the last index of a digit.
for (int i = 0; i < arr.length; i++) {
buckets[arr[i] - '0'] = i;
}

for (int i = 0; i < arr.length; i++) {
//try all number that is larger than current position.
for (int k = 9; k >= arr[i] - '0'; k--) {
//if this larger number has one that is after the current position i
//than can swap to current position.
if (buckets[k] > i) {
//swap and return.
char temp = arr[i];
arr[i] = arr[buckets[k]];
arr[buckets[k]] = temp;
return Integer.parseInt(String.valueOf(arr));
}
}
}

//no need to swap, it's already the largest possible.
return num;
}
}

``````

## 901. Online Stock Span

### Description

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

``````For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Example 1:

Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation:
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.

Note:

Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
There will be at most 10000 calls to StockSpanner.next per test case.
There will be at most 150000 calls to StockSpanner.next across all test cases.
The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.
``````

### Solution

``````/**
Let's trace the algorithm together on [100, 80, 60, 70, 60, 75, 85]
1. calling StockSpanner.next(100) should result in first element in our stack will be (100, 1) (s.size() == 1)
2. calling StockSpanner.next(80) should result in second element in our stack will be (80, 1) (s.size() == 2)
3. calling StockSpanner.next(60) should result in third element in our stack will be (60, 1) (s.size() == 3)
4. Now on calling StockSpanner.next(70) we should add span of (60) + 1 {the current day}
and remove it from stack (70, 2) (s.size() == 3)
5. Now on calling StockSpanner.next(60) result in fourth element in our stack will be (60, 1) (s.size() == 4)
6. Now on calling StockSpanner.next(75) we should add span of (60) and (70) + 1 {the current day}
and remove it from stack : (75, 4) (s.size() == 3)
7. Now on calling StockSpanner.next(85) we should add span of (75) and (80) + 1 {the current day}
and remove it from stack : (85, 6) (s.size() == 2)
*/
class StockSpanner {

ArrayDeque<int[]> stack;

public StockSpanner() {
this.stack = new ArrayDeque<>();
}

public int next(int price) {
int count = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) {
count += stack.pop()[1];
}
stack.push(new int[]{price, count});
return count;
}
}
``````

# 2020-07-14

## 1248. Count Number of Nice Subarrays

### Description

Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

``````Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.
Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length
``````

### Solution

``````//Exactly K times = at most K times - at most K - 1 times
class Solution {

public int numberOfSubarrays(int[] nums, int k) {
return atMost(nums,k) - atMost(nums,k-1);
}

public int atMost(int[] nums, int k) {
int count = 0;
int i = 0, j = 0;
while (j < nums.length) {
k -= nums[j] % 2;
while(k < 0){
k += nums[i++]%2;
}
count += j-i+1;
j++;
}
return count;
}
}

``````

## 1071. Greatest Common Divisor of Strings

### Description

For strings S and T, we say “T divides S” if and only if S = T + … + T (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides str2.

``````Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Note:

1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] and str2[i] are English uppercase letters.
``````

### Solution

``````class Solution {

public String gcdOfStrings(String str1, String str2) {
String s = str1.length() < str2.length() ? str1 : str2;
int len = s.length();
for (int d = 1; d <= len; ++d) {
if (len % d != 0) {
continue;
}
// only if length of s mod d is 0, can sub be common divisor.
String sub = s.substring(0, len / d);
if (str1.replace(sub, "").isEmpty() && str2.replace(sub, "").isEmpty()) {
return sub;
}
}
return "";
}

}
``````

# 2020-07-15

### Description

``````Given a C++ program, remove comments from it. The program source is an array where source[i] is the i-th line of the source code. This represents the result of splitting the original source code string by the newline character \n.

The string // denotes a line comment, which represents that it and rest of the characters to the right of it in the same line should be ignored.

The string /* denotes a block comment, which represents that all characters until the next (non-overlapping) occurrence of */ should be ignored. (Here, occurrences happen in reading order: line by line from left to right.) To be clear, the string /*/ does not yet end the block comment, as the ending would be overlapping the beginning.

The first effective comment takes precedence over others: if the string // occurs in a block comment, it is ignored. Similarly, if the string /* occurs in a line or block comment, it is also ignored.

If a certain line of code is empty after removing comments, you must not output that line: each string in the answer list will be non-empty.

There will be no control characters, single quote, or double quote characters. For example, source = "string s = "/* Not a comment. */";" will not be a test case. (Also, nothing else such as defines or macros will interfere with the comments.)

It is guaranteed that every open block comment will eventually be closed, so /* outside of a line or block comment always starts a new comment.

Finally, implicit newline characters can be deleted by block comments. Please see the examples below for details.

After removing the comments from the source code, return the source code in the same format.

Example 1:
Input:
source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]

The line by line code is visualized as below:
/*Test program */
int main()
{
// variable declaration
int a, b, c;
/* This is a test
multiline
comment for
testing */
a = b + c;
}

Output: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]

The line by line code is visualized as below:
int main()
{

int a, b, c;
a = b + c;
}

Explanation:
The string /* denotes a block comment, including line 1 and lines 6-9. The string // denotes line 4 as comments.
Example 2:
Input:
source = ["a/*comment", "line", "more_comment*/b"]
Output: ["ab"]
Explanation: The original source string is "a/*comment\nline\nmore_comment*/b", where we have bolded the newline characters.  After deletion, the implicit newline characters are deleted, leaving the string "ab", which when delimited by newline characters becomes ["ab"].
Note:

The length of source is in the range [1, 100].
The length of source[i] is in the range [0, 80].
Every open block comment is eventually closed.
There are no single-quote, double-quote, or control characters in the source code.
``````

### Solution

``````/**
Consider case:
[
"struct Node{",
"    /*/ declare members;/**\/",
"    int size;",
"    /**\/int val;",
"};"
]
*/
class Solution {

List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
boolean mode = false;
for (String s : source) {
for (int i = 0; i < s.length(); i++) {
if (mode) {
if (s.charAt(i) == '*' && i < s.length() - 1 && s.charAt(i + 1) == '/') {
mode = false;
i++;        //skip '/' on next iteration of i
}
} else {
if (s.charAt(i) == '/' && i < s.length() - 1 && s.charAt(i + 1) == '/') {
break;      //ignore remaining characters on line s
} else if (s.charAt(i) == '/' && i < s.length() - 1 && s.charAt(i + 1) == '*') {
mode = true;
i++;           //skip '*' on next iteration of i
} else {
sb.append(s.charAt(i));     //not a comment
}
}
}
if (!mode && sb.length() > 0) {
sb = new StringBuilder();   //reset for next line of source code
}
}
return res;
}
}

``````

## 1428. Leftmost Column with at Least a One

### Description

(This problem is an interactive problem.)

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1.

You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

BinaryMatrix.get(row, col) returns the element of the matrix at index (row, col) (0-indexed). BinaryMatrix.dimensions() returns a list of 2 elements [rows, cols], which means the matrix is rows * cols. Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

``````Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0
``````

``````Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1
``````

``````Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1
``````

``````Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1
``````
``````
Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is either 0 or 1.
mat[i] is sorted in a non-decreasing way.
``````

### Solution

Liner solution

``````/**
if cur is 1, means we can still go further as left as possible until met a one
so we can keep record of the min col index for 1
no need to go back since we have the best answer right now and better answer lies on our left.

if cur is 0, means current row has larger index for 1, so skip for next.
*/
class Solution {

public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
List<Integer> size = binaryMatrix.dimensions();
int row = size.get(0);
int col = size.get(1);
int min_idx = Integer.MAX_VALUE;
int r = 0,c =col-1;
while(r<row && c>=0){
if(binaryMatrix.get(r,c)==1){
min_idx = Math.min(min_idx,c);
c--;
}else{
r++;
}
}

return min_idx==Integer.MAX_VALUE?-1:min_idx;

}
}
``````

binary solution

``````//for each row, we use binary search to find the first index for 1.
class Solution {

public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
List<Integer> size = binaryMatrix.dimensions();
int row = size.get(0);
int col = size.get(1);
int min_idx = Integer.MAX_VALUE;
for(int i = 0;i<row;i++){
int left = 0, right = col - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int last = binaryMatrix.get(i, mid);
if (last == 0) {
left = mid+1;
} else {
right = mid;
}
}
min_idx = Math.min(min_idx,binaryMatrix.get(i, left)==1?left:Integer.MAX_VALUE);
}

return min_idx==Integer.MAX_VALUE?-1:min_idx;

}
}

``````

## 1209. Remove All Adjacent Duplicates in String II

### Description

Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made.

It is guaranteed that the answer is unique.

``````Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.
Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Constraints:

1 <= s.length <= 10^5
2 <= k <= 10^4
s only contains lower case English letters.
``````

### Solution

``````//use stack to store information about previous continues string length and char.
//bbaaab -> (b,2),(a,3), then (a,3) will pop out, and find out b belongs to (b,2)
//increment by one -> (b,3) so valid again, pop out again.
//until loop over the whole string.
class Solution {
public String removeDuplicates(String s, int k) {
StringBuilder sb = new StringBuilder();
ArrayDeque<int[]> pre = new ArrayDeque<>();
pre.push(new int[]{-1,0});
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i));
int[] record = pre.peek();
if(s.charAt(i)-'a'==record[0]){
record[1]++;
if(record[1]==k){
sb.delete(sb.length()-k, sb.length());
pre.pop();
}else{
pre.pop();
pre.push(new int[]{record[0],record[1]});
}
}else{
pre.push(new int[]{s.charAt(i)-'a',1});
}
}

return sb.toString();
}
}

``````

## 351. Android Unlock Patterns

### Description

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

``````Rules for a valid pattern:

Each pattern must connect at least m keys and at most n keys.
All the keys must be distinct.
If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
The order of keys used matters.

``````

``````
Explanation:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Invalid move: 4 - 1 - 3 - 6
Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2
Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6
Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Example:

Input: m = 1, n = 1
Output: 9
``````

### Solution

``````public class Solution {

// cur: the current position
// remain: the steps remaining
int DFS(boolean vis[], int[][] skip, int cur, int remain) {
if (remain < 0) {
return 0;
}
if (remain == 0) {
return 1;
}
vis[cur] = true;
int rst = 0;
for (int i = 1; i <= 9; ++i) {
// If vis[i] is not visited and (two numbers are adjacent or skip number is already visited)
if (!vis[i] && (skip[cur][i] == 0 || (vis[skip[cur][i]]))) {
rst += DFS(vis, skip, i, remain - 1);
}
}
vis[cur] = false;
return rst;
}

public int numberOfPatterns(int m, int n) {
// Skip array represents number to skip between two pairs
int skip[][] = new int[10][10];
skip[1][3] = skip[3][1] = 2;
skip[1][7] = skip[7][1] = 4;
skip[3][9] = skip[9][3] = 6;
skip[7][9] = skip[9][7] = 8;
skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
boolean vis[] = new boolean[10];
int rst = 0;
// DFS search each length from m to n
for (int i = m; i <= n; ++i) {
rst += DFS(vis, skip, 1, i - 1) * 4;    // 1, 3, 7, 9 are symmetric
rst += DFS(vis, skip, 2, i - 1) * 4;    // 2, 4, 6, 8 are symmetric
rst += DFS(vis, skip, 5, i - 1);        // 5
}
return rst;
}
}

``````

## 59. Spiral Matrix II

### Description

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

``````Example:

Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
``````

### Solution

``````class Solution {

public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int end = n*n+1;
if (n == 0) {
return res;
}

int rowStart = 0, rowEnd = n - 1;
int colStart = 0, colEnd = n - 1;
int num = 1;
while (rowStart <= rowEnd && colStart <= colEnd) {
for (int i = colStart; i <= colEnd; i++) {
res[rowStart][i] = num++;
//end case
if(num==end)break;
}
rowStart++;

for(int i=rowStart;i<=rowEnd;i++){
res[i][colEnd] = num++;
//end case
if(num==end)break;
}
colEnd--;

for(int i = colEnd;i>=colStart;i--){
res[rowEnd][i] = num++;
//end case
if(num==end)break;
}
rowEnd--;

for(int i = rowEnd;i>=rowStart;i--){
res[i][colStart] = num++;
//end case
if(num==end)break;
}
colStart++;
}
return res;
}
}

``````