最大长度单词乘积
解法:位运算
暴力解法需要遍历每一对单词,对其中每个字母进行判断是否含有公共字母。复杂度大于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
两个列表最小索引总和
解法:哈希表
对于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