Leetcode【648、1072】

问题描述:【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())

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券