Leetcode【648、1072】
2019-07-29 本文已影响0人
牛奶芝麻
问题描述：【Hash Table】648. Replace Words
解题思路：
这道题是给一个词典和句子，词典中保存着词根，将句子中的所有继承词（在词根后面加字符）用对应词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
因为句子中的单词数 <= 1000 并且每个单词长度 <= 1000，因此可以对句子中的每个单词 word 的每个字符 ch 进行遍历，并且用一个变量 pre 记录单词 word 的前缀。如果 pre 在词典中能找到（为加快查找速度，可以将词典转化为 set），说明以 pre 为前缀的 word 可以用词典中的对应词根替换掉。如果 pre 在词典中都不能找到，则不替换即可。
如果句子中单词数为 m，单词长度为 n，则时间复杂度为 O(m*n)。
Python3 实现：
class Solution:
def replaceWords(self, dict: List[str], sentence: str) -> str:
ans = []
setd = set(dict) # 转化为集合，使得查找为O(1)
for word in sentence.split(" "): # 按照空格划分句子中的单词
pre = "" # 记录单词前缀
flag = False
for ch in word:
pre += ch # 记录word前缀
if pre in setd: # 如果word前缀在集合中
ans.append(pre)
flag = True
break
if not flag: # 没有在集合中找到该单词的根
ans.append(word)
return " ".join(ans)
问题描述：【Hash Table】1072. Flip Columns For Maximum Number of Equal Rows
解题思路：
这道题是给一个01矩阵，通过翻转列使得相等的行数（一行全0或全1）最多。
- 根据题意，我们翻转的目的是保证其中一行全是 0（或者 1）。所以可以考虑固定每一行，使得这一行全部变成 0 （或者 1），然后统计其他行是否有所有值都相等的。
- 进一步发现，其实没有必要对固定的那一行真正进行翻转。当某些行的值完全相等或完全相反时，他们总会同时变为符合条件的行。比如 [0,1,0] 和 [1,0,1] 总会同时变成符合条件的行。
基于上述分析，可以直接用 Hash Table 统计行的种类有多少个，找到行的种类数最多的就是答案。
举例，matrix = [[0,0,0],[0,0,1],[1,1,0]]
- 第一行 [0,0,0]，则 dic = { (0,0,0): 1}
- 第二行 [0,0,1]，则 dic = { (0,0,0): 1, (0,0,1): 1}
- 第三行 [1,1,0]，因为第一个数字是 1，可以先将每一位按位取反，变成 [0,0,1]，发现 [0,0,1] 在 dic 中出现过，则统计数加 1，dic = { (0,0,0): 1, (0,0,1): 2}。
- 遍历结束，dic 中记录的是如果一行变成 0 或者变成 1 的行的种类的数目，则 max(dic.valuesI()) 就是答案。
如果矩阵为 m*n，则时间复杂度为 O(m*n)，空间复杂度为 O(k*n)，k 为行种类的个数。
Python3 实现：
class Solution:
def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
dic = collections.defaultdict(int) # 统计不同行的种类的个数
for row in matrix:
if row[0] == 0:
dic[tuple([col for col in row])] += 1
elif row[0] == 1: # 如果某一行以1开头，则先按位取反，再加入到dic中
dic[tuple([1-col for col in row])] += 1
return max(dic.values())
