Question

We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It’s transfer season, and some employees want to change the building they reside in.

You are given an array requests where requests[i] = [fromi, toi] represents an employee’s request to transfer from building fromi to building toi.

All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.

Return the maximum number of achievable requests.

Question

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

• nums1[i] == nums2[j], and
• the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

Question

You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the ith obstacle.

For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:

• You choose any number of obstacles between 0 and i inclusive.
• You must include the ith obstacle in the course.
• You must put the chosen obstacles in the same order as they appear in obstacles.
• Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.

Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.

Question

Alice and Bob have an undirected graph of n nodes and three types of edges:

• Type 1: Can be traversed by Alice only.
• Type 2: Can be traversed by Bob only.
• Type 3: Can be traversed by both Alice and Bob.

Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.

Solution

对于A，B皆互通的边的权重比只对A或B连通的边的权重高。（多提供另一种联通）

因此先选择双连通的边，并加入两个并查集，由于选择了边，因此res–。

然后选择单连通的边，如果并查集中的两个节点并不互通，则选择这个边，并加入对应并查集。

每次连通两个节点，则集合数量减少1。

如果最终两个并查集的数量不是1，则并非所有节点都互相连通，返回-1。

否则返回未选择的边数res。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFind ufA = new UnionFind(n), ufB = new UnionFind(n);
        int res = edges.length;

        for(int[] edge : edges){
            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1; 
            if(type == 3 && !ufA.isConnected(u, v)){
                ufA.union(u, v);
                ufB.union(u, v);
                res--;
            }

        }

        for(int[] edge : edges){
            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1; 

            if(type == 1 && !ufA.isConnected(u, v)){
                ufA.union(u, v);
                res--;
            }
            else if(type == 2 && !ufB.isConnected(u, v)){
                ufB.union(u, v);
                res--;
            }
        }
        return ufA.sets == ufB.sets && ufA.sets == 1 ? res : -1;
    }
}

class UnionFind{
    int[] parent;
    int[] rank;
    public int sets;

    UnionFind(int n){
        parent = new int[n];
        rank = new int[n];
        sets = n;
        for(int i = 0; i < n; i++){
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int i){
        if(parent[i] == i){
            return i;
        }
        return find(parent[i]);
    }

    public void union(int a, int b){
        int pa = find(a), pb = find(b);
        if(pa != pb) sets--;
        if(rank[pa] < rank[pb]){
            parent[pa] = pb;
        }
        else if(rank[pa] > rank[pb]){
            parent[pb] = pa;
        }
        else{
            parent[pa] = pb;
            rank[pb]++;
        }
    }

    public boolean isConnected(int a, int b){
        return find(a) == find(b);
    }
}

Question

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.