 20200901
 20200903
 20200904
 20200905
 20200906
 20200907
 20200908
 20200909
 20200910
 20200913
 20200915
20200901
1258. Synonymous Sentences
Description
Given a list of pairs of equivalent words synonyms and a sentence text, Return all possible synonymous sentences sorted lexicographically.
Example 1:
Input:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
Output:
["I am cheerful today but was sad yesterday",
"I am cheerful today but was sorrow yesterday",
"I am happy today but was sad yesterday",
"I am happy today but was sorrow yesterday",
"I am joy today but was sad yesterday",
"I am joy today but was sorrow yesterday"]
Constraints:
0 <= synonyms.length <= 10
synonyms[i].length == 2
synonyms[i][0] != synonyms[i][1]
All words consist of at most 10 English letters only.
text is a single space separated sentence of at most 10 words.
Solution
class Solution {
public List<String> generateSentences(List<List<String>> synonyms, String text) {
Map<String, List<String>> graph = new HashMap<>();
for (List<String> pair : synonyms) {
graph.putIfAbsent(pair.get(0), new ArrayList<>());
graph.putIfAbsent(pair.get(1), new ArrayList<>());
graph.get(pair.get(0)).add(pair.get(1));
graph.get(pair.get(1)).add(pair.get(0));
}
TreeSet<String> res = new TreeSet();
Queue<String> queue = new LinkedList<>();
queue.add(text);
while (!queue.isEmpty()) {
String cur = queue.poll();
res.add(cur);
String[] words = cur.split("\\W+");
for (int i = 0; i < words.length; i++) {
String word = words[i];
if (graph.containsKey(word)) {
for (String synonym : graph.get(word)) {
words[i] = synonym;
String next = String.join(" ", words);
if (!res.contains(next)) {
queue.add(next);
}
}
}
}
}
return new ArrayList<>(res);
}
}
Faster solution
class Solution {
Map<String, Set<String>> map = new HashMap<>();
public List<String> generateSentences(List<List<String>> synonyms, String text) {
//build graph.
for (List<String> s : synonyms) {
String a = s.get(0);
String b = s.get(1);
if (!map.containsKey(a)) {
map.put(a, new HashSet<>());
}
if (!map.containsKey(b)) {
map.put(b, new HashSet<>());
}
map.get(a).add(b);
map.get(b).add(a);
}
String[] split = text.split("\\W+");
List<String> res = new ArrayList<>();
helper(res, split, 0, "");
Collections.sort(res);
return res;
}
public void helper(List<String> res, String[] split, int index, String cur) {
if (index == split.length) {
res.add(cur);
return;
}
if (map.containsKey(split[index])) {
List<String> choices = new ArrayList<>();
//find all synonyms related to s
dfs(split[index], new HashSet<>(), choices);
//try to change word at index to every possible synonyms word
for (String s : choices) {
helper(res, split, index + 1, cur + (index == split.length  1 ? s : s + " "));
}
} else {
//if the word at index has no synonyms, just go for next.
helper(res, split, index + 1, cur + (index == split.length  1 ? split[index] : split[index] + " "));
}
}
//get all synonyms related to s
public void dfs(String s, Set<String> visited, List<String> choices) {
choices.add(s);
visited.add(s);
for (String next : map.get(s)) {
if (!visited.contains(next)) {
dfs(next, visited, choices);
}
}
}
}
1166. Design File System
Description
You are asked to design a file system which provides two functions:
createPath(path, value): Creates a new path and associates a value to it if possible and returns True. Returns False if the path already exists or its parent path doesn't exist.
get(path): Returns the value associated with a path or returns 1 if the path doesn't exist.
The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.
Implement the two functions.
Please refer to the examples for clarifications.
Example 1:
Input:
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1
Example 2:
Input:
["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
Output:
[null,true,true,2,false,1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/leet", 1); // return true
fileSystem.createPath("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return 1 because this path doesn't exist.
Constraints:
The number of calls to the two functions is less than or equal to 10^4 in total.
2 <= path.length <= 100
1 <= value <= 10^9
Solution
import java.util.HashMap;
class FileSystem {
Node root;
public FileSystem() {
root = new Node();
}
public boolean createPath(String path, int value) {
String[] paths = path.split("/");
Node cursor = root;
for (int i = 1; i < paths.length  1; i++) {
String file = paths[i];
if (!cursor.next.containsKey(file)) {
return false;
}
cursor = cursor.next.get(file);
}
String file = paths[paths.length  1];
if (cursor.next.containsKey(file)) {
return false;
} else {
cursor.next.put(file, new Node(value));
return true;
}
}
public int get(String path) {
String[] paths = path.split("/");
Node cursor = root;
for (int i = 1; i < paths.length; i++) {
String file = paths[i];
if (!cursor.next.containsKey(file)) {
return 1;
}
cursor = cursor.next.get(file);
}
return cursor.value==null?1: cursor.value;
}
class Node {
HashMap<String, Node> next;
Integer value;
Node() {
this.next = new HashMap();
}
Node(int val) {
this.next = new HashMap();
this.value = val;
}
}
}
/**
* Your FileSystem object will be instantiated and called as such: FileSystem obj = new FileSystem(); boolean param_1 = obj.createPath(path,value); int param_2
* = obj.get(path);
*/
Optimal Solution using only map.
class FileSystem {
Map<String, Integer> file = new HashMap<>();
public FileSystem() {
file.put("", 1);
}
public boolean createPath(String path, int value) {
int idx = path.lastIndexOf("/");
String parent = path.substring(0, idx);
if (!file.containsKey(parent)) { return false; }
return file.putIfAbsent(path, value) == null;
}
public int get(String path) {
return file.getOrDefault(path, 1);
}
}
/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem obj = new FileSystem();
* boolean param_1 = obj.createPath(path,value);
* int param_2 = obj.get(path);
*/
754. Reach a Number
Description
You are standing at position 0 on an infinite number line. There is a goal at position target.
On each move, you can either go left or right. During the nth move (starting from 1), you take n steps.
Return the minimum number of steps required to reach the destination.
Example 1:
Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.
Example 2:
Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step from 1 to 1.
On the third move we step from 1 to 2.
Note:
target will be a nonzero integer in the range [10^9, 10^9].
Solution
Main idea: to switch from + to , the diff will always be even(2 times the step)
So first reach the target, than try to switch + to , and check if the sumtarget is even.
if it’s even, means it’s valid to switch some of the action from + to .
/**
Step 0: Get positive target value (step to get negative target is the same as to get positive value due to symmetry).
Step 1: Find the smallest step that the summation from 1 to step just exceeds or equalstarget.
Step 2: Find the difference between sum and target. The goal is to get rid of the difference to reach target. For ith move, if we switch the right move to the left, the change in summation will be 2*i less. Now the difference between sum and target has to be an even number in order for the math to check out.
Step 2.1: If the difference value is even, we can return the current step.
Step 2.2: If the difference value is odd, we need to increase the step until the difference is even (at most 2 more steps needed).
Eg:
target = 5
Step 0: target = 5.
Step 1: sum = 1 + 2 + 3 = 6 > 5, step = 3.
Step 2: Difference = 6  5 = 1. Since the difference is an odd value, we will not reach the target by switching any right move to the left. So we increase our step.
Step 2.2: We need to increase step by 2 to get an even difference (i.e. 1 + 2 + 3 + 4 + 5 = 15, now step = 5, difference = 15  5 = 10). Now that we have an even difference, we can simply switch any move to the left (i.e. change + to ) as long as the summation of the changed value equals to half of the difference. We can switch 1 and 4 or 2 and 3 or 5.
*/
class Solution {
public int reachNumber(int target) {
target = Math.abs(target);
int step = 0, sum = 0;
while(sum < target){
step++;
sum += step;
}
while((sumtarget)%2!=0){
step++;
sum += step;
}
return step;
}
}
1271. Hexspeak
Description
A decimal number can be converted to its Hexspeak representation by first converting it to an uppercase hexadecimal string, then replacing all occurrences of the digit 0 with the letter O, and the digit 1 with the letter I. Such a representation is valid if and only if it consists only of the letters in the set {"A", "B", "C", "D", "E", "F", "I", "O"}.
Given a string num representing a decimal integer N, return the Hexspeak representation of N if it is valid, otherwise return "ERROR".
Example 1:
Input: num = "257"
Output: "IOI"
Explanation: 257 is 101 in hexadecimal.
Example 2:
Input: num = "3"
Output: "ERROR"
Constraints:
1 <= N <= 10^12
There are no leading zeros in the given string.
All answers must be in uppercase letters.
Solution
class Solution {
public String toHexspeak(String num) {
HashSet<Character> set = new HashSet<Character>(Arrays.asList(new Character[]{'A','B','C','D','E','F'}));
String hex = Long.toHexString(Long.parseLong(num)).toUpperCase();
//System.out.println(hex);
char[] res = hex.toCharArray();
for(int i = 0;i<res.length;i++){
char c = res[i];
if(set.contains(c)){
continue;
}else if(c=='1'){
res[i] = 'I';
}else if(c=='0'){
res[i] = 'O';
}else{
return "ERROR";
}
}
return String.valueOf(res);
}
}
class Solution {
public String toHexspeak(String num) {
StringBuilder result = new StringBuilder();
long n = Long.parseLong(num);
while (n > 0) {
int currDigit = (int) (n % 16);
if (currDigit == 0) {
result.append('O');
} else if (currDigit == 1) {
result.append('I');
} else if (10 <= currDigit) {
result.append((char) (currDigit  10 + 'A'));
} else {
return "ERROR";
}
n /= 16;
}
return result.reverse().toString();
}
}
213. House Robber II
Description
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of nonnegative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.
Example 2:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Solution
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if(len==0){
return 0;
}else if(len==1){
return nums[0];
}
return Math.max(maxProfit(nums,0,len2),maxProfit(nums,1,len1));
}
public int maxProfit(int[] nums, int start, int end){
int[] dp = new int[nums.length];
for(int i = start;i<=end;i++){
dp[i] = Math.max(nums[i]+(i2>=0?dp[i2]:0),(i1>=0?dp[i1]:0));
}
//System.out.println(end +" "+dp[end]);
return dp[end];
}
}
1245. Tree Diameter
Description
Given an undirected tree, return its diameter: the number of edges in a longest path in that tree.
The tree is given as an array of edges where edges[i] = [u, v] is a bidirectional edge between nodes u and v. Each node has labels in the set {0, 1, ..., edges.length}.
Example 1:
Input: edges = [[0,1],[0,2]]
Output: 2
Explanation:
A longest path of the tree is the path 1  0  2.
Example 2:
Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation:
A longest path of the tree is the path 3  2  1  4  5.
Constraints:
0 <= edges.length < 10^4
edges[i][0] != edges[i][1]
0 <= edges[i][j] <= edges.length
The given edges form an undirected tree.
Solution
class Solution {
int max_length = 0;
public int treeDiameter(int[][] edges) {
HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.putIfAbsent(edge[0], new HashSet<>());
graph.putIfAbsent(edge[1], new HashSet<>());
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
dfs(0,0,graph);
return max_length;
}
public int dfs(int node, int parent, HashMap<Integer, HashSet<Integer>> graph) {
List<Integer> lengths = new ArrayList<>();
for (int next : graph.getOrDefault(node, new HashSet<>())) {
if (next != parent) {
lengths.add(dfs(next, node, graph));
}
}
lengths.sort((a, b) > Integer.compare(b, a));
if (lengths.size() >= 2) {
max_length = Math.max(lengths.get(0) + lengths.get(1), max_length);
}
if (lengths.size() == 0) {
return 1;
}
return lengths.get(0)+1;
}
}
20200903
397. Integer Replacement
Description
Given a positive integer n and you can do operations as follow:
If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n  1.
What is the minimum number of replacements needed for n to become 1?
Example 1:
Input:
8
Output:
3
Explanation:
8 > 4 > 2 > 1
Example 2:
Input:
7
Output:
4
Explanation:
7 > 8 > 4 > 2 > 1
or
7 > 6 > 3 > 2 > 1
Solution
public class Solution {
HashMap<Long,Integer> dp;
public int integerReplacement(int n) {
dp = new HashMap();
return helper(n);
}
private int helper(long n) {
if (dp.containsKey(n)) {
return dp.get(n);
}
if (n == 1) {
return 0;
}
if (n <= 0) {
return Integer.MAX_VALUE;
}
int minS;
if (n % 2 == 0) {
minS = helper(n / 2);
} else {
minS = Math.min(helper(n + 1), helper(n  1));
}
dp.put(n, minS+1);
return minS+1;
}
}
386. Lexicographical Numbers
Description
Given an integer n, return 1  n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
Solution
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
helper(0,n,res);
return res;
}
public void helper(int cur, int n, List<Integer> res){
if(cur >n){
return;
}
for(int i = 0;i<=9;i++){
int next = cur * 10 + i;
if(next==0){
continue;
}
if(next <= n){
res.add(next);
helper(next,n,res);
}else{
return;
}
}
}
}
1382. Balance a Binary Search Tree
Description
Given a binary search tree, return a balanced binary search tree with the same node values.
A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.
If there is more than one answer, return any of them.
Example 1:
Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.
Constraints:
The number of nodes in the tree is between 1 and 10^4.
The tree nodes will have distinct values between 1 and 10^5.
Solution
class Solution {
List<TreeNode> sortedArr = new ArrayList<>();
public TreeNode balanceBST(TreeNode root) {
inorderTraverse(root);
return sortedArrayToBST(0, sortedArr.size()  1);
}
void inorderTraverse(TreeNode root) {
if (root == null) {
return;
}
inorderTraverse(root.left);
sortedArr.add(root);
inorderTraverse(root.right);
}
TreeNode sortedArrayToBST(int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
TreeNode root = sortedArr.get(mid);
root.left = sortedArrayToBST(start, mid  1);
root.right = sortedArrayToBST(mid + 1, end);
return root;
}
}
Solution with constant space.
class Solution {
int makeVine(TreeNode grand) {
int cnt = 0;
var n = grand.right;
while (n != null) {
if (n.left != null) {
var old_n = n;
n = n.left;
old_n.left = n.right;
n.right = old_n;
grand.right = n;
} else {
++cnt;
grand = n;
n = n.right;
}
}
return cnt;
}
void compress(TreeNode grand, int m) {
var n = grand.right;
while (m > 0) {
var old_n = n;
n = n.right;
grand.right = n;
old_n.right = n.left;
n.left = old_n;
grand = n;
n = n.right;
}
}
public TreeNode balanceBST(TreeNode root) {
TreeNode grand = new TreeNode(0);
grand.right = root;
int cnt = makeVine(grand);
int m = (int) Math.pow(2, (int) (Math.log(cnt + 1) / Math.log(2)))  1;
compress(grand, cnt  m);
for (m = m / 2; m > 0; m /= 2) {
compress(grand, m);
}
return grand.right;
}
}
515. Find Largest Value in Each Tree Row
Description
Given the root of a binary tree, return an array of the largest value in each row of the tree (0indexed).
Example 1:
Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]
Example 2:
Input: root = [1,2,3]
Output: [1,3]
Example 3:
Input: root = [1]
Output: [1]
Example 4:
Input: root = [1,null,2]
Output: [1,2]
Example 5:
Input: root = []
Output: []
Constraints:
The number of the nodes in the tree will be in the range [1, 104].
231 <= Node.val <= 231  1
Solution
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
helper(root, res, 0);
return res;
}
private void helper(TreeNode root, List<Integer> res, int d) {
if (root == null) {
return;
}
//expand list size
if (d == res.size()) {
res.add(root.val);
} else {
//or set value
res.set(d, Math.max(res.get(d), root.val));
}
helper(root.left, res, d + 1);
helper(root.right, res, d + 1);
}
}
962. Maximum Width Ramp
Description
Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j  i.
Find the maximum width of a ramp in A. If one doesn't exist, return 0.
Example 1:
Input: [6,0,8,2,1,5]
Output: 4
Explanation:
The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.
Example 2:
Input: [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation:
The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.
Note:
2 <= A.length <= 50000
0 <= A[i] <= 50000
Solution
class Solution {
public int maxWidthRamp(int[] A) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int max_len = 0;
for (int i = 0; i < A.length; ++i) {
if (stack.isEmpty()  A[stack.peek()] > A[i]) {
stack.push(i);
}
}
//System.out.println(stack);
for (int i = A.length1; i >max_len; i) {
while (!stack.isEmpty() && A[stack.peek()] <= A[i]) {
max_len = Math.max(max_len, i  stack.pop());
}
}
return max_len;
}
}
825. Friends Of Appropriate Ages
Description
Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.
Person A will NOT friend request person B (B != A) if any of the following conditions are true:
age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100
Otherwise, A will friend request B.
Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.
How many total friend requests are made?
Example 1:
Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.
Example 2:
Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 > 16, 18 > 17.
Example 3:
Input: [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 > 100, 120 > 110, 120 > 100.
Notes:
1 <= ages.length <= 20000.
1 <= ages[i] <= 120.
Solution
only need to taek care conditions:

age larger than 14, people under 14 will not friend anyone.

smaller or equal than A

B larger than A/2 + 7.
class Solution {
public int numFriendRequests(int[] ages) {
int[] numInAge = new int[121];
int[] sumBeforeAge = new int[121];
for (int age : ages) {
numInAge[age]++;
}
for (int i = 1; i < 121; i++) {
sumBeforeAge[i] = numInAge[i] + sumBeforeAge[i  1];
}
int count = 0;
for (int i = 15; i < 121; i++) {
if(numInAge[i]==0){
continue;
}
//valid B will only be someone smaller or equal than A and larger than A/2+7
int num = sumBeforeAge[i]  sumBeforeAge[i / 2 + 7];
//A will not friend themselves, so  numsInAge[i].
count += num * numInAge[i]  numInAge[i];
}
return count;
}
}
20200904
1391. Check if There is a Valid Path in a Grid
Description
Given a m x n grid. Each cell of the grid represents a street. The street of grid[i][j] can be:
1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.
You will initially start at the street of the upperleft cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottomright cell (m  1, n  1). The path should only follow the streets.
Notice that you are not allowed to change any street.
Return true if there is a valid path in the grid or false otherwise.
Example 1:
Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m  1, n  1).
Example 2:
Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)
Example 3:
Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).
Example 4:
Input: grid = [[1,1,1,1,1,1,3]]
Output: true
Example 5:
Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6
Solution
class Solution {
public boolean hasValidPath(int[][] grid) {
int[][][] dirs = [
[[0, 1], [0, 1]],
[[1, 0], [1, 0]],
[[0, 1], [1, 0]],
[[0, 1], [1, 0]],
[[0, 1], [1, 0]],
[[0, 1], [1, 0]]
];
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0});
visited[0][0] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
for (int[] dir : dirs[grid[x][y]  1]) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx < 0  nx >= m  ny < 0  ny >= n  visited[nx][ny]) {
continue;
}
for (int[] backDir : dirs[grid[nx][ny]  1]) {
if (nx + backDir[0] == x && ny + backDir[1] == y) {
visited[nx][ny] = true;
q.add(new int[]{nx, ny});
break;
}
}
}
}
return visited[m  1][n  1];
}
}
1395. Count Number of Teams
Description
There are n soldiers standing in a line. Each soldier is assigned a unique rating value.
You have to form a team of 3 soldiers amongst them under the following rules:
Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).
Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).
Example 1:
Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).
Example 2:
Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.
Example 3:
Input: rating = [1,2,3,4]
Output: 4
Constraints:
n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5
Solution
/**
Count smaller number left to and right to a certain number.
than for pattern 1,2,3 and number i as 2, the total number can be caled by:
(# of number smaller than i) * (# of number larger than i)
vice versa
*/
class Solution {
public int numTeams(int[] rating) {
TreeMap<Integer, Integer> map = new TreeMap<>();
int[] leftSmaller = new int[rating.length];
int[] rightSmaller = new int[rating.length];
//count number of numbers smaller than rating[i] to its left.
map.put(rating[0], map.getOrDefault(rating[0], 0) + 1);
for (int i = 1; i < rating.length; i++) {
leftSmaller[i] = map.headMap(rating[i]).size();
map.put(rating[i], map.getOrDefault(rating[i], 0) + 1);
}
map = new TreeMap();
//count number of numbers smaller than rating[i] to its right.
map.put(rating[rating.length  1], map.getOrDefault(rating[rating.length  1], 0) + 1);
for (int i = rating.length  2; i >= 0; i) {
rightSmaller[i] = map.headMap(rating[i]).size();
map.put(rating[i], map.getOrDefault(rating[i], 0) + 1);
}
int count = 0;
for (int i = 1; i < rating.length  1; i++) {
//pattern 3,2,1
count += (i  leftSmaller[i]) * rightSmaller[i];
//pattern 1,2,3
count += leftSmaller[i] * (rating.length  1  i  rightSmaller[i]);
}
return count;
}
}
20200905
1411. Number of Ways to Paint N × 3 Grid
Description
You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: Red, Yellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).
You are given n the number of rows of the grid.
Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.
Example 1:
Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:
Example 2:
Input: n = 2
Output: 54
Example 3:
Input: n = 3
Output: 246
Example 4:
Input: n = 7
Output: 106494
Example 5:
Input: n = 5000
Output: 30228214
Constraints:
n == grid.length
grid[i].length == 3
1 <= n <= 5000
Solution
/**
Two pattern for each row, 121 and 123.
121, the first color same as the third in a row.
123, one row has three different colors.
We consider the state of the first row,
pattern 121: 121, 131, 212, 232, 313, 323.
pattern 123: 123, 132, 213, 231, 312, 321.
So we initialize a121 = 6, a123 = 6.
We consider the next possible for each pattern:
Patter 121 can be followed by: 212, 213, 232, 312, 313
Patter 123 can be followed by: 212, 231, 312, 232
121 => three 121, two 123
123 => two 121, two 123
So we can write this dynamic programming transform equation:
b121 = a121 * 3 + a123 * 2
b123 = a121 * 2 + a123 * 2
We calculate the result iteratively
and finally return the sum of both pattern a121 + a123
Complexity
Time O(N), Space O(1)
Of course, we can do better.
O(logN) Time Solution
*/
class Solution {
public int numOfWays(int n) {
long a121 = 6, a123 = 6, b121, b123, mod = (long)1e9 + 7;
for (int i = 1; i < n; ++i) {
b121 = a121 * 3 + a123 * 2;
b123 = a121 * 2 + a123 * 2;
a121 = b121 % mod;
a123 = b123 % mod;
}
return (int)((a121 + a123) % mod);
}
}
1296. Divide Array in Sets of K Consecutive Numbers
Description
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into sets of k consecutive numbers
Return True if its possible otherwise return False.
Example 1:
Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].
Example 2:
Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].
Example 3:
Input: nums = [3,3,2,2,1,1], k = 3
Output: true
Example 4:
Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length
Solution
class Solution {
public boolean isPossibleDivide(int[] A, int k) {
//must use treemap to keep it sorted, and start from smaller number.
Map<Integer, Integer> c = new TreeMap<>();
for (int i : A) {
c.put(i, c.getOrDefault(i, 0) + 1);
}
for (int it : c.keySet()) {
if (c.get(it) > 0) {
for (int i = k  1; i >= 0; i) {
if (c.getOrDefault(it + i, 0) < c.get(it)) {
return false;
}
c.put(it + i, c.get(it + i)  c.get(it));
}
}
}
return true;
}
}
1019. Next Greater Node In Linked List
Description
We are given a linked list with head as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ... etc.
Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.
Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).
Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
Example 1:
Input: [2,1,5]
Output: [5,5,0]
Example 2:
Input: [2,7,4,3,5]
Output: [7,0,5,5,0]
Example 3:
Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]
Note:
1 <= node.val <= 10^9 for each node in the linked list.
The given list has length in the range [0, 10000].
Solution
class Solution {
public int[] nextLargerNodes(ListNode head) {
ArrayDeque<ListNode> stack = new ArrayDeque<>();
HashMap<ListNode, Integer> record = new HashMap<>();
ListNode cur = head;
int count = 0;
while (cur != null) {
while (!stack.isEmpty() && stack.peek().val < cur.val) {
record.put(stack.pop(), cur.val);
}
stack.push(cur);
cur = cur.next;
count++;
}
int[] res = new int[count];
cur = head;
int index = 0;
while (cur != null) {
res[index++] = record.getOrDefault(cur, 0);
cur = cur.next;
}
return res;
}
}
839. Similar String Groups
Description
Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.
For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".
Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.
We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?
Example 1:
Input: A = ["tars","rats","arts","star"]
Output: 2
Constraints:
1 <= A.length <= 2000
1 <= A[i].length <= 1000
A.length * A[i].length <= 20000
All words in A consist of lowercase letters only.
All words in A have the same length and are anagrams of each other.
The judging time limit has been increased for this question.
Solution
/**
try every possible combination and union group.
*/
class Solution {
public int numSimilarGroups(String[] A) {
if (A.length < 2) {
return A.length;
}
int size = A.length;
int[] parent = new int[size];
Arrays.fill(parent, 1);
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
//System.out.println(A[i]+" "+A[j]+" "+helper(A[i], A[j]));
if (find(parent, i) != find(parent, j) && helper(A[i], A[j])) {
union(parent, i, j);
}
}
}
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < size; i++) {
set.add(find(parent, i));
}
//System.out.println(set);
return set.size();
}
public int find(int[] parent, int num) {
if (parent[num] == 1) {
parent[num] = num;
} else if (parent[num] != num) {
parent[num] = find(parent, parent[num]);
}
return parent[num];
}
public void union(int[] parent, int num1, int num2) {
int p1 = find(parent, num1);
int p2 = find(parent, num2);
if (p1 != p2) {
parent[p2] = p1;
}
}
public boolean helper(String s, String t) {
int res = 0, i = 0;
while (res <= 2 && i < s.length()) {
if (s.charAt(i) != t.charAt(i)) {
res++;
}
i++;
}
return res == 2  res == 0;
}
}
898. Bitwise ORs of Subarrays
Description
We have an array A of nonnegative integers.
For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i]  A[i+1]  ...  A[j].
Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)
Example 1:
Input: [0]
Output: 1
Explanation:
There is only one possible result: 0.
Example 2:
Input: [1,1,2]
Output: 3
Explanation:
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.
Example 3:
Input: [1,2,4]
Output: 6
Explanation:
The possible results are 1, 2, 3, 4, 6, and 7.
Note:
1 <= A.length <= 50000
0 <= A[i] <= 10^9
Solution
/**
cur contains all the prex.
*/
class Solution {
public int subarrayBitwiseORs(int[] A) {
Set<Integer> res = new HashSet<>(), cur = new HashSet<>(), cur2;
for (Integer i : A) {
cur2 = new HashSet<>();
cur2.add(i);
for (Integer j : cur) {
cur2.add(i  j);
}
res.addAll(cur = cur2);
}
return res.size();
}
}
1002. Find Common Characters
Description
Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.
You may return the answer in any order.
Example 1:
Input: ["bella","label","roller"]
Output: ["e","l","l"]
Example 2:
Input: ["cool","lock","cook"]
Output: ["c","o"]
Note:
1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] is a lowercase letter
Solution
//Count the min times a letter appears in all words.
class Solution {
public List<String> commonChars(String[] A) {
int[] map = new int[26];
Arrays.fill(map, Integer.MAX_VALUE);
for (String word : A) {
int[] count = new int[26];
for (char c : word.toCharArray()) {
count[c  'a']++;
}
for (int i = 0; i < 26; i++) {
map[i] = Math.min(map[i], count[i]);
}
}
List<String> res = new ArrayList<>();
for (int i = 0; i < 26; i++) {
while (map[i] > 0) {
res.add("" + (char) (i + 'a'));
map[i];
}
}
return res;
}
}
1131. Maximum of Absolute Value Expression
Description
Given two arrays of integers with equal lengths, return the maximum value of:
arr1[i]  arr1[j] + arr2[i]  arr2[j] + i  j
where the maximum is taken over all 0 <= i, j < arr1.length.
Example 1:
Input: arr1 = [1,2,3,4], arr2 = [1,4,5,6]
Output: 13
Example 2:
Input: arr1 = [1,2,5,0,10], arr2 = [0,2,1,7,4]
Output: 20
Constraints:
2 <= arr1.length == arr2.length <= 40000
10^6 <= arr1[i], arr2[i] <= 10^6
Solution
/**
f we look carefully, 1 & 8 ; 2 & 7; 3 & 6; 4 & 5 are practically the same.
So , problem reduces to finding max of (1,2,3,4).
And in each 1,2,3,4, values in both brackets are same, so we simply find max(value in bracket)  min(value in bracket) for each.
Then find max of values obtained from (1,2,3,4)
*/
class Solution {
public static int maxAbsValExpr(int[] arr1, int[] arr2) {
int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max3 = Integer.MIN_VALUE;
int max4 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
int min3 = Integer.MAX_VALUE;
int min4 = Integer.MAX_VALUE;
int n = arr1.length;
for (int i = 0; i < n; i++) {
// 1st scenario arr1[i] + arr2[i] + i
max1 = Integer.max(arr1[i] + arr2[i] + i, max1);
min1 = Integer.min(arr1[i] + arr2[i] + i, min1);
// 2nd scenario arr1[i] + arr2[i]  i
max2 = Integer.max(arr1[i] + arr2[i]  i, max2);
min2 = Integer.min(arr1[i] + arr2[i]  i, min2);
// 3rd scenario arr1[i]  arr2[i]  i
max3 = Integer.max(arr1[i]  arr2[i]  i, max3);
min3 = Integer.min(arr1[i]  arr2[i]  i, min3);
// 4th scenario arr1[i]  arr2[i] + i
max4 = Integer.max(arr1[i]  arr2[i] + i, max4);
min4 = Integer.min(arr1[i]  arr2[i] + i, min4);
}
int diff1 = max1  min1;
int diff2 = max2  min2;
int diff3 = max3  min3;
int diff4 = max4  min4;
return Integer.max(Integer.max(diff1, diff2), Integer.max(diff3, diff4));
}
}
20200906
849. Maximize Distance to Closest Person
Description
In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty.
There is at least one empty seat, and at least one person sitting.
Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.
Return that maximum distance to closest person.
Example 1:
Input: [1,0,0,0,1,0,1]
Output: 2
Explanation:
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.
Example 2:
Input: [1,0,0,0]
Output: 3
Explanation:
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.
Constraints:
2 <= seats.length <= 20000
seats contains only 0s or 1s, at least one 0, and at least one 1.
Solution
class Solution {
public int maxDistToClosest(int[] seats) {
int res = 0, n = seats.length, last = 1;
for (int i = 0; i < n; ++i) {
if (seats[i] == 1) {
res = last < 0 ? i : Math.max(res, (i  last) / 2);
last = i;
}
}
res = Math.max(res, n  last  1);
return res;
}
}
992. Subarrays with K Different Integers
Description
Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
Return the number of good subarrays of A.
Example 1:
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Example 2:
Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
Note:
1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length
Solution
class Solution {
public int subarraysWithKDistinct(int[] A, int K) {
return atMostK(A, K)  atMostK(A, K  1);
}
int atMostK(int[] A, int K) {
int i = 0, res = 0;
Map<Integer, Integer> count = new HashMap<>();
for (int j = 0; j < A.length; ++j) {
if (count.getOrDefault(A[j], 0) == 0) {
K;
}
count.put(A[j], count.getOrDefault(A[j], 0) + 1);
while (K < 0) {
count.put(A[i], count.get(A[i])  1);
if (count.get(A[i]) == 0) {
K++;
}
i++;
}
res += j  i + 1;
}
return res;
}
}
1497. Check If Array Pairs Are Divisible by k
Description
Given an array of integers arr of even length n and an integer k.
We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.
Return True If you can find a way to do that or False otherwise.
Example 1:
Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).
Example 2:
Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).
Example 3:
Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.
Example 4:
Input: arr = [10,10], k = 2
Output: true
Example 5:
Input: arr = [1,1,2,2,3,3,4,4], k = 3
Output: true
Solution
/**
Use mod to calc, if A%k=x and B%k=kx then (A+B) can be divided by k.
*/
class Solution {
public boolean canArrange(int[] arr, int k) {
int[] mod = new int[k];
for(int num:arr){
int temp = num % k;
if(temp<0){
temp+=k;}
mod[temp]++;
}
if(mod[0]%2!=0){
return false;
}
//be careful that i<=k/2
//k=4 > 1,2  3,4
//k=5 > 1,2  4,5 (3 is no need to check since all others are valid then 3 will always be valid.)
for(int i = 1;i<=k/2;i++){
if(mod[i]!=mod[ki]){
return false;
}
}
return true;
}
}
376. Wiggle Subsequence
Description
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,3,5,7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Example 1:
Input: [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.
Example 2:
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Example 3:
Input: [1,2,3,4,5,6,7,8,9]
Output: 2
Solution
//up[i] and down[i] means max len ending at i that is up/down.
//up: /\/\/(ending with up)
public class Solution {
public int wiggleMaxLength(int[] nums) {
if( nums.length == 0 ) return 0;
int[] up = new int[nums.length];
int[] down = new int[nums.length];
up[0] = 1;
down[0] = 1;
for(int i = 1 ; i < nums.length; i++){
//i1 / i
if( nums[i] > nums[i1] ){
//add (i1,i) to sub and ending at i with up.
up[i] = down[i1]+1;
//length of down will not change.
down[i] = down[i1];
}else if( nums[i] < nums[i1]){
down[i] = up[i1]+1;
up[i] = up[i1];
}else{
//both will not change
down[i] = down[i1];
up[i] = up[i1];
}
}
return Math.max(down[nums.length1],up[nums.length1]);
}
}
813. Largest Sum of Averages
Description
We partition a row of numbers A into at most K adjacent (nonempty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?
Note that our partition must use every number in A, and that scores are not necessarily integers.
Example:
Input:
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation:
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
Note:
1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
Answers within 10^6 of the correct answer will be accepted as correct.
Solution
//dp[i][k] means the max result from subarray [0,i](inclusive) with k groups.
class Solution {
double[][] memo;
public double largestSumOfAverages(int[] A, int K) {
int N = A.length;
memo = new double[N][K+1];
double cur = 0;
for(int i =0;i<N;i++){
cur += A[i];
memo[i][1] = cur /(i+1);
}
return dp(A,N1,K);
}
public double dp(int[] A, int i, int k) {
if (memo[i][k] != 0) {
return memo[i][k];
}
if (i+1 < k) {
return 0;
}
double max_res = 0;
double sum = 0;
//divide to two part: [0,j] and (j,end]
//[0,j] > dp(A,j,k1)
//(j,end] > sum / (ij)
for (int j = i  1; j >= 0; j) {
sum += A[j+1];
max_res = Math.max(max_res,dp(A,j,k1)+sum/(ij));
}
memo[i][k] = max_res;
return max_res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.largestSumOfAverages(new int[]{9, 1, 2, 3, 9}, 3));
}
}
1402. Reducing Dishes
Description
A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.
Liketime coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i]*satisfaction[i]
Return the maximum sum of Liketime coefficient that the chef can obtain after dishes preparation.
Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.
Example 1:
Input: satisfaction = [1,8,0,5,9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total Liketime coefficient will be equal to (1*1 + 0*2 + 5*3 = 14). Each dish is prepared in one unit of time.
Example 2:
Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
Example 3:
Input: satisfaction = [1,4,5]
Output: 0
Explanation: People don't like the dishes. No dish is prepared.
Example 4:
Input: satisfaction = [2,5,1,0,3,3]
Output: 35
Constraints:
n == satisfaction.length
1 <= n <= 500
10^3 <= satisfaction[i] <= 10^3
Solution
/**
sort the arrays first, so start from the largest one.
1*B + 2*C + 3*D > 1*A + 2*B + c*C + 4*D
diff = B+C+D
keep a sum that B+C+D, then calc the max res.
*/
class Solution {
public int maxSatisfaction(int[] satisfaction) {
int max_res = 0;
Arrays.sort(satisfaction);
int cur = 0, sum = 0;
for (int i = satisfaction.length  1; i >= 0; i) {
sum += satisfaction[i];
cur += sum;
max_res = Math.max(max_res,cur);
}
return max_res;
}
}
392. Is Subsequence
Description
Given a string s and a string t, check if s is subsequence of t.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
Constraints:
0 <= s.length <= 100
0 <= t.length <= 10^4
Both strings consists only of lowercase characters.
Solution
class Solution {
public boolean isSubsequence(String s, String t) {
int i =0,j=0;
while(i<s.length() && j<t.length()){
if(s.charAt(i)==t.charAt(j)){
i++;
}
j++;
}
return i==s.length();
}
}
FollowUp:
Store all the premutations in a HashSet.
1035. Uncrossed Lines
Description
We write the integers of A and B (in the order they are given) on two separate horizontal lines.
Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:
A[i] == B[j];
The line we draw does not intersect any other connecting (nonhorizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.
Return the maximum number of connecting lines we can draw in this way.
Example 1:
Input: A = [1,4,2], B = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.
Example 2:
Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3
Example 3:
Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2
Note:
1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000
Solution
/**
Longest Common Subsequence.
keep orders to avoid cross link.
*/
class Solution {
public int maxUncrossedLines(int[] A, int[] B) {
int m = A.length, n = B.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1 ; j <= n; j++) {
if (A[i  1] == B[j  1]) {
dp[i][j] = dp[i  1][j  1] + 1;
} else {
dp[i][j] = Math.max(dp[i  1][j], dp[i][j  1]);
}
}
}
return dp[m][n];
}
}
20200907
454. 4Sum II
Description
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of 228 to 228  1 and the result is guaranteed to be at most 231  1.
Example:
Input:
A = [ 1, 2]
B = [2,1]
C = [1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) > A[0] + B[0] + C[0] + D[1] = 1 + (2) + (1) + 2 = 0
2. (1, 1, 0, 0) > A[1] + B[1] + C[0] + D[0] = 2 + (1) + (1) + 0 = 0
Solution
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
HashMap<Integer, Integer> count = new HashMap<>();
for (int a : A) {
for (int b : B) {
count.put(a + b, count.getOrDefault(a + b, 0) + 1);
}
}
int res = 0;
for (int c : C) {
for (int d : D) {
res += count.getOrDefault((c + d), 0);
}
}
return res;
}
}
473. Matchsticks to Square
Description
Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.
Example 1:
Input: [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.
Note:
The length sum of the given matchsticks is in the range of 0 to 10^9.
The length of the given matchstick array will not exceed 15.
Solution
/**
Sorting the input array DESC will make the DFS process run much faster. Reason behind this is we always try to put the next matchstick in the first subset.
If there is no solution, trying a longer matchstick first will get to negative conclusion earlier.
Runtime is improved from more than 1000ms to around 40ms. A big improvement.
*/
public class Solution {
public boolean makesquare(int[] nums) {
if (nums == null  nums.length < 4) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 4 != 0) {
return false;
}
Arrays.sort(nums);
reverse(nums);
return dfs(nums, new int[4], 0, sum / 4);
}
private boolean dfs(int[] nums, int[] sums, int index, int target) {
if (index == nums.length) {
if (sums[0] == target && sums[1] == target && sums[2] == target) {
return true;
}
return false;
}
for (int i = 0; i < 4; i++) {
if (sums[i] + nums[index] > target) {
continue;
}
sums[i] += nums[index];
if (dfs(nums, sums, index + 1, target)) {
return true;
}
sums[i] = nums[index];
}
return false;
}
private void reverse(int[] nums) {
int i = 0, j = nums.length  1;
while (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j;
}
}
}
820. Short Encoding of Words
Description
Given a list of words, we may encode it by writing a reference string S and a list of indexes A.
For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].
Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.
What is the length of the shortest reference string S possible that encodes the given words?
Example:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].
Note:
1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.
Solution
/**
Build Trie backward, so the words sharing the same ending will be merged
Only need to count the longest word among all words sharing the same ending.
*/
class Solution {
public int minimumLengthEncoding(String[] words) {
TrieNode root = new TrieNode();
List<TrieNode> leaves = new ArrayList<TrieNode>();
for (String w : new HashSet<>(Arrays.asList(words))) {
TrieNode cur = root;
for (int i = w.length()  1; i >= 0; i) {
char j = w.charAt(i);
if (!cur.next.containsKey(j)) {
cur.next.put(j, new TrieNode());
}
cur = cur.next.get(j);
}
cur.word = w;
leaves.add(cur);
}
int res = 0;
for (TrieNode leaf : leaves) {
if (leaf.next.isEmpty()) {
res += leaf.word.length()+1;
}
}
return res;
}
class TrieNode {
HashMap<Character, TrieNode> next = new HashMap<>();
String word;
}
}
Solution Using StringBuilder without Trie.
class Solution {
public int minimumLengthEncoding(String[] words) {
Set<String> s = new HashSet<>(Arrays.asList(words));
for (String w : words) {
StringBuilder sb = new StringBuilder();
for (int i = w.length()  1; i >0; i) {
sb.insert(0, w.charAt(i));
s.remove(sb.toString());
}
}
int res = 0;
for (String w : s) {
res += w.length() + 1;
}
return res;
}
}
524. Longest Word in Dictionary through Deleting
Description
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"
Example 2:
Input:
s = "abpcplea", d = ["a","b","c"]
Output:
"a"
Note:
All the strings in the input will only contain lowercase letters.
The size of the dictionary won't exceed 1,000.
The length of all the strings in the input won't exceed 1,000.
Solution
class Solution {
public String findLongestWord(String s, List<String> d) {
String res = "";
//no need to sort, simply compare and swap the res.
//d.sort((a, b) > (b.length()  a.length()==0?a.compareTo(b):b.length()a.length()));
for (int i = 0; i < d.size(); i++) {
String word = d.get(i);
if (isSub(word, s)) {
if(res.length() < word.length()  (res.length() == word.length() && res.compareTo(word)>0)){
res = word;
}
}
}
return res;
}
public boolean isSub(String str1, String str2) {
if (str2.length() < str1.length()) {
return false;
}
int i = 0, j = 0;
while (i < str1.length() && j < str2.length()) {
if (str1.charAt(i) == str2.charAt(j)) {
i++;
}
j++;
}
return i == str1.length();
}
}
1162. As Far from Land as Possible
Description
Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is x0  x1 + y0  y1.
If no land or water exists in the grid, return 1.
Example 1:
Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation:
The cell (1, 1) is as far as possible from all the land with distance 2.
Example 2:
Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation:
The cell (2, 2) is as far as possible from all the land with distance 4.
Note:
1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1
Solution
/**
BFS from all the land until all visited.
travel by levels.
*/
class Solution {
public int maxDistance(int[][] grid) {
if (grid == null  grid.length == 0  grid[0].length == 0) {
return 0;
}
int[][] dirs = new int[][][[0, 1], [0, 1], [1, 0], [1, 0]];
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue.add(new int[]{i, j});
visited[i][j] = true;
}
}
}
//special case where all 0s or all 1s, then no valid ans.
if (queue.size() == 0  queue.size() == m * n) {
return 1;
}
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
for (int[] dir : dirs) {
int nx = cur[0] + dir[0];
int ny = cur[1] + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
queue.add(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
level++;
}
return level;
}
}
1363. Largest Multiple of Three
Description
Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.
Since the answer may not fit in an integer data type, return the answer as a string.
If there is no answer return an empty string.
Example 1:
Input: digits = [8,1,9]
Output: "981"
Example 2:
Input: digits = [8,6,7,1,0]
Output: "8760"
Example 3:
Input: digits = [1]
Output: ""
Example 4:
Input: digits = [0,0,0,0,0,0]
Output: "0"
Constraints:
1 <= digits.length <= 10^4
0 <= digits[i] <= 9
The returning answer must not contain unnecessary leading zeros.
Solution
/**
Observation 1: since the order does not matter, the largest number can be formed by adding digits from largest (9) to smallest (0), e.g. 9999966330000.
Therefore, we can just count the occurrences of each digit, and then generate the string.
Observation 2: we need to use all digits to form the maximum number. If we sum all digits, and the modulo of 3 is not zero, we need to remove 1 (preferably) or 2 smallest digits. If modulo 3 of the sum is 1, for example, we will try to remove 1, 4, or 7, if exists, or two of 2, 5, or 8.
*/
class Solution {
public String largestMultipleOfThree(int[] digits) {
int m1[] = new int[]{1, 4, 7, 2, 5, 8}, m2[] = new int[]{2, 5, 8, 1, 4, 7};
int sum = 0, ds[] = new int[10];
for (int d : digits) {
++ds[d];
sum += d;
}
//if mod is 1, then try delete 1,4,7 once.
//if not exist, then try to delete 2,5,8 twice.
//vice versa for mod 2.
while (sum % 3 != 0) {
for (int i : sum % 3 == 1 ? m1 : m2) {
if (ds[i] > 0) {
ds[i];
sum = i;
//if delete 2,5,8, while loop will continue cause num%3!=0.
break;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 9; i >= 0; i) {
String c = Character.toString((char) ('0' + i));
for(int j=0;j<ds[i];j++){
sb.append(c);
}
}
return sb.length() > 0 && sb.charAt(0) == '0' ? "0" : sb.toString();
}
}
20200908
1051. Height Checker
Description
Students are asked to stand in nondecreasing order of heights for an annual photo.
Return the minimum number of students that must move in order for all students to be standing in nondecreasing order of height.
Notice that when a group of students is selected they can reorder in any possible way between themselves and the non selected students remain on their seats.
Example 1:
Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation:
Current array : [1,1,4,2,1,3]
Target array : [1,1,1,2,3,4]
On index 2 (0based) we have 4 vs 1 so we have to move this student.
On index 4 (0based) we have 1 vs 3 so we have to move this student.
On index 5 (0based) we have 3 vs 4 so we have to move this student.
Example 2:
Input: heights = [5,1,2,3,4]
Output: 5
Example 3:
Input: heights = [1,2,3,4,5]
Output: 0
Constraints:
1 <= heights.length <= 100
1 <= heights[i] <= 100
Solution
import java.util.Arrays;
class Solution {
public int heightChecker(int[] heights) {
int[] copy = Arrays.copyOf(heights, heights.length);
Arrays.sort(copy);
int count = 0;
for (int i = 0; i < heights.length; i++) {
if (copy[i] != heights[i]) {
count++;
}
}
return count;
}
}
867. Transpose Matrix
Description
Given a matrix A, return the transpose of A.
The transpose of a matrix is the matrix flipped over it's main diagonal, switching the row and column indices of the matrix.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
Example 2:
Input: [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]
Note:
1 <= A.length <= 1000
1 <= A[0].length <= 1000
Solution
class Solution {
public int[][] transpose(int[][] A) {
if (A == null  A.length == 0  A[0].length == 0) {
return A;
}
int m = A.length, n = A[0].length;
int[][] res = new int[n][m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res[j][i] = A[i][j];
}
}
return res;
}
}
172. Factorial Trailing Zeroes
Description
Given an integer n, return the number of trailing zeroes in n!.
Example 1:
Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Example 2:
Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Solution
/**
Because all trailing 0 is from factors 5 * 2.
But sometimes one number may have several 5 factors, for example, 25 have two 5 factors, 125 have three 5 factors. In the n! operation, factors 2 is always ample. So we just count how many 5 factors in all number from 1 to n.
*/
class Solution {
public int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
}
20200909
853. Car Fleet
Description
N cars are going to the same destination along a one lane road. The destination is target miles away.
Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.
A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.
The distance between these two cars is ignored  they are assumed to have the same position.
A car fleet is some nonempty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
How many car fleets will arrive at the destination?
Example 1:
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.
Note:
0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
All initial positions are different.
Solution
/**
Sort cars by the start positions pos
Loop on each car from the end to the beginning
Calculate its time needed to arrive the target
cur records the current biggest time (the slowest)
If another car needs less or equal time than cur,
it can catch up this car fleet.
If another car needs more time,
it will be the new slowest car,
and becomes the new lead of a car fleet.
*/
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int N = position.length;
Double[][] cars = new Double[N][2];
for (int i = 0; i < N; i++) {
cars[i] = new Double[]{(double) position[i], (double) (target  position[i]) / speed[i]};
}
Arrays.sort(cars, (a, b) > Double.compare(a[0], b[0]));
int count = 0;
double cur = 0;
for (int i = N  1; i >= 0; i) {
if(cars[i][1] > cur){
count++;
cur = cars[i][1];
}
}
return count;
}
}
1413. Minimum Value to Get Positive Step by Step Sum
Description
Given an array of integers nums, you start with an initial positive value startValue.
In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).
Return the minimum positive value of startValue such that the step by step sum is never less than 1.
Example 1:
Input: nums = [3,2,3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4  startValue = 5  nums
(4 3 ) = 1  (5 3 ) = 2  3
(1 +2 ) = 3  (2 +2 ) = 4  2
(3 3 ) = 0  (4 3 ) = 1  3
(0 +4 ) = 4  (1 +4 ) = 5  4
(4 +2 ) = 6  (5 +2 ) = 7  2
Example 2:
Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.
Example 3:
Input: nums = [1,2,3]
Output: 5
Constraints:
1 <= nums.length <= 100
100 <= nums[i] <= 100
Solution
/**
Find the min value it can achieve IF start from 0, then add the minvalue will make all
occuring number larger than 1.
*/
class Solution {
public int minStartValue(int[] nums) {
int cur = 0, min_val =Integer.MAX_VALUE ;
for(int num:nums){
cur += num;
min_val = Math.min(min_val,cur);
}
min_val = Math.min(0,min_val);
return min_val+1;
}
}
640. Solve the Equation
Description
Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '' operation, the variable x and its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of x is an integer.
Example 1:
Input: "x+53+x=6+x2"
Output: "x=2"
Example 2:
Input: "x=x"
Output: "Infinite solutions"
Example 3:
Input: "2x=x"
Output: "x=0"
Example 4:
Input: "2x+3x6x=x+2"
Output: "x=1"
Example 5:
Input: "x=x+2"
Output: "No solution"
Solution
class Solution {
public String solveEquation(String equation) {
String[] temp = equation.split("=");
String[] arr1 = temp[0].split("(?=[+])");
String[] arr2 = temp[1].split("(?=[+])");
int count_x = 0, count_num = 0;
for (String str : arr1) {
if (str.contains("x")) {
str = str.replace("x", "");
if ("".equals(str)"+".equals(str)) {
count_x++;
}else if("".equals(str)){
count_x;
}else{
count_x += Integer.parseInt(str);
}
} else {
count_num = Integer.parseInt(str);
}
}
for (String str : arr2) {
if (str.contains("x")) {
str = str.replace("x", "");
if ("".equals(str)"+".equals(str)) {
count_x;
}else if("".equals(str)){
count_x++;
}else{
count_x = Integer.parseInt(str);
}
} else {
count_num += Integer.parseInt(str);
}
}
if (count_x == 0) {
if (count_num == 0) {
//x=x
return "Infinite solutions";
} else {
//x=x+2
return "No solution";
}
}
return "x=" + (count_num / count_x);
}
}
1267. Count Servers that Communicate
Description
You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.
Return the number of servers that communicate with any other server.
Example 1:
Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.
Example 2:
Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.
Example 3:
Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.
Constraints:
m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1
Solution
import java.util.HashSet;
class Solution {
public int countServers(int[][] grid) {
int M = grid.length, N = grid[0].length;
int[] rowsCount = new int[M];
int[] colsCount = new int[N];
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < M; i++) {
int head = 1;
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
rowsCount[i]++;
colsCount[j]++;
}
}
}
for (int i = 0; i < M; i++) {
if (rowsCount[i] > 1) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
set.add(i * N + j);
}
}
}
}
for (int j = 0; j < N; j++) {
if (colsCount[j] > 1) {
for (int i = 0; i < M; i++) {
if (grid[i][j] == 1) {
set.add(i * N + j);
}
}
}
}
return set.size();
}
}
20200910
409. Longest Palindrome
Description
Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Letters are case sensitive, for example, "Aa" is not considered a palindrome here.
Example 1:
Input: s = "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
Example 2:
Input: s = "a"
Output: 1
Example 3:
Input: s = "bb"
Output: 2
Constraints:
1 <= s.length <= 2000
s consits of lowercase and/or uppercase English letters only.
Solution
/**
if contains a odd, then can placed at the center.
*/
class Solution {
public int longestPalindrome(String s) {
int[] letters = new int[256];
for (char c : s.toCharArray()) {
letters[c]++;
}
int count = 0;
boolean isOdd = false;
for (int i = 0; i < letters.length; i++) {
count+= letters[i];
if(letters[i]%2!=0){
isOdd = true;
count;
}
}
return isOdd?count+1:count;
}
}
674. Longest Continuous Increasing Subsequence
Description
Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.
Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.
Note: Length of the array will not exceed 10,000.
Solution
class Solution {
public int findLengthOfLCIS(int[] nums) {
if (nums == null  nums.length == 0) {
return 0;
}
int i = 0;
int maxLen = 1;
for (int j = 0; j < nums.length; j++) {
if (j != 0 && nums[j] <= nums[j  1]) {
i = j;
}
maxLen = Math.max(maxLen, j  i + 1);
}
return maxLen;
}
}
1472. Design Browser History
Design
You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.
Implement the BrowserHistory class:
BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
void visit(string url) Visits url from the current page. It clears up all the forward history.
string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.
Example:
Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]
Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com"); // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com"); // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com"); // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1); // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1); // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1); // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com"); // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2); // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(2); // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"
browserHistory.back(7); // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"
Constraints:
1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage and url consist of '.' or lower case English letters.
At most 5000 calls will be made to visit, back, and forward.
Solution
import java.util.ArrayDeque;
class BrowserHistory {
ArrayDeque<String> backward;
ArrayDeque<String> forward;
String cur;
public BrowserHistory(String homepage) {
backward = new ArrayDeque<>();
forward = new ArrayDeque<>();
cur = homepage;
}
public void visit(String url) {
backward.push(cur);
cur = url;
forward.clear();
}
public String back(int steps) {
while (!backward.isEmpty() && steps > 0) {
forward.push(cur);
cur = backward.pop();
}
return cur;
}
public String forward(int steps) {
while (!forward.isEmpty() && steps > 0) {
backward.push(cur);
cur = forward.pop();
}
return cur;
}
}
1345. Jump Game IV
Description
Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:
i + 1 where: i + 1 < arr.length.
i  1 where: i  1 >= 0.
j where: arr[i] == arr[j] and i != j.
Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [100,23,23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 > 4 > 3 > 9. Note that index 9 is the last index of the array.
Example 2:
Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.
Example 3:
Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
Example 4:
Input: arr = [6,1,9]
Output: 2
Example 5:
Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3
Constraints:
1 <= arr.length <= 5 * 10^4
10^8 <= arr[i] <= 10^8
Solution
/**
BFS, search all next possible indexes including left, right and indexes with same values.
*/
class Solution {
public int minJumps(int[] arr) {
HashMap<Integer, List<Integer>> indexOfValue = new HashMap<>();
//to look up all the indexes with same value.
for (int i = 0; i < arr.length; i++) {
indexOfValue.putIfAbsent(arr[i], new ArrayList<>());
indexOfValue.get(arr[i]).add(i);
}
int len = arr.length;
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
queue.add(0);
visited.add(0);
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
int cur = queue.poll();
//reached the end.
if(cur==len1){
return step;
}
List<Integer> next = indexOfValue.get(arr[cur]);
//add left and right as possible next position.
if(cur1>= 0){
next.add(cur1);
}
if(cur+1 < len){
next.add(cur+1);
}
for(int n : next){
if(!visited.contains(n)){
visited.add(n);
queue.add(n);
}
}
next.clear();
}
step++;
}
return 1;
}
}
163. Missing Ranges
Description
Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
Example:
Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4>49", "51>74", "76>99"]
Solution
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new ArrayList<>();
if (nums == null  nums.length == 0) {
result.add(formRange(lower, upper));
return result;
}
// 1st step
if (nums[0] > lower) {
result.add(formRange(lower, nums[0]  1));
}
// 2nd step
for (int i = 0; i < nums.length  1; i++) {
//== is to protect from overflow
//[2147483648,2147483648,0,2147483647,2147483647], 2147483648, 2147483647
if (nums[i + 1] != nums[i] && nums[i + 1] > nums[i] + 1) {
result.add(formRange(nums[i] + 1, nums[i + 1]  1));
}
}
// 3rd step
if (nums[nums.length  1] < upper) {
result.add(formRange(nums[nums.length  1] + 1, upper));
}
return result;
}
public String formRange(int low, int high) {
return low == high ? String.valueOf(low) : (low + ">" + high);
}
}
20200913
1373. Maximum Sum BST in Binary Tree
Description
Given a binary tree root, the task is to return the maximum sum of all keys of any subtree which is also a Binary Search Tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.
Example 2:
Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.
Example 3:
Input: root = [4,2,5]
Output: 0
Explanation: All values are negatives. Return an empty BST.
Example 4:
Input: root = [2,1,3]
Output: 6
Example 5:
Input: root = [5,4,8,3,null,6,3]
Output: 7
Constraints:
The given binary tree will have between 1 and 40000 nodes.
Each node's value is between [4 * 10^4 , 4 * 10^4].
Solution
/**
* Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }
*/
class Solution {
int max_val;
public int maxSumBST(TreeNode root) {
if (root == null) {
return 0;
}
helper(root);
return max_val;
}
public int[] helper(TreeNode root) {
boolean isValid = true;
//if the node is leaf, then min and max will be its own value.
int min = root.val, max = root.val;
int sum = root.val;
if (root.left != null) {
int[] leftRes = helper(root.left);
if (leftRes[0] == 1  leftRes[2] >= root.val) {
isValid = false;
}
sum += leftRes[3];
min = leftRes[1];
}
if (root.right != null) {
int[] rightRes = helper(root.right);
if (rightRes[0] == 1  rightRes[1] <= root.val) {
isValid = false;
}
sum += rightRes[3];
max = rightRes[2];
}
if (!isValid) {
return new int[]{1, min, max, 0};
}
max_val = Math.max(max_val, sum);
return new int[]{1, min, max, sum};
}
}
1335. Minimum Difficulty of a Job Schedule
Description
You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i).
You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done in that day.
Given an array of integers jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].
Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return 1.
Example 1:
Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7
Example 2:
Input: jobDifficulty = [9,9,9], d = 4
Output: 1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
Example 3:
Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.
Example 4:
Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15
Example 5:
Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843
Constraints:
1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10
Solution
/**
dfs help find the the minimum difficulty
if start work at ith job with d days left.
If d = 1, only one day left, we have to do all jobs,
return the maximum difficulty of jobs.
*/
class Solution {
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
if (n < d) {
return 1;
}
int[][] cache = new int[n][d + 1];
for (int i = 0; i < n; i++) {
Arrays.fill(cache[i], 1);
}
return dfs(jobDifficulty, n, 0, d, cache);
}
private int dfs(int[] arr, int n, int i, int d, int[][] cache) {
if (cache[i][d] != 1) {
return cache[i][d];
}
if (d == 1) {
int max = 0;
while (i < n) {
max = Math.max(max, arr[i++]);
}
return max;
}
int res = Integer.MAX_VALUE, maxDifficulty = 0;
for (int j = i; j < n  d + 1; j++) {
maxDifficulty = Math.max(arr[j], maxDifficulty);
res = Math.min(res, maxDifficulty + dfs(arr, n, j + 1, d  1, cache));
}
return cache[i][d] = res;
}
}
702. Search in a Sorted Array of Unknown Size
Description
Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return 1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0indexed).
You may assume all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.
Example 1:
Input: array = [1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: array = [1,0,3,5,9,12], target = 2
Output: 1
Explanation: 2 does not exist in nums so return 1
Constraints:
You may assume that all elements in the array are unique.
The value of each element in the array will be in the range [9999, 9999].
The length of the array will be in the range [1, 10^4].
###Solution
/**
* // This is ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* interface ArrayReader {
* public int get(int index) {}
* }
*/
class Solution {
public int search(ArrayReader reader, int target) {
int left = 0, right = (int) 1e4;
while (left <= right) {
int mid = left + (right  left) / 2;
int val = reader.get(mid);
System.out.print(mid+" "+val);
if (val == target) {
return mid;
} else if (val == 2147483647  val > target) {
right = mid  1;
} else {
left = mid + 1;
}
}
return 1;
}
}
491. Increasing Subsequences
Description
Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2.
Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Constraints:
The length of the given array will not exceed 15.
The range of integer in the given array is [100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.
Solution
class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
helper(0, nums, new ArrayList<>(), res);
return res;
}
public void helper(int index, int[] nums, List<Integer> temp, List<List<Integer>> res) {
if (index == nums.length) {
return;
}
//to handle special case with duplicates.
//[1,2,3,4,5,6,7,8,9,10,1,1,1,1,1] > [1,1] [1,1,1] [1,1,1,1] [1,1,1,1,1] [1,1,1,1,1,1]
HashSet<Integer> visited = new HashSet<>();
for (int i = index; i < nums.length; i++) {
if (!visited.contains(nums[i])) {
visited.add(nums[i]);
if (temp.size() == 0) {
temp.add(nums[i]);
helper(i + 1, nums, temp, res);
temp.remove(temp.size()  1);
} else if (temp.get(temp.size()  1) <= nums[i]) {
temp.add(nums[i]);
res.add(new ArrayList<>(temp));
helper(i + 1, nums, temp, res);
temp.remove(temp.size()  1);
}
}
}
}
}
20200915
720. Longest Word in Dictionary
Description
Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.
If there is no answer, return the empty string.
Example 1:
Input:
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation:
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
Example 2:
Input:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation:
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Note:
All the strings in the input will only contain lowercase letters.
The length of words will be in the range [1, 1000].
The length of words[i] will be in the range [1, 30].
Solution
class Solution {
public String longestWord(String[] words) {
HashSet<String> dicts = new HashSet<>();
//no need to sort in length, just sort lexelly.
//so case like: apple and apply can be avoid.
Arrays.sort(words);
String res = "";
for (String word : words) {
if (word.length() == 1  dicts.contains(word.substring(0, word.length()  1))) {
dicts.add(word);
if (res.length() < word.length() ) {
res = word;
}
}
}
return res;
}
}
1498. Number of Subsequences That Satisfy the Given Sum Condition
Description
Given an array of integers nums and an integer target.
Return the number of nonempty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] > Min value + max value <= target (3 + 3 <= 9)
[3,5] > (3 + 5 <= 9)
[3,5,6] > (3 + 6 <= 9)
[3,6] > (3 + 6 <= 9)
Example 2:
Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
Example 3:
Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 nonempty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63  2 = 61).
Example 4:
Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All nonempty subset satisfy the condition (2^7  1) = 127
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6
Solution
/**
Sort input A first,
For each A[i], find out the maximum A[j]
that A[i] + A[j] <= target.
For each elements in the subarray A[i+1] ~ A[j],
we can pick or not pick,
so there are 2 ^ (j  i) subsequences in total.
So we can update res = (res + 2 ^ (j  i)) % mod.
We don't care the original elements order,
we only want to know the count of sub sequence.
So we can sort the original A, and the result won't change.
*/
class Solution {
public int numSubseq(int[] nums, int target) {
int count = 0;
int mod = (int) 1e9 + 7;
Arrays.sort(nums);
int[] pows = new int[nums.length];
pows[0] = 1;
for (int i = 1; i < nums.length; i++) {
pows[i] = pows[i  1] * 2 % mod;
}
int left = 0, right = nums.length  1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
count += pows[right  left];
count %= mod;
left++;
} else {
right;
}
}
return count % mod;
}
}