1 January 2020
LeetCode(72) -- 1192, 3, 380
by Jerry Zhang
P1192. Critical Connections in a Network (Medium)
There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.
My Solution
If I removed any connection, and the endpoints of this connection can still be connected by some other path, then this connection is not critical.
public class P1192_CriticalConnectionsinaNetwork {
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
List<List<Integer>> ans = new ArrayList<>();
HashMap<Integer, List<Integer>> graph = new HashMap<>();
for (List<Integer> connection : connections) {
Integer node1 = connection.get(0);
Integer node2 = connection.get(1);
List<Integer> list = graph.getOrDefault(node1, new ArrayList<>());
list.add(node2);
graph.put(node1, list);
list = graph.getOrDefault(node2, new ArrayList<>());
list.add(node1);
graph.put(node2, list);
}
for (List<Integer> connection : connections) {
removeConnection(graph, connection);
Integer node1 = connection.get(0);
Integer node2 = connection.get(1);
HashSet<Integer> visited = new HashSet<>();
if (!dfs(graph, node1, node2, visited)) {
ans.add(connection);
}
pushBackConnection(graph, connection);
}
return ans;
}
private boolean dfs(HashMap<Integer, List<Integer>> graph, Integer node1, Integer node2, HashSet<Integer> visited) {
List<Integer> list = graph.get(node1);
if (list.contains(node2)) {
return true;
}
for (Integer neighbour : list) {
if (!visited.contains(neighbour)) {
visited.add(neighbour);
if (dfs(graph, neighbour, node2, visited)) {
return true;
}
}
}
return false;
}
private void removeConnection(HashMap<Integer, List<Integer>> graph, List<Integer> connection) {
Integer node1 = connection.get(0);
Integer node2 = connection.get(1);
List<Integer> list = graph.get(node1);
list.remove(node2);
graph.put(node1, list);
list = graph.get(node2);
list.remove(node1);
graph.put(node2, list);
}
private void pushBackConnection(HashMap<Integer, List<Integer>> graph, List<Integer> connection) {
Integer node1 = connection.get(0);
Integer node2 = connection.get(1);
List<Integer> list = graph.get(node1);
list.add(node2);
graph.put(node1, list);
list = graph.get(node2);
list.add(node1);
graph.put(node2, list);
}
public static void main(String[] args) {
ArrayList<List<Integer>> connections = new ArrayList<>();
connections.add(Arrays.asList(1, 0));
connections.add(Arrays.asList(2, 0));
connections.add(Arrays.asList(3, 2));
connections.add(Arrays.asList(4, 2));
connections.add(Arrays.asList(4, 3));
connections.add(Arrays.asList(3, 0));
connections.add(Arrays.asList(4, 0));
List<List<Integer>> lists = new P1192_CriticalConnectionsinaNetwork().criticalConnections(5, connections);
System.out.println("lists = " + lists);
}
}
failed. Time limit exceeded.
Discuss
An edge is a critical connection, if and only if it is not in a cycle.
Tarjan Algorithm:
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
int[] disc = new int[n], low = new int[n];
// use adjacency list instead of matrix will save some memory, adjmatrix will cause MLE
List<Integer>[] graph = new ArrayList[n];
List<List<Integer>> res = new ArrayList<>();
Arrays.fill(disc, -1); // use disc to track if visited (disc[i] == -1)
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
// build graph
for (int i = 0; i < connections.size(); i++) {
int from = connections.get(i).get(0), to = connections.get(i).get(1);
graph[from].add(to);
graph[to].add(from);
}
for (int i = 0; i < n; i++) {
if (disc[i] == -1) {
dfs(i, low, disc, graph, res, i);
}
}
return res;
}
int time = 0; // time when discover each vertex
private void dfs(int u, int[] low, int[] disc, List<Integer>[] graph, List<List<Integer>> res, int pre) {
disc[u] = low[u] = ++time; // discover u
for (int j = 0; j < graph[u].size(); j++) {
int v = graph[u].get(j);
if (v == pre) {
continue; // if parent vertex, ignore
}
if (disc[v] == -1) { // if not discovered
dfs(v, low, disc, graph, res, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) {
// u - v is critical, there is no path for v to reach back to u or previous vertices of u
res.add(Arrays.asList(u, v));
}
} else { // if v discovered and is not parent of u, update low[u], cannot use low[v] because u is not subtree of v
low[u] = Math.min(low[u], disc[v]);
}
}
}
80%
The Best Solution
class Solution {
int edgeIndex = 0;
int[] to;
int[] next;
int[] head;
int[] low;
int[] disc;
int time = -1;
List<List<Integer>> res = new ArrayList<>();
private void addEdge(int u, int v) {
to[edgeIndex] = v;
next[edgeIndex] = head[u];
head[u] = edgeIndex ++;
}
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
low = new int[n];
disc = new int[n];
int m = connections.size();
to = new int[m * 2];
head = new int[n];
next = new int[m * 2];
Arrays.fill(head, -1);
Arrays.fill(next, -1);
Arrays.fill(low, -1);
Arrays.fill(disc, -1);
for (List<Integer> edge : connections) {
int u = edge.get(0);
int v = edge.get(1);
addEdge(u, v);
addEdge(v, u);
}
dfs(1, -1);
return res;
}
private void dfs(int node, int parent) {
if (disc[node] != -1) {
return;
}
low[node] = disc[node] = ++ time;
for (int edge = head[node]; edge != -1; edge = next[edge]) {
int next = to[edge];
if (disc[next] == -1) {
dfs(next, node);
low[node] = Math.min(low[node], low[next]);
if (low[next] > disc[node]) {
res.add(Arrays.asList(node, next));
}
} else if (next != parent) {
low[node] = Math.min(low[node], disc[next]);
}
}
}
}
P3. Longest Substring Without Repeating Characters (Medium)
Given a string, find the length of the longest substring without repeating characters.
HashMap
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int start = 0;
char[] chars = s.toCharArray();
int length = 0;
for (int i = 0; i < chars.length; i++) {
start = Math.max(start, map.getOrDefault(chars[i], 0));
length = Math.max(length, i - start + 1);
map.put(chars[i], i + 1);
}
return length;
}
}
The Best Solution
public class P3_LongestSubstringWithoutRepeatingCharacters {
public int lengthOfLongestSubstring(String s) {
int longest = 0;
int[] index = new int[128];
int start = 0;
for (int i = 0; i < s.length(); i++) {
start = Math.max(index[s.charAt(eind)], start);
longest = Math.max(longest, i - start + 1);
index[s.charAt(i)] = i + 1;
}
return longest;
}
}
99%
P380. Insert Delete GetRandom O(1) (Medium)
Design a data structure that supports all following operations in average O(1) time.
- insert(val): Inserts an item val to the set if not already present.
- remove(val): Removes an item val from the set if present.
- getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Solution
public class P380_InsertDeleteGetRandomO1 {
Map<Integer, Integer> dict;
List<Integer> list;
Random rand = new Random();
/** Initialize your data structure here. */
public P380_InsertDeleteGetRandomO1() {
dict = new HashMap<>();
list = new ArrayList<>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (dict.containsKey(val)) {
return false;
}
dict.put(val, list.size());
list.add(list.size(), val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!dict.containsKey(val)) return false;
// move the last element to the place idx of the element to delete
int lastElement = list.get(list.size() - 1);
int idx = dict.get(val);
list.set(idx, lastElement);
dict.put(lastElement, idx);
// delete the last element
list.remove(list.size() - 1);
dict.remove(val);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
public static void main(String[] args) {
P380_InsertDeleteGetRandomO1 obj = new P380_InsertDeleteGetRandomO1();
obj.insert(-1);
obj.remove(-2);
obj.insert(-2);
obj.getRandom();
obj.remove(-1);
obj.insert(-2);
obj.getRandom();
}
}
99%
tags: LeetCode