leetcode day 8【 822. 翻转卡片游戏】从暴力到哈希

leetcode day 8【 822. 翻转卡片游戏】从暴力到哈希

解题思路 暴力

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        minnum = 0
        samelist = []
        for i in range(len(fronts)):
            if fronts[i] == backs[i]:
                samelist.append(fronts[i])
        for i in range(len(fronts)):
            if fronts[i] not in samelist and (minnum == 0 or fronts[i] < minnum):
                minnum = fronts[i]
            if backs[i] not in samelist and (minnum == 0 or backs[i] < minnum):
                minnum = backs[i]
        return minnum

引入哈希

用哈希代替重复列表

• set:

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        minnum = 2001
        sameset = set()
        for i in range(len(fronts)):
            if fronts[i] == backs[i]:
                sameset.add(fronts[i])
        for ele in fronts+backs:
            if ele not in sameset:
                minnum = min(ele, minnum)
        return minnum if minnum != 2001 else 0

• dict:

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        minnum = 2001
        same = {fronts[i] for i in range(len(fronts)) if fronts[i] == backs[i]}
        for ele in fronts+backs:
            if ele not in same:
                minnum = min(ele, minnum)
        return minnum if minnum != 2001 else 0

总结：
python中的set是一个无重复的集合。
python中的hash可以用字典来实现，字典的更新可以直接用dict[…] = ……更新，其中，key可以是非字符串。