it前端是做网站的,网站开发前端和后端的区别,网站注册怎么做屏蔽过滤,网站建设与设计实训总结题目描述 题目分析
看到题目以后第一个想法是遍历数组#xff0c;对每个元素有一个数据结构中保存了该元素出现的次数#xff0c;然后往结果中相加#xff08;表示该元素和前面的对数#xff09;#xff0c;然后再将元素出现的次数加一。 思考用什么数据结构保存元素出现…题目描述 题目分析
看到题目以后第一个想法是遍历数组对每个元素有一个数据结构中保存了该元素出现的次数然后往结果中相加表示该元素和前面的对数然后再将元素出现的次数加一。 思考用什么数据结构保存元素出现次数的时候想到用线性哈希看到数据最大不超过10那么就用10∗xy10*xy10∗xy即可。这样很容易获得所有牌出现的次数。 这个时候我懒得每次往结果中加元素了。如果很容易获得牌出现的次数n想要得到有多少对即就是Cn2C_{n}^{2}Cn2。 看了题解以后我觉得应该我这样的做法复杂度稍微优秀一点点因为往结果中加入是O(n)O(n)O(n)的复杂度但是将所有牌遍历一遍是O(1)O(1)O(1)的复杂度
AC代码
class Solution {
public:int numEquivDominoPairs(vectorvectorint dominoes) {int ret 0;constexpr int MAXN 10;vectorint mp(MAXN * MAXN, 0);for (auto item : dominoes) {int hash;if (item[0] item[1]) {hash item[0] * MAXN item[1];} else {hash item[1] * MAXN item[0];}mp[hash];}for (auto n : mp) {if (n 1) {ret n * (n-1) / 2;}}return ret;}
};官方代码
class Solution {
public:int numEquivDominoPairs(vectorvectorint dominoes) {vectorint 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;}
};//作者LeetCode-Solution
//链接https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/solution/deng-jie-duo-mi-nuo-gu-pai-dui-de-shu-li-yjlz/
//来源力扣LeetCode
//著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。题解写法的优秀的地方在于用了一个三元表达式显得代码比较简洁。
