【LeetCode】Day32

最大长度单词乘积

【LeetCode】Day32
解法:位运算
暴力解法需要遍历每一对单词,对其中每个字母进行判断是否含有公共字母。复杂度大于O(n^2)。考虑到题目中规定只包含小写字母,因此可以考虑用26位二进制掩码来表示字母,0-25位分别表示a-z。由此对于每个单词,我们可以计算其字母种类对应的二进制表示,进而对公共字母进行判断。因为每一种字母组合有其唯一的二进制表示,所以可以对单词是否含有公共字母进行判断。
位运算优化:由于我们要求的是最大长度乘积,因此若某个单词的字母集和另一个单词相同,但单词长度更小,则可以忽略对其与其它字母之间的判断。

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        def hashset(word):
            # 用26位位运算表示二十六个字母在word中被使用的情况
            return sum(1 << (ord(c) - ord('a')) for c in set(word))
        print(hashset("aaa"))
        d, ans = defaultdict(int), 0
        for w in words:
            h = hashset(w)
            # 位运算优化
            if d[h] < len(w):
                for other in d:
                    # 如果位运算&的结果为0,说明他们没有使用过同样的字母,可以计算答案
                    if not other & h:
                        ans = max(d[other] * len(w), ans)
                d[h] = len(w)
        return ans

两个列表最小索引总和

【LeetCode】Day32
解法:哈希表
对于list1和list2,先遍历list1,构建各餐厅对应索引字典,key=餐厅,value=索引。
再遍历list2,判断餐厅是否在字典中,若不在,则忽略,否则进一步判断其索引和是否小于当前最小索引和。
若更小,则更新min_index和result列表。若相等,则更新result列表,增加当前餐厅。否则忽略该餐厅。

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        n2id = {}
        min_sum = float("inf")
        result = []
        for i, name in enumerate(list1):
            if name not in n2id:
                n2id[name] = i 
        for i, name in enumerate(list2):
            if name in n2id:
                # print(i + n2id[name])
                if i + n2id[name] < min_sum:
                    result = [name]
                    min_sum = i + n2id[name]
                elif i + n2id[name] == min_sum:
                    result.append(name)
        return result 

上一篇:day32 HTML


下一篇:day32