1491-Average-Salary-Excluding-the-Minimum-and-Maximum-Salary
1579. Remove Max Number of Edges to Keep Graph Fully Traversable

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

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);
}
}
1697. Checking Existence of Edge Length Limited Paths

1697. Checking Existence of Edge Length Limited Paths

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.

Read more
319. Bulb Switcher

319. Bulb Switcher

Question

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

Solution

Each position is only switched on its factor rounds, and factors appear in pairs except when squared, where the factor is the same. Therefore, the problem is equivalent to finding the number of times a perfect square appears.

每个位置只在其因子回合会被切换,除了平方时因子相同,其他时候因子都是成对出现的。因此改题目等价于求平方数出现次数。

Code

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int bulbSwitch(int n) {
// bulbs will switch in factor round
// since factor round will appear with pair
// we just need to count square round

return (int) sqrt(n);
}
};

Augment Reality


Augment Reality

Augmented reality (AR) technology can be a valuable tool for architects during the design process, and my work demonstrates how AR can be used to enhance the design process. By combining models in Blender and using AI and prompts to generate images, we were able to select appropriate images and model them in Rhino, creating physical models using 3D printing.

To showcase these models, I developed an AR application in Unity and C# that uses QR code recognition to locate the model and display a virtual version in the app. With this AR technology, clients can swipe left and right or up and down in the app to replace different parts of the model with different materials, providing a visual representation of various material combinations. Additionally, clicking on the screen generates random agents that navigate through the model, providing an interactive experience between the architect and the building.

Read more