IrisJavaDiary: January 2019

Thursday, January 31, 2019

248. Strobogrammatic Number III

21.52 %
class Solution {
public int strobogrammaticInRange(String low, String high) {
// 1 1
// 6 9
// 8 8
// 9 6
// 0 0
int start = low.length(), end = high.length();
List<String> rawResult = new ArrayList<>();
for (int i = start; i <= end; i++) {
rawResult.addAll(helper(i));
List<String> curr = helper(i);
}
int count = 0;
for (String str : rawResult) {
if ((str.length() > 1 && str.charAt(0) == '0')
|| (str.length() == low.length() && str.compareTo(low) < 0)
|| (str.length() == high.length() && str.compareTo(high) > 0)) continue;
count++;
}
return count;
}

private List<String> helper(int len) {
if (len == 0) return Arrays.asList(new String[]{""});
if (len == 1) return Arrays.asList(new String[]{"0", "1", "8"});

List<String> result = new ArrayList<>();
List<String> center = helper(len - 2);
for (String cen : center) {
result.add("1" + cen + "1");
result.add("6" + cen + "9");
result.add("8" + cen + "8");
result.add("9" + cen + "6");
result.add("0" + cen + "0");
}
return result;
}
}

150. Evaluate Reverse Polish Notation

Version #1 Stack

15.27 %
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String curr = tokens[i];
if (curr.equals("+") || curr.equals("-") || curr.equals("*") || curr.equals("/")) {
int operand2 = stack.pop();
int operand1 = stack.pop();
int res = 0;
switch (curr) {
case "+":
res = operand1 + operand2;
break;
case "-":
res = operand1 - operand2;
break;
case "*":
res = operand1 * operand2;
break;
case "/":
res = operand1 / operand2;
}
stack.push(res);
} else {
stack.push(Integer.valueOf(curr));
}
}
return stack.pop();
}
}

Wednesday, January 30, 2019

115. Distinct Subsequences

Version #1 DP
1st row must be 1s because we are using s to match empty string
and an empty string is the subsequence of any string

10.00 %
class Solution {
public int numDistinct(String s, String t) {
// dp[i][j] -> number of ways to match s.substring[0, i) with t.substring[0, j)
// if (s.charAt(i - 1) == t.charAt(j - 1))
// dp[i][j] += for all k, s.charAt(k - 1) == t.charAt(j - 2)
// if j == 1, dp[i][j] = 1
int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i <= s.length(); i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= t.length(); j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
// use or not use
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j]; // cannot use
}
}
}
return dp[s.length()][t.length()];
}
}

918. Maximum Sum Circular Subarray

Bug
One** corner case** to pay attention:
If all number are negative,
return the maximum one,
(which equals to the max subarray sum)

If the maximum sum is negative, means all numbers are negative
In this case, total sum is the minimum one -> total sum - min sum = 0, which is not a valid subarray
So when maxSum < 0, return maxSum

21.88 %
class Solution {
public int maxSubarraySumCircular(int[] A) {
// max subarray sum, min suarray sum
// result = Math.max(max, totalSum - min)
if (A == null || A.length == 0) return 0;
int prevMin = A[0], prevMax = A[0]; // min/max subarray sum end with i-1
int sum = A[0], max = A[0], min = A[0];
for (int i = 1; i < A.length; i++) {
sum += A[i];
int currMin = Math.min(prevMin, 0) + A[i];
int currMax = Math.max(prevMax, 0) + A[i];
max = Math.max(max, currMax);
min = Math.min(min, currMin);
prevMin = currMin;
prevMax = currMax;
}
return max > 0 ? Math.max(max, sum - min) : max;
}
}

152. Maximum Product Subarray

Version #1 Optimized DP
是一个dp题，对于乘法来说情况比较特殊，因为有负数
如果一个绝对值非常大的负数再乘一个负数，负负得正，有产生最大值的可能
所以要同时keep track of dpMin 以及dpMax
更新dp的时候要考虑也可是nums[i] 单独成为最大或者最小

70.82 %
class Solution {
public int maxProduct(int[] nums) {
// pos[i] -> maxProduct ends with current nums[i]
// neg[i] -> minProduct ends with current nums[i]
// pos[i] = Math.max(nums[i], Math.max(post[i - 1] * nums[i], neg[i - 1] * nums[i]));
// neg[i] = Math.min(nums[i], Math.min(post[i - 1] * nums[i], neg[i - 1] * nums[i]));
int result = Integer.MIN_VALUE;
int pos = 1, neg = 1;
for (int i = 0; i < nums.length; i++) {
int currPos = Math.max(nums[i], Math.max(pos * nums[i], neg * nums[i]));
int currNeg = Math.min(nums[i], Math.min(pos * nums[i], neg * nums[i]));
pos = currPos;
neg = currNeg;
result = Math.max(pos, result);
}
return result;
}
}

Tuesday, January 29, 2019

780. Reaching Points

Follow up:
What if any x, y can be negative
对source的正负号进行分类讨论，如果同号，则可以转化成原题
因为如果source的xy value同负，那么target也只能是负的

所以最后只需要讨论xy异号的情况，易知由于xy异号所以abs(x + y) will always become closer to zero
所以我们尝试枚举出所有这样的情况直到xy同号，然后问题退化成原问题

95.45 %
class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
// all sx,sy,tx,ty are larger than zero
// if (tx > ty) -> it can only be generated from (tx - ty, ty)
// we can keep subtract ty from tx until tx < ty
// new tx = tx - kty = tx % ty
while (tx > sx && ty > sy) {
if (tx > ty) {
tx = tx % ty;
} else {
ty = ty % tx;
}
}
return tx == sx && (ty - sy) % tx == 0 ||
ty == sy && (tx - sx) % ty == 0;
}
}

Sunday, January 27, 2019

337. House Robber III

三刷 07/2022

Version #2 Bottom up DFS

Time O(N)

Space O(H) - height of the tree, worst O(N)

Runtime: 1 ms, faster than 92.27% of Java online submissions for House Robber III.

Memory Usage: 44.8 MB, less than 29.44% of Java online submissions for House Robber III.

class Solution {

public int rob(TreeNode root) {

int[] result = robHelper(root);

return Math.max(result[0], result[1]);

}

private int[] robHelper(TreeNode node) {

int[] result = new int[2];

if (node == null) {

return result;

}

int[] left = robHelper(node.left);

int[] right = robHelper(node.right);

result[0] = node.val + left[1] + right[1];

result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

return result;

}

二刷 06/2022

Version #2 Bottom up DFS

我们return一个int[]表示rob current node/ not rob current node两个结果

每个node保证只visited一次

Time O(N)

Space - depth of the stack, O(N) worst, O(logN) best

Runtime: 0 ms, faster than 100.00% of Java online submissions for House Robber III.

Memory Usage: 41.5 MB, less than 98.09% of Java online submissions for House Robber III.

class Solution {

public int rob(TreeNode root) {

// For each node, return two values - int[0] max if rob the house, int[1] max of the children no matter rob or not rob

int[] res = robHelper(root);

return Math.max(res[0], res[1]);

}

private int[] robHelper(TreeNode node) {

if (node == null) {

return new int[]{0, 0};

}

// leaf

if (node.left == null && node.right == null) {

return new int[]{node.val, 0};

}

int[] left = robHelper(node.left);

int[] right = robHelper(node.right);

// if we rob the house, then we cannot rob it's children

int curr = node.val + left[1] + right[1];

// if not rob, we are free to choose rob the children or not

int children = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

return new int[]{curr, children};

}

一刷
Version #1 DFS

67.32 %
class Solution {
public int rob(TreeNode root) {
Map<TreeNode, Integer> map = new HashMap<>();
return dfs(root, map);
}

private int dfs(TreeNode node, Map<TreeNode, Integer> map) {
// max amount of money we can get if we enter through this node
if (node == null) {
return 0;
}
if (map.containsKey(node)) return map.get(node);

// if we rob this node, then we can't rob any of its child node
int curr = node.val;
if (node.left != null) {
curr += dfs(node.left.left, map) + dfs(node.left.right, map);
}
if (node.right != null) {
curr += dfs(node.right.left, map) + dfs(node.right.right, map);
}

curr = Math.max(curr, dfs(node.left, map) + dfs(node.right, map));
map.put(node, curr);
return curr;
}
}

983. Minimum Cost For Tickets

二刷 07/2022

Version #1 DP

感觉这题有点难，想了很久想不出来

看了一刷的答案感觉一刷写的更好用了一个pointer for days

一开始写了bug就是只有当i >= 7的时候才检查min，这种情况在7日票价低于1日票价的时候是有错误的

Time O(D) - D = 365

Space O(D) - D = 365

Runtime: 6 ms, faster than 17.80% of Java online submissions for Minimum Cost For Tickets.

Memory Usage: 42.4 MB, less than 33.67% of Java online submissions for Minimum Cost For Tickets.

class Solution {

public int mincostTickets(int[] days, int[] costs) {

Set<Integer> daySet = new HashSet<>();

for (int d : days) {

daySet.add(d);

}

// The min cost to cover travel until day i

int[] dp = new int[366];

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

if (!daySet.contains(i)) {

dp[i] = dp[i - 1];

} else {

dp[i] = dp[i - 1] + costs[0];

dp[i] = Math.min(dp[i], (i >= 7 ? dp[i - 7] : 0) + costs[1]);

dp[i] = Math.min(dp[i], (i >= 30 ? dp[i - 30] : 0) + costs[2]);

}

return dp[365];

}

一刷

Version #1 DP

100.00 %
class Solution {
public int mincostTickets(int[] days, int[] costs) {
// dp[i] - minimum cost to travel to day i
int[] dp = new int[366];
int daysIndex = 0;
// Easy to know that dp[i] >= dp[j] when i > j
for (int i = 1; i <= 365; i++) {
if (daysIndex >= days.length || days[daysIndex] != i) {
dp[i] = dp[i - 1];
} else {
daysIndex++;
dp[i] = Math.min(dp[Math.max(0, i - 1)] + costs[0],
Math.min(dp[Math.max(0, i - 7)] + costs[1],
dp[Math.max(0, i - 30)] + costs[2]));
}
}
return dp[365];
}
}

982. Triples with Bitwise AND Equal To Zero

Version #1 DP

37.50 %
class Solution {
public int countTriplets(int[] A) {
int N = 1 << 16;
int[] dp = new int[N];
for (int a : A) {
dp[a] += 1;
}
for (int i = 0; i < 2; i++) {
int[] temp = new int[N];
for (int k = 0; k < N; k++) {
for (int a : A) {
temp[k & a] += dp[k];
}
}
dp = temp;
}
return dp[0];
}
}

Saturday, January 26, 2019

556. Next Greater Element III

96.55 %
class Solution {
public int nextGreaterElement(int n) {
char[] chars = String.valueOf(n).toCharArray();
int i = 0;
for (i = chars.length - 1; i > 0; i--) {
if (chars[i] > chars[i - 1]) break;
}
int nextLargerDigit = i;
if (i != 0) {
for (int j = chars.length - 1; j > i; j--) {
if (chars[j] > chars[i - 1] && chars[j] < chars[nextLargerDigit]) {
nextLargerDigit = j;
}
}
char temp = chars[i - 1];
chars[i - 1] = chars[nextLargerDigit];
chars[nextLargerDigit] = temp;
Arrays.sort(chars, i, chars.length);
} else {
return -1;
}
long result = Long.valueOf(new String(chars));
return result > Integer.MAX_VALUE ? -1 : (int) result;
}
}

Tuesday, January 22, 2019

249. Group Shifted Strings

3.04 %
public List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strings) {
map.computeIfAbsent(normalize(str), list -> new ArrayList<>()).add(str);
}
List<List<String>> result = new ArrayList<>();
for (List<String> list : map.values()) {
result.add(list);
}
return result;
}

private String normalize(String s) {
int offset = (int)(s.charAt(0) - 'a');
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
sb.append((char) ('a' + ((s.charAt(i) - offset + 26) % 26)));
}
// System.out.println(sb.toString());
return sb.toString();
}

Monday, January 21, 2019

935. Knight Dialer

Version #1 DP

71.11 %
class Solution {
public int knightDialer(int N) {
int[][] map = new int[][]{{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
int[] prev = new int[10];
int mod = (int)(1e9 + 7);
Arrays.fill(prev, 1);
for (int i = 2; i <= N; i++) {
int[] curr = new int[10];
for (int x = 0; x <= 9; x++) {
for (int last : map[x]) {
curr[x] = (curr[x] + prev[last]) % mod;
}
}
prev = curr;
}
int sum = 0;
for (int i = 0; i <= 9; i++) {
sum = (sum + prev[i]) % mod;
}
return sum;
}
}

421. Maximum XOR of Two Numbers in an Array

Version #1 PrefixTrie + DFS

We are passing two nodes into dfs simultaneously, if we can choose branch of different value, we choose. Otherwise choose the same value

95.05 %
class Solution {
class TrieNode {
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
}
}
public int findMaximumXOR(int[] nums) {
TrieNode root = new TrieNode();
for (int num : nums) {
insert(root, num);
}
return dfs(root.children[0], root.children[1] == null ? root.children[0] : root.children[1], 0);
}

private int dfs(TrieNode left, TrieNode right, int diff) {
TrieNode left0 = left.children[0], left1 = left.children[1];
TrieNode right0 = right.children[0], right1 = right.children[1];

if (left0 == null && left1 == null) {
return diff;
} else if (left0 != null && left1 != null && right0 != null && right1 != null) {
return Math.max(dfs(left0, right1, (diff << 1) + 1), dfs(left1, right0, (diff << 1) + 1));
} else if (left0 != null && right1 != null) {
return dfs(left0, right1, (diff << 1) + 1);
} else if (left1 != null && right0 != null) {
return dfs(left1, right0, (diff << 1) + 1);
} else if (left0 != null && right0 != null){
return dfs(left0, right0, (diff << 1));
} else if (left1 != null && right1 != null) {
return dfs(left1, right1, (diff << 1));
}
return 0;
}

private void insert(TrieNode root, int num) {
TrieNode curr = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[bit] == null) {
curr.children[bit] = new TrieNode();
}
curr = curr.children[bit];
}
}
}

Saturday, January 19, 2019

448. Find All Numbers Disappeared in an Array

69.09 %
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
// If we see this number, we mark the number that at this index as negative
for (int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
result.add(i + 1);
}
}
return result;
}
}

463. Island Perimeter

86.10 %
class Solution {
public int islandPerimeter(int[][] grid) {
// try to add 4 edges to each node
// if there are to node connect to each other, then 2 edges should be subtracted
int result = 0;
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (grid[y][x] == 1) {
result += 4;
if (y + 1 < grid.length && grid[y + 1][x] == 1) {
result -= 2;
}
if (x + 1 < grid[0].length && grid[y][x + 1] == 1) {
result -= 2;
}
}
}
}
return result;
}
}

657. Robot Return to Origin

91.43 %
class Solution {
public boolean judgeCircle(String moves) {
int y = 0;
int x = 0;
for (int i = 0; i < moves.length(); i++) {
char c = moves.charAt(i);
if (c == 'U') {
y--;
} else if (c == 'D') {
y++;
} else if (c == 'L') {
x--;
} else {
x++;
}
}
return x == 0 && y == 0;
}
}

972. Equal Rational Numbers

68.52 %
class Solution {
public boolean isRationalEqual(String S, String T) {
return Double.valueOf(normalize(S)).compareTo(
Double.valueOf(normalize(T))) == 0;
}

private String normalize(String s) {
int index = s.indexOf("(");
String result = s;
if (index > 0) {
result = s.substring(0, index);
for (int i = 0; i < 20; i++) {
result += s.substring(index + 1, s.length() - 1);
}
}
return result;
}
}

958. Check Completeness of a Binary Tree

Version #2 BFS[TODO]

Version #1 DFS

98.36
class Solution {
int count;
public boolean isCompleteTree(TreeNode root) {
count = getCount(root);
return validate(root, 1);
}

private boolean validate(TreeNode node, int id) {
if (node == null) return true;
if (id > count) return false;
return validate(node.left, id * 2) && validate(node.right, id * 2 + 1);
}

private int getCount(TreeNode node) {
if (node == null) return 0;
return 1 + getCount(node.left) + getCount(node.right);
}
}

943. Find the Shortest Superstring

Version #1 DP

非常难的一道题
bug出在了当A[i] 为第一个word的时候，如果不设parent[1 << i][i] = i 而default为0的话就会陷入死循环
其余的思路其实和knapsack有点类似
关键在于状态压缩
把两个word之间的连接状态，压缩成一个已知的set，append一个word的状态

95.59 %
class Solution {
public String shortestSuperstring(String[] A) {
// int state -> which words index have been visited
// dp[state][i] -> minimum superstring length to cover state, and i is the last word
// having dp[state][j] -> try to expand to word that have not been visited before
// dp[state][i] = Math.min(dp[state][i], dp[state][j] + cost[j][i])
// store the last index j for dp[state][i] -> parent[state][i] = j
// cost[i][j] -> the length increased to append A[j] after A[i], not including length of A[i]
int len = A.length;
int[][] cost = new int[len][len];
int endState = 0; // if state reached this state, we know that all words have been used
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) {
cost[i][j] = getCost(A[i], A[j]);
cost[j][i] = getCost(A[j], A[i]);
}
endState += 1 << i;
}
int totalCost = Integer.MAX_VALUE;
int lastIndex = 0;
int[][] dp = new int[endState + 1][len];
int[][] parent = new int[endState + 1][len]; // parent index for min cost
for (int i = 0; i < len; i++) {
dp[1 << i][i] = A[i].length(); // A[i] is the first word, cost is it self
parent[1 << i][i] = i;
}
for (int s = 0; s <= endState; s++) {
for (int i = 0; i < len; i++) {
// check if this state has visited A[i] or not
if ((s & (1 << i)) == 0 || s == (1 << i)) continue;
dp[s][i] = Integer.MAX_VALUE;
int prevState = s & (~(1 << i)); // reset bit i
for (int j = 0; j < len; j++) {
if ((prevState & (1 << j)) == 0) continue;
// All possible prev states
if (dp[prevState][j] + cost[j][i] < dp[s][i]) {
dp[s][i] = dp[prevState][j] + cost[j][i];
parent[s][i] = j;
}
}
if (s == endState && dp[s][i] < totalCost) {
totalCost = dp[s][i];
lastIndex = i;
}
}
}
StringBuilder sb = new StringBuilder();
while (endState != 0) {
int curr = lastIndex;
lastIndex = parent[endState][curr];
endState = endState & (~(1 << curr)); // reset lastIndex
String temp = A[curr].substring(A[curr].length() - cost[lastIndex][curr]);
sb.insert(0, temp);
}
sb.insert(0, A[lastIndex]);
return sb.toString();
}

private int getCost(String first, String second) {
// abcd cdef
int overlap = 0;
for (int i = 0; i < first.length(); i++) {
if (second.startsWith(first.substring(i))) {
overlap = first.length() - i;
break;
}
}
return second.length() - overlap;
}
}

347. Top K Frequent Elements

二刷 06/2022

Version #3 Quick Select

和973用了不同的partition方法

这里没有把pivot swap到它正确的位置

返回的index是left - 1, 表示从(0-index) >= partition, (index+1, len-1) <= partition

如果index<k-1表示从0到index不足k个数，这时候要start=index+1，如果不+1会infinite loop

表示从0到index有大于等于k个数，这时候要end=index

Time O(N)

Space O(#distinct number)

Runtime: 16 ms, faster than 58.05% of Java online submissions for Top K Frequent Elements.

Memory Usage: 50.2 MB, less than 59.80% of Java online submissions for Top K Frequent Elements.

class Solution {

public int[] topKFrequent(int[] nums, int k) {

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

return new int[0];

}

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

for (int num : nums) {

count.put(num, count.getOrDefault(num, 0) + 1);

}

int[] unique = new int[count.size()];

int i = 0;

for (int num : count.keySet()) {

unique[i++] = num;

}

int index = unique.length;

int start = 0, end = unique.length - 1;

while (index != k - 1) {

index = partition(unique, start, end, count);

// System.out.printf("start=%d,end=%d,index=%d\n", start, end, index);

if (index < k - 1) {

start = index + 1;

} else {

end = index;

}

int[] result = new int[k];

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

result[j] = unique[j];

}

return result;

}

private int partition(int[] nums, int start, int end, Map<Integer, Integer> count) {

int pivot = nums[start + (end - start) / 2];

int pivotCnt = count.get(pivot);

int left = start, right = end;

while (left <= right) {

while (left <= right && count.get(nums[left]) > pivotCnt) {

left++;

}

while (left <= right && count.get(nums[right]) < pivotCnt) {

right--;

}

if (left <= right) {

swap(nums, left, right);

left++;

right--;

}

return left - 1;

}

private void swap(int[] nums, int a, int b) {

int temp = nums[a];

nums[a] = nums[b];

nums[b] = temp;

}

Version #2 Bucket Sort
有一个bug
因为count 是从1开始，所以生成的bucket size 需要是length + 1

Time O(n)
95.43 %
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
// key-num, value-count
for (int num : nums) {
map.put(num, 1 + map.getOrDefault(num, 0));
}
// the frequency can't exceed total number of nums
List<Integer>[] bucket = new List[nums.length + 1];
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int count = entry.getValue();
if (bucket[count] == null) {
bucket[count] = new ArrayList<>();
}
bucket[count].add(entry.getKey());
}
List<Integer> result = new ArrayList<>();
int i = nums.length;
while (i >= 0 && result.size() < k) {
if (bucket[i] != null) {
result.addAll(bucket[i]);
}
i--;
}
return result;
}
}

Version #1 HashMap + minHeap
Time O(nlogk)
Space O(count of unique values)

51.98 %
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// Count frequency -> Map<num, count> -> O(n) for all nums
// get most k count
// retrieve from map
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
int count = 1 + map.getOrDefault(num, 0);
map.put(num, count);
}
// O(nlogk)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int count : map.values()) {
if (minHeap.size() < k) {
minHeap.offer(count);
} else if (count > minHeap.peek()) {
minHeap.poll();
minHeap.offer(count);
}
}
Set<Integer> countK = new HashSet<>(minHeap);
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (countK.contains(entry.getValue())) {
result.add(entry.getKey());
}
}
return result;
}
}

Friday, January 18, 2019

760. Find Anagram Mappings

92.70 %
class Solution {
public int[] anagramMappings(int[] A, int[] B) {
// key-num, value-index
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < B.length; i++) {
map.putIfAbsent(B[i], i);
}
int[] result = new int[A.length];
for (int i = 0; i < A.length; i++) {
result[i] = map.get(A[i]);
}
return result;
}
}

832. Flipping an Image

97.14 %
class Solution {
public int[][] flipAndInvertImage(int[][] A) {
if (A == null || A.length == 0 || A[0] == null || A[0].length == 0) return A;
int cols = A[0].length;
for (int y = 0; y < A.length; y++) {
int left = 0;
int right = cols - 1;
while (left <= right) {
if (left == right) {
A[y][left] ^= 1;
} else {
int temp = A[y][left] ^ 1;
A[y][left] = A[y][right] ^ 1;
A[y][right] = temp;
}
left++;
right--;
}
}
return A;
}
}

Wednesday, January 16, 2019

929. Unique Email Addresses

need to escape special chars in .split()
no need to escape in .replace()

59.26 %
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> set = new HashSet<>();
for (String email : emails) {
String[] parts = email.split("@");
String local = parts[0].split("\\+", 2)[0];
set.add(local.replace(".", "") + "@" + parts[1]);
}
return set.size();
}
}

Monday, January 14, 2019

743. Network Delay Time

Version #1 Dijastra

1 BUG-> it is possible that a node be added to minHeap more than once
Since we are marking visited when we are polling it -> it is possible that one node is not polled yet and it is added one more time with an larger distance
So we have to check visited in to place
-> right after we poll out one node
-> before we add a node to minHeap

25.65 %
class Solution {
/*
times[i] = (u, v, w), where u is the source node, v is the target node,
and w is the time it takes for a signal to travel from source to target.
*/
public int networkDelayTime(int[][] times, int N, int K) {
// source target weight
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
for (int[] time : times) {
// time[0]-source, time[1]-target, time[2]-weight
graph.computeIfAbsent(time[0], weightMap -> new HashMap<>()).put(time[1], time[2]);
}
int max = Integer.MIN_VALUE;
boolean[] visited = new boolean[N + 1]; // since nodes are 1 indexed
// a[0]-current node, a[1]-weight from source
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparing(a -> a[1]));
minHeap.offer(new int[]{K, 0});
while (!minHeap.isEmpty()) {
int[] curr = minHeap.poll();
int index = curr[0], distance = curr[1];
if (visited[index]) continue;
// System.out.println(index + " " + distance);
max = Math.max(max, distance);
visited[index] = true;
Map<Integer, Integer> neighbors = graph.get(index);
if (neighbors != null) {
for (int neighbor : neighbors.keySet()) {
if (!visited[neighbor]) {
minHeap.offer(new int[]{neighbor, distance + neighbors.get(neighbor)});
}
}
}
}
for (int i = 1; i < visited.length; i++) {
if (!visited[i]) return -1;
}
return max;
}
}

694. Number of Distinct Islands

二刷 05/2022

Version #2 BFS

Hash each island into List<List<Integer>>

Each position is normalize by calculating the offset from the left top grid of the island

caveat: 这里如果用int[]是不work的，可能int array的hash function是由地址代替的

Runtime: 21 ms, faster than 30.36% of Java online submissions for Number of Distinct Islands.

Memory Usage: 54.5 MB, less than 20.22% of Java online submissions for Number of Distinct Islands.

class Solution {

public int numDistinctIslands(int[][] grid) {

if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {

return 0;

}

// Find all points of an island and store them in List<int[]>

// Since we iterate from smaller to larger indexes, the fisrt grid in the list is always the top left grid

// Normalize an island by calculate the relative position of every point with the top left point

// Store the island grid list in a hash set

Set<List<List<Integer>>> islands = new HashSet<>();

int rows = grid.length, cols = grid[0].length;

boolean[][] visited = new boolean[rows][cols];

for (int y = 0; y < rows; y++) {

for (int x = 0; x < cols; x++) {

if (!visited[y][x] && grid[y][x] == 1) {

// Expand an island from starting point (x, y) and returns all of its grids

List<List<Integer>> island = findIsland(grid, y, x, visited);

islands.add(island);

}

return islands.size();

}

private int[] dx = new int[]{1, 0, -1, 0};

private int[] dy = new int[]{0, -1, 0, 1};

List<List<Integer>> findIsland(int[][] grid, int y, int x, boolean[][] visited) {

List<List<Integer>> island = new ArrayList<>();

Queue<List<Integer>> que = new ArrayDeque<>();

que.offer(Arrays.asList(y, x));

visited[y][x] = true;

while (!que.isEmpty()) {

List<Integer> curr = que.poll();

island.add(Arrays.asList(curr.get(0) - y, curr.get(1) - x));

// iterate all 4 directions

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

int ny = curr.get(0) + dy[i];

int nx = curr.get(1) + dx[i];

// out of the boundary

if (ny < 0 || ny >= grid.length || nx < 0 || nx >= grid[0].length) {

continue;

}

if (!visited[ny][nx] && grid[ny][nx] == 1) {

visited[ny][nx] = true;

que.offer(Arrays.asList(ny, nx));

}

return island;

}

Test Cases:
[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
[[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]

一刷
Version #1 DFS
Hash each island by grids offset from its left most & top grid

58.50 %
class Solution {
public int numDistinctIslands(int[][] grid) {
// when we see the left,top grid of an island, try to expand it
// keep track of each grid by its relative position, seperated by " "
// use a string to encode the shape of each island
Set<String> set = new HashSet<>();
StringBuilder sb = new StringBuilder();
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (grid[y][x] == 1) {
dfs(grid, y, x, 0, 0, sb);
set.add(sb.toString());
sb.setLength(0);
}
}
}
return set.size();
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void dfs(int[][] grid, int y, int x, int offY, int offX, StringBuilder sb) {
sb.append(offY).append(" ").append(offX).append(" ");
grid[y][x] = 0;
for (int i = 0; i < 4; i++) {
int nextY = y + dy[i];
int nextX = x + dx[i];
if (nextX >= 0 && nextX < grid[0].length && nextY >= 0 && nextY < grid.length
&& grid[nextY][nextX] == 1) {
dfs(grid, nextY, nextX, offY + dy[i], offX + dx[i], sb);
}
}
}
}

695. Max Area of Island

三刷 07/2022

Version #3 Union Find

Time O(MN) - we have 4 MN union operations, union with size rank and path compression will result in amortized O(1) time

Space O(MN)

Runtime: 6 ms, faster than 25.46% of Java online submissions for Max Area of Island.

Memory Usage: 48 MB, less than 21.47% of Java online submissions for Max Area of Island.

class Solution {

private static int ISLAND = 1;

class UnionFind {

private int[] size;

private int[] id;

private int rows;

private int cols;

int maxSize = 0;

public UnionFind(int[][] grid) {

rows = grid.length;

cols = grid[0].length;

size = new int[rows * cols];

id = new int[rows * cols];

for (int y = 0; y < rows; y++) {

for (int x = 0; x < cols; x++) {

int index = getIndex(cols, y, x);

if (grid[y][x] == 1) {

maxSize = 1;

size[index] = 1;

id[index] = index;

}

public int root(int i) {

while (id[i] != i) {

id[i] = id[id[i]];

i = id[i];

}

return i;

}

public void union(int p, int q) {

int rootP = root(p);

int rootQ = root(q);

if (rootP == rootQ) {

return;

}

if (size[rootP] < size[rootQ]) {

id[rootP] = rootQ;

size[rootQ] += size[rootP];

maxSize = Math.max(maxSize, size[rootQ]);

} else {

id[rootQ] = rootP;

size[rootP] += size[rootQ];

maxSize = Math.max(maxSize, size[rootP]);

}

public int getMaxSize() {

return maxSize;

}

public int getIndex(int cols, int y, int x) {

return y * cols + x;

}

private int[] dx = new int[]{1, 0, -1, 0};

private int[] dy = new int[]{0, -1, 0, 1};

public int maxAreaOfIsland(int[][] grid) {

int rows = grid.length;

int cols = grid[0].length;

UnionFind uf = new UnionFind(grid);

for (int y = 0; y < rows; y++) {

for (int x = 0; x < cols; x++) {

if (grid[y][x] != ISLAND) {

continue;

}

int index = getIndex(cols, y, x);

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

int ny = y + dy[i];

int nx = x + dx[i];

if (ny < 0 || nx < 0 || ny >= rows || nx >= cols || grid[ny][nx] != ISLAND) {

continue;

}

uf.union(index, getIndex(cols, ny, nx));

}

return uf.getMaxSize();

}

二刷 06/2022

We could also use stack based DFS to avoid using recursion

Version #2 DFS without changing the original matrix

Time O(MN)

Space O(MN)

Runtime: 4 ms, faster than 52.28% of Java online submissions for Max Area of Island.

Memory Usage: 47.4 MB, less than 48.23% of Java online submissions for Max Area of Island.

class Solution {

public int maxAreaOfIsland(int[][] grid) {

int rows = grid.length;

int cols = grid[0].length;

boolean[][] visited = new boolean[rows][cols];

int max = 0;

for (int y = 0; y < rows; y++) {

for (int x = 0; x < cols; x++) {

if (grid[y][x] == 1 && !visited[y][x]) {

visited[y][x] = true;

max = Math.max(max, dfs(grid, visited, y, x));

}

return max;

}

private static int[] dx = new int[]{1, 0, -1, 0};

private static int[] dy = new int[]{0, -1, 0, 1};

// Return how many 1s are in current island

private int dfs(int[][] grid, boolean[][] visited, int y, int x) {

int count = 1;

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

int nx = x + dx[i];

int ny = y + dy[i];

if (nx < 0 || ny < 0 || nx >= grid[0].length || ny >= grid.length || visited[ny][nx] || grid[ny][nx] != 1) {

continue;

}

visited[ny][nx] = true;

count += dfs(grid, visited, ny, nx);

}

return count;

}

一刷
Version #1 DFS

43.59 %
class Solution {
public int maxAreaOfIsland(int[][] grid) {
// iterate through the grid, if we see any 1, we try to expand this island
// set any visited grid to 0
int max = 0;
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (grid[y][x] == 1) {
max = Math.max(max, dfs(grid, x, y));
}
}
}
return max;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private int dfs(int[][] grid, int x, int y) {
// return the size of current island
int size = 1;
grid[y][x] = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < grid[0].length && ny >= 0 && ny < grid.length
&& grid[ny][nx] == 1) {
size += dfs(grid, nx, ny);
}
}
return size;
}
}

725. Split Linked List in Parts

Version #1 Straight-forward

98.82 %
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
//Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
// length = 10, bucketLength = 10/3=3, residual = 10%3 = 1
ListNode[] result = new ListNode[k];
ListNode curr = root;
int length = 0;
while (curr != null) {
length++;
curr = curr.next;
}
int bucketLength = length / k;
int residual = length % k;
curr = root;
for (int i = 0; i < k && curr != null; i++) {
int len = bucketLength;
if (residual > 0) {
len++;
residual--;
}
result[i] = curr;
ListNode prev = null;
while (curr != null && len > 0) {
prev = curr;
curr = curr.next;
len--;
}
prev.next = null;
}
return result;
}
}

729. My Calendar I

二刷 08/2022

Version #1 TreeMap

一个bug，如果用floorKey(end)的话// [19,25)[25,32)[33,41)[47,50) 要加入[19,25)就会失败，因为25的floorKey是[25,32)entry，然后32又比19大

所以应该用lowerKey

注意这里没有必要合并相邻的intervals

Time O(logN)

Space O(N)

Runtime: 30 ms, faster than 75.04% of Java online submissions for My Calendar I.

Memory Usage: 54.6 MB, less than 51.82% of Java online submissions for My Calendar I.

class MyCalendar {

TreeMap<Integer, Integer> events;

public MyCalendar() {

this.events = new TreeMap<>();

}

// [19,25)[25,32)[33,41)[47,50)

public boolean book(int start, int end) {

// [start, end)

Integer prevStart = events.lowerKey(end);

if (prevStart != null && events.get(prevStart) > start) {

return false;

}

// [prevStart, prevEnd) [start, end)

events.put(start, end);

return true;

}

一刷
Version #1 TreeMap

Time O(logn) for each book() call

94.57 %
class MyCalendar {

TreeMap<Integer, Integer> treeMap;
public MyCalendar() {
// key-start, value-end
this.treeMap = new TreeMap<>();
}

public boolean book(int start, int end) {
// [start, end) [start, end)
// There should be two constraints
// 1.any event happens after current start time, should start after end time
// 2.any event happens before current start time, should end before start time
Map.Entry<Integer, Integer> prev = treeMap.floorEntry(start);
if (prev != null && prev.getValue() > start) return false;
Map.Entry<Integer, Integer> next = treeMap.ceilingEntry(start);
if (next != null && next.getKey() < end) return false;
treeMap.put(start, end);
return true;
}
}