Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day. Given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.
1 O(nlogn)
Use the TreeSet to record the already open place
TreeSet add, delete, search O(logn)
return the first one match requirement
public int kEmptySlots(int[] flowers, int k) {
TreeSet<Integer> active = new TreeSet();
int day = 0;
for (int flower: flowers) {
day++;
active.add(flower);
Integer lower = active.lower(flower)
Integer higher = active.higher(flower);
if (lower != null && flower - lower - 1 == k ||
higher != null && higher - flower - 1 == k)
return day;
}
return -1;
}
2 O(n)
A position array, pos[x] = i means the flower x blooms at i day
fix left and right pointer, check if we can find an array [left, 1, 2,..., k, right] is valids
public int kEmptySlots(int[] flowers, int k) {
int len = flowers.length;
int[] pos = new int[len];
for(int i=0; i<len; i++){
// pos[x] = i means the flower x blooms at i day
pos[flowers[i]-1] = i+1;
}
int left = 0, right = k + 1;
for(int i=0; Math.max(i, right) < len; i++){
System.out.println(i);
if(pos[left] > pos[i] || pos[right] > pos[i]){
left = i;
right = left + k + 1;
}else if( i == right){
return Math.max(left, right);
}
}
return -1;
}
889. Construct Binary Tree from Preorder and Postorder Traversal
Return any binary tree that matches the given preorder and postorder traversals.
Example
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
find the length of left tree and use it split the left tree and right tree
Preorder and postorder left tree length are the same, and pre[1] the head of left tree, use is to find the last position in postorder
public TreeNode constructFromPrePost(int[] pre, int[] post) {
// pre [1][2,4,5][3,6,7]
// post [4,5,2][6,7,3][1]
int len = pre.length;
if(len == 0) return null;
TreeNode node = new TreeNode(pre[0]);
if(len == 1) return node;
// find out the length of left tree
int left_len = 0;
for(int i=0; i<len; i++){
if(post[i] == pre[1]) left_len = i+1;
}
node.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, 1+left_len),
Arrays.copyOfRange(post, 0, left_len));
node.right = constructFromPrePost(Arrays.copyOfRange(pre, 1+left_len, len),
Arrays.copyOfRange(post, left_len, len-1));
return node;
}
280 Wiggle Sort
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
public void wiggleSort(int[] nums) {
if (nums.length == 0) return;
for(int i=0; i<nums.length-1; i++){
if(i%2 == 0){
if(nums[i] > nums[i+1]) swap(nums, i, i+1);
}else{
if(nums[i] < nums[i+1]) swap(nums, i, i+1);
}
}
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
324 Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Copy the array and sort it, the number smaller than mid should put in odd slots; others should put in even slots.
public void wiggleSort(int[] nums) {
if (nums.length == 0) return;
int n = nums.length;
int mid = (n+1)/2;
int[] copy = Arrays.copyOf(nums, n);
Arrays.sort(copy);
// corner case [4,5,5,6] medium must be at head and tail
// put smaller than nums[mid] elements to odd slot, start from mid-1
for(int i=mid-1, j=0; i>=0; i--, j+=2) nums[j] = copy[i];
// put greater than nums[mid] elements to even slot, start from n-1
for(int i=n-1, j=1; i>=mid; i--, j+=2) nums[j] = copy[i];
}
475 Heaters
you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.
Example:
Input: [1,2,3,4],[1,4]
Output: 1
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int i=0, ans=0;
for(int house: houses){
while(i<heaters.length-1 && Math.abs(house-heaters[i]) >= Math.abs(house-heaters[i+1])){
i++;
}
ans = Math.max(ans, Math.abs(house-heaters[i]));
}
return ans;
}
656 Coin Path
Given an array(index start from 1), B is the step you can jump from index i. Return the path indexes starting from 1 to last index in array.
A next[] array to record the indexes
Statement: dp[i] is the min jumping cost starting from index i to end of array.
Func: dp[i] = min(A[i]+dp[i+B]) B <- 1:B
Ans: Loop the next[], if index == -1, then return empty list
public List<Integer> cheapestJump(int[] A, int B) {
int[] dp = new int[A.length];
int[] next = new int[A.length-1];
Arrays.fill(next, -1);
for(int i=A.length-2; i>=0; i--){
int cost = Integer.MAX_VALUE;
for(int j=i+1; j<=i+B && j<A.length; j++){
if(A[j] != -1){
if(A[i] + dp[j] < cost){
cost = A[i] + dp[j];
next[i] = j;
}
}
}
dp[i] = cost;
}
List<Integer> ans = new ArrayList<>();
int i=0;
// if i is not init means it cannot proceed
while(i<A.length-1 && i != -1){
System.out.println(i);
ans.add(i+1);
i=next[i];
}
ans.add(i+1);
if(i == -1) return new ArrayList<>();
return ans;
}
399. Evaluate Division
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Time: O(q+ q*E), q is the number of queries, E is the connecting edges. The best case of E is 1, worst is length of equations
Space: O(q)
Map<String, ArrayList<String>> pair = new HashMap<>();
Map<String, ArrayList<Double>> pairValue = new HashMap<>();
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
for(int i=0; i<equations.length; i++){
String x = equations[i][0];
String y = equations[i][1];
// update nodes connected with x
if(!pair.containsKey(x)){
pair.put(x, new ArrayList<String>());
pairValue.put(x, new ArrayList<Double>());
}
pair.get(x).add(y);
pairValue.get(x).add(values[i]);
// update nodes connected with y
if(!pair.containsKey(y)){
pair.put(y, new ArrayList<String>());
pairValue.put(y, new ArrayList<Double>());
}
pair.get(y).add(x);
pairValue.get(y).add(1/values[i]);
}
double[] ans = new double[queries.length];
for(int i=0; i<queries.length; i++){
String[] query = queries[i];
ans[i] = dfs(query[0], query[1], new HashSet<String>(), 1.0);
if(ans[i] == 0.0) ans[i] = -1.0;
}
return ans;
}
private double dfs(String start, String end, Set<String> visited, double value){
// 有環
if(visited.contains(start)) return 0.0;
if(!pair.containsKey(start)) return 0.0;
if(start.equals(end)) return value;
visited.add(start);
for(int i=0; i<pair.get(start).size(); i++){
String s = pair.get(start).get(i);
// visited.add(s);
double tmp = dfs(s, end, visited, value*pairValue.get(start).get(i));
if(tmp != 0.0) return tmp;
// visited.remove(s);
}
visited.remove(start);
return 0.0;
}
524. Longest Word in Dictionary through Deleting
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.
class Node{
String word;
int index;
public Node(String word, int index){
this.word = word;
this.index = index;
}
}
public int numMatchingSubseq(String S, String[] words) {
int count=0;
Map<Character, List<Node>> map = new HashMap<>();
// build the heads
for(int i=0; i<26; i++){
map.put((char)('a'+ i), new ArrayList<Node>());
}
// init
for(String w: words){
char c = w.charAt(0);
map.get(c).add(new Node(w, 0));
}
// loop the String s
// if index == word len means it got throght the whole word
for(char c: S.toCharArray()){
// list在loop過程中不能更動，不然會拋出ConcurrentModificationException
List<Node> list = map.get(c);
map.put(c, new ArrayList<>());
for(Node node: list){
node.index++;
if(node.index == node.word.length()) count++;
else map.get(node.word.charAt(node.index)).add(node);
}
list.clear();
}
return count;
}
835. Image Overlap
Two images A and B are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)
We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.
What is the largest possible overlap?
Count the moving vector from image A to image B
Time O(n^4)
public int largestOverlap(int[][] A, int[][] B) {
// count the moving vector from A to B
int n = A.length;
int[][] vector = new int[2*n][2*n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(A[i][j] == 1){
for(int k=0; k<n; k++){
for(int l=0; l<n; l++){
if(B[k][l] == 1) vector[k-i+n][l-j+n]+=1;
}
}
}
}
}
// count the max
int max=0;
for(int[] row: vector){
for(int num: row){
max = Math.max(max, num);
}
}
return max;
}
328. Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
There are N workers. The i-th worker has a quality[i] and a minimum wage expectation wage[i].
Now we want to hire exactly K workers to form a paid group. When hiring a group of K workers, we must pay them according to the following rules:
Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
Every worker in the paid group must be paid at least their minimum wage expectation.
Return the least amount of money needed to form a paid group satisfying the above conditions.
public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
double[][] workers = new double[quality.length][2];
for(int i=0; i<quality.length; i++){
workers[i] = new double[]{(double)wage[i]/quality[i], (double)quality[i]};
}
Arrays.sort(workers, (a,b) -> Double.compare(a[0], b[0]));
double ans = Double.MAX_VALUE;
double qualitySum = 0;
Queue<Double> maxHeap = new PriorityQueue<>();
for(double[] w: workers){
qualitySum += w[1];
maxHeap.add(-w[1]);
if(maxHeap.size() > K) qualitySum += maxHeap.poll();
if(maxHeap.size() == K) ans = Math.min(ans, qualitySum*w[0]);
}
return ans;
}
843. Guess the Word
We are given a word list of unique words, each word is 6 letters long, and one word in this list is chosen as secret.
You may call master.guess(word) to guess a word. You can not guess the word more than 10 times. The test case has 100 words in wordlist
Strategy: find a word 有最大的可猜測族群, 利用guess API縮減wordlist
public void findSecretWord(String[] wordlist, Master master) {
for(int i=0; i<10; i++){
Map<String, Integer> map = new HashMap<>();
for(String w1: wordlist){
for(String w2: wordlist){
// find a word with the least frequent varietion to others.
// The group of similar words is bigger
if(match(w1, w2) == 0) map.put(w1, map.getOrDefault(w1, 0)+1);
}
}
int min = 100;
String candidate = "";
for(Map.Entry<String, Integer> entry: map.entrySet()){
if(entry.getValue() < min){
min = entry.getValue();
candidate = entry.getKey();
}
}
if(candidate.equals("")) candidate = wordlist[0];
int diff = master.guess(candidate);
List<String> tmp = new ArrayList<>();
for(String w: wordlist){
if(match(w, candidate) == diff) tmp.add(w);
}
wordlist = tmp.toArray(new String[0]);
}
}
private int match(String s1, String s2){
int match=0;
for(int i=0; i<s1.length(); i++)
if(s1.charAt(i) == s2.charAt(i)) match++;
return match;
}
863. All Nodes Distance K in Binary Tree
We are given a binary tree (with root node root), a target node, and an integer value K.
Return a list of the values of all nodes that have a distance K from the target node.
Node分兩種，從target往上跟往下
findTarget(), 返回target跟node之間的距離
node is null
target is node
dfs計算node.left, node.right
分別根據距離addNode(), 返回距離
private List<Integer> ans;
private int K;
private TreeNode target;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
this.K= K;
this.target = target;
ans = new ArrayList<>();
findTarget(root);
return ans;
}
private int findTarget(TreeNode node){
if(node == null){
return -1;
}else if(node.val == target.val){
addNode(node, 0);
return 1;
}else{
int L = findTarget(node.left);
int R = findTarget(node.right);
// 必定在某一邊，選擇在一邊return
if(L != -1){
if(L == K) ans.add(node.val);
addNode(node.right, L+1);
return L+1;
}else if( R != -1){
if(R == K) ans.add(node.val);
addNode(node.left, R+1);
return R+1;
}else{
return -1;
}
}
}
private void addNode(TreeNode node, int dist){
if(node == null) return;
if(dist == K) ans.add(node.val);
addNode(node.left, dist+1);
addNode(node.right, dist+1);
}
858. Mirror Reflection
There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 0, 1, and 2.
The square room has walls of length p, and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor.
Return the number of the receptor that the ray meets first.
public int mirrorReflection(int p, int q) {
int m=1, n=1;
while( m*p != n*q){
n++;
m = n*q/p;
}
// if light reflection is even(n is odd), on the rhs; otherwise lhs
// if box extension is even(m is odd), on 1; otherwise on 0
if(m%2==0 && n%2==1) return 0;
if(m%2==1 && n%2==1) return 1;
if(m%2==1 && n%2==0) return 2;
return -1;
}
855. Exam Room
In an exam room, there are N seats in a single row, numbered 0, 1, 2, ..., N-1.
When a student enters the room, they must sit in the seat that maximizes the distance to the closest person
Need a dynamic sorted array, use TreeSet
比較dist分三部分
array head to first seat
seat betweens
last seat to array tail
class ExamRoom {
TreeSet<Integer> students;
int N;
public ExamRoom(int N) {
this.N = N;
students = new TreeSet<>();;
}
public int seat() {
int pos = 0;
if(students.size() > 0){
// first dist is the dist from beginning to first student
int dist = students.first();
Integer prev = null;
for(int s: students){
if(prev != null){
int tmp = (s-prev)/2;
if(tmp > dist){
dist = tmp;
pos = prev + tmp;
}
}
prev = s;
}
// test the dist from last student to end of array
if( (N-1) - students.last() > dist) pos = N-1;
}
// add pos to treeSet
students.add(pos);
return pos;
}
public void leave(int p) {
students.remove(p);
}
}
853. Car Fleet
N cars is array. Each car i has a constant speed speed[i] and initial position position[i]
A car can never pass another car ahead of it, if car A catch up car B, they are assumed to have the same position.
Return how many car fleets arrive target
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
if(position.length == 0 || speed.length == 0) return 0;
int n = position.length;
Car[] cars = new Car[n];
for(int i=0; i<n; i++){
cars[i] = new Car(position[i], (double)(target-position[i])/speed[i]);
}
Arrays.sort(cars, (a,b) -> a.pos-b.pos);
int ans = 0;
for(int i=n-1; i>0; i--){
// i較i-1早到, 自成fleet
if(cars[i].time < cars[i-1].time) ans++;
// i-1 跟i 結合成fleet, 將i的時間更新至i-1
else cars[i-1] = cars[i];
}
//有無fleet皆+1
return ans+1;
}
}
class Car{
int pos;
double time;
public Car(int pos, double time){
this.pos = pos;
this.time = time;
}
}
850. Rectangle Area II
We are given a list of (axis-aligned) rectangles. Each rectangle[i] = [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the ith rectangle.
Find the total area covered by all rectangles in the plane. Since the answer may be too large, return it modulo 10^9 + 7.
記錄每一個rectangle 在y軸上in & out的event, 並且sort by y dimention
Use sweep line to count x distance, multiple y diff
Put 'in' event in active lit, move 'out' event
// int[0]: y1/y2, int[1]: in/out, int[2]: x1, int[3]: x2
public int rectangleArea(int[][] rectangles) {
int n = rectangles.length;
List<int[]> line = new ArrayList<>();
for(int[] rec: rectangles){
line.add(new int[]{rec[1], 0, rec[0], rec[2]});
line.add(new int[]{rec[3], 1, rec[0], rec[2]});
}
// sort by y dimention
Collections.sort(line, (a,b) -> a[0] - b[0]);
int y = line.get(0)[0];
long ans = 0;
List<int[]> intervals = new ArrayList<>();
for(int i=0; i<line.size(); i++){
int[] cur = line.get(i);
long dis = getXDistance(intervals);
ans += dis*(cur[0] - y);
if(cur[1] == 0){
intervals.add(new int[]{cur[2], cur[3]});
Collections.sort(intervals, (a,b) -> a[0] - b[0]);
}else{
for(int[] tmp: intervals){
if(tmp[0] == cur[2] && tmp[1] == cur[3]){
intervals.remove(tmp);
break;
}
}
}
y = cur[0];
}
ans %= 1e9 + 7;
// if(ans < 0) ans += 1e9+7;
return (int)ans;
}
private long getXDistance(List<int[]> intervals){
long ans = 0;
int prev = -1;
for(int[] cur: intervals){
// prev 為上一個x2
prev = Math.max(prev, cur[0]);
ans += Math.max(cur[1]-prev, 0);
prev = Math.max(prev, cur[1]);
}
return ans;
}
846. Hand of Straights
Alice has a hand of cards, given as an array of integers.
Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.
Return true if and only if she can.
Use a TreeMap to record the frequency and continuous of number
public boolean isNStraightHand(int[] hand, int W) {
if (hand.length%W != 0) return false;
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int c: hand) map.put(c, map.getOrDefault(c, 0)+1);
for(int n: map.keySet()){
int iter=W;
// == 0 代表之前已經扣完
if(map.get(n) > 0){
while(--iter >=0){
int cur_val = map.get(n);
int iter_val = map.getOrDefault(n+iter, 0);
// 1. n+iter 的數量要大於 n 才對
// 2. 0 的話沒找到, return false
if(iter_val < cur_val) return false;
map.put(n+iter, iter_val - cur_val);
}
}
}
return true;
}
845. Longest Mountain in Array
Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:
B.length >= 3 There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
return the longest len of mountain
public int longestMountain(int[] A) {
int max = 0;
int iter = 1;
Boolean checked1 = false;
Boolean checked2 = false;
while(iter < A.length){
// 若相等，跟山峰沒關係
if(A[iter] == A[iter-1]){
iter++;
continue;
}
int start = iter-1;
while(iter < A.length && A[iter] > A[iter-1]){
checked1 = true;
iter++;
}
while(iter < A.length && A[iter] < A[iter-1]){
checked2 = true;
iter++;
}
if(checked1 && checked2){
max = Math.max(max, iter-start);
}
checked1 = false;
checked2 = false;
}
return max;
}
833. Find And Replace in String
The indexes is not sorted order, use a map to store the string index and array index
StringBuilder starts to update from rear, it doesn't affect the subString
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
int n = indexes.length;
StringBuilder sb = new StringBuilder(S);
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<n; i++) map.put(indexes[i], i);
// 從sb後面開始更改，對前面不會影響
for(int i=sb.length()-1; i>=0; i--){
if(map.containsKey(i)){
int index = map.get(i);
if(S.substring(i).startsWith(sources[index])){
sb.replace(i, i+sources[index].length(), targets[index]);
}
}
}
return sb.toString();
}
818. Race Car
Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)
Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).
When you get an instruction "A", your car does the following: position += speed, speed *= 2.
When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. Return the shortest sequence of instructions
Recursion + memorization
DP(t): the shortest sequence to achieve target
3 condition
t is exact nA: n
t is over 2^n-1 (nA1R): n+1+helper(left)
t is reverse twice (n-1)ARmAR: (n+m+1) + helper( t - (2^(n-1)-1+2^(m)-1))
class Solution {
private int[] dp;
public int racecar(int target) {
dp = new int[target+1];
return helper(target);
}
private int helper(int t){
if(dp[t] > 0) return dp[t];
int n = (int)Math.ceil(Math.log(t+1)/Math.log(2));
// best case nA: n
if(1 << n == t+1){
dp[t] = n;
return dp[t];
}
// nA1R: n+1+helper(left) 超過回來
dp[t] = n+1 + helper((1 << n) - 1 - t);
// (n-1)ARmAR: (n+m+1) + helper( t - (2^(n-1)-1+2^(m)-1))
// m 最多只會到2^(n-2) 長度, 需要n-1 steps
for(int m=0; m<n-1; m++){
int diff = (1 << (n-1)) - (1 << m);
dp[t] = Math.min(dp[t], n+m+1 + helper(t - diff));
}
return dp[t];
}
}
815. Bus Routes
We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.
We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
BFS from bust stop 2 each routes it connected
Prune if stop is visited
public int numBusesToDestination(int[][] routes, int S, int T) {
Map<Integer, Set<Integer>> stop2route = new HashMap<>();
Set<Integer> visited = new HashSet<>();
Queue<int[]> q = new LinkedList<>();
// init the map
for(int i=0; i<routes.length; i++){
for(int j: routes[i]){
if(!stop2route.containsKey(j)) stop2route.put(j, new HashSet<>());
stop2route.get(j).add(i);
}
}
// int[0]: stop, int[1]: count of rount
q.add(new int[]{S, 0});
while(!q.isEmpty()){
int[] cur = q.poll();
if(cur[0] == T) return cur[1];
for(Integer route: stop2route.get(cur[0])){
for(int stop: routes[route]){
if(visited.contains(stop)) continue;
visited.add(stop);
q.add(new int[]{stop, cur[1]+1});
}
}
}
return -1;
}
805. Split Array With Same Average
In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)
Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.
The avg of A and avg of B and C are the same.
totalSum/n = Asum/k => Asum = totalSum*k/n整除
利用combinationSum, 遞回到 k=0 && remain == 0
public boolean splitArraySameAverage(int[] A) {
int sum=0;
int n = A.length;
for(int num:A) sum+=num;
Arrays.sort(A);
for(int i=1; i<=n/2;i++){
if(sum*i%n == 0 && combinationSum(A, 0, i, sum*i/n)) return true;
}
return false;
}
private boolean combinationSum(int[] A, int start, int num, int remain){
if(remain==0) return num == 0;
if(remain<0 || num<1) return false;
for(int i=start; i<A.length-num+1; i++){
if(combinationSum(A, i+1, num-1, remain-A[i])) return true;
}
return false;
}
684. Redundant Connection
Undirected Graph
Use union find to find cycle
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length + 1;
UF uf = new UF(n);
for(int[] edge: edges){
if(uf.union(edge[0], edge[1])) return edge;
}
return new int[]{};
}
}
class UF{
int[] father;
int[] size;
public UF(int n){
father = new int[n];
size = new int[n];
for(int i=0; i<n; i++){
father[i] = i;
size[i] = 1;
}
}
public int find(int a){
if(father[a] != a) father[a] = find(father[a]);
return father[a];
}
public boolean union(int a, int b){
int f_a = find(a);
int f_b = find(b);
if(f_a == f_b) return true;
if(size[f_a] > size[f_b]){
father[f_b] = f_a;
size[f_a] += f_b;
}else{
father[f_a] = f_b;
size[f_b] += f_a;
}
return false;
}
}
685. Redundant Connection II
Directed Graph
3 circumstances
Only multiple parents
Only cycle
Both
Example:[[2,1],[3,1],[4,2],[1,4]]
class Solution {
class UF{
int[] father;
public UF(int n){
father = new int[n];
for(int i=0; i<n; i++){
father[i] = i;
}
}
public int find(int a){
if(father[a] != a) father[a] = find(father[a]);
return father[a];
}
public void union(int a, int b){
int f_a = find(a);
int f_b = find(b);
father[f_b] = f_a;
}
}
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length+1;
UF uf = new UF(n);
int[] candidate1 = null, candidate2 = null;
for(int[] e: edges){
int f_a = uf.find(e[0]), f_b = uf.find(e[1]);
if(f_a != f_b){
// multiple parents, means e[1] has been seen before and its parents is not itself
if(f_b != e[1]) candidate1 = e;
else uf.union(e[0], e[1]);
}else{
// cycle
candidate2 = e;
}
}
// if only either multiple parents or cycle happens
if(candidate2 == null) return candidate1;
if(candidate1 == null) return candidate2;
// if both happen, we don't consider the 2nd multiple edge since beginning
// The first edge caused multiple father must be removed
for(int[] e: edges){
if(e[1] == candidate1[1]) return e;
}
return new int[2];
}
}
312. Burst Balloons
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. nums[-1] = nums[n] = 1
dp[i][j]: 第i個到第j個nums的array中, ballon burst的最大值
Trans: dp[i][j] = dp[i][k-1] + nums[i]nums[k]nums[j] + dp[k+1][j], i <= k <= j
public int maxCoins(int[] nums) {
int n = nums.length;
int[][] dp = new int[n+2][n+2];
// create arr with arr[-1] & arr[n]
int[] arr = new int[n+2];
for(int i=1; i<arr.length-1; i++){
arr[i] = nums[i-1];
}
arr[0] = arr[arr.length-1] = 1;
// 第一個 loop 間距
for(int l=1; l<=n; l++){
for(int i=1; i<=n-l+1; i++){
int j = i+l-1;
for(int k=i; k<=j; k++){
dp[i][j] = Math.max(dp[i][j],
dp[i][k-1] + arr[i-1]*arr[k]*arr[j+1] + dp[k+1][j]);
}
}
}
return dp[1][n];
}
Back 1017t. Similar RGB Color
Given the color "#ABCDEF", return a 7 character color that is most similar to #ABCDEF, and has a shorthand (that is, it can be represented as some "#XYZ")
// 要求的形式為AA, 必定為轉換後的數字為17的倍數
public String similarRGB(String color) {
return "#" + helper(color.substring(1, 3))
+ helper(color.substring(3, 5)) + helper(color.substring(5));
}
private String helper(String s){
int num = Integer.parseInt(s, 16);
num = num / 17 + (num % 17 > 8 ? 1 : 0);
return String.format("%02x", num * 17);
}
