題目描述

題目分析

看到題目以后第一個想法是遍歷數(shù)組，對每個元素有一個數(shù)據(jù)結(jié)構(gòu)中保存了該元素出現(xiàn)的次數(shù)，然后往結(jié)果中相加（表示該元素和前面的對數(shù)），然后再將元素出現(xiàn)的次數(shù)加一。
思考用什么數(shù)據(jù)結(jié)構(gòu)保存元素出現(xiàn)次數(shù)的時候想到用線性哈希，看到數(shù)據(jù)最大不超過10，那么就用$10?x+y$即可。這樣很容易獲得所有牌出現(xiàn)的次數(shù)。
這個時候我懶得每次往結(jié)果中加元素了。如果很容易獲得牌出現(xiàn)的次數(shù)n，想要得到有多少對，即就是$C_n^2$。
看了題解以后，我覺得應(yīng)該我這樣的做法復(fù)雜度稍微優(yōu)秀一點點，因為往結(jié)果中加入是$O(n)$的復(fù)雜度，但是將所有牌遍歷一遍是$O(1)$的復(fù)雜度

AC代碼

class Solution { public:int numEquivDominoPairs(vector<vector<int>>& dominoes) {int ret = 0;constexpr int MAXN = 10;vector<int> 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(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;} };//作者：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） //著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

題解寫法的優(yōu)秀的地方在于用了一個三元表達式，顯得代碼比較簡潔。

總結(jié)

以上是生活随笔為你收集整理的每日一题：leetcode1128.等价多米诺骨牌对数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。