- 2020-09-16
- 2020-09-24
- 2020-09-27
- 2020-09-28
- 2020-09-29
2020-09-16
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
Description
Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.
Example 1:
Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.
Example 2:
Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0
Example 3:
Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3
Example 4:
Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2
Constraints:
1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5
Solution
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length;
int n = mat[0].length;
int[][] sum = new int[m + 1][n + 1];
int res = 0;
int len = 1; // square side length
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1];
if (i >= len && j >= len && sum[i][j] - sum[i-len][j] - sum[i][j-len] + sum[i-len][j-len] <= threshold)
res = len++;
}
}
return res;
}
}
Binary Search
class Solution {
int m, n;
public int maxSideLength(int[][] mat, int threshold) {
m = mat.length;
n = mat[0].length;
int[][] sum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1];
}
}
int lo = 0, hi = Math.min(m, n);
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (isSquareExist(sum, threshold, mid)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return hi;
}
private boolean isSquareExist(int[][] sum, int threshold, int len) {
for (int i = len; i <= m; i++) {
for (int j = len; j <= n; j++) {
if (sum[i][j] - sum[i-len][j] - sum[i][j-len] + sum[i-len][j-len] <= threshold) return true;
}
}
return false;
}
}
870. Advantage Shuffle
Description
Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].
Return any permutation of A that maximizes its advantage with respect to B.
Example 1:
Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]
Example 2:
Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]
Note:
1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
Solution
class Solution {
public int[] advantageCount(int[] A, int[] B) {
Arrays.sort(A);
int len = A.length;
int[] res = new int[len];
PriorityQueue<int[]> pq = new PriorityQueue<>(len, (a, b) -> (b[1] - a[1]));
for (int i = 0; i < len; i++) {
pq.offer(new int[]{i, B[i]});
}
int lo = 0, hi = len - 1;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int index = cur[0], val = cur[1];
if (A[hi] > val) {
res[index] = A[hi--];
} else {
res[index] = A[lo++];
}
}
return res;
}
}
1381. Design a Stack With Increment Operation
Description
Design a stack which supports the following operations.
Implement the CustomStack class:
CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
void push(int x) Adds x to the top of the stack if the stack hasn't reached the maxSize.
int pop() Pops and returns the top of stack or -1 if the stack is empty.
void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.
Example 1:
Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1); // stack becomes [1]
customStack.push(2); // stack becomes [1, 2]
customStack.pop(); // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2); // stack becomes [1, 2]
customStack.push(3); // stack becomes [1, 2, 3]
customStack.push(4); // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100); // stack becomes [101, 102, 103]
customStack.increment(2, 100); // stack becomes [201, 202, 103]
customStack.pop(); // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop(); // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop(); // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop(); // return -1 --> Stack is empty return -1.
Constraints:
1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
At most 1000 calls will be made to each method of increment, push and pop each separately.
Solution
class CustomStack {
int[] stack;
//pointer is the next empty slot.
int pointer;
int max_size;
public CustomStack(int maxSize) {
stack = new int[maxSize];
pointer = 0;
max_size = maxSize;
}
public void push(int x) {
if(pointer==max_size){
return;
}
stack[pointer++] = x;
}
public int pop() {
if(pointer==0){
return -1;
}else{
return stack[--pointer];
}
}
public void increment(int k, int val) {
int size = Math.min(k,pointer);
for(int i = 0;i<size;i++){
stack[i] += val;
}
}
}
1200. Minimum Absolute Difference
Description
Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.
Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows
a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr
Example 1:
Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.
Example 2:
Input: arr = [1,3,6,10,15]
Output: [[1,3]]
Example 3:
Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]
Constraints:
2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6
Solution
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
int min = Integer.MAX_VALUE;
for (int i = 1; i < arr.length; i++) {
min = Math.min(min, arr[i] - arr[i - 1]);
}
List<List<Integer>> res = new ArrayList<>();
for (int i = 1; i < arr.length; i++) {
if (arr[i] - arr[i - 1] == min) {
List<Integer> pair = new ArrayList<>();
pair.add(arr[i - 1]);
pair.add(arr[i]);
res.add(pair);
}
}
return res;
}
}
389. Find the Difference
Description
Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.
Solution
class Solution {
public char findTheDifference(String s, String t) {
int[] dict = new int[26];
for(int i = 0;i<s.length();i++){
dict[s.charAt(i)-'a']++;
}
for(int i = 0;i<t.length();i++){
if(--dict[t.charAt(i)-'a'] <0 ){
return t.charAt(i);
}
}
return '0';
}
}
196. Delete Duplicate Emails
Description
Write a SQL query to delete all duplicate email entries in a table named Person, keeping only unique emails based on its smallest Id.
+----+------------------+
| Id | Email |
+----+------------------+
| 1 | john@example.com |
| 2 | bob@example.com |
| 3 | john@example.com |
+----+------------------+
Id is the primary key column for this table.
For example, after running your query, the above Person table should have the following rows:
+----+------------------+
| Id | Email |
+----+------------------+
| 1 | john@example.com |
| 2 | bob@example.com |
+----+------------------+
Solution
delete from Person where id not in(
select t.id from (
select min(id) as id from Person group by email
) as t
)
507. Perfect Number
Description
We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.
Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.
Example:
Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14
Note: The input number n will not exceed 100,000,000. (1e8)
Solution
public class Solution {
public boolean checkPerfectNumber(int num) {
if (num == 1) return false;
int sum = 0;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
sum += i + num / i;
}
}
sum++;
return sum == num;
}
}
2020-09-24
1215. Stepping Numbers
Description
A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a Stepping Number while 421 is not.
Given two integers low and high, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.
Example 1:
Input: low = 0, high = 21
Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]
Constraints:
0 <= low <= high <= 2 * 10^9
Solution
class Solution {
public List<Integer> countSteppingNumbers(int low, int high) {
List<Integer> list = new ArrayList();
for (long i = 0; i <= 9; i++) {
dfs(low, high, i, list);
}
list.sort(Integer::compareTo);
return list;
}
private void dfs(int low, int high, long cur, List<Integer> list) {
if (cur >= low && cur <= high) {
list.add((int) cur);
}
if (cur == 0 || cur > high) {
return;
}
long last = cur % 10, inc = cur * 10 + last + 1, dec = cur * 10 + last - 1;
if (last == 0) {
dfs(low, high, inc, list);
} else if (last == 9) {
dfs(low, high, dec, list);
} else {
dfs(low, high, inc, list);
dfs(low, high, dec, list);
}
}
}
358. Rearrange String k Distance Apart
Description
Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.
All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".
Example 1:
Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least distance 3 from each other.
Example 2:
Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.
Example 3:
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least distance 2 from each other.
Solution
/**
Using waitQueue to temp store the char that's unabailable.
give it back k steps later
*/
class Solution {
public String rearrangeString(String s, int k) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(26, (a, b) -> (b[1] - a[1]));
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
pq.offer(new int[]{i, count[i]});
}
}
StringBuilder sb = new StringBuilder();
Queue<int[]> waitQueue = new LinkedList<>();
while (!pq.isEmpty()) {
int[] cur = pq.poll();
sb.append((char) (cur[0] + 'a'));
cur[1]--;
waitQueue.offer(cur);
if (waitQueue.size() < k) {
continue;
}
int[] front = waitQueue.poll();
if (front[1] > 0) {
pq.offer(front);
}
}
return sb.length() == s.length() ? sb.toString() : "";
}
}
425. Word Squares
Description
Given a set of words (without duplicates), find all word squares you can build from them.
A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).
For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.
b a l l
a r e a
l e a d
l a d y
Note:
There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
Each word contains only lowercase English alphabet a-z.
Example 1:
Input:
["area","lead","wall","lady","ball"]
Output:
[
[ "wall",
"area",
"lead",
"lady"
],
[ "ball",
"area",
"lead",
"lady"
]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Example 2:
Input:
["abat","baba","atan","atal"]
Output:
[
[ "baba",
"abat",
"baba",
"atan"
],
[ "baba",
"abat",
"baba",
"atal"
]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Solution
public class Solution {
class TrieNode {
List<String> startWith;
TrieNode[] children;
TrieNode() {
startWith = new ArrayList<>();
children = new TrieNode[26];
}
}
class Trie {
TrieNode root;
Trie(String[] words) {
root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char ch : w.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null) {
cur.children[idx] = new TrieNode();
}
cur.children[idx].startWith.add(w);
cur = cur.children[idx];
}
}
}
List<String> findByPrefix(String prefix) {
List<String> ans = new ArrayList<>();
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null) {
return ans;
}
cur = cur.children[idx];
}
ans.addAll(cur.startWith);
return ans;
}
}
public List<List<String>> wordSquares(String[] words) {
Trie root = new Trie(words);
List<List<String>> res = new ArrayList<>();
List<String> temp = new ArrayList<>();
int len = words[0].length();
for (String word : words) {
temp.add(word);
helper(root, temp, res, len);
temp.remove(0);
}
return res;
}
private void helper(Trie root, List<String> temp, List<List<String>> res, int len) {
if (temp.size() == len) {
res.add(new ArrayList<>(temp));
return;
}
int idx = temp.size();
StringBuilder sb = new StringBuilder();
for (String word : temp) {
sb.append(word.charAt(idx));
}
String startWith = sb.toString();
List<String> candidates = root.findByPrefix(startWith);
for (String word : candidates) {
temp.add(word);
helper(root, temp, res, len);
temp.remove(temp.size() - 1);
}
}
}
266. Palindrome Permutation
Description
Given a string, determine if a permutation of the string could form a palindrome.
Example 1:
Input: "code"
Output: false
Example 2:
Input: "aab"
Output: true
Example 3:
Input: "carerac"
Output: true
Solution
class Solution {
public boolean canPermutePalindrome(String s) {
Set<Character> set = new HashSet<Character>();
for (char c:s.toCharArray()) {
if (set.contains(c)) {
set.remove(c);
}else{
set.add(c);
}
}
return set.size() <= 1;
}
}
267. Palindrome Permutation II
Description
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
Example 1:
Input: "aabb"
Output: ["abba", "baab"]
Example 2:
Input: "abc"
Output: []
Solution
class Solution {
public List<String> generatePalindromes(String s) {
List<String> ans = new ArrayList<>();
int[] count = new int[256];
boolean hasOdd = false;
Character oddChar = null;
for (char c : s.toCharArray()) {
count[c]++;
}
for (int i = 0; i < count.length; i++) {
if (count[i] % 2 != 0) {
if (hasOdd) {
return new ArrayList<>();
} else {
hasOdd = true;
oddChar = (char) i;
count[i]--;
}
}
}
generate(ans, count, (oddChar != null ? "" + oddChar : ""), s.length());
return ans;
}
private void generate(List<String> ans, int[] count, String build, int len) {
for (int idx = 0; idx < count.length; idx++) {
if (count[idx] > 0) {
count[idx] -= 2;
generate(ans, count, ((char) idx) + build + ((char) idx), len);
count[idx] += 2;
}
}
if (build.length() == len) {
ans.add(build);
}
}
}
298. Binary Tree Longest Consecutive Sequence
Description
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
Example 1:
Input:
1
\
3
/ \
2 4
\
5
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.
Example 2:
Input:
2
\
3
/
2
/
1
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.
Solution
public class Solution {
private int max = 0;
public int longestConsecutive(TreeNode root) {
if (root == null) {
return 0;
}
helper(root, 0, root.val);
return max;
}
public void helper(TreeNode root, int cur, int target) {
if (root == null) {
return;
}
if (root.val == target) {
cur++;
} else {
cur = 1;
}
max = Math.max(cur, max);
helper(root.left, cur, root.val + 1);
helper(root.right, cur, root.val + 1);
}
}
2020-09-27
265. Paint House II
Description
There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.
Note:
All costs are positive integers.
Example:
Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5;
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.
Follow up:
Could you solve it in O(nk) runtime?
###Solution
/**
use an array minValue to store three items: min, second min and min's color
so for the next house:
1. if we choose to paint any color except the same as previous min(third item in the array):
cost + previous min
2. if choose previous min color, then second min + cost.
*/
class Solution {
public int minCostII(int[][] costs) {
if(costs==null || costs.length==0 || costs[0].length==0){
return 0;
}
int n = costs.length, k = costs[0].length;
int[][] minValue = new int[n][3];
minValue[0][0] = Integer.MAX_VALUE;
minValue[0][1] = Integer.MAX_VALUE;
for (int i = 0; i < k; i++) {
if(costs[0][i] < minValue[0][0]){
minValue[0][1] = minValue[0][0];
minValue[0][0] = costs[0][i];
minValue[0][2] = i;
}else if(costs[0][i] < minValue[0][1]){
minValue[0][1] = costs[0][i];
}
}
for (int i = 1; i < n; i++) {
minValue[i][0] = Integer.MAX_VALUE;
minValue[i][1] = Integer.MAX_VALUE;
for (int j = 0; j < k; j++) {
int cost = costs[i][j];
int min = Integer.MAX_VALUE;
if(minValue[i-1][2]==j){
min = Math.min(min,cost+minValue[i-1][1]);
}else{
min = Math.min(min,cost+minValue[i-1][0]);
}
if(min < minValue[i][0]){
minValue[i][1] = minValue[i][0];
minValue[i][0] = min;
minValue[i][2] = j;
}else if(min < minValue[i][1]){
minValue[i][1] = min;
}
}
}=
return minValue[n-1][0];
}
}
842. Split Array into Fibonacci Sequence
Description
Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].
Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:
0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
F.length >= 3;
and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.
Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.
Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.
Example 1:
Input: "123456579"
Output: [123,456,579]
Example 2:
Input: "11235813"
Output: [1,1,2,3,5,8,13]
Example 3:
Input: "112358130"
Output: []
Explanation: The task is impossible.
Example 4:
Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.
Example 5:
Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.
Note:
1 <= S.length <= 200
S contains only digits.
Solution
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> splitIntoFibonacci(String S) {
List<Integer> ans = new ArrayList<>();
helper(S, ans, 0);
return ans;
}
public boolean helper(String s, List<Integer> ans, int idx) {
if (idx == s.length() && ans.size() >= 3) {
return true;
}
for (int i = idx; i < s.length(); i++) {
if (s.charAt(idx) == '0' && i > idx) {
break;
}
long num = Long.parseLong(s.substring(idx, i + 1));
if (num > Integer.MAX_VALUE) {
break;
}
int size = ans.size();
// early termination
if (size >= 2 && num > ans.get(size - 1) + ans.get(size - 2)) {
break;
}
if (size <= 1 || num == ans.get(size - 1) + ans.get(size - 2)) {
ans.add((int) num);
// branch pruning. if one branch has found fib seq, return true to upper call
if (helper(s, ans, i + 1)) {
return true;
}
ans.remove(ans.size() - 1);
}
}
return false;
}
}
1062. Longest Repeating Substring
Description
Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.
Example 1:
Input: S = "abcd"
Output: 0
Explanation: There is no repeating substring.
Example 2:
Input: S = "abbaba"
Output: 2
Explanation: The longest repeating substrings are "ab" and "ba", each of which occurs twice.
Example 3:
Input: S = "aabcaabdaab"
Output: 3
Explanation: The longest repeating substring is "aab", which occurs 3 times.
Example 4:
Input: S = "aaaaa"
Output: 4
Explanation: The longest repeating substring is "aaaa", which occurs twice.
Constraints:
The string S consists of only lowercase English letters from 'a' - 'z'.
1 <= S.length <= 1500
Solution
class Solution {
public int longestRepeatingSubstring(String S) {
int l = S.length();
int[][] dp = new int[l + 1][l + 1];
int res = 0;
for (int i = 1; i <= l; i++) {
for (int j = i + 1; j <= l; j++) {
if (S.charAt(i - 1) == S.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
res = Math.max(dp[i][j], res);
}
}
}
return res;
}
}
276. Paint Fence
Description
There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.
Note:
n and k are non-negative integers.
Example:
Input: n = 3, k = 2
Output: 6
Explanation: Take c1 as color 1, c2 as color 2. All possible ways are:
post1 post2 post3
----- ----- ----- -----
1 c1 c1 c2
2 c1 c2 c1
3 c1 c2 c2
4 c2 c1 c1
5 c2 c1 c2
6 c2 c2 c1
Solution
class Solution {
public int numWays(int n, int k) {
if (n == 0 || k == 0) {
return 0;
}
if (n == 1) {
return k;
}
// same[i] means the ith post has the same color with the (i-1)th post.
int[] same = new int[n];
// diff[i] means the ith post has a different color with the (i-1)th post.
int[] diff = new int[n];
same[0] = same[1] = k;
diff[0] = k;
diff[1] = k * (k - 1);
for (int i = 2; i < n; ++i) {
same[i] = diff[i - 1];
diff[i] = (k - 1) * (same[i - 1] + diff[i - 1]);
}
return same[n - 1] + diff[n - 1];
}
}
298. Binary Tree Longest Consecutive Sequence
Description
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
Example 1:
Input:
1
\
3
/ \
2 4
\
5
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.
Example 2:
Input:
2
\
3
/
2
/
1
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.
Solution
public class Solution {
//min length would be root itself which is 1.
private int max = 1;
public int longestConsecutive(TreeNode root) {
if (root == null) {
return 0;
}
helper(root);
return max;
}
//return the max length of consequtive.
public int helper(TreeNode root) {
if (root.left == null && root.right == null) {
return 1;
}
int max_local = 1;
if (root.left != null) {
int resLeft = helper(root.left);
if(root.left.val==root.val+1){
max_local = Math.max(max_local,resLeft+1);
}
}
if (root.right != null) {
int resRight = helper(root.right);
if(root.right.val==root.val+1){
max_local = Math.max(max_local,resRight+1);
}
}
this.max = Math.max(this.max,max_local);
return max_local;
}
}
1120. Maximum Average Subtree
Description
Given the root of a binary tree, find the maximum average value of any subtree of that tree.
(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)
Example 1:
Input: [5,6,1]
Output: 6.00000
Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.
Note:
The number of nodes in the tree is between 1 and 5000.
Each node will have a value between 0 and 100000.
Answers will be accepted as correct if they are within 10^-5 of the correct answer.
Solution
class Solution {
Double max;
public double maximumAverageSubtree(TreeNode root) {
max = 0d;
helper(root);
return max;
}
public int[] helper(TreeNode root) {
if (root.left == null && root.right == null) {
this.max = Math.max(max, root.val);
return new int[]{root.val, 1};
}
int sum = root.val, count = 1;
if (root.left != null) {
int[] res_left = helper(root.left);
sum += res_left[0];
count += res_left[1];
}
if (root.right != null) {
int[] res_right = helper(root.right);
sum += res_right[0];
count += res_right[1];
}
this.max = Math.max(max, (double) sum / (double) count);
return new int[]{sum, count};
}
}
2020-09-28
742. Closest Leaf in a Binary Tree
Description
Given a binary tree where every node has a unique value, and a target key k, find the value of the nearest leaf node to target k in the tree.
Here, nearest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.
In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.
Example 1:
Input:
root = [1, 3, 2], k = 1
Diagram of binary tree:
1
/ \
3 2
Output: 2 (or 3)
Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.
Example 2:
Input:
root = [1], k = 1
Output: 1
Explanation: The nearest leaf node is the root node itself.
Example 3:
Input:
root = [1,2,3,4,null,null,null,5,null,6], k = 2
Diagram of binary tree:
1
/ \
2 3
/
4
/
5
/
6
Output: 3
Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.
Note:
root represents a binary tree with at least 1 node and at most 1000 nodes.
Every node has a unique node.val in range [1, 1000].
There exists some node in the given binary tree for which node.val == k.
Solution
class Solution {
int min_dist;
int min_val;
public int findClosestLeaf(TreeNode root, int k) {
HashMap<Integer, Integer> dist = new HashMap<>();
min_dist = Integer.MAX_VALUE;
findTarget(root, dist, k);
System.out.println(dist);
findMinDist(root, dist, 0);
return min_val;
}
private int findTarget(TreeNode root, HashMap<Integer, Integer> dist, int target) {
if (root == null) {
return -1;
}
if (root.val == target) {
dist.put(root.val, 0);
return 0;
}
if (root.left != null) {
int res_left = findTarget(root.left, dist, target);
if (res_left != -1) {
dist.put(root.val, res_left + 1);
return res_left + 1;
}
}
if (root.right != null) {
int res_right = findTarget(root.right, dist, target);
if (res_right != -1) {
dist.put(root.val, res_right + 1);
return res_right + 1;
}
}
return -1;
}
private void findMinDist(TreeNode root, HashMap<Integer, Integer> dist, int level) {
if (root == null) {
return;
}
if (dist.containsKey(root.val)) {
level = dist.get(root.val);
}
if (root.left == null && root.right == null) {
if (min_dist > level) {
min_dist = level;
min_val = root.val;
}
}
findMinDist(root.left, dist, level + 1);
findMinDist(root.right, dist, level + 1);
}
}
2020-09-29
302. Smallest Rectangle Enclosing Black Pixels
Description
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
Example:
Input:
[
"0010",
"0110",
"0100"
]
and x = 0, y = 2
Output: 6
Solution
class Solution {
int[][] dirs = new int[][][[0, 1}, {0, -1}, {1, 0}, {-1, 0]];
int leftMost, rightMost, top, btm;
public int minArea(char[][] image, int x, int y) {
int rowLen = image.length, colLen = image[0].length;
leftMost = colLen - 1;
rightMost = 0;
top = rowLen - 1;
btm = 0;
dfs(image, x, y);
return (rightMost - leftMost + 1) * (btm - top + 1);
}
private void dfs(char[][] image, int x, int y) {
leftMost = Math.min(leftMost, y);
rightMost = Math.max(rightMost, y);
top = Math.min(top, x);
btm = Math.max(btm, x);
image[x][y] = 0;
for (int[] dir : dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx < 0 || nx >= image.length || ny < 0 || ny >= image[nx].length || image[nx][ny] != '1') {
continue;
}
dfs(image, nx, ny);
}
image[x][y] = 1;
}
}
1156. Swap For Longest Repeated Character Substring
Description
Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.
Example 1:
Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.
Example 2:
Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.
Example 3:
Input: text = "aaabbaaa"
Output: 4
Example 4:
Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.
Example 5:
Input: text = "abcdef"
Output: 1
Constraints:
1 <= text.length <= 20000
text consist of lowercase English characters only.
Solution
class Solution {
public int maxRepOpt1(String text) {
int[] freq = new int[26];
List<int[]> groups = new ArrayList<>();
int left = 0;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
freq[c - 'a']++;
if (text.charAt(left) != c) {
groups.add(new int[]{text.charAt(left), i - left});
left = i;
}
}
groups.add(new int[]{text.charAt(left), text.length() - left});
int max_len = 0;
int size = groups.size();
for (int i = 0; i < size; i++) {
int len = groups.get(i)[1];
char c = (char)groups.get(i)[0];
if(i+2 < size && groups.get(i+2)[0]==c && groups.get(i+1)[1]==1){
len += groups.get(i+2)[1];
}
if(freq[c-'a'] > len){
max_len = Math.max(max_len,len+1);
}else{
max_len = Math.max(max_len,len);
}
}
return max_len;
}
}