Leetcode 【49、539、709、833、916】
Leetcode 【49、539、709、833、916】
题目描述：【Hash Table】49. Group Anagrams
解题思路：
给一个字符串数组，按照字母异序词分组。字母异位词指字母相同，但排列不同的字符串。
利用字典数组。可以对数组中的每个字符串排序，将排序结果作为键，原字符串作为值。如 { "aet": ["eat","aet","tea"] }。最后字典中所有的值就是答案。
Python3 实现：
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dic = dict()
for str in strs:
s = "".join(sorted(str)) # 对字符串排序
if s not in dic:
dic[s] = [str]
else:
dic[s].append(str)
return list(dic.values())题目描述：【Sort】539. Minimum Time Difference
解题思路：
给定一个 24 小时制（小时:分钟）的时间列表，找出列表中任意两个时间的最小时间差并已分钟数表示。
很明显，先将字符数组按照（小时:分钟）从小到大排序，然后依次比较相邻时间的分钟数差值，更新最小时间差。最后记得还要比较最后一个和第一个时间的差值，如 ["00:00", "23:59"] 的最小差值是 1，而不是 (23-0)*60+59。
Python3 实现：
class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
timeFormat = []
min_minute = float("inf")
for time in timePoints:
timeFormat.append([int(time.split(":")[0]), int(time.split(":")[1])])
timeFormat.sort()
for i in range(1, len(timeFormat)):
min_minute = min(min_minute, ((timeFormat[i][0] - timeFormat[i-1][0]) * 60 + timeFormat[i][1] - timeFormat[i-1][1]))
min_minute = min(min_minute, ((timeFormat[0][0] - timeFormat[-1][0] + 24) * 60 + timeFormat[0][1] - timeFormat[-1][1]))
return min_minute题目描述：【String】709. To Lower Case
解题思路：
水题，实现 .lower() 方法。直接看代码。
Python3 实现：
class Solution:
def toLowerCase(self, str: str) -> str:
ans = ""
for s in str:
if 'A' <= s <= 'Z':
ans += chr(ord(s) + 32) # 'A': 65, 'a': 97
else:
ans += s
return ans题目描述：【Sort，Hash Table】833. Find And Replace in String
解题思路：
给一个字符串 S、索引数组 indexes、源数组 sources、目标数组 targets，根据 indexes[i] 找到字符串中的 sources[i]，将其替换成 targets[i]。替换的时候，相邻索引不会出现重叠情况。
方法1（Sort）：
因为没有说 indexes 是按照从小到大的顺序排序的，因此可以先按照 indexes 对 indexes、sources 和 targets 从小到大排序。然后，就可以从左到右遍历字符串 S 的每个位置 i：
- 如果 indexes 已经全部替换或者某个字符 S[i] 不在 indexes[i] 中，就直接拷贝该字符到结果中，同时 i 向后移动 1 位。
- 否则，找到了 i == indexes[j]（j 指向 indexes），判断 sources[j] 是否和 S 的位置对应。如果不是，结果直接加上原来字符对应位置的子串；如果是，结果加上 targets[j]，表示进行替换。一个 indexes[j] 判断完成后，i 向后移动 len(sources[j]）位，j 向后移动一位，继续上一步的判断。
- 最后，返回的结果就是答案。
Python3 实现：
class Solution:
def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
if len(indexes) == 0:
return S
# 先按照indexes排序
sort = sorted(zip(indexes, sources, targets))
for i in range(len(indexes)):
indexes[i], sources[i], targets[i] = sort[i][0], sort[i][1], sort[i][2]
ans = ""
i = j = 0 # i指向S的每个位置，j指向indexes的每个位置
while i < len(S):
if j == len(indexes) or i != indexes[j]: # indexes已经找完或不在indexes中
ans += S[i]
i += 1 # i向后移动一位
else:
if S[indexes[j]:indexes[j]+len(sources[j])] != sources[j]: # sources和S不对应
ans += S[i:i+len(sources[j])]
else:
ans += targets[j]
i += len(sources[j]) # i的下一个位置
j += 1 # j向后移动一位
return ans
print(Solution().findReplaceString("vmokgggqzp", [3,5,1], ["kg","ggq","mo"], ["s","so","bfr"])) # "vbfrssozp"方法2（Hash Table）：
可以不用对 indexes 排序，也能实现字符查找和替换吗？是可以的，这时我们可以利用字典 dic，字典 dic 的键是 indexes 中的索引 indexes[i]，字典 dic 的值是一个元组 (sources[i], targets[i])。
同样的，从左到右遍历字符串 S 的每个位置 i：
- 如果位置 i 在字典 dic 中找到并且 S[i:] 是以 dic[i][0] 开头的，说明可以进行替换，结果加上 dic[i][1]，同时 i 向后移动 len(dic[i][0]) 位。
- 否则，不进行替换，结果加上原字符 S[i]，i 向后移动 1 位即可。
Python3 实现：
class Solution:
def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
dic = {i: (s, t) for i, s, t in zip(indexes, sources, targets)}
i, ans = 0, ""
while i < len(S):
if i in dic and S[i:].startswith(dic[i][0]):
ans += dic[i][1]
i += len(dic[i][0])
else:
ans += S[i]
i += 1
return ans
print(Solution().findReplaceString("vmokgggqzp", [3,5,1], ["kg","ggq","mo"], ["s","so","bfr"])) # "vbfrssozp"题目描述：【Hash Table】916. Word Subsets
解题思路：
有两个单词数组 A 和 B，B 中每个单词 b 的每个字符 b[i] 可能包括在 A 中的某个单词 a 里面。找到满足 B 中每个单词 b 的每个字符 b[i] 都在 A 中的某个单词 a 中的这样的单词 a。
A 和 B 单词数组长度为 10000 且 A 和 B 中每个单词长度为 10，如果直接暴力，时间复杂度为 10000*10000*10*10，超时！如果将 A 和 B 中每个单词的每个字符存储到数组字典中，并统计每个字符出现的次数，时间复杂度为 10000*10000，也会超时！
所有，只要涉及到遍历 A 和 B 两层循环的，都超时了。那么，我们就要想到怎么避免 10000*10000 这种双循环。
再读一下题目，因为我们要将 B 中的每个单词 b 的每个字符 b[i] 都同 A 中某个单词 a 来比较，因此我们可以将 B 中的每个单词 b 合并到一个字典中，并统计各个字符出现的次数。比如 B = ["eo", "ooc"]，对于第一个单词 "eo"，我们得到字典 {"e": 1, "o": 1}；对于第二个单词 "ooc"，我们得到字典 {"e":1, "o":2, "c": 1}（更新 "o" 为某个单词中出现的最多次数，同时把 "c" 加入字典）。这样，我们就可以得到一个字典 dicB，记录了 A 中每个单词 a 都要满足的条件。
因此，这时我们的双层循环就变为 10000*26（26 为字典 dicB 中最多有 26 个小写字母的键）。
得到 dicB 后，遍历 A 中每个单词 a，对 a 中每个字符计数（使用 dic = collections.Counter(a) 得到一个字典）。然后，判断 dicB 中的每个字符（键 k）是否都在 dic 中且 dicB 中的每个字符出现的次数（值 v）不大于对应的 dic[k]，说明这个单词 a 就是满足题意的，将其加入到结果 ans 中。
Python3 实现：
class Solution:
def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
ans = []
# 处理B数组，计数，将公共部分合并到一个字典中
dicB = dict()
for b in B:
dic = collections.Counter(b)
for k, v in dic.items():
dicB[k] = max(dicB.get(k,0), v)
# 处理A数组，计数
for a in A:
dic = collections.Counter(a)
if all((k in dic and v <= dic[k]) for k, v in dicB.items()):
ans.append(a)
return ans腾讯云开发者
