Google面试问题指南:使用Python删除重复出现的字符

栏目: Python · 发布时间: 5年前

内容简介:本文阅读时长:5min当下,谷歌的面试时常被程序员提及。有时,面试能让我们发挥最好的一面,从而获得我们想要的职位。

Google面试问题指南:使用 <a href='https://www.codercto.com/topics/20097.html'>Python</a> 删除重复出现的字符

  • 来源 | 愿码(ChainDesk.CN) 内容编辑
  • 愿码Slogan | 连接每个 程序员 的故事
  • 网站 | http://chaindesk.cn
  • 愿码愿景 | 打造全学科IT系统免费课程,助力小白用户、初级工程师0成本免费系统学习、低成本进阶,帮助BAT一线资深工程师成长并利用自身优势创造睡后收入。
  • 官方公众号 | 愿码 | 愿码服务号 | 区块链部落
  • 免费加入愿码全思维工程师社群 | 任一公众号回复“愿码”两个字获取入群二维码

本文阅读时长:5min

当下,谷歌的面试时常被程序员提及。有时,面试能让我们发挥最好的一面,从而获得我们想要的职位。

本文我们将讨论一个可能出现在Google面试中的经典问题。

  • 愿码提示:如果您是编码老手,您可能已经知道如何解决这个问题!如果你经验较浅,那么你一定会从本文中受益。

问题

给定一个字符串作为输入,删除任何重复出现的字符,并返回新字符串。

Google面试问题指南:使用Python删除重复出现的字符

正如我们从上面的例子中看到的那样,输出是“abc”,因为我们删除了第二个'a','b'和'c'。

首先,让我们在Python 2.7中设置我们的功能。

def deleteReoccurringCharacters(string):

为了解决这个问题,我们将使用一个名为HashSet的特定数据结构。

Google面试问题指南:使用Python删除重复出现的字符

您可以将集合视为与数组类似,但有两个主要例外。

  1. 这是完全无序的
  2. 它不能包含重复项

因为它是无序的,我们还需要一个空字符串来存储我们按顺序添加到集合中的字符。这将是我们返回的字符串。

我们来设置一下

def deleteReoccurringCharacters(string):
    seenCharacters = set()
    outputString = ''

现在我们已经建立了我们需要的数据结构,让我们再来谈谈我们的算法。

由于集合在内存中的工作方式,它的查找时间复杂度为0(1)。

这意味着我们可以用它来检查我们是否已经访问过一个角色!

我们的算法

遍历初始字符串中的所有字符并执行以下操作:

第1步:检查角色是否已经在我们的设置中

第2歩:如果它不在集合中,则将其添加到集合中并将其附加到字符串

让我们看看代码中的内容

for char in string:
    if char not in seenCharacters:
        seenCharacters.add(char)
        outputString += char

我们不必担心“else”情况,因为我们不需要处理重复出现的字符本身。现在剩下要做的就是返回outputString。

这是完成的代码的样子:

def deleteReoccurringCharacters(string):
    seenCharacters = set()
    outputString = ''
    for char in string:
        if char not in seenCharacters:
            seenCharacters.add(char)
            outputString += char
    return outputString

如果这是一次面试,招聘人员会问你时间和空间的复杂性。我们来分析一下。

时间复杂性

迭代整个输入字符串的时间复杂度为O(n),因为字符串本身有n个字符。

但是,由于HashSet的查找时间为O(1),所以不会影响时间复杂度。最后的时间复杂度为O(n)。

空间复杂性

最糟糕的情况是,我们得到一个包含所有唯一字符的字符串。例如,“abcdef”。

在这种情况下,我们将在字符串和集合中存储所有n个元素。然而,我们也受到英语字母大小的限制。这是一个很好的机会来问我们的面试官什么类型的字符在字符串中是唯一的(大写/小写/数字/符号)。假设初始字符串将包含字母表中的小写字母,因为字母表是有限的,所以集合和输出字符串不能大于26个字符。留给我们最坏的情况空间复杂度为O(1)。


以上所述就是小编给大家介绍的《Google面试问题指南:使用Python删除重复出现的字符》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

黑客

黑客

Steven Levy / 赵俐、刁海鹏、田俊静 / 机械工业出版社华章公司 / 2011-10-31 / 69.00元

黑客文化和伦理的奠基之作,计算机专业人士必读。 二十五周年新版,涵盖比尔·盖茨、马克·扎克伯格、理查德·斯托曼、史蒂夫·沃兹尼克等著名黑客的最新资料。 多年前,射击游戏之父、Doom游戏的作者约翰·卡马克由于读到本书,坚定了游戏开发的决心。 谷歌首席信息官本·弗里德也是本书的忠实读者。 探寻黑客文化的本质,体会黑客精神的精髓。一起来看看 《黑客》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

MD5 加密
MD5 加密

MD5 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换