題目描述

題目分析

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

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）
//著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

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