首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 【537、890、1016】

Leetcode 【537、890、1016】

作者头像
echobingo
发布2019-06-25 10:24:57
3530
发布2019-06-25 10:24:57
举报
题目描述:【String】537. Complex Number Multiplication
解题思路:

计算两个复数相乘,先将两个复数的实数和虚数部分分别提取出来,然后按照复数的运算规则分别计算结果的实数和虚数部分,最后把结果的两部分拼接起来就能得到答案。

Python3 实现:
class Solution:
    def complexNumberMultiply(self, a: str, b: str) -> str:
        real, comp, ret = [0, 0], [0, 0], [0, 0]
        la, lb = a.split("+"), b.split("+")
        real[0], real[1] = int(la[0]), int(lb[0])  # 实数部分
        comp[0], comp[1] = int(la[1][:-1]), int(lb[1][:-1])  # 虚数部分
        ret[0] = real[0] * real[1] - comp[0] * comp[1]
        ret[1] = real[0] * comp[1] + real[1] * comp[0]
        return str(ret[0]) + "+" + str(ret[1]) + "i"  # 拼接结果
题目描述:【String】890. Find and Replace Pattern
解题思路:

这道题意思是给一个模式串,需要从字典中找到和模式串相同类型的单词(模式串和字典中的单词长度相同)。

初步的想法是对于一个单词 word 和模式串 pattern,先遍历 word 中的每个字符,建立一个 pattern 中每个字符到 word 中每个字符的映射关系,比如 pattern = "abb",word = "chh",我们可以建立 {'a':'c', 'b': 'h'};如果 word = "fpk",我们可以建立 {'a':'f', 'b':'k'} ('b': 'p' 被 'b':'k' 覆盖了)。建立好映射关系后,我们再遍历一遍 word 中的每个字符,如果这种映射关系还存在,就说明这个 word 满足 pattern 到 word 的映射。比如上面的 word = "chh" 满足,但是 word = "fpk" 就不满足,因为 'b' 映射到了 'k',而不是 'p'。

但是这样做有一个问题:比如 pattern = "abb",word = "ccc",我们建立的 pattern 到 word 的映射关系是 {'a':'c', 'b':'c'},然后我们再遍历 word 中的每个字符,这种映射关系还是满足的。但是实际上,'a' 和 'b' 不能映射到同一个字符,换句话说,从 word 到 pattern 的映射也要满足。因此,按照上述做法,我们再建立一个 pattern 到 word 的映射,即 {'c':'b'} ('c':'a' 被 'c':'b' 覆盖了)。这时,我们再遍历 word 中的每个字符,发现 pattern = "abb" 就不满足,因为 'c' 映射到了 'b',而不是 'a'。

因此,我们需要建立 word 和 pattern 双向的映射关系,然后再遍历时,要同时满足两个方向的对应。如果不对应,就不满足。

时间复杂度 O(len(words)*len(word)),空间复杂度为 O(len(word))。

Python3 实现:
class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        ans = []
        for word in words:
            ptow = dict()  # pattern到word的映射
            wtop = dict()  # word到pattern的映射
            flag = True
            for i in range(len(word)):
                ptow[pattern[i]] = word[i]
                wtop[word[i]] = pattern[i]
            for i in range(len(word)):
                # 两个方向的映射都要保证唯一性
                if ptow[pattern[i]] == word[i] and wtop[word[i]] == pattern[i]:
                    continue
                else:
                    flag = False
                    break
            if flag:
                ans.append(word)
        return ans

print(Solution().findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc"], "abb"))  # ["mee","aqq"]
题目描述:【String】1016. Binary String With Substrings Representing 1 To N
解题思路:

方法1(时间复杂度 O(len(s)*len(s)),空间复杂度 O(N)):

因为看到 S 的长度为 1000,所以第一种想法很简单,就是将 S 所有的子串找出来,转化为数字,存储在集合中(因为可能重复)。然后,对于 1~N,判断每个数字是不是在集合中,如果不在返回 False,都在返回 True。

Python3 实现:

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        ans = set()
        for i in range(len(S)-1, -1, -1):
            s = 0
            b = 1
            for j in range(i, -1, -1):
                s += int(S[j]) * b  # 字串转化为数字
                b *= 2
                ans.add(s)
        for i in range(1, N+1):  # 各个数字是否在集合中
            if i not in ans:
                return False
        return True

方法2(时间复杂度 O(N),空间复杂度 O(1)):

方法 1 必须先计算出 S 中所有字串转化成的数字,然后再去判断 1~N 是否都在。那么,如果 S 很长,而 N 很小,求 S 的所有字串就浪费了很多时间。因此,我们有第二种解题方法,就是我们遍历 1~N,对于每个数字 i,把 i 转化为二进制 s = bin(i)[2:],然后判断这个二进制字串是否在 S 中。如果 s not in S,直接返回 False。如果所有字串都在,返回 True。 这样做也不用开辟空间。

Python3 实现:

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        for i in range(1, N + 1):
            if bin(i)[2:] not in S:
                return False
        return True

提交后发现,方法 2 时间比方法 1 快了很多。其实,上述代码可以用一行来解决:

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        return all(bin(i)[2:] in S for i in range(1,N+1))

其中, all(iterable) 函数接收一个可迭代的元组或列表,如果都为 True,返回 True,否则返回 False。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019.06.24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:【String】537. Complex Number Multiplication
  • 解题思路:
  • Python3 实现:
  • 题目描述:【String】890. Find and Replace Pattern
  • 解题思路:
  • Python3 实现:
  • 题目描述:【String】1016. Binary String With Substrings Representing 1 To N
  • 解题思路:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档