5130-等价多米诺骨牌对的数量

chaos_G 发布于2019-08-16 18:40 / 894人阅读

摘要：如果其中某一张多米诺骨牌可以通过旋转度或度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。等价多米诺骨牌对的数量暴力破解法有效解答等价多米诺骨牌对的数量由于，所以最大值不会超过以形式表示骨牌对，这个是翻转度即本身翻转度后，只要累加一次即可

前言

Weekly Contest 146的等价多米诺骨牌对的数量：

给你一个由一些多米诺骨牌组成的列表 dominoes。
如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。
形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。
在 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

解题思路

一开始我是试了一下暴力破解这个方法，可惜运行超时，只好另想它法了。

后续参考了Java中的HashMap的位桶的设计，思路如下：

数字result表示等价的骨牌对个数，数组arr表示多米诺骨牌出现的次数，其中数组下标i（假设骨牌dominoe=[a,b]，则i=a*10+b）表示对应的多米诺骨牌，arr[i]表示该骨牌出现的次数

遍历多米诺骨牌列表dominoes，对于每个骨牌dominoe，假设dominoe=[a,b]，然后按照以下逻辑处理

使用a*10+b计算出旋转0度时在arr的下标index1；使用b*10+a计算出旋转180度是在arr的下标index2

如果index1等于index2，即表示dominoe的a等于b，此时result增加arr[index1]，同时arr[index1]的值自增（避免多累加一次）即可

如果index1不等于index2，即表示dominoe的a不等于b，此时result增加arr[index1]，同时arr[index1]和arr[index2]都自增。

实现代码 暴力破解

暴力破解的方法会出现运行超时的情况，这个是一个错误的示例，列出来给大家参考一下。

    /**
     * 5130. 等价多米诺骨牌对的数量
     * 暴力破解法
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;
        for (int i = 0; i < dominoes.length; i++) {
            int a = dominoes[i][0];
            int b = dominoes[i][1];
            for (int j = i+1; j < dominoes.length; j++) {
                int c = dominoes[j][0];
                int d = dominoes[j][1];
                if((a==c && b==d) || (a==d && b==c)){
                    ++result;
                }
            }
        }
        return result;
    }

有效解答

    /**
     * 5130. 等价多米诺骨牌对的数量
     *
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;
        // 由于1 <= dominoes[i][j] <= 9，所以最大值不会超过99
        int[] arr = new int[100];
        for (int i = 0; i < dominoes.length; i++) {
            // 以ij形式表示骨牌对(i,j)，这个是翻转0度（即本身）
            int index1=dominoes[i][0]*10+dominoes[i][1];
            // 翻转180度后
            int index2=dominoes[i][1]*10+dominoes[i][0];
            if(index1 == index2){ // i==j，只要累加一次即可
                result+=arr[index1];
                arr[index1]++;
            }else{
                result+=arr[index1];
                arr[index1]++;
                arr[index2]++;
            }
        }
        return result;
    }

云服务器 GPU云服务器戴尔5130cdn 多米诺骨牌 python对的处理等价

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75530.html

第3章：抽象数据类型（ADT）和面向对象编程（OOP） 3.2设计规约

摘要：程序失败时，很难确定错误的位置。它保护客户免受单位工作细节的影响。将前提条件放在中，并将后置条件放入和。涉及可变对象的契约现在取决于每个引用可变对象的每个人的良好行为。设计规约按规约分类比较规约它是如何确定性的。大纲 1.编程语言中的功能/方法2.规约：便于交流的编程，为什么需要规约行为等同规约结构：前提条件和后条件测试和验证规约3.设计规约分类规约图表规约质量规约4.总结编程...

mozillazg 2019-08-16 12:34 评论0 收藏0
【EASYDOM系列教程】之获取内联样式

摘要：回顾什么是内联样式所谓内联样式，就是通过页面元素的属性为当前元素定义样式。对象提供的属性和方法可以帮助我们获取样式的具体内容。遍历对象由于对象具有属性，返回该对象的属性的数量。方法通过获取的样式属性名，这种方式也可以通过方式进行替换。回顾什么是内联样式所谓内联样式，就是通过 HTML 页面元素的 style 属性为当前元素定义 CSS 样式。以下代码示例，就是通过 style 属...

xiaodao 2019-08-22 11:05 评论0 收藏0
关于javascript函数式编程中compose的实现

摘要：结论这次主要介绍了函数式编程中的函数的原理和实现方法，由于篇幅原因，我把打算分析的源码实现放到下一篇来介绍，可以说实现的更加函数式，需要单独好好分析。上一篇文章介绍了javascript函数式编程中curry（柯里化）的实现，当然那个柯里化是有限参数的柯里化，等有机会在补上无限参数的那一种柯里化，这次主要说的是javascript函数式编程中另外一个很重要的函数compose，com...

jonh_felix 2019-08-20 14:21 评论0 收藏0
《javascript高级程序设计》笔记：Function类型

摘要：这么长时间没有写博客，就是因为函数这部分比较麻烦，自己一直想抽出大把的时间来研究这个，可是结果却是一拖再拖，这样不好。这么长时间没有写博客，就是因为函数这部分比较麻烦，自己一直想抽出大把的时间来研究这个，可是结果却是一拖再拖，这样不好。有时间就写才是王道啊，不然这计划得一直卡在这里了.. 1. 几个概念函数：将代码进行封装, 复用的逻辑单元（代码）对象：无序键值对的集合数组：有序键...

habren 2019-08-21 12:05 评论0 收藏0
Codepen 每周精选：22个页面特效（2018-5-2）

摘要：按下右侧的点击预览按钮可以在当前页面预览，点击链接可以打开原始页面。按下右侧的点击预览按钮可以在当前页面预览，点击链接可以打开原始页面。 1. 观影打分特效https://codepen.io/PointC/pen... 2. 纯 css 写的骑自行车的动画https://codepen.io/dmaristem/... 3. 移动端菜单特效https://codepen.io/mi...

ddongjian0000 2019-08-29 15:15 评论0 收藏0