IrisJavaDiary: December 2018

Monday, December 31, 2018

805. Split Array With Same Average

class Solution {
public boolean splitArraySameAverage(int[] A) {
// for a previous i numbers in A [0, i)
// countB = m, countC = i - m
// B sumB C sumC
// We could have same
// For each coming A[i] -> we have 2 choices
// put into B -> sumB = sumB + A[i], countB = countB + 1, sumC = sumC, countC = countC
// put into C -> sumB = sumB, countB = countB, sumC = sumC + A[i], countC = countC + 1

// split into 2 groups -> avgB = sumB / countB, avgC = sumC / countC
// sumB / countB = sumC / countC -> sumB * countC = sumC * countB -> sumB * (count - countB) = (sum - sumB) * countB
// avg = avgB = avgC
// sumB * count = sum * countB -> sumC * count = sum * countC
int count = A.length;
int sum = 0;
for(int a : A) sum += a;
// Can we find a subset of A whose average equals to the average of A
// knapsack problem

}
}

815. Bus Routes

Version #1 BFS on buses

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

I choose to store buses instead of stops is because that number of stops worst case is 500*500 if they are all distinct
However the number is buses is only 500
So considering the Space complexity, I used bus number to represent the state

We visit all bus at most twice
Time O(#buses)

38.92 %
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T) return 0;
// if we are at bus j, then we can travel to any stop that can be reached by bus j
// Which means we can trafer to any of the buses that stop by all those stops
// routes[j] -> stop number that we can reach by taking bus[j]
Map<Integer, Set<Integer>> stopToBus = new HashMap<>();
for (int j = 0; j < routes.length; j++) { // bus[j]
for (int i = 0; i < routes[j].length; i++) { // routes[j][i] -> stop number
stopToBus.putIfAbsent(routes[j][i], new HashSet<>());
stopToBus.get(routes[j][i]).add(j);
}
}
// que of bus
Set<Integer> taken = new HashSet<>();
Set<Integer> visited = new HashSet<>();
Queue<Integer> que = new LinkedList<>();
Set<Integer> buses = stopToBus.get(S);
for (int bus : buses) {
que.offer(bus);
}
int level = 0;
while (!que.isEmpty()) {
int size = que.size();
level++;
while (size-- > 0) {
int bus = que.poll();
for (int i = 0; i < routes[bus].length; i++) { // stops that can be reached by current bus
if (routes[bus][i] == T) return level;
if (visited.add(routes[bus][i])) { // this stop is never reached before
buses = stopToBus.get(routes[bus][i]);
for (int nextBus : buses) {
if (taken.add(nextBus)) { // this bus is never taken before
que.offer(nextBus);
}
}
}
}
}
}
return -1;
}
}

814. Binary Tree Pruning

Version #2 DFS -> using null to represent false

47.32 %
class Solution {
public TreeNode pruneTree(TreeNode root) {
if (root == null) return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.left == null && root.right == null && root.val == 0) return null;
return root;
}
}

Version #1 Typical DFS

5.28 %
class Solution {
public TreeNode pruneTree(TreeNode root) {
// recursively check if a node's left&right subtree containing 1
// if substree returns false, then set that subtree to null
// return dfs(left) || dfs(right) || node.val == 1
if (dfs(root)) return root;
return null;
}
private boolean dfs(TreeNode node) {
if (node == null) return false;
boolean left = dfs(node.left);
boolean right = dfs(node.right);
if (!left) {
node.left = null;
}
if (!right) {
node.right = null;
}
return left || right || node.val == 1;
}
}

813. Largest Sum of Averages

It is a classical O(n^3) DP problem
Related Problems
LC 139 Word Break
LC 312 Burst Balloons
It also looks like the buying stock series of problems

二刷 06/2022

Version #2 DP with optimized space

这里的dp可以有两个定义

第一种就是a划分成exactly K partitions, 第二种是bat most K partitions

Time O(KN^2)

Space O(N)

Version 2.a

Exactly K partitions，需要对每个K的dp[len]都取一次max

class Solution {

public double largestSumOfAverages(int[] nums, int k) {

int len = nums.length;

int[] prefixSum = new int[len + 1];

// prefixSum[i] - the sum of nums [0, i)

for (int i = 1; i <= len; i++) {

prefixSum[i] = prefixSum[i - 1] + nums[i - 1];

}

// dp[i] - the max score to partition nums [0, i) into n groups

double max = 0.0;

double[] dp = new double[len + 1];

for (int n = 1; n <= k; n++) {

double[] currDP = new double[len + 1];

for (int i = 1; i <= len; i++) {

if (n == 1) {

// to split sub array [0, i) into 1 partition

currDP[i] = (double)(prefixSum[i] - prefixSum[0]) / i;

} else {

for (int j = i - 1; j >= n - 1; j--) {

currDP[i] = Math.max(currDP[i], dp[j] + (double)(prefixSum[i] - prefixSum[j]) / (i - j));

}

if (i == len) {

max = Math.max(max, currDP[i]);

}

dp = currDP;

}

return max;

}

Version 2.b

class Solution {

public double largestSumOfAverages(int[] nums, int k) {

int len = nums.length;

int[] prefixSum = new int[len + 1];

// prefixSum[i] - the sum of nums [0, i)

for (int i = 1; i <= len; i++) {

prefixSum[i] = prefixSum[i - 1] + nums[i - 1];

}

// dp[i] - the max score to partition nums [0, i) into n groups

double max = 0.0;

double[] dp = new double[len + 1];

for (int n = 1; n <= k; n++) {

double[] currDP = new double[len + 1];

for (int i = 1; i <= len; i++) {

if (n == 1) {

// to split sub array [0, i) into 1 partition

currDP[i] = (double)(prefixSum[i] - prefixSum[0]) / i;

} else {

for (int j = i - 1; j >= 0; j--) {

currDP[i] = Math.max(currDP[i], dp[j] + (double)(prefixSum[i] - prefixSum[j]) / (i - j));

}

// if (i == len) {

// max = Math.max(max, currDP[i]);

// }

}

dp = currDP;

}

return dp[len];

}

一刷
Version # 1 DP (Space can be optimized)
Time O(n^2 k)
Space O(nk)

44.02 %
class Solution {
public double largestSumOfAverages(int[] A, int K) {
// dp[i][m] - partition previous[0,i] items into m groups where m >= 1, m <= i + 1, m <= K
// dp[i][m] = Math.min(dp[j][m-1]) + avg(A[j+1, i])
int len = A.length;
double sum = 0;
double[][] dp = new double[len][K + 1];
for (int i = 0; i < len; i++) {
sum += A[i]; // sum[0, A[i]]
// K = 0 -> don't partition
dp[i][1] = sum / (i + 1); // the average of A[0, i], m = 0 is invalid
for (int m = 2; m <= Math.min(i + 1, K); m++) { // partition previous i numbers into m groups m -> [1, Math.min(i + 1, K)]
double subSum = 0;
double avg = 0;
for (int j = i - 1; j >= 0; j--) {
// [0,j][j+1,i]
subSum += A[j + 1];
avg = Math.max(avg, dp[j][m - 1] + subSum / (i - j));
}
dp[i][m] = avg;
}
}
return dp[len - 1][K];
}
}

823. Binary Trees With Factors

二刷 08/2022

Version #1 DP

之前的做法是存num value和dp的值

这次的做法是存index 和value-index的mapping，明显更快

Time O(N^2)

Space O(N)

Runtime: 19 ms, faster than 99.42% of Java online submissions for Binary Trees With Factors.

Memory Usage: 46.9 MB, less than 53.76% of Java online submissions for Binary Trees With Factors.

class Solution {

private int MOD = (int)(1e9 + 7);

public int numFactoredBinaryTrees(int[] arr) {

Arrays.sort(arr);

// key-number, value-index

Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < arr.length; i++) {

map.put(arr[i], i);

}

int sum = 0;

// dp[i] - number of trees with numbers from arr[0, i]

int[] dp = new int[arr.length];

for (int j = 0; j < arr.length; j++) {

dp[j] = 1;

for (int i = 0; i <= j; i++) {

int quotient = arr[j] / arr[i];

if (quotient < arr[i]) {

break;

}

if (quotient * arr[i] == arr[j] && map.containsKey(quotient)) {

long product = (long)dp[i] * dp[map.get(quotient)] * (i == map.get(quotient) ? 1 : 2) % MOD;

dp[j] = (int)(dp[j] + product) % MOD;

}

// System.out.printf("dp[%d]=%d\n", j, dp[j]);

sum = (sum + dp[j]) % MOD;

}

return sum;

}

一刷
Version #1 DP
Time O(n^2)
Space O(n)

17.09 %
class Solution {
public int numFactoredBinaryTrees(int[] A) {
// key-number, valud-count of possible numFactoredBinaryTrees with root as current number
Map<Integer, Long> dp = new HashMap<>();
long mod = (long) (1e9 + 7);
Arrays.sort(A);
int len = A.length;
for (int i = 0; i < len; i++) { // number
int root = A[i];
dp.put(root, 1l); // -> number itself can always be a tree
for (int j = 0; j < i; j++) {
int left = A[j];
if (root % left == 0 && dp.containsKey(root / left)) {
dp.put(root, (dp.get(root) + dp.get(left) * dp.get(root / left)) % mod);
}
}
}
long result = 0;
for (long count : dp.values()) {
result = (result + count) % mod;
}
return (int)result;
}
}

820. Short Encoding of Words

二刷 06/2022

Version #1 Trie + DFS

和一刷写的基本一样

看到答案有一个优化就是记录每一个TrieNode的children count，然后用一个hashmap把所有的TrieNode存起来，最后iterate一遍所有的TrieNode，如果children count是0，就是leaf 这样可以避免再做一次dfs

Time O(Sum{word length})

Space O(Sum{word length})

Runtime: 33 ms, faster than 64.02% of Java online submissions for Short Encoding of Words.

Memory Usage: 59 MB, less than 47.56% of Java online submissions for Short Encoding of Words.

一刷class Solution {

class TrieNode {

TrieNode[] children;

boolean isWord;

public TrieNode() {

children = new TrieNode[26];

}

private void addWord(TrieNode root, String word) {

for (int i = word.length() - 1; i >= 0; i--) {

int index = word.charAt(i) - 'a';

if (root.children[index] == null) {

root.children[index] = new TrieNode();

}

root = root.children[index];

}

root.isWord = true;

}

public int minimumLengthEncoding(String[] words) {

// Build a suffix trie with the revered order of all words

// Search for all the leaf nodes and add up their depth + 1 '#'

TrieNode root = new TrieNode();

for (String word : words) {

addWord(root, word);

}

int[] result = new int[1];

dfs(root, 0, result);

return result[0];

// root

// t

// \

// isWord

}

private void dfs(TrieNode node, int depth, int[] result) {

boolean isLeaf = true;

for (int i = 0; i < 26; i++) {

if (node.children[i] != null) {

isLeaf = false;

dfs(node.children[i], depth + 1, result);

}

if (isLeaf) {

result[0] += depth + 1;

}

Version #1 Trie + DFS

The complexity of creating a trie is O(W*L), where W is the number of words, and L is an average length of the word: you need to perform L lookups on the average for each of the W words in the set.

Same goes for looking up words later: you perform L steps for each of the W words.

/*
root
\
e
\
m
*/

81.33 %
class Solution {
class Trie {
Trie[] children;
}
public int minimumLengthEncoding(String[] words) {
// build trie for reversed word
// e.g. time -> e-m-i-t, me -> e-m so time and me will share the same e-m path
// we build the result with the longest length of each path
Trie root = new Trie();
for (String word : words) {
add(root, word);
}
int[] result = new int[1];
dfs(root, result, 1);
return result[0];
}

private void dfs(Trie node, int[] result, int path) {
if (node.children == null) { // isleaf
result[0] += path;
return;
}
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
dfs(node.children[i], result, path + 1);
}
}
}

private void add(Trie root, String word) {
Trie curr = root;
for (int i = word.length() - 1; i >= 0; i--) {
int index = word.charAt(i) - 'a';
if (curr.children == null) {
curr.children = new Trie[26];
}
if (curr.children[index] == null) {
curr.children[index] = new Trie();
}
curr = curr.children[index];
}
}
}

818. Race Car

Version #1 BFS with mem

Naive BFS will run at O(2^n) since for each position we have two choices: either accelerate or reverse.
Optimizations
1. To avoid duplicate search we need to keep track of searched states, however the Space will be O(2^n) -> we can only record the states that have speed +1 / -1
2. We don't accelerate once the next position has exceed the range of 2 * target

53.19 %
class Solution {
public int racecar(int target) {
// BFS
// standing at a point a[0] with speed a[1], we can either A -> new int[]{a[0] + a[1], 2 * a[1]} or new int[]{a[0], -a[1]/a[1]}
Queue<int[]> que = new LinkedList<>();
//state -> integer -> last bit for 0-> move backword, 1-> move forward, other bits-> position
Set<Integer> visited = new HashSet<>();
que.offer(new int[]{0, 1});
visited.add(0);
visited.add(1);
int level = 0;
while (!que.isEmpty()) {
level++;
int size = que.size();
while (size-- > 0) {
int[] curr = que.poll(); // curr[0]-pos, curr[1]-speed
// System.out.println(curr[0] + curr[1]);
if (curr[0] + curr[1] == target) {
return level;
}
// A
if (Math.abs(curr[0] + curr[1]) < 2 * target) {
que.offer(new int[]{curr[0] + curr[1], 2 * curr[1]});
}
// R
curr[1] = -curr[1] / Math.abs(curr[1]); // curr[1] = 4 -> -4/4=-1 curr[1] = -1 -> 4/4 = 1
int state = (curr[0] << 1) | (curr[1] == -1 ? 0 : 1);
// System.out.println("state " + Integer.toBinaryString(state));
if (visited.add(state)) {
que.offer(new int[]{curr[0], curr[1]});
}
}
}
return -1;
}
}

Sunday, December 30, 2018

964. Least Operators to Express Number

Version #2 Dijastra[TODO]

Version #1 Memorized DFS
最重要的是要掌握如何用一个x的多项式，组成target？
1 '/' 一定是多余的，因为没有必要进行任何形式的 x * x / x 的冗余操作
2 '/' 只出现在我们需要1的情况下 1 == 'x / x'
3 多项式表示为arget = c0*x^0 + c1*x^1 + c2*x^2 + ...
+ cn*x^(log(target) / log(x)) + cn+1*x^(log(target) / log(x) + 1)
其中的c 在 (+/- x)
4 避免成环就是要避免重复搜索
case 1 不会造成重复搜索，因为 target - x^k永远只能越来越小
case 2 如果x^(k+1) - target 比target大或相等，就无法收敛，所以要避免这种情况

写了一个bug
出现在当我们需要 c0 * x^0 的时候
因为我没没有办法以任何形式表示 x^0，所以只能用 x/x 代替 x^0
根据其他k的规律， x^2 = x * x -> 1 = k-1
x^ 3 = x * x * x -> 2 = k-1
在这里是违反的，因为 x^0 -> 1
所以要特殊情况特殊讨论

Time O(log target)

26.14 %
class Solution {
public int leastOpsExpressTarget(int x, int target) {
// target = c0*x^0 + c1*x^1 + c2*x^2 + ...
// + cn*x^(log(target) / log(x)) + cn+1*x^(log(target) / log(x) + 1)
Map<Integer, Integer> visited = new HashMap<>();
visited.put(0, 0); // no ops needed for 0
visited.put(1, 1); // 1 -> x/x -> 1 op for 1
return dfs(x, target, visited);
}

private int dfs(int x, int target, Map<Integer, Integer> visited) {
if (visited.containsKey(target)) return visited.get(target);
int k = (int) Math.floor(Math.log(target) / Math.log(x));
// when k == 0, we can't make 3^0
int p = (int) Math.pow(x, k);
if (p == target) { // x*x*x -> 2 ops
visited.put(target, k - 1);
return k - 1;
}
// 1st choice -> target - x^k
int min = (k == 0 ? 2 : k) + dfs(x, target - p, visited);
// 2nd choice -> x^(k+1) - target -> we have to guarantee that x^(k+1) - target < target
if (p * x - target < target) {
min = Math.min(min, k + 1 + dfs(x, p * x - target, visited));
}
// we don't minus 1 for both case 1 and 2
// because we need an extra (+/-) to combine current result to its subproblem's result
visited.put(target, min);
return min;
}
}

Saturday, December 29, 2018

398. Random Pick Index[Sampling Algo]

Version #2 Reservoir Sampling
https://www.geeksforgeeks.org/reservoir-sampling/

26.07 %
class Solution {
Random rd;
int[] nums;
public Solution(int[] nums) {
this.rd = new Random();
this.nums = nums;
}

public int pick(int target) {
int count = 0;
int result = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != target) continue;
count++;
if (rd.nextInt(count) == 0) result = i;
}
return result;
}
}

Version #1 Naiive
4.42 %
class Solution {

Map<Integer, List<Integer>> map = new HashMap<>();
Random rd;
public Solution(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], new ArrayList<>());
}
map.get(nums[i]).add(i);
}
rd = new Random();
}

public int pick(int target) {
List<Integer> index = map.get(target);
return index.get(rd.nextInt(index.size()));
}
}

Friday, December 28, 2018

822. Card Flipping Game

This problem's description is a trash...

I just copied one of the solutions in the discuss forum...

JVM Garbage Collection

https://stackoverflow.com/questions/2414105/why-is-it-bad-practice-to-call-system-gc

Thursday, December 27, 2018

358. Rearrange String k Distance Apart

Version #1 Greedy
Always append the char of most count
Use wait list to hold chars that need cool down time
[2ND TRY]
When the items in the waiting queue has satisfied the k limit, we check if its remaining count is larger than 0 or not. Only push back to maxHeap if its remaining count is larger than 0

class Solution {
public String rearrangeString(String s, int k) {
if (k == 0) return s;
// abacabcd
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
if (count[index] > s.length() / k + 1) return "";
count[index]++;
}
// int[0] -> char index in 26, int[1] -> remaining count
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
maxHeap.offer(new int[]{i, count[i]});
}
}
StringBuilder sb = new StringBuilder();
Queue<int[]> waitingQue = new LinkedList<>();
while (!maxHeap.isEmpty()) {
int[] curr = maxHeap.poll();
curr[1]--;
sb.append((char) (curr[0] + 'a'));
waitingQue.offer(curr);
if (waitingQue.size() >= k) {
int[] back = waitingQue.poll();
if (back[1] > 0) {
maxHeap.offer(back);
}
}
}
return sb.length() == s.length() ? sb.toString() : "";
// return sb.toString();
}
}

[1ST TRY]
int[]
8.45 %
class Solution {
public String rearrangeString(String s, int k) {
// Every time we are trying to arrange the char with the most count
int[] map = new int[26];
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i) - 'a']++;
}
// index is char, value is count
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < 26; i++) {
if (map[i] > 0) maxHeap.offer(new int[]{i, map[i]});
}
Queue<int[]> que = new LinkedList<>();
StringBuilder sb = new StringBuilder();
while (!maxHeap.isEmpty()) {
int[] curr = maxHeap.poll();
// System.out.println(curr[0] + " " + curr[1]);
sb.append((char)('a' + curr[0]));
curr[1]--;
que.offer(curr);
if (que.size() >= k) {
int[] item = que.poll();
if (item[1] > 0) maxHeap.offer(item);
}

}
return sb.length() == s.length() ? sb.toString() : "";
}
}

Map.Entry

class Solution {
public String rearrangeString(String s, int k) {
// Every time we are trying to arrange the char with the most count
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
map.put(c, 1 + map.getOrDefault(c, 0));
}
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
maxHeap.addAll(map.entrySet());
Queue<Map.Entry<Character, Integer>> que = new LinkedList<>();
StringBuilder sb = new StringBuilder();
while (!maxHeap.isEmpty()) {
Map.Entry<Character, Integer> curr = maxHeap.poll();
// System.out.println(curr.getKey() + " " + curr.getValue());
sb.append(curr.getKey());
curr.setValue(curr.getValue() - 1);
que.offer(curr);
if (que.size() < k) continue;
Map.Entry<Character, Integer> item = que.poll();
if (item.getValue() > 0) maxHeap.offer(item);
}
return sb.length() == s.length() ? sb.toString() : "";
}
}

812. Largest Triangle Area

81.34 %
class Solution {
public double largestTriangleArea(int[][] points) {
if (points == null || points.length < 3) return 0;
double result = 0;
int N = points.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
result = Math.max(result, area(points[i][0], points[i][1], points[j][0], points[j][1], points[k][0], points[k][1]));
}
}
}
return result;
}
// [[8,3],[5,6],[3,5]]
private double area(int ax, int ay, int bx, int by, int cx, int cy) {
// Area = 0.5 * (Ax(By - Cy) + Bx(Cy - Ay) + Cx(Ay-By))
return 0.5 * Math.abs(ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));
}
}

811. Subdomain Visit Count

Use substring() instead of spilt() will be more efficient

46.36 %
class Solution {
public List<String> subdomainVisits(String[] cpdomains) {
List<String> result = new ArrayList<>();
if (cpdomains == null || cpdomains.length == 0) return result;
Map<String, Integer> map = new HashMap<>();
for (String domain : cpdomains) {
int count = Integer.valueOf(domain.split(" ")[0]);

String[] strs = domain.split(" ")[1].split("\\.");
String curr = "";
for (int i = strs.length - 1; i >= 0; i--) {
if (curr.length() > 0) curr = "." + curr;
curr = strs[i] + curr;
if (!map.containsKey(curr)) {
map.put(curr, count);
} else {
map.put(curr, map.get(curr) + count);
}
}
}
for (Map.Entry<String, Integer> entry : map.entrySet()) {
result.add(entry.getValue() + " " + entry.getKey());
}
return result;
}
}

810. Chalkboard XOR Game[TODO]

MinMax approach

809. Expressive Words

52.66 %
class Solution {
public int expressiveWords(String S, String[] words) {
if (S == null || S.length() == 0 || words == null || words.length == 0) return 0;
int result = 0;
for (String word : words) {
if (check(S, word)) result++;
}
return result;
}
private boolean check(String S, String word) {
int pw = 0; // pointer of char position in word
for (int i = 0; i < S.length();) {
// Assume previous substring has already been matched
if (pw >= word.length() || S.charAt(i) != word.charAt(pw)) return false;
int countS = 1, countW = 1;
while (i + countS < S.length() && S.charAt(i + countS) == S.charAt(i)) countS++;
while (pw + countW < word.length() && word.charAt(pw + countW) == S.charAt(i)) countW++;
if (countS < countW) return false;
// countS >= 3 we can expand
if (countS != countW && countS < 3) return false;
pw += countW;
i += countS;
}
return pw == word.length();
}
}

Wednesday, December 26, 2018

808. Soup Servings

It is a very very good question

Version #1 Memorized DFS
The key is to properly define the state
The base case if very very tricky

Time O(N^2) Since there are total of N(a) * N(b) states

[2ND TRY]

70.19 %
class Solution {
public double soupServings(int N) {
if (N > 5000) return 1;
int a = (int) Math.ceil(N / 25.0);
int b = (int) Math.ceil(N / 25.0);
double[][] dp = new double[a + 1][b + 1];
for (int i = 0; i <= a; i++) {
Arrays.fill(dp[a], -1);
}
return dfs(a, b, dp);
}

private double dfs(int a, int b, double[][] dp) {
if (a >= 0 && b >= 0 && dp[a][b] > 0) {
return dp[a][b];
}
if (a <= 0) {
if (b <= 0) { // A,B become empty at the same time
return 0.5;
} else { // A be empty first
return 1;
}
} else if (b <= 0){ // B be empty first
return 0;
}
dp[a][b] = 0.25 * (dfs(a - 4, b, dp) + dfs(a - 3, b - 1, dp) + dfs(a - 2, b - 2, dp) + dfs(a - 1, b - 3, dp));
return dp[a][b];
}
}

[1ST TRY]
65.80 %
class Solution {
public double soupServings(int N) {
if (N > 5000) return 1.0;
// Since the states are discrete, we should solve it by memorized dfs instead of dp
// we use 25ml as one serve, if the remaining amount is less than 25, it is also treated as one serve
int n = N / 25 + (N % 25 == 0 ? 0 : 1);
// we use the remaining quantity to represent the state
return dfs(n, n, new HashMap<>());
}

private double dfs(int a, int b, Map<Integer, Map<Integer, Double>> map) {
// if we have a remaining and b remaming
if (a <= 0 && b <= 0) return 0.5;
if (a <= 0) return 1.0;
if (b <= 0) return 0.0;

if (map.containsKey(a) && map.get(a).containsKey(b)) {
return map.get(a).get(b);
}
// Serve 100 ml of soup A and 0 ml of soup B A4 B0
// Serve 75 ml of soup A and 25 ml of soup B A3 B1
// Serve 50 ml of soup A and 50 ml of soup B A2 B2
// Serve 25 ml of soup A and 75 ml of soup B A1 B3
double prob = 0.25 * (dfs(a - 4, b, map) + dfs(a - 3, b - 1, map) + dfs(a - 2, b - 2, map) + dfs(a - 1, b - 3, map));
Map<Integer, Double> aMap = map.getOrDefault(a, new HashMap<>());
aMap.put(b, prob);
map.put(a, aMap);
return prob;
}
}

807. Max Increase to Keep City Skyline

For grid[i][j], it can't be higher than the maximun of its row nor the maximum of its col.
So the maximum increasing height for a building at (i, j) is min(row[i], col[j]) - grid[i][j]
Time O(MN)
Space O(M + N)

96.74 %
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int[] rowMax = new int[rows];
int[] colMax = new int[cols];
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
rowMax[y] = Math.max(rowMax[y], grid[y][x]);
colMax[x] = Math.max(colMax[x], grid[y][x]);
}
}
int result = 0;
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
result += Math.min(rowMax[y], colMax[x]) - grid[y][x];
}
}
return result;
}
}

806. Number of Lines To Write String

73.79 %
class Solution {
public int[] numberOfLines(int[] widths, String S) {
if (S == null || S.length() == 0) return new int[]{0, 0};
int count = 1;
int curr = 0;
int len = 100; // can't exceed len for each row
for (int i = 0; i < S.length(); i++) {
if (curr + widths[S.charAt(i) - 'a'] > 100) {
count++;
curr = 0;
}
curr += widths[S.charAt(i) - 'a'];
}
return new int[]{count, curr};
}
}

804. Unique Morse Code Words

二刷 08/2022

Version #1 HashSet

Time O(ML) - M is number of words, L is the average length of words

Space O(ML)

Runtime: 2 ms, faster than 99.55% of Java online submissions for Unique Morse Code Words.

Memory Usage: 39.8 MB, less than 99.94% of Java online submissions for Unique Morse Code Words.

class Solution {

public int uniqueMorseRepresentations(String[] words) {

String[] map = new String[]{

".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."

};

Set<String> visited = new HashSet<>();

for (String word : words) {

StringBuilder sb = new StringBuilder();

for (int i = 0; i < word.length(); i++) {

sb.append(map[word.charAt(i) - 'a']);

}

visited.add(sb.toString());

}

return visited.size();

}

一刷
90.21 %
class Solution {
public int uniqueMorseRepresentations(String[] words) {
if (words == null || words.length == 0) return 0;
String[] dict = new String[]{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
Set<String> set = new HashSet<>();
StringBuilder sb = new StringBuilder();
for (String word : words) {
for (int i = 0; i < word.length(); i++) {
sb.append(dict[word.charAt(i) - 'a']);
}
set.add(sb.toString());
sb.setLength(0);
}
return set.size();
}
}

Tuesday, December 25, 2018

770. Basic Calculator IV[TODO]

469. Convex Polygon

if tmp == 0, a -> b 180° on the same line;
elif tmp > 0, a -> b clockwise;
else tmp < 0, a -> anticlockwise;

float BAx = Ax - Bx;
    float BAy = Ay - By;
    float BCx = Cx - Bx;
    float BCy = Cy - By;

    // Calculate the Z coordinate of the cross product.
    return (BAx * BCy - BAy * BCx);

如果cross product = 0证明在同一条直线上，需要直接skip
63.79 %
class Solution {
public boolean isConvex(List<List<Integer>> points) {
if (points == null || points.size() <= 2) return false;
int len = points.size();
Integer prev = null;
for (int i = 0; i < len; i++) {
List<Integer> A = i == 0 ? points.get(len - 1) : points.get(i - 1);
List<Integer> B = points.get(i);
List<Integer> C = i == len - 1 ? points.get(0) : points.get(i + 1);
int BAx = A.get(0) - B.get(0);
int BAy = A.get(1) - B.get(1);
int BCx = C.get(0) - B.get(0);
int BCy = C.get(1) - B.get(1);
int curr = BAx * BCy - BAy * BCx;
// System.out.println(i + " " + curr);
if (curr == 0) continue;
if (prev == null) {
prev = curr > 0 ? 1 : -1;
} else if (prev * curr < 0) {
return false;
}
}
return true;
}
}

666. Path Sum IV

二刷 06/2022

Version #1 DFS

Time O(N)

Space O(N)

Runtime: 1 ms, faster than 96.05% of Java online submissions for Path Sum IV.

Memory Usage: 39.7 MB, less than 95.39% of Java online submissions for Path Sum IV.

class Solution {

public int pathSum(int[] nums) {

if (nums == null || nums.length == 0) {

return 0;

}

// Split the numbers into index, value pairs

Map<Integer, Integer> map = new HashMap<>();

for (int num : nums) {

map.put(num / 10, num % 10);

}

// Given a node with index x

// its left child index is:

// ((x / 10) + 1) * 10 + (x % 10 - 1) * 2 + 1

// its right child index is:

// ((x / 10) + 1) * 10 + (x % 10 - 1) * 2 + 2

// e.g. 11

// / \

// 21 22

int[] sum = new int[1];

dfs(map, sum, nums[0] / 10, 0);

return sum[0];

}

private void dfs(Map<Integer, Integer> map, int[] sum, int index, int pathSum) {

int val = map.get(index);

pathSum += val;

int leftIndex = (index / 10 + 1) * 10 + (index % 10 - 1) * 2 + 1;

int rightIndex = leftIndex + 1;

if (!map.containsKey(leftIndex) && !map.containsKey(rightIndex)) {

sum[0] += pathSum;

return;

}

if (map.containsKey(leftIndex)) {

dfs(map, sum, leftIndex, pathSum);

}

if (map.containsKey(rightIndex)) {

dfs(map, sum, rightIndex, pathSum);

}

一刷
Path Sum的精髓是dfs到leaf然后维护一个path sum
在leaf处把这个path sum加到result里面

97.99 %
class Solution {
public int pathSum(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// traverse the tree, add path sum at leaf
int[] result = new int[1];
// key-id, value-value
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num / 10, num % 10);
}
dfs(nums[0] / 10, map, 0, result);
return result[0];
}
private void dfs(int id, Map<Integer, Integer> map, int path, int[] result) {
int val = map.get(id);
path += val;
//[113, 215, 221]
int left = id + 10 + id % 10 - 1;
int right = id + 10 + id % 10;
if (!map.containsKey(left) && !map.containsKey(right)) {
result[0] += path;
return;
}
if (map.containsKey(left)) {
dfs(left, map, path, result);
}
if (map.containsKey(right)) {
dfs(right, map, path, result);
}
}
}

Monday, December 24, 2018

932. Beautiful Array[TODO]

似懂非懂基本不懂
Version #1 Divide-Conquer
32.22 %
class Solution {
public int[] beautifulArray(int N) {
ArrayList<Integer> res = new ArrayList<>();
res.add(1);
while (res.size() < N) {
ArrayList<Integer> tmp = new ArrayList<>();
for (int i : res) if (i * 2 - 1 <= N) tmp.add(i * 2 - 1);
for (int i : res) if (i * 2 <= N) tmp.add(i * 2);
res = tmp;
}
return res.stream().mapToInt(i -> i).toArray();
}
}

962. Maximum Width Ramp

Version #2 Stack
Since we are looking for the maximum width between A[i] <= A[j]
We need the left to be as small as possible to match any potential right numbers
If a number is larger than its left value, it is useless for us, since it will never be the left part of our final result.
So our stack will become a decreasing array
After we add all the decreasing numbers to the stack, we iterate from the last element to the first element in our number array
We need our right number to be as large as possible
So we pop numbers from the stack for all numbers that less or equal to curr
We don't care any number that is smaller than current number because it has less chance to become larger than our potential left, and its index is smaller than our curr, so it will never become part of our final result

100.00 %
class Solution {
public int maxWidthRamp(int[] A) {
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < A.length; i++) {
if (stack.isEmpty() || A[i] < A[stack.peek()]) {
stack.push(i);
}
}
int max = 0;
for (int i = A.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && A[i] >= A[stack.peek()]) {
max = Math.max(max, i - stack.pop());
}
}
return max;
}
}

Version #1 Binary Search
O(nlogn)
85.71 %

class Solution {
public int maxWidthRamp(int[] A) {
// [6,0,8,2,1,5]
// decreasing list of index
List<Integer> list = new ArrayList<>();
int max = 0;
list.add(0);
for (int i = 1; i < A.length; i++) {
if (A[i] < A[list.get(list.size() - 1)]) {
list.add(i);
}
int start = 0;
int end = list.size() - 1;
// current A[i]
while (start < end) {
int mid = start + (end - start) / 2;
// System.out.println(A[list.get(mid)] + " " + A[i]);
if (A[list.get(mid)] > A[i]) {
start = mid + 1;
// System.out.println(A[list.get(mid)] + " " + A[i]);
} else {
end = mid;
}
}
// System.out.println(A[list.get(start)] + " " + A[i]);
if (A[list.get(start)] <= A[i]) {
max = Math.max(max, i - list.get(start));
}
}
return max;
}
}

Sunday, December 23, 2018

172. Factorial Trailing Zeroes

[2ND TRY]

class Solution {
public int trailingZeroes(int n) {
// given a number, how can we calculate trailing zeros of its factorial
// e.g. 10 -> 1 2 3 4 5 6 7 8 9 10 -> 5(2) -> 2
// 25 -> 1..5..10..15..20..25 -> 5(5) + 25(1) -> although in 25 we have two 5s, one of them is already counted in count of 5s
// so every time we count how many 5,25,125... are their less than num, and add them together
int counter = 0;
while (n > 0) {
counter += n / 5;
n /= 5;
}
return counter;
}
}

[1ST TRY]
先找有多少个5
然后找有多少个25
然后找有多少个625
bug是temp一开始overflow了

89.52 %
class Solution {
public int trailingZeroes(int n) {
long temp = 5;
int result = 0;
while (temp <= n) {
result += n / temp;
temp *= 5;
}
return result;
}
}

638. Shopping Offers

Version #1 DFS

69.12 %
class Solution {
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int curr = 0;
int N = price.size();
for (int i = 0; i < N; i++) {
curr += needs.get(i) * price.get(i);
}
// try if we can use any of the special offeres
for (List<Integer> offer : special) {
int i = 0;
List<Integer> next = new ArrayList<>();
for (i = 0; i < N; i++) {
if (needs.get(i) < offer.get(i)) { // we can't apply this offer, otherwise exceed #item
break;
}
next.add(needs.get(i) - offer.get(i));
}
if (i == N) { // only try this offer if it is valid for current state
curr = Math.min(curr, offer.get(i) + shoppingOffers(price, special, next));
}
}
return curr;
}
}

Saturday, December 22, 2018

712. Minimum ASCII Delete Sum for Two Strings

Version #2 DP Space O(N)
55.15 %
class Solution {
public int minimumDeleteSum(String s1, String s2) {
// dp[i][j] min to match s1[0,i) s2[0,j)
int[] dp = new int[s2.length() + 1];
int prev = 0;
int curr = 0;
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 && j == 0) {
dp[j] = 0;
} else if (i == 0) { // 1st row
dp[j] = dp[j - 1] + (int) s2.charAt(j - 1);
} else if (j == 0) { // 1st column
curr = dp[j];
dp[j] += (int) s1.charAt(i - 1); // accumulate last row's 1st column
} else {
curr = dp[j];
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[j] = prev;
} else {
dp[j] = Math.min(dp[j] + (int) s1.charAt(i - 1),
dp[j - 1] + (int) s2.charAt(j - 1));
}
}
prev = curr;
}
}
return dp[s2.length()];
}
}

Version #1 DP Space O(MN)

64.38 %
class Solution {
public int minimumDeleteSum(String s1, String s2) {
// dp[i][j] min to match s1[0,i) s2[0,j)
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 && j == 0) {
dp[i][j] = 0;
} else if (i == 0) {
dp[i][j] = dp[i][j - 1] + (int) s2.charAt(j - 1);
} else if (j == 0) {
dp[i][j] = dp[i - 1][j] + (int) s1.charAt(i - 1);
} else {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j] + (int) s1.charAt(i - 1),
dp[i][j - 1] + (int) s2.charAt(j - 1));
}
}
}
}
return dp[s1.length()][s2.length()];
}
}

Thursday, December 20, 2018

59. Spiral Matrix II

二刷
An edge case is when left == right

26.58 %
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int counter = 1;
// [1, 2]
// [4, 3]
for (int offset = 0; offset < Math.ceil(n / 2.0); offset++) {
int left = offset;
int right = n - 1 - offset;
int top = offset;
int bottom = n - 1 - offset;
// 1st row, left to right
if (left == right) {
matrix[top][left] = counter++;
}
for (int i = left; i < right; i++) {
matrix[top][i] = counter++;
}
for (int i = top; i < bottom; i++) {
matrix[i][right] = counter++;
}
for (int i = right; i > left; i--) {
matrix[bottom][i] = counter++;
}
for (int i = bottom; i > top; i--) {
matrix[i][left] = counter++;
}
}
return matrix;
}
}

一刷
Can be optimized! [TODO]

100.00 %

class Solution {
public int[][] generateMatrix(int n) {
if (n <= 0) return new int[0][0];
int[][] result = new int[n][n];
int counter = 0;
int left = 0;
int right = n - 1;
int top = 0;
int bottom = n - 1;
while (left <= right && top <= bottom) {
int x = left;
int y = top;
while (x <= right) {
counter++;
result[y][x] = counter;
// System.out.println(y + " " + x + " " + counter);
x++;
}
x = right;
y = top + 1;
while (y <= bottom) {
counter++;
result[y][x] = counter;
// System.out.println(y + " " + x + " " + counter);
y++;
}
y = bottom;
x = right - 1;
if (left != right && top != bottom) {
while (x >= left) {
counter++;
result[y][x] = counter;
// System.out.println(y + " " + x + " " + counter);
x--;
}
x = left;
y = bottom - 1;
while (y > top) {
counter++;
result[y][x] = counter;
// System.out.println(y + " " + x + " " + counter);
y--;
}
}
left++;
right--;
top++;
bottom--;
}
return result;

}
}

54. Spiral Matrix

Version #2 Two Pointers[TODO]
Two Pointers on [rowStart, rowEnd] [colStart, colEnd]

Version #1 Recursion
Using an index to mark the layer
Even it is not a square matrix, we can still use [index, index] to mark the left top boundary

100.00 %
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return result;
helper(matrix, 0, matrix.length, matrix[0].length, result);
return result;
}

private void helper(int[][] matrix, int index, int rows, int cols, List<Integer> result) {

if (rows <= 0 || cols <= 0) return;
// System.out.println(index);
int y = index;
int x = index;
y = index;
for (x = index; x < index + cols; x++) {
result.add(matrix[y][x]);
}
x--;
for (y = y + 1; y < index + rows; y++) {
result.add(matrix[y][x]);
}
if (rows > 1 && cols > 1) {
y--;
for (x = x - 1; x >= index && y > index; x--) {
result.add(matrix[y][x]);
}
x++;
for (y = y - 1; y > index; y--) {
result.add(matrix[y][x]);
}
}
helper(matrix, index + 1, rows - 2, cols - 2, result);
}
}