一刷 08/2022
Version #1 Divide by 3
Time O(logN)
Space O(1)
class Solution {
public boolean isPowerOfThree(int n) {
if (n == 0) {
return false;
}
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
}
一刷 08/2022
Version #1 Divide by 4
Time O(logN)
Space O(1)
class Solution {
public boolean isPowerOfFour(int n) {
if (n == 0) {
return false;
}
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}
}
一刷 08/2022
Version #1 HashMap + sorting
Time - N is array length, create the hash map O(N), sort the count worst case O(NlogN) - total O(NlogN)
Space - O(N)
class Solution {
public int minSetSize(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
List<Integer> counts = new ArrayList<>(map.values());
Collections.sort(counts, Collections.reverseOrder());
// 0 1
int want = arr.length / 2 + arr.length % 2;
int i = 0;
while (want > 0) {
want -= counts.get(i++);
}
return i;
}
}
一刷 08/2022
Version #1 Sliding Window
感觉这个的重点是sliding window invalid的时候不skip而是一个一个地挪left
Time - word length W, word count N, string length L - outer loop W, inner loop L / W * W(for substring operation), N to initialize the word count map - total O (N + WL)
Space O(NL)
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (words == null || words.length == 0) {
return result;
}
int wordL = words[0].length();
int totalL = wordL * words.length;
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
for (int i = 0; i < wordL; i++) {
// start using sliding window
int left = i, right = i;
int wordCount = words.length;
// count of words between [left, right)
Map<String, Integer> currMap = new HashMap<>();
while (right + wordL <= s.length()) {
// expand for one word
String currWord = s.substring(right, right + wordL);
right += wordL;
int currCount = currMap.getOrDefault(currWord, 0) + 1;
currMap.put(currWord, currCount);
if (currCount <= map.getOrDefault(currWord, 0)) {
wordCount--;
}
if (right - left > totalL) {
currWord = s.substring(left, left + wordL);
left += wordL;
currCount = currMap.getOrDefault(currWord, 0) - 1;
currMap.put(currWord, currCount);
if (currCount < map.getOrDefault(currWord, 0)) {
wordCount++;
}
}
if (wordCount == 0) {
result.add(left);
}
}
}
return result;
}
}
一刷 08/2022
Version #1 Two Pointers
Time O(N) - construction, O(N) - calculate product
Space O(N)
class SparseVector {
public List<Integer> indices;
public List<Integer> values;
SparseVector(int[] nums) {
indices = new ArrayList<>();
values = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
continue;
}
indices.add(i);
values.add(nums[i]);
}
}
// Return the dotProduct of two sparse vectors
public int dotProduct(SparseVector vec) {
int result = 0;
int p = 0, q = 0;
while (p < this.indices.size() && q < vec.indices.size()) {
if (this.indices.get(p) < vec.indices.get(q)) {
p++;
} else if (this.indices.get(p) > vec.indices.get(q)) {
q++;
} else {
result += this.values.get(p) * vec.values.get(q);
p++;
q++;
}
}
return result;
}
}
一刷 08/2022
Version #1 1D DP
Time O(N)
Space O(1)
class Solution {
private int MOD = (int)(1e9 + 7);
public int countVowelPermutation(int n) {
//0 a -> e
//1 e -> a, i
//2 i -> a, e, o, u
//3 o -> i, u
//4 u -> a
// number of combinations with length i and ending with char (a,e,i,o,u)
int[] dp = new int[5];
Arrays.fill(dp, 1);
for (int i = 2; i <= n; i++) {
int[] ndp = new int[5];
// a can follow e,i,u
ndp[0] = ((dp[1] + dp[2]) % MOD + dp[4]) % MOD;
// e can follow a,i
ndp[1] = (dp[0] + dp[2]) % MOD;
// i can follow e,o
ndp[2] = (dp[1] + dp[3]) % MOD;
// o can follow i
ndp[3] = dp[2];
// u can follow i,o
ndp[4] = (dp[2] + dp[3]) % MOD;
dp = ndp;
}
int sum = 0;
for (int i = 0; i < 5; i++) {
sum = (sum + dp[i]) % MOD;
}
return sum;
}
}
一刷 08/2022
Version #1 Stack
因为要保证最小，所以要reverse some subarray in the min array if we encountered a 'D'
因为在min array里面前面的element 永远是小于后面的element的，所以即使前面reverse，也一定满足I
我觉得难点在于'D''I'都是针对两个elements来说的，所以index的处理有点麻烦
Time O(N)
Space O(N)
class Solution {
public int[] findPermutation(String s) {
int[] result = new int[s.length() + 1];
int p = 0;
int num = 1;
Stack<Integer> stack = new Stack<>();
// "DI"
//
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'D') {
stack.push(num++);
continue;
}
stack.push(num++);
while (!stack.isEmpty()) {
result[p++] = stack.pop();
}
}
stack.push(num);
while (!stack.isEmpty()) {
result[p++] = stack.pop();
}
return result;
}
}
一刷 08/2022
Version #2 Merge Sort
看某一个prefix index后面有多少个prefix满足lower <= prefix[j]-prefix[i] <= upper
Time O(NlogN)
Space O(N)
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
long[] prefixSum = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
// find count of prefixSum on the right that lower <= prefixSum[j] - prefixSum[i] <= uppder
// [-2,5,-1,-4]
// [0, -2, 3, 2, -2]
// [-2, 0] [-2, 2, 3]
int[] count = new int[1];
mergeSort(prefixSum, new long[prefixSum.length], 0, prefixSum.length - 1, count, lower, upper);
return count[0];
}
private void mergeSort(long[] nums, long[] aux, int start, int end, int[] count, int lower, int upper) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(nums, aux, start, mid, count, lower, upper);
mergeSort(nums, aux, mid + 1, end, count, lower, upper);
// left is the first index that nums[left] - num[i] >= lower
// right is the first index that nums[right] - nums[i] > upper
int left = mid + 1, right = mid + 1;
// int i = mid + 1, j = mid + 1;
// for (int k = low; k <= mid; k++) {
// while (i <= high && pfxSum[i] - pfxSum[k] < lower) i++;
// while (j <= high && pfxSum[j] - pfxSum[k] <= upper) j++;
// count += j - i;
// }
// [0, -2, 3, 2]
// [-2, 0, 2, 3]
for (int i = start; i <= mid; i++) {
while (left <= end && nums[left] - nums[i] < lower) {
left++;
}
while (right <= end && nums[right] - nums[i] <= upper) {
right++;
}
count[0] += right - left;
}
for (int i = start; i <= end; i++) {
aux[i] = nums[i];
}
int pleft = start, pright = mid + 1;
int p = start;
while (pleft <= mid && pright <= end) {
if (aux[pleft] <= aux[pright]) {
nums[p++] = aux[pleft++];
} else {
nums[p++] = aux[pright++];
}
}
while (pleft <= mid) {
nums[p++] = aux[pleft++];
}
while (pright <= end) {
nums[p++] = aux[pright++];
}
}
}
Version #1 Segment Tree[TLE]
Time O(NlogN)
Space O(Range of all prefix sums)
class Solution {
class Node {
Node left, right;
int count;
int start, end;
public Node(int start, int end) {
this.start = start;
this.end = end;
}
}
public int countRangeSum(int[] nums, int lower, int upper) {
int[] prefixSum = new int[nums.length + 1];
int min = 0, max = 0;
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
min = Math.min(min, prefixSum[i + 1]);
max = Math.max(max, prefixSum[i + 1]);
}
Node root = buildTree(min, max);
int count = 0;
for (int i = nums.length; i >= 0; i--) {
// prefixSum[i] - try to find the count of j that lower <= prefixSum[j] - prefixSum[i] <= upper
// lower + prefixSum[i] <= prefixSum[j] <= upper + prefixSum[j]
count += query(root, (long)lower + prefixSum[i], (long)upper + prefixSum[i]);
update(root, prefixSum[i]);
}
return count;
}
private void update(Node node, int num) {
if (node.start == num && node.end == num) {
node.count++;
return;
}
int mid = node.start + (node.end - node.start) / 2;
if (num <= mid) {
update(node.left, num);
} else {
update(node.right, num);
}
node.count = node.left.count + node.right.count;
}
private int query(Node node, long left, long right) {
// [start, end]
// [left, right]
if (left > node.end || right < node.start) {
return 0;
}
if (left <= node.start && right >= node.end) {
return node.count;
}
return query(node.left, left, right) + query(node.right, left, right);
}
private Node buildTree(int start, int end) {
Node n = new Node(start, end);
if (start == end) {
return n;
}
int mid = start + (end - start) / 2;
n.left = buildTree(start, mid);
n.right = buildTree(mid + 1, end);
return n;
}
}
一刷 08/2022
Version #1 Map of DoublyLinkedList
Time O(1) for all
Space O(N) - N is number of keys
class LFUCache {
// key-the counter, value-the most recent used node with this counter
Map<Integer, DList> counterToList;
Map<Integer, Node> keyToNode;
int cap;
int minCounter;
class Node {
Node prev, next;
int key;
int val;
int counter;
public Node(int key, int val) {
this.key = key;
this.val = val;
this.counter = 1;
}
}
class DList {
Node head, tail;
int size;
public DList() {
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
this.size = 0;
}
// add after head
public void add(Node node) {
Node next = head.next;
head.next = node;
node.next = next;
node.prev = head;
next.prev = node;
size++;
}
public void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
size--;
}
// remove the last element and returns its key
public int removeLast() {
if (size == 0) {
return 0;
}
size--;
Node last = tail.prev;
Node prev = last.prev;
prev.next = tail;
tail.prev = prev;
return last.key;
}
}
public LFUCache(int capacity) {
this.cap = capacity;
this.minCounter = 0;
counterToList = new HashMap<>();
keyToNode = new HashMap<>();
}
public int get(int key) {
if (!keyToNode.containsKey(key)) {
return -1;
}
Node curr = keyToNode.get(key);
DList list = counterToList.get(curr.counter);
list.remove(curr);
if (list.size == 0 && curr.counter == minCounter) {
minCounter++;
}
curr.counter++;
counterToList.putIfAbsent(curr.counter, new DList());
counterToList.get(curr.counter).add(curr);
return curr.val;
}
public void put(int key, int value) {
if (keyToNode.containsKey(key)) {
keyToNode.get(key).val = value;
get(key);
return;
}
if (cap == 0) {
if (minCounter == 0) {
return;
}
cap++;
DList list = counterToList.get(minCounter);
int removedKey = list.removeLast();
keyToNode.remove(removedKey);
}
minCounter = 1;
cap--;
Node curr = new Node(key, value);
counterToList.putIfAbsent(1, new DList());
counterToList.get(1).add(curr);
keyToNode.put(key, curr);
}
}
一刷 07/2022
Version #1 TreeMap
思路比较简单就是把interval用key-value pair的形式存在treemap里面，然后维持所有的invervals没有overlap
需要特别处理的case
exists [8, 9)
add [1,8)
这时候首先需要取floowKey(8)获得[8, 9)然后合并获得[1,9)
另外一个case就是
exists [1, 9)
add [9, 10)
取完floorKey获得[1, 9)这时候需要判断的是get(floorKey) >= start
Time Amortized O(logN) - N is number of intervals
Space O(N)
class RangeModule {
TreeMap<Integer, Integer> map;
public RangeModule() {
map = new TreeMap<>();
}
public void addRange(int left, int right) {
int start = left, end = right;
// System.out.printf("left=%d, right=%d\n", left, right);
Integer lk = map.floorKey(end);
while (lk != null && map.get(lk) >= left) {
start = Math.min(start, lk);
end = Math.max(end, map.get(lk));
map.remove(lk);
lk = map.floorKey(end);
// System.out.printf("start=%d, end=%d\n", start, end);
}
map.put(start, end);
}
public boolean queryRange(int left, int right) {
Integer lk = map.lowerKey(right);
if (lk == null) {
return false;
}
if (lk <= left && map.get(lk) >= right) {
return true;
}
return false;
}
public void removeRange(int left, int right) {
// [ ]
// [ ] [ ]
Integer lk = map.lowerKey(right);
while (lk != null && map.get(lk) > left) {
int prevLeft = lk;
int prevRight = map.get(lk);
//left right
// [ ]
// pl pr
// [ ]
map.remove(lk);
if (prevRight > right) {
map.put(right, prevRight);
}
if (prevLeft < left) {
map.put(prevLeft, left);
}
lk = map.lowerKey(right);
}
}
}
一刷 07/2022
Version #1 HashMap
Time O(1)
Space O(N^2 + P) - N is number of stations, P is number of passengers
class UndergroundSystem {
// key-startStation,endStation value-sum of all travel times, count of customers
Map<List<String>, Pair<Long, Integer>> timeMap;
// key-customer id, value-startStation,checkin time
Map<Integer, Pair<String, Integer>> checkinMap;
public UndergroundSystem() {
this.timeMap = new HashMap<>();
this.checkinMap = new HashMap<>();
}
public void checkIn(int id, String stationName, int t) {
checkinMap.put(id, new Pair(stationName, t));
}
public void checkOut(int id, String stationName, int t) {
if (!checkinMap.containsKey(id)) {
return;
}
Pair<String, Integer> checkinInfo = checkinMap.get(id);
List<String> stations = new ArrayList<>();
stations.add(checkinInfo.getKey());
stations.add(stationName);
int duration = t - checkinInfo.getValue();
Pair<Long, Integer> stationInfo = timeMap.getOrDefault(stations, new Pair(0l, 0));
Pair<Long, Integer> nInfo = new Pair(stationInfo.getKey() + duration, stationInfo.getValue() + 1);
timeMap.put(stations, nInfo);
}
public double getAverageTime(String startStation, String endStation) {
Pair<Long, Integer> stationInfo = timeMap.get(new ArrayList<>(Arrays.asList(new String[]{startStation, endStation})));
return (1.0 * stationInfo.getKey()) / stationInfo.getValue();
}
}
一刷 07/2022
Version #1 Sliding Window
感觉很难，照着答案写还是一知半解的感觉
Time O(N)
Space O(N)
class Solution {
public int minKBitFlips(int[] nums, int k) {
// number of flips in the sliding window
int flipCounter = 0;
int flips = 0;
boolean[] isFlipped = new boolean[nums.length];
for (int i = 0; i < nums.length; i++) {
if (i >= k && isFlipped[i - k]) {
flipCounter--;
}
// check if we need to flip current bit
if (flipCounter % 2 == nums[i]) {
if (i + k > nums.length) {
return -1;
}
isFlipped[i] = true;
flipCounter++;
flips++;
}
}
return flips;
}
}
一刷 07/2022
Version #1 Topological Sort
Time O(N + E)
Space O(N + E)
class Solution {
public int minimumSemesters(int n, int[][] relations) {
int[] prevCount = new int[n];
List<Integer>[] nextCourses = new ArrayList[n];
for (int i = 0; i < n; i++) {
nextCourses[i] = new ArrayList<>();
}
for (int[] relation : relations) {
int prev = relation[0] - 1;
int next = relation[1] - 1;
nextCourses[prev].add(next);
prevCount[next]++;
}
int taken = 0;
int semester = 0;
Queue<Integer> que = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (prevCount[i] == 0) {
que.offer(i);
}
}
while (!que.isEmpty()) {
int size = que.size();
semester++;
// 1 - 3 - 2
while (size-- > 0) {
int curr = que.poll();
taken++;
for (int next : nextCourses[curr]) {
prevCount[next]--;
if (prevCount[next] == 0) {
que.offer(next);
}
}
}
}
return taken == n ? semester : -1;
}
}
一刷 07/2022
Version #1 DP game theory
Time O(N^2)
Space O(N^2) - space can be optimized to O(N)
class Solution {
public boolean PredictTheWinner(int[] nums) {
int len = nums.length;
int[][] dp = new int[len][len];
// dp[i][j] - max score diff that we can get between nums [j, i]
for (int i = 0; i < nums.length; i++) {
for (int j = i; j >= 0; j--) {
if (i == j) {
dp[i][j] = nums[i];
} else {
// [j, i]
dp[i][j] = Math.max(nums[i] - dp[i - 1][j], nums[j] - dp[i][j + 1]);
}
}
}
return dp[len - 1][0] >= 0;
}
}
一刷 07/2022
Version #1 Stack
关键是求maximum rectangle in histogram
Time O(MN)
Space O(N)
class Solution {
public int maximalRectangle(char[][] matrix) {
int[] row = new int[matrix[0].length];
int max = 0;
for (int y = 0; y < matrix.length; y++) {
for (int x = 0; x < matrix[0].length; x++) {
if (matrix[y][x] == '0') {
row[x] = 0;
} else {
row[x]++;
}
}
max = Math.max(max, maxRecInHisto(row));
}
return max;
}
private int maxRecInHisto(int[] row) {
int max = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < row.length; i++) {
while (!stack.isEmpty() && row[stack.peek()] >= row[i]) {
int h = row[stack.pop()];
int w = i - (stack.isEmpty() ? -1 : stack.peek()) - 1;
max = Math.max(max, h * w);
}
stack.push(i);
}
int i = row.length;
while (!stack.isEmpty()) {
int h = row[stack.pop()];
int w = i - (stack.isEmpty() ? -1 : stack.peek()) - 1;
max = Math.max(max, h * w);
}
return max;
}
}
一刷 07/2022
Version #1 Array as HashMap
Time O(M + N)
Space O(1)
class Solution {
public List<String> wordSubsets(String[] words1, String[] words2) {
// calculate the maximum counter of each character in words2
// the counter of characters in words1 need to be at least larger than or equals to the maximum counter of words2
int[] maxCount = new int[26];
for (String word : words2) {
int[] count = new int[26];
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
count[index]++;
maxCount[index] = Math.max(maxCount[index], count[index]);
}
}
List<String> result = new ArrayList<>();
for (String word : words1) {
int[] count = new int[26];
for (int i = 0; i < word.length(); i++) {
count[word.charAt(i) - 'a']++;
}
int i = 0;
for (i = 0; i < 26; i++) {
if (count[i] < maxCount[i]) {
break;
}
}
if (i == 26) {
result.add(word);
}
}
return result;
}
}
一刷 07/2022
Version #2 Better DP with two states
不是特别理解
Time O(N)
Space O(1)
class Solution {
public int maxProfit(int[] prices, int fee) {
int cash = 0;
int hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
cash = Math.max(cash, hold + prices[i] - fee);
hold = Math.max(hold, cash - prices[i]);
}
return cash;
}
}
Version #1 DP with max previous profit
Time O(N)
Space O(N)
class Solution {
public int maxProfit(int[] prices, int fee) {
int[] dp = new int[prices.length];
int prevMax = -prices[0] - fee;
// dp[i] - max profix that can achieve on day i
for (int i = 1; i < prices.length; i++) {
prevMax = Math.max(prevMax, (i >= 2 ? dp[i - 2] : 0) - prices[i - 1] - fee);
dp[i] = Math.max(dp[i - 1], prices[i] + prevMax);
}
return dp[prices.length - 1];
}
}
一刷 07/2022
Version #1 Backtracking
重点是每次要回到原位原方向
而且每次当前方向要传到下一层，因为需要知道进入当前层的时候robot的方向
同时如果不能move的时候也要记得转
Time O(MN)
Space O(MN)
class Solution {
public void cleanRoom(Robot robot) {
// try to turn 4 directions and move
Set<Pair<Integer, Integer>> visited = new HashSet<>();
clean(robot, 0, 0, visited, 0);
}
private int[] dx = new int[]{0, 1, 0, -1};
private int[] dy = new int[]{1, 0, -1, 0};
private void clean(Robot robot, int y, int x, Set<Pair<Integer, Integer>> visited, int dir) {
if (!visited.add(new Pair(y, x))) {
return;
}
robot.clean();
//
for (int i = 0; i < 4; i++) {
int nd = (dir + i) % 4;
if (robot.move()) {
clean(robot, y + dy[nd], x + dx[nd], visited, nd);
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnLeft();
} else {
robot.turnRight();
}
}
}
}
一刷 07/2022
Version #1 Backtracking
Time O(N!)
Space O(N)
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[] array = new char[n];
Arrays.fill(array, '.');
helper(n, 0, new HashSet<>(), new HashSet<>(), new HashSet<>(), new ArrayList<>(), result, array);
return result;
}
private void helper(int n, int y, Set<Integer> cols, Set<Integer> diff, Set<Integer> sum, List<String> path, List<List<String>> result, char[] array) {
if (y == n) {
result.add(new ArrayList<>(path));
return;
}
for (int x = 0; x < n; x++) {
if (cols.contains(x) || diff.contains(y - x) || sum.contains(y + x)) {
continue;
}
array[x] = 'Q';
cols.add(x);
diff.add(y - x);
sum.add(y + x);
path.add(new String(array));
array[x] = '.';
helper(n, y + 1, cols, diff, sum, path, result, array);
cols.remove(x);
diff.remove(y - x);
sum.remove(y + x);
path.remove(path.size() - 1);
}
}
}
一刷 07/2022
Version #1 Backtracking
自己想的时候先计算了一下小于等于sqrt(n)的所有factor
然后每次取一些factor和它们的remainder组成一组答案，要求remaider必须大于等于factor来保证没有重复答案
看了其他人的做法不需要提前算出factor，只要在i和n之间iterate找到能整除的数 感觉这个做法比较慢
Time O(logN^logN) given that we have logN number of factors and we called the recursive function time complexity of a recursive function = number of choices ^ number of steps
Space O(logN)
class Solution {
public List<List<Integer>> getFactors(int n) {
List<Integer> factors = new ArrayList<>();
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
factors.add(i);
}
}
List<List<Integer>> result = new ArrayList<>();
select(factors, 0, new ArrayList<>(), n, result);
return result;
}
private void select(List<Integer> factors, int index, List<Integer> path, int target, List<List<Integer>> result) {
if (path.size() > 0) {
path.add(target);
result.add(new ArrayList<>(path));
path.remove(path.size() - 1);
}
for (int i = index; i < factors.size(); i++) {
int f = factors.get(i);
if (target % f != 0) {
continue;
}
if (target / f < f) {
break;
}
path.add(f);
select(factors, i, path, target / f, result);
path.remove(path.size() - 1);
}
}
}
一刷 07/2022
Version #1 DFS with node rank
一开始想到了是要求cycle，但是没有想到怎么把cycle里面的edge记录下来
看答案学习了这个rank的方法，是以前从来没有遇到过的，狠狠记住
Time O(E + V)
Space O(E + V)
class Solution {
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
// If an edge is part of a cycle, then it is not a critical connection
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (List<Integer> conn : connections) {
int node1 = conn.get(0);
int node2 = conn.get(1);
graph.get(node1).add(node2);
graph.get(node2).add(node1);
}
Set<List<Integer>> nonCriticalConn = new HashSet<>();
dfs(graph, 0, nonCriticalConn, 0, new HashMap<>());
List<List<Integer>> result = new ArrayList<>();
for (List<Integer> conn : connections) {
Collections.sort(conn);
if (nonCriticalConn.contains(conn)) {
continue;
}
result.add(conn);
}
return result;
}
private int dfs(List<List<Integer>> graph, int node, Set<List<Integer>> nonCriticalConn, int rank, Map<Integer, Integer> ranks) {
// assign rank + 1 to all the neighbors
// if a neighbor already has a rank smaller than current rank, it means the neighbor has been visited
// return the min rank of all neighbors recursively
if (ranks.containsKey(node)) {
return ranks.get(node);
}
ranks.put(node, rank);
int minRank = rank;
for (int next : graph.get(node)) {
Integer nextRank = ranks.get(next);
// skip the parent
if (nextRank != null && nextRank == rank - 1) {
continue;
}
nextRank = dfs(graph, next, nonCriticalConn, rank + 1, ranks);
if (nextRank <= rank) {
nonCriticalConn.add(new ArrayList<>(Arrays.asList(new Integer[]{Math.min(node, next), Math.max(node, next)})));
minRank = Math.min(minRank, nextRank);
}
}
return minRank;
}
}
一刷 07/2022
Version #1 DFS
If we want to detect cycle in a graph, we need to keep track of each path with backtracking instead of keep track of the globally visited nodes
Time O(V + E) - for full graph dfs
Space O(V + E) - E is occupied by the adjacency list and V is used by the system stack
class Solution {
public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
// If there's any cycles, then return false
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
// edge[0] -> edge[1]
graph.get(edge[0]).add(edge[1]);
}
Set<Integer> path = new HashSet<>();
path.add(source);
return dfs(graph, source, destination, path);
}
private boolean dfs(List<List<Integer>> graph, int node, int destination, Set<Integer> path) {
if (graph.get(node).size() == 0) {
return node == destination;
}
for (Integer next : graph.get(node)) {
if (!path.add(next)) {
return false;
}
path.add(next);
if (!dfs(graph, next, destination, path)) {
return false;
}
path.remove(next);
}
return true;
}
}
