- 2020-08-02
- 2020-08-03
- 2020-08-04
- 2020-08-10
- 2020-08-11
- 2020-08-13
2020-08-02
1423. Maximum Points You Can Obtain from Cards
Description
There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.
In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.
Your score is the sum of the points of the cards you have taken.
Given the integer array cardPoints and the integer k, return the maximum score you can obtain.
Example 1:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.
Example 2:
Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.
Example 3:
Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.
Example 4:
Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1.
Example 5:
Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202
Constraints:
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
Solution
/**
Main idea is to find the min value continuous subarray that with length cardPoints.length-k.
DP also works, but slow and timed pout for this question.
*/
class Solution {
public int maxScore(int[] cardPoints, int k) {
int len = cardPoints.length - k;
int running_min = 0;
int sum = 0;
for(int i = 0;i<len;i++){
sum += cardPoints[i];
running_min += cardPoints[i];
}
int min_value = running_min;
for (int i = len; i < cardPoints.length; i++) {
sum += cardPoints[i];
running_min += cardPoints[i];
running_min -= cardPoints[i - len];
min_value = Math.min(min_value,running_min);
}
return sum - min_value;
}
}
1027. Longest Arithmetic Sequence
Description
Given an array A of integers, return the length of the longest arithmetic subsequence in A.
Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).
Example 1:
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].
Note:
2 <= A.length <= 2000
0 <= A[i] <= 10000
Solution
class Solution {
public int longestArithSeqLength(int[] A) {
//<index,<diff,length>>
//for array ending at <index>, the length of an array that ending with A[index]
//and with diff <diff>
HashMap<Integer, Integer>[] dp = new HashMap[A.length];
int max_length = 0;
//loop from the beginning.
for (int j = 0; j < A.length; j++) {
dp[j]= new HashMap<>(j);
//for all numbers that is before.
for (int i = 0; i < j; i++) {
//the diff between.
int diff = A[j] - A[i];
//get the max length with pre and cur, if not exist, then the length will be 2.
int pre_length = dp[i].getOrDefault(diff,1)+1;
//no need to check if j already contains diff
dp[j].put(diff,pre_length);
max_length = Math.max(max_length,pre_length);
}
}
return max_length;
}
}
1429. First Unique Number
Description
You have a queue of integers, you need to retrieve the first unique integer in the queue.
Implement the FirstUnique class:
FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
void add(int value) insert value to the queue.
Example 1:
Input:
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5); // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2); // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3); // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1
Example 2:
Input:
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:
[null,-1,null,null,null,null,null,17]
Explanation:
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17); // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17
Example 3:
Input:
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output:
[null,809,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809); // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -1
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^8
1 <= value <= 10^8
At most 50000 calls will be made to showFirstUnique and add.
Solution
class FirstUnique {
LinkedHashSet<Integer> unique;
HashSet<Integer> nonUnique;
public FirstUnique(int[] nums) {
unique = new LinkedHashSet<Integer>(nums.length);
nonUnique = new LinkedHashSet<Integer>(nums.length);
for(int num:nums){
add(num);
}
}
public int showFirstUnique() {
if(unique.isEmpty()){
return -1;
}
return unique.iterator().next();
}
public void add(int value) {
if(!unique.contains(value) && !nonUnique.contains(value)){
unique.add(value);
}else if(unique.contains(value)){
unique.remove(value);
nonUnique.add(value);
}
}
}
DoubleLinkedLIst + HashMap
DoubleLinkedLIst to store the order of unique, and HashMap to store information about the node and their position.
class FirstUnique {
class Node {
Node prev;
Node next;
int val;
public Node(int val) {
this.val = val;
}
}
Node head;
Node tail;
HashMap<Integer, Node> find;
public FirstUnique(int[] nums) {
head = new Node(0);
tail = new Node(0);
head.next = tail;
tail.prev = head;
find = new HashMap<Integer, Node>();
for (int num : nums) {
add(num);
}
}
public int showFirstUnique() {
if (head.next == tail) {
return -1;
}
return head.next.val;
}
public void add(int value) {
if (find.containsKey(value)) {
remove(find.get(value));
} else {
Node temp = new Node(value);
append(temp);
find.put(value, temp);
}
}
private boolean remove(Node node) {
//if node is not in the list
if (node.prev == null || node.next == null) {
return false;
}
Node pre = node.prev;
Node next = node.next;
pre.next = next;
next.prev = pre;
node.next = null;
node.prev = null;
return true;
}
private boolean append(Node node) {
//tail not valid.
if (tail == null || tail.prev == null) {
return false;
}
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
return true;
}
}
653. Two Sum IV - Input is a BST
Description
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
Output: False
Solution
import java.util.ArrayDeque;
class Solution {
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
ArrayDeque<TreeNode> leftArrayDeque = new ArrayDeque<TreeNode>();
ArrayDeque<TreeNode> rightArrayDeque = new ArrayDeque<TreeNode>();
initArrayDeque(leftArrayDeque, root, true);
initArrayDeque(rightArrayDeque, root, false);
while (leftArrayDeque.peek() != rightArrayDeque.peek()) {
int sum = leftArrayDeque.peek().val + rightArrayDeque.peek().val;
if (sum == k) {
return true;
} else if (sum > k) {
//find next smaller on right to reduce sum;
findNext(rightArrayDeque, false);
} else {
//find next large on left to increase sum;
findNext(leftArrayDeque, true);
}
}
return false;
}
//ex. for left, pop the previous one and push all left for its right.
private void initArrayDeque(ArrayDeque<TreeNode> arrayDeque, TreeNode node, boolean isLeft) {
TreeNode cur = node;
while (cur != null) {
arrayDeque.push(cur);
cur = isLeft ? cur.left : cur.right;
}
}
//ex. for left, pop one and go for its right, to find it's next smaller value.
private void findNext(ArrayDeque<TreeNode> arrayDeque, boolean isLeft) {
TreeNode cur = arrayDeque.pop();
if (isLeft) {
initArrayDeque(arrayDeque, cur.right, isLeft);
} else {
initArrayDeque(arrayDeque, cur.left, isLeft);
}
}
}
361. Bomb Enemy
Description
Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note: You can only put the bomb at an empty cell.
Example:
Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3
Explanation: For the given grid,
0 E 0 0
E 0 W E
0 E 0 0
Placing a bomb at (1,1) kills 3 enemies.
Solution
public class Solution {
public int maxKilledEnemies(char[][] grid) {
int m = grid.length;
int n = m != 0 ? grid[0].length : 0;
int result = 0;
int rowhits = 0;
int[] colhits = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
//for horizontal rows,
//because last one is wall, so start a new intervals that the bomb will will all E in this intervals.
if (j == 0 || grid[i][j - 1] == 'W') {
rowhits = 0;
//start counting until hit a wall or reach the end.
for (int k = j; k < n && grid[i][k] != 'W'; k++) {
rowhits += grid[i][k] == 'E' ? 1 : 0;
}
}
//for vertical cols,
//last one is wall, start a new interval.
//since we are staying with same i, so only need to store one array of length grid.length.
//and colhits[j] means there's certain hits if we place a boom at col j.
if (i == 0 || grid[i - 1][j] == 'W') {
colhits[j] = 0;
for (int k = i; k < m && grid[k][j] != 'W'; k++) {
colhits[j] += grid[k][j] == 'E' ? 1 : 0;
}
}
if (grid[i][j] == '0') {
result = Math.max(result, rowhits + colhits[j]);
}
}
}
return result;
}
}
414. Third Maximum Number
Description
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
Solution
class Solution {
public int thirdMax(int[] nums) {
Integer max1 = null;
Integer max2 = null;
Integer max3 = null;
for (Integer n : nums) {
if (n.equals(max1) || n.equals(max2) || n.equals(max3)) {
continue;
}
if (max1 == null || n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (max2 == null || n > max2) {
max3 = max2;
max2 = n;
} else if (max3 == null || n > max3) {
max3 = n;
}
}
return max3 == null ? max1 : max3;
}
}
/**
Using long can save time for boxing and unboxing and also handle the Integer.MIN_VALUE case.
*/
class Solution {
public static int thirdMax(int[] nums) {
long firstMax = Long.MIN_VALUE, secondMax = Long.MIN_VALUE, thirdMax = Long.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > firstMax) {
thirdMax = secondMax;
secondMax = firstMax;
firstMax = nums[i];
} else if (nums[i] > secondMax && nums[i] < firstMax) {
thirdMax = secondMax;
secondMax = nums[i];
} else if (nums[i] > thirdMax && nums[i] < secondMax) {
thirdMax = nums[i];
}
}
return (int) (thirdMax == Long.MIN_VALUE ? firstMax : thirdMax);
}
}
852. Peak Index in a Mountain Array
Description
Let's call an array A a mountain if the following properties hold:
A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].
Example 1:
Input: [0,1,0]
Output: 1
Example 2:
Input: [0,2,1,0]
Output: 1
Note:
3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.
Solution
class Solution {
public int peakIndexInMountainArray(int[] A) {
int left = 0, right = A.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if(A[mid]<A[mid+1]){
left = mid+1;
}else{
right = mid;
}
}
return left;
}
}
1191. K-Concatenation Maximum Sum
Description
Given an integer array arr and an integer k, modify the array by repeating it k times.
For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].
Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.
As the answer can be very large, return the answer modulo 10^9 + 7.
Example 1:
Input: arr = [1,2], k = 3
Output: 9
Example 2:
Input: arr = [1,-2,1], k = 5
Output: 2
Example 3:
Input: arr = [-1,-2], k = 7
Output: 0
Constraints:
1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4
Solution
class Solution {
int mod = (int) Math.pow(10, 9) + 7;
public int kConcatenationMaxSum(int[] ar, int k) {
//max sum subarray in single ar.
long kadanes = kadanesAlgo(ar);
if (k == 1) {
return (int) kadanes;
}
//max sum subarray for ar[0:i]
long prefixSum = prefixSum(ar);
//max sum subarray for ar[i,end]
long suffixSum = suffixSum(ar);
long sum = 0;
for (int i1 : ar) {
sum += i1;
}
if (sum > 0) {
//only when total sum is larger than 0 can we add (k-2) * sum, otherwise no need to reduce the sum.
//case 1: use the while k arr with part of the head and tail removed.
//case 2: use only one arr and return the max subarray inside it.
return (int) (Math.max(((sum * (k - 2)) % mod + suffixSum % mod + prefixSum % mod) % mod, kadanes % mod));
} else {
//case 1: use only 2 arr with part of the head and tail removed.
//case 2: use only one arr and return the max subarray inside it.
return (int) (Math.max((prefixSum % mod + suffixSum % mod) % mod, kadanes % mod));
}
}
public long kadanesAlgo(int[] ar) {
long currentSum = 0;
long maxSum = Integer.MIN_VALUE;
for (int i = 0; i < ar.length; i++) {
currentSum = currentSum > 0 ? (currentSum + ar[i]) % mod : ar[i];
maxSum = Math.max(currentSum, maxSum);
}
return maxSum < 0 ? 0 : maxSum % mod;
}
public long prefixSum(int[] ar) {
long currentSum = 0;
long maxSum = Integer.MIN_VALUE;
for (int i = 0; i < ar.length; i++) {
currentSum = (currentSum + ar[i]) % mod;
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public long suffixSum(int[] ar) {
long currentSum = 0;
long maxSum = Integer.MIN_VALUE;
for (int i = ar.length - 1; i >= 0; i--) {
currentSum = (currentSum + ar[i]) % mod;
maxSum = Math.max(currentSum, maxSum);
}
return maxSum;
}
}
2020-08-03
1312. Minimum Insertion Steps to Make a String Palindrome
Description
Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.
A Palindrome String is one that reads the same backward as well as forward.
Example 1:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.
Example 2:
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".
Example 3:
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".
Example 4:
Input: s = "g"
Output: 0
Example 5:
Input: s = "no"
Output: 1
Constraints:
1 <= s.length <= 500
All characters of s are lower case English letters.
Solution
//find the longest palidorm subsequenceq, and fill s.length - length of max subsq.
class Solution {
public int minInsertions(String s) {
int max_length = longestPalindromeSubseq(s);
return s.length()-max_length;
}
public int longestPalindromeSubseq(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[] pre = new int[len];
for (int i = len - 1; i >= 0; i--) {
int[] dp = new int[len];
dp[i] = 1;
for (int j = i + 1; j < len; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[j] = pre[j - 1] + 2;
} else {
dp[j] = Math.max(pre[j], dp[j - 1]);
}
}
pre = dp;
}
return pre[len - 1];
}
}
592. Fraction Addition and Subtraction
Description
Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.
Example 1:
Input:"-1/2+1/2"
Output: "0/1"
Example 2:
Input:"-1/2+1/2+1/3"
Output: "1/3"
Example 3:
Input:"1/3-1/2"
Output: "-1/6"
Example 4:
Input:"5/3+1/3"
Output: "2/1"
Note:
The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
The number of given fractions will be in the range [1,10].
The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.
Solution
/**
The (?=) part is a zero-width positive lookahead. Since [-,+] means - or +, the regex (?=[-,+]) means the next element is either - or +.
Since | is logical or operator, "/|(?=[-+])" means the element is "/", or the next element is either - or +.
*/
class Solution {
public String fractionAddition(String expression) {
String[] expres = expression.split("/|(?=[+-])");
int index = 0;
int A=0,B=1;
while(index < expres.length){
int a = Integer.parseInt(expres[index++]);
int b = Integer.parseInt(expres[index++]);
A = A*b + B*a;
B = B*b;
int div = gcd(A,B);
A/=div;
B/=div;
}
return A+"/"+B;
}
public int gcd(int a, int b){
if(b==0){
return Math.abs(a);
}else{
return gcd(b,a%b);
}
}
}
827. Making A Large Island
Description
In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).
Example 1:
Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
Notes:
1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.
Solution
/**
dfs all islands and asign it an index, store the size of the island.
after dfs, gothrough all cell with 1, set it to 1, and find its 4 directions to combine all island.
the size will be sum(4 island adjacent to cell) + 1.
return max.
*/
class Solution {
int[][] dirs = new int[][][[0, 1], [0, -1], [1, 0], [-1, 0]];
public int largestIsland(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
boolean[][] visited = new boolean[n][m];
HashMap<String, Integer> pos2Idx = new HashMap<>();
HashMap<Integer, Integer> islandSize = new HashMap<>();
int max_size = 0;
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
int size = dfs(grid, visited, i, j, pos2Idx, index);
max_size = Math.max(max_size, size);
islandSize.put(index, size);
index++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) {
HashSet<Integer> neighbor = new HashSet<>();
for (int[] dir : dirs) {
int next_i = i + dir[0];
int next_j = j + dir[1];
if (next_i >= 0 && next_i < grid.length && next_j >= 0 && next_j < grid[0].length
&& grid[next_i][next_j] == 1) {
neighbor.add(pos2Idx.get(next_i + " " + next_j));
}
}
int temp_size = 1;
for (int island : neighbor) {
temp_size += islandSize.get(island);
}
max_size = Math.max(max_size, temp_size);
}
}
}
return max_size;
}
public int dfs(int[][] grid, boolean[][] visited, int i, int j, HashMap<String, Integer> pos2Idx, int index) {
int count = 1;
visited[i][j] = true;
pos2Idx.put(i + " " + j, index);
for (int[] dir : dirs) {
int next_i = i + dir[0];
int next_j = j + dir[1];
if (next_i >= 0 && next_i < grid.length && next_j >= 0 && next_j < grid[0].length
&& grid[next_i][next_j] == 1 && !visited[next_i][next_j]) {
count += dfs(grid, visited, next_i, next_j, pos2Idx, index);
}
}
return count;
}
}
630. Course Schedule III
Description
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
Example:
Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation:
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.
Note:
The integer 1 <= d, t, n <= 10,000.
You can't take two courses simultaneously.
Solution
/**
* Approach:
* Sort courses by the end date, this way, when we're iterating through the courses, we can switch out any previous course with the current one without worrying about end date.
*
* Next, we iterate through each course, if we have enough days, we'll add it to our priority queue. If we don't have enough days, then we can either
* 2.1 ignore this course OR
* 2.2 We can replace this course with the longest course we added earlier.
*/
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses, (a, b) -> (Integer.compare(a[1], b[1])));
PriorityQueue<Integer> pq = new PriorityQueue<>(courses.length, (a, b) -> Integer.compare(b, a));
int sum = 0;
for (int[] course : courses) {
int time = course[0];
int ddl = course[1];
pq.offer(time);
sum += time;
while(sum > ddl){
sum -= pq.poll();
}
}
return pq.size();
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.scheduleCourse(new int[][]{}));
}
}
2020-08-04
1262. Greatest Sum Divisible by Three
Description
Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.
Example 1:
Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).
Example 2:
Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.
Example 3:
Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).
Constraints:
1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4
Solution
/**
dp[i] stand for max sum that mod to i [0,1,2].
*/
class Solution {
public int maxSumDivThree(int[] nums) {
int[] dp = new int[]{0, Integer.MIN_VALUE, Integer.MIN_VALUE};
for (int num : nums) {
int[] temp = new int[3];
for (int i = 0; i < 3; i++) {
temp[(i + num) % 3] = Math.max(dp[(i + num) % 3], dp[i] + num);
}
dp = temp;
}
return dp[0];
}
}
2020-08-10
1190. Reverse Substrings Between Each Pair of Parentheses
Description
You are given a string s that consists of lower case English letters and brackets.
Reverse the strings in each pair of matching parentheses, starting from the innermost one.
Your result should not contain any brackets.
Example 1:
Input: s = "(abcd)"
Output: "dcba"
Example 2:
Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.
Example 3:
Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.
Example 4:
Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"
Constraints:
0 <= s.length <= 2000
s only contains lower case English characters and parentheses.
It's guaranteed that all parentheses are balanced.
Solution
class Solution {
public String reverseParentheses(String s) {
ArrayDeque<String> stack = new ArrayDeque<>();
StringBuilder temp = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(temp.toString());
temp=new StringBuilder();
} else if (c == ')') {
String p= stack.pop();
temp.reverse().insert(0,p);
}else{
temp.append(c);
}
}
return temp.toString();
}
}
665. Non-decreasing Array
Description
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
Example 1:
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.
Solution
/**
Key idea: two case by comparing nums[i-2] and nums[i]
a[i - 2] <= a[i] -> lower a[i-1]
a[i - 2] > a[i] -> rise a[i]
*/
class Solution {
public boolean checkPossibility(int[] a) {
int modified = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] < a[i - 1]) {
if (modified++ > 0) {
return false;
}
if (i - 2 < 0 || a[i - 2] <= a[i]) {
a[i - 1] = a[i]; // lower a[i - 1]
} else {
a[i] = a[i - 1]; // rise a[i]
}
}
}
return true;
}
}
408. Valid Word Abbreviation
Description
Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.
A string such as "word" contains only the following valid abbreviations:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".
Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.
Example 1:
Given s = "internationalization", abbr = "i12iz4n":
Return true.
Example 2:
Given s = "apple", abbr = "a2e":
Return false.
Solution
class Solution {
public boolean validWordAbbreviation(String word, String abbr) {
int wordLen = word.length();
int abbrLen = abbr.length();
int i = 0, j = 0;
while (i < wordLen && j < abbrLen) {
//if the same, move to next.
if (word.charAt(i) == abbr.charAt(j)) {
i++;
j++;
continue;
}
//if the first digit in the number is 0, also invalid
//case: 01 -> a in invalid.
if (abbr.charAt(j) == '0' || !Character.isDigit(abbr.charAt(j))) {
return false;
}
int num =0;
//keep counting the number
while (j < abbrLen && Character.isDigit(abbr.charAt(j))) {
num *= 10;
num += abbr.charAt(j)-'0';
j++;
}
i += num;
}
return i == wordLen && j == abbrLen;
}
}
2020-08-11
829. Consecutive Numbers Sum
Description
Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?
Example 1:
Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3
Example 2:
Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4
Example 3:
Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Note: 1 <= N <= 10 ^ 9.
Solution
/**
Key point: sum = n*(n+1)/2 + n * offset
try every n so offset is integer.5
*/
class Solution {
public int consecutiveNumbersSum(int N) {
int count = 1;
int n = 2;
while (true) {
int sum = n * (n + 1) / 2;
if (sum > N) {
break;
}
if((N-sum)%n==0){
count++;
}
n++;
}
return count;
}
}
958. Check Completeness of a Binary Tree
Description
Given a binary tree, determine if it is a complete binary tree.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example 1:
Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
Example 2:
Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.
Solution
//find the total nubmer and use index to check validation.
class Solution {
public boolean isCompleteTree(TreeNode root) {
int total = countNodes(root);
return helper(root, 1, total);
}
private int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
private boolean helper(TreeNode root, int idx, int total) {
if (root == null) {
return true;
}
if (idx > total) {
return false;
}
return helper(root.left, idx * 2, total)
&& helper(root.right, idx * 2 + 1, total);
}
}
435. Non-overlapping Intervals
Description
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Note:
You may assume the interval's end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Solution
/**
Key idea: find the max length of non-overlappings
sort the array based on 1.end 2. start to greedily form non-overlappings.
*/
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> (a[1] == b[1] ? a[0]- b[0] : a[1]-b[1]));
int i = 0,count=0,end=0;
int len = intervals.length;
while (i < len) {
end = intervals[i][1];
//get rid of the intervals that overlap with the current one
//that is they start before the current end.
while(i<len && intervals[i][0]<end){
i++;
}
count++;
}
return len-count;
}
}
1202. Smallest String With Swaps
Description
You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.
You can swap the characters at any pair of indices in the given pairs any number of times.
Return the lexicographically smallest string that s can be changed to after using the swaps.
Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"
Example 2:
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"
Example 3:
Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination:
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"
Constraints:
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.
Solution
/**
Use union find to group all the groups that can swap
inside of each group, sort all the chars lexlly so it will be the min.
*/
class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int len = s.length();
int[] parent = new int[len];
Arrays.fill(parent,-1);
//union all pairs.
for(List<Integer> pair:pairs){
union(parent,pair.get(0),pair.get(1));
}
Map<Integer,List<Integer>> map=new HashMap<>();
for(int i=0;i<len;i++){
//it's non-swap, leave it.
if(parent[i]==-1){
continue;
}
//add all items to the same group.
int p = findParent(parent,i);
map.putIfAbsent(p,new ArrayList<>());
map.get(p).add(i);
}
char[] sArr = s.toCharArray();
for(List<Integer> group :map.values()){
//group is already sorted as it's added from head to tail.
List<Character> cArr = new ArrayList<>();
for(int idx:group){
cArr.add(sArr[idx]);
}
//lexicographically smallest for the char in the group.
Collections.sort(cArr);
for(int i =0;i<cArr.size();i++){
sArr[group.get(i)]=cArr.get(i);
}
}
return String.valueOf(sArr);
}
private int findParent(int[] parent, int index) {
if(parent[index]==-1){
parent[index]=index;
return index;
}
if (parent[index] != index) {
parent[index] = findParent(parent, parent[index]);
}
return parent[index];
}
private void union(int[] parent, int index1, int index2) {
int p1 = findParent(parent, index1);
int p2 = findParent(parent, index2);
if (p1 != p2) {
parent[p1] = p2;
}
}
}
290. Word Pattern
Description
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Example 1:
Input: pattern = "abba", str = "dog cat cat dog"
Output: true
Example 2:
Input:pattern = "abba", str = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
Example 4:
Input: pattern = "abba", str = "dog dog dog dog"
Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.
Solution
class Solution {
public boolean wordPattern(String pattern, String str) {
HashMap<Character,String> c2s = new HashMap<>();
HashMap<String,Character> s2c = new HashMap<>();
String[] strArr = str.split(" ");
if(pattern.length()!= strArr.length){
return false;
}
for(int i = 0;i< strArr.length;i++){
char c = pattern.charAt(i);
if(c2s.containsKey(c) && s2c.containsKey(strArr[i])){
if(!c2s.get(c).equals(strArr[i]) || s2c.get(strArr[i])!=c){
return false;
}
}else if(!c2s.containsKey(c) && !s2c.containsKey(strArr[i])){
c2s.put(c,strArr[i]);
s2c.put(strArr[i],c);
}else{
return false;
}
}
return true;
}
}
652. Find Duplicate Subtrees
Description
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.
Example 1:
1
/ \
2 3
/ / \
4 2 4
/
4
The following are two duplicate subtrees:
2
/
4
and
4
Solution
class Solution {
HashMap<String,HashSet<TreeNode>> map;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
map = new HashMap<>();
helper(root);
List<TreeNode> res = new ArrayList<>();
for(HashSet<TreeNode> set:map.values()){
if(set.size()>1){
res.add(set.iterator().next());
}
}
return res;
}
public String helper(TreeNode root) {
if (root == null) {
return "";
}
String key = root.val + " " + helper(root.left) + " " + helper(root.right);
map.putIfAbsent(key,new HashSet<>());
map.get(key).add(root);
return key;
}
}
2020-08-13
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+5-3+x=6+x-2"
Output: "x=2"
Example 2:
Input: "x=x"
Output: "Infinite solutions"
Example 3:
Input: "2x=x"
Output: "x=0"
Example 4:
Input: "2x+3x-6x=x+2"
Output: "x=-1"
Example 5:
Input: "x=x+2"
Output: "No solution"
Solution
/**
Key point is to use regex to split using +-
or can use this:
str.replace("+","#+").replace("-","#-").split("#")
but need extra take care of the "" empth string.
*/
class Solution {
public String solveEquation(String equation) {
int[] res = evaluateExpression(equation.split("=")[0]),
res2 = evaluateExpression(equation.split("=")[1]);
res[0] -= res2[0];
res[1] = res2[1] - res[1];
if (res[0] == 0 && res[1] == 0) {
return "Infinite solutions";
}
if (res[0] == 0) {
return "No solution";
}
return "x=" + String.format("%3d",res[1] / res[0]);
}
public int[] evaluateExpression(String exp) {
String[] tokens = exp.split("(?=[-+])");
int[] res = new int[2];
for (String token : tokens) {
if ("+x".equals(token) || "x".equals(token)) {
res[0] += 1;
} else if ("-x".equals(token)) {
res[0] -= 1;
} else if (token.contains("x")) {
res[0] += Integer.parseInt(token.substring(0, token.indexOf("x")));
} else {
res[1] += Integer.parseInt(token);
}
}
return res;
}
}