LeetCode.1128

Stella981
• 阅读 733

这是小川的第394次更新,第428篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第259题(顺位题号是1128)。给定多米诺骨牌列表,当且仅当(a == cb == d)或(a == db == c),dominoes[i] = [a,b]等价于dominoes[j] = [c,d],也就是说,一个多米诺骨牌可以旋转到等价于另一个多米诺骨牌。

返回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


02 第一种解法

暴力解法,直接使用两层循环,会超时。

public int numEquivDominoPairs(int[][] dominoes) {
    int count = 0;
    for (int i=0; i<dominoes.length; i++) {
        for (int j=i+1; j<dominoes.length; j++) {
            int a = dominoes[i][0], b = dominoes[i][1];
            int c = dominoes[j][0], d = dominoes[j][1];
            if ((a == c && b == d) || (a == d && b == c)) {
                count++;
            }
        }
    }
    return count;    
}

03 第二种解法

题目的意思是找可以配对的数组,也就是元素值相等的数组,为了降低时间复杂度,就必须将二维数组降为一维数组。

既然是值相等,那可不可以用加法或者乘法?

不行,因为加法或乘法不能保证唯一性。比如[1,6]和[2,3],做乘法后都等于6,但是这两数组明显不配对。

那我们把它变成一个两位数,较小的一个当做十位数,较大的当做个位数,这样一转换后,二维数组就变成了一维数组,此时题目也就变成了计数的问题。

因为数组元素的取值范围是[1,9],所以最大的两位数是99,最小的两位数是11,使用一个长度为100的整型数组即可。

最后遍历计数数组中的元素,计算对数,其实就是计算排列组合,有n个数,分两次取,总共有n*(n-1)种可能,但是需要去重,因为i要小于j,所以最后就是n*(n-1)/2种可能,将每次的结果累加,最后返回即可。

public int numEquivDominoPairs2(int[][] dominoes) {
    int[] count = new int[100];
    for (int[] temp : dominoes) {
        int num = Math.min(temp[0], temp[1])*10
                + Math.max(temp[0], temp[1]);
        count[num]++;
    }
    int result = 0;
    for (int num : count) {
        result += num*(num-1)/2;
    }
    return result;
}

04 第三种解法

和第二种解法一样的处理逻辑,只是将计数数组换成HashMap来处理。

public int numEquivDominoPairs3(int[][] dominoes) {
    Map<Integer, Integer> map = new HashMap<Integer,Integer>();
    for (int[] temp : dominoes) {
        int num = Math.min(temp[0], temp[1])*10
                + Math.max(temp[0], temp[1]);
        map.put(num, map.getOrDefault(num, 0)+1);
    }
    int result = 0;
    for (Integer times : map.values()) {
        result += times*(times-1)/2;
    }
    return result;
}

05 第四种解法

此解法同样利用HashMap,但是HashMapkey是字符串,先转为一个两位数,然后再转成字符串。另外,计算配对的对数也有一点不同,是用累加来算的,不算最后的n,只从1算到n-1,效果和前面用排列组合的一样。

public int numEquivDominoPairs4(int[][] dominoes) {
    Map<String, Integer> map = new HashMap<String,Integer>();
    int count = 0;
    for (int[] temp : dominoes) {
        StringBuilder sb = new StringBuilder();
        sb.append(""+Math.min(temp[0], temp[1])
                + Math.max(temp[0], temp[1]));
        String str = sb.toString();
        if (map.containsKey(str)) {
            count += map.get(str);
        }
        map.put(str, map.getOrDefault(str, 0)+1);
    }
    return count;
}

06 小结

算法专题目前已连续日更超过八个月,算法题文章265+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,在看、留言、转发就是对我最大的回报和支持!

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
LeetCode算法题
这是悦乐书的第258次更新,第271篇原创<br/01看题和准备今天介绍的是LeetCode算法题中Easy级别的第125题(顺位题号是551)。您将获得一个表示学生出勤记录的字符串。该记录仅包含以下三个字符:'A':缺席。'L':迟到。'P':在场。如果学生的出勤记录不超过一个“A”(缺席)或超过两个
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
ES6 新增的数组的方法
给定一个数组letlist\//wu:武力zhi:智力{id:1,name:'张飞',wu:97,zhi:10},{id:2,name:'诸葛亮',wu:55,zhi:99},{id:3,name:'赵云',wu:97,zhi:66},{id:4,na
Stella981 Stella981
3年前
LeetCode.1170
这是小川的第412次更新,第444篇原创<br/看题和准备今天介绍的是LeetCode算法题中Easy级别的第263题(顺位题号是1170)。在一个非空字符串s上定义一个函数f(s),该函数计算s中最小字符的出现频率。例如,如果s"dcce",则f(s)2,因为最
Stella981 Stella981
3年前
LeetCode.1029
这是小川的第383次更新,第412篇原创<br/01看题和准备今天介绍的是LeetCode算法题中Easy级别的第245题(顺位题号是1029)。公司计划采访的人数为2N。将第i个人飞往城市A的费用是i0,将第i个人飞到城市B的费用是费用i1。返回将
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这