Leetcode_Contest_146

1128. Number of Equivalent Domino Pairs

check a list of dominoes, to see the number of pairs.
Ex: Input: dominoes = [[1, 2], [2,1], [3, 4], [5, 6]];
Outout: 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
	int numEquivDominoPairs(vector<vector<int>>& dominoes){
		map<pair<int, int>, int> freq;
		long long total = 0;
		for(vector<int> domino: dominoes){
			if(domino[0] > domino[1]){
				swap(domino[0], domino[1]);
			}
			total += freq[make_pair(domino[0], domino[1])]++;
		} 
		return total;
	}
}

leetcode.1129 Shortest Path with Alternating Colors

BFS: 1 = red, 2 = blue, 0 = root-edge(special case)

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
public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges){
	List<Integer>[] res = new ArrayList[n], blues = new ArrayList[n];
	for(int[] e: red_edges){
		if(reds[e[0]]==null) reds[e[0]] = new ArrayList<>();
	reds[e[0]].add(e[1]);
 	}
 	for(int[] e: blue_edges){
	 	if(blues[e[0]]==null) blue[e[0]] = new ArrayList<>();
	 	blues[e[0]].add(e[1]);
 	}
 	Queue<int[]> q = new LinkedList<>();
 	int[] res = new int[n];
 	Arrays.fill(res, -1);
 	q.add(new int[]{0, 0});
 	int moves = 0;
 	Set<String> seen = new HashSet<>();
 	while(!q.isEmpty()){
 		int size = queue.size(){
 		for(int i = 0; i < size; i++){
 			int curr = q.remove();
 			String key = curr[0] + " " + curr[1];
 			if(seen.contains(key)) continue;
 			seen.add(key);
 			if(curr[1] == 2 || curr[1] == 0)
 				if(reds[curr[0]] != null){
 					for(int child: reds[curr[0]])
 						q.add(new int[]{child, 1});
 			} 
 			if(curr[1]==1 || curr[1] == 0)
 				if(blues[curr[0]] != null)
 					for(int child: blues[curr[0]])
 						q.add(new int[]{child, 2});
 		}
 		moves++;
 	}
 	return res;
 }
}

Leetcode popular answers. initialize all nodes as unreachable(-1)