Graph
Recursion + tree / 2D graph
/**
* Definition for _Node.
* class _Node {
* val: boolean
* isLeaf: boolean
* topLeft: _Node | null
* topRight: _Node | null
* bottomLeft: _Node | null
* bottomRight: _Node | null
* constructor(val?: boolean, isLeaf?: boolean, topLeft?: _Node, topRight?: _Node, bottomLeft?: _Node, bottomRight?: _Node) {
* this.val = (val===undefined ? false : val)
* this.isLeaf = (isLeaf===undefined ? false : isLeaf)
* this.topLeft = (topLeft===undefined ? null : topLeft)
* this.topRight = (topRight===undefined ? null : topRight)
* this.bottomLeft = (bottomLeft===undefined ? null : bottomLeft)
* this.bottomRight = (bottomRight===undefined ? null : bottomRight)
* }
* }
*/
function construct(grid: number[][]): _Node | null {
const m = grid.length, n = grid[0].length;
return constructTree(grid, 0, m - 1, 0, n - 1);
};
function constructTree(grid: number[][], tLeft: number, tRight: number, bLeft: number, bRight: number): _Node | null {
if (tLeft > tRight || bLeft > bRight || tRight - tLeft !== bRight - bLeft) {
return null;
}
if (tLeft === tRight && bLeft === bRight) {
return new _Node(grid[tLeft][bLeft] === 1, true, null, null, null, null);
}
if (isLeaf(grid, tLeft, tRight, bLeft, bRight)) {
return new _Node(grid[tLeft][bLeft] === 1, true, null, null, null, null);
}
const tMid = Math.floor((tLeft + tRight) / 2);
const bMid = Math.floor((bLeft + bRight) / 2);
return new _Node(grid[tLeft][bLeft] === 1,
false,
constructTree(grid, tLeft, tMid, bLeft, bMid), // topLeft
constructTree(grid, tLeft, tMid, bMid + 1, bRight), // topRight
constructTree(grid, tMid + 1, tRight, bLeft, bMid), // bottomLeft
constructTree(grid, tMid + 1, tRight, bMid + 1, bRight)); // bottomRight
}
function isLeaf(grid: number[][], tLeft: number, tRight: number, bLeft: number, bRight: number) {
const val = grid[tLeft][bLeft];
for (let i = tLeft; i <= tRight; i++) {
for (let j = bLeft; j <= bRight; j++) {
if (grid[i][j] !== val) return false;
}
}
return true;
}Convert edge to graph map. DFS traverse from 0 node, assign new id every time. Use arrays ids[] and low[] to store the corresponding ids and the low index of the connect graph. If next node is unvisited, DFS to next node. Update low[curt] after the traverse by low[curt] = Math.min(low[curt], low[next]). Add to result if ids[curt] < low[next]
int[] ids;
int[] low;
int index = 0;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
this.ids = new int[n];
this.low = new int[n];
Arrays.fill(ids, -1);
Map<Integer, Set<Integer>> graph = buildGraph(connections);
List<List<Integer>> res = new ArrayList<>();
dfs(0, -1, graph, res);
return res;
}
private void dfs(int curt,
int prev,
Map<Integer, Set<Integer>> graph,
List<List<Integer>> res) {
ids[curt] = low[curt] = index++;
if (!graph.containsKey(curt)) return;
for (int next : graph.get(curt)) {
if (next == prev) continue;
if (ids[next] == -1) {
dfs(next, curt, graph, res);
low[curt] = Math.min(low[curt], low[next]);
if (ids[curt] < low[next]) {
res.add(Arrays.asList(curt, next));
}
} else {
low[curt] = Math.min(low[curt], low[next]);
}
}
}
private Map<Integer, Set<Integer>> buildGraph(List<List<Integer>> edges) {
Map<Integer, Set<Integer>> map = new HashMap<>();
for (List<Integer> e : edges) {
map.putIfAbsent(e.get(0), new HashSet<>());
map.putIfAbsent(e.get(1), new HashSet<>());
map.get(e.get(0)).add(e.get(1));
map.get(e.get(1)).add(e.get(0));
}
return map;
}Use maxHeap to store a new class (val, x, y). Every time it pops the largest node, and maintain a min from the val.
int[][] dirs = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public int maximumMinimumPath(int[][] A) {
int m = A.length, n = A[0].length;
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<>(){
public int compare(int[] a, int[] b) {
return b[0] - a[0];
}
});
pq.offer(new int[]{A[0][0], 0, 0});
A[0][0] = -1;
int min = Integer.MAX_VALUE;
while (!pq.isEmpty()) {
int[] curt = pq.poll();
min = Math.min(min, curt[0]);
if (curt[1] == m - 1 && curt[2] == n - 1) break;
for (int[] d : dirs) {
int nx = curt[1] + d[0];
int ny = curt[2] + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && A[nx][ny] != -1) {
pq.offer(new int[]{A[nx][ny], nx, ny});
A[nx][ny] = -1;
}
}
}
return min;
}Use PQ instead of Set as we can get the next stops in lexicographical order. DFS to the end of next and use bottom-up to construct itinerary.
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> map = new HashMap<>();
for (List<String> l : tickets) {
map.putIfAbsent(l.get(0), new PriorityQueue<>());
map.get(l.get(0)).add(l.get(1));
}
List<String> list = new ArrayList<>();
dfs("JFK", list, map);
return list;
}
private void dfs(String curt, List<String> list, Map<String, PriorityQueue<String>> map) {
PriorityQueue<String> pq = map.get(curt);
while (pq != null && !pq.isEmpty()) {
String next = pq.poll();
dfs(next, list, map);
}
list.add(0, curt);
}Get the largest time spent on each level.
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < manager.length; i++) {
int u = manager[i], v = i;
if (u == -1) {
continue;
}
graph.putIfAbsent(u, new HashSet<>());
graph.get(u).add(v);
}
int totalTime = 0;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{headID, 0});
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] curt = q.poll();
int emp = curt[0], time = curt[1];
totalTime = Math.max(time, totalTime);
if (graph.get(emp) == null) continue;
for (int next : graph.get(emp)) {
q.offer(new int[]{next, time + informTime[emp]});
}
}
}
return totalTime;
}Last updated
Was this helpful?