力扣1128,等价多米诺骨牌对——python

题目的意思我们很容易去理解,但是他们还有可能反转才相等,那太麻烦了吧,不如我们直接用map函数对内部的所有小列表排序

        newDominoes = map(lambda x:sorted(x),dominoes)

之后我们只需要去重就行了,但是我们注意有一个坑,每有一个重复的出现,对数实际上是加的原来的重复个数,如果原来由两个[1, 2],再出现一个[1, 2],他们的对数实际上是加了两个,而不是只加一个。
我们的第一个方法肯定会暴力简单的循环,双循环就可以完成了所有,但是两个循环复杂度似乎有点高直接超出了时间限制

        ps = 0
        m = []
        for x in newDominoes:
            m.append(x)
        for i in range(len(m)-1):
            for j in range(i+1, len(m)):
                if m[i] == m[j]:
                    ps += 1
        return ps

这里的map类型没有len函数,于是我就重新弄了个列表
我们会尝试用集合去重,但是列表是不可hash类型,我们如果用字典的话也是相同的,字典的键也要求不可hash,这我们可咋办,我们可以尝试把列表里的数转成字符串合并以下,但是似乎太麻烦了,我们可以*10直接合并

for i, j in newDominoes:
    num = 10*i+j

这样就是唯一的了,之后我们只需要计算就行了

        n = len(dominoes)
        newDominoes = map(lambda x:sorted(x),dominoes)
        result = {}
        x = 0
        for i, j in newDominoes:
            num = 10*i+j
            if num not in result.keys():
                result[num] = 1
            else:
                x += result[num]
                result[num] = result[num]+1
        return x

在这里插入图片描述


版权声明:本文为qq_51718832原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。