Algorithm
lc1128_等价多米诺骨牌对的数量
思路:
这个题目的核心就是编码+计数。
很容易看到数据范围是1 <= dominoes[i][j] <= 9，加上多米诺牌可以正反两面，于是就能让2位数字各自为十位和个位，然后进行编码。
也可以按大小排序编码。
编码后，使用map计数，最后遍历map，计算等价多米诺牌对的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
use std::collections::HashMap;
impl Solution {
pub fn num_equiv_domino_pairs(dominoes: Vec<Vec<i32>>) -> i32 {
let mut map = HashMap::new();
for domino in dominoes {
// 将多米诺骨牌编码为一个数字，确保 [a,b] 和 [b,a] 得到相同的编码
let a = domino[0].min(domino[1]);
let b = domino[0].max(domino[1]);
let key = a * 10 + b; // 使用十位和个位进行编码
*map.entry(key).or_insert(0) += 1;
}
let mut result = 0;
for (_, count) in map {
if count > 1 {
result += count * (count - 1) / 2;
}
}
result
}
}
|
题解的逐加法更是妙，直接出现一个就直接累加之前的，也就是和之前的相同牌凑成对子，从而不再需要后续重新乘法计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& dominoes) {
vector<int> num(100);
int ret = 0;
for (auto& it : dominoes) {
int val = it[0] < it[1] ? it[0] * 10 + it[1] : it[1] * 10 + it[0];
ret += num[val];
num[val]++;
}
return ret;
}
};
|
Review
美国的种族贫富差距令人震惊！【TED演讲】
马太效应的真实案例。
Tip
colosseum共创找人平台
Share
cudis分享