2020-01-23 | 1128. 等价多米诺骨牌对的数量

落日映苍穹つ 2022-10-29 11:27 233阅读 0赞

### 1. 题目描述 ###

给你一个由一些多米诺骨牌组成的列表 dominoes。

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。

形式上，dominoes\[i\] = \[a, b\] 和 dominoes\[j\] = \[c, d\] 等价的前提是 ac 且 bd，或是 ad 且 bc。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes\[i\] 和 dominoes\[j\] 等价的骨牌对 (i, j) 的数量。

示例：

输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
    输出：1

提示：

*  1 <= dominoes.length <= 40000
 *  1 <= dominoes\[i\]\[j\] <= 9

### 2. 解题思路 ###

扎个题目中，我们要找的是翻转之后相同数组的对数，所以可以将一组中的两组数字转化为两位数，让大数在前，小数灾后，这样，只要两个数组翻转后能相等，那么他们转化成的两位数也一定是相等。

由于这两个数字都是1-9的数，所以，我们可以初始化一个长度为100的数组，将转化成的两位数作为索引，在数组中进行标记，这样如果有一样的，结果就加一。

**复杂度分析:**

*  时间复杂度：O(N)， 需要遍历一遍数组，其中N是数组的长度
 *  空间复杂度：O(1)， 因为1 <= dominoes\[i\]\[j\] <= 9所以键值得组合是有限的常数

### 3. 代码实现 ###

/** * @param {number[][]} dominoes * @return {number} */
    var numEquivDominoPairs = function(dominoes) { 
        let res = 0
        const arr = new Array(100).fill(0)
        for(let [x, y] of dominoes){ 
            const value = x > y ? x * 10 + y : y * 10 + x
            res += arr[value]
            arr[value]++ 
        }
        return res
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210213221816163.png]

[20210213221816163.png]: /images/20221024/4d301b0577ae43689f95ee5304cb7ccf.png?

发表评论取消回复

表情：

评论列表（有 0 条评论，233人围观）

还没有评论，来说两句吧...

相关阅读

相关 1128. 等价多米诺骨牌对的数量

给你一个由一些多米诺骨牌组成的列表 dominoes。如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。形式上

超、凢脫俗/ 2023年10月04日 18:56/ 0 赞/ 36 阅读

相关 P1282-多米诺骨牌

1 include <bits/stdc++.h> 2 define maxn 13003 3 define _for(i,a,b) for(int

￡神魔★判官ぃ/ 2023年06月01日 08:51/ 0 赞/ 89 阅读

相关多米诺骨牌

在课堂上，我们分析了棋盘覆盖问题，同学们也看了我的程序运行的情况，今天我们来看一下另外一个覆盖问题。今天的问题是这样的：用n个2X1的矩形（这种矩形我们以后称之为骨牌或多米诺）

╰半橙微兮°/ 2023年02月23日 05:25/ 0 赞/ 108 阅读

相关【每日一题】 1128. 等价多米诺骨牌对的数量

【每日一题】 1128. 等价多米诺骨牌对的数量 > 避免每日太过咸鱼，一天搞定一道LeetCode算法题一、题目描述给你一个由一些多米诺骨牌组成的列表 `d

分手后的思念是犯贱/ 2023年01月12日 10:10/ 0 赞/ 184 阅读

相关 LeetCode 1128. 等价多米诺骨牌对的数量

给你一个由一些多米诺骨牌组成的列表 dominoes。如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。形式上

女爷i/ 2023年01月11日 09:26/ 0 赞/ 192 阅读

相关 LeetCode：1128. Number of Equivalent Domino Pairs等价多米诺骨牌对的数量（C语言）

题目描述：给你一个由一些多米诺骨牌组成的列表 dominoes。如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等

冷不防/ 2023年01月11日 08:33/ 0 赞/ 89 阅读

相关多米诺骨牌问题

> 现有n块”多米诺骨牌”s1,s2,s3,…sn水平放成一排,每次骨牌si包含左右两个部分,每个部分赋予一个非负整数值,如下图所示为包含6块骨牌的序列.骨牌可做180度旋转,

超、凢脫俗/ 2022年12月24日 09:57/ 0 赞/ 238 阅读

相关 leetcode.等价多米诺骨牌对的数量

[1128. 等价多米诺骨牌对的数量][1128.] 中文给你一个由一些多米诺骨牌组成的列表 `dominoes`。如果其中某一张多米诺骨牌可以通过旋转 `0

朴灿烈づ我的快乐病毒、/ 2022年11月19日 07:45/ 0 赞/ 217 阅读

相关 2020-01-23 | 1128. 等价多米诺骨牌对的数量

1. 题目描述给你一个由一些多米诺骨牌组成的列表 dominoes。如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张

落日映苍穹つ/ 2022年10月29日 11:27/ 0 赞/ 234 阅读

相关【题解】多米诺骨牌

题目描述一个矩形可以划分成M×N个小正方形，其中有一些小正方形不能使用。一个多米诺骨牌占用两个相邻的小正方形。试问整个区域内最多可以不重叠地放多少个多米

比眉伴天荒/ 2021年11月11日 03:58/ 0 赞/ 747 阅读