内容简介:本文阅读时长:5min当下,谷歌的面试时常被程序员提及。有时,面试能让我们发挥最好的一面,从而获得我们想要的职位。
- 来源 | 愿码(ChainDesk.CN) 内容编辑
- 愿码Slogan | 连接每个 程序员 的故事
- 网站 | http://chaindesk.cn
- 愿码愿景 | 打造全学科IT系统免费课程,助力小白用户、初级工程师0成本免费系统学习、低成本进阶,帮助BAT一线资深工程师成长并利用自身优势创造睡后收入。
- 官方公众号 | 愿码 | 愿码服务号 | 区块链部落
- 免费加入愿码全思维工程师社群 | 任一公众号回复“愿码”两个字获取入群二维码
本文阅读时长:5min
当下,谷歌的面试时常被程序员提及。有时,面试能让我们发挥最好的一面,从而获得我们想要的职位。
本文我们将讨论一个可能出现在Google面试中的经典问题。
- 愿码提示:如果您是编码老手,您可能已经知道如何解决这个问题!如果你经验较浅,那么你一定会从本文中受益。
问题
给定一个字符串作为输入,删除任何重复出现的字符,并返回新字符串。
正如我们从上面的例子中看到的那样,输出是“abc”,因为我们删除了第二个'a','b'和'c'。
首先,让我们在Python 2.7中设置我们的功能。
def deleteReoccurringCharacters(string):
为了解决这个问题,我们将使用一个名为HashSet的特定数据结构。
您可以将集合视为与数组类似,但有两个主要例外。
- 这是完全无序的
- 它不能包含重复项
因为它是无序的,我们还需要一个空字符串来存储我们按顺序添加到集合中的字符。这将是我们返回的字符串。
我们来设置一下
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删除重复出现的字符》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 高频算法面试题(字符串)leetcode 387. 字符串中的第一个唯一字符
- 关于PHP字符串的一道面试题
- 高频算法面试题(字符串) leetcode 125. 验证回文串
- 高频算法面试题(字符串) 242. 有效的字母异位词
- 高频算法面试题(字符串) leetcode 212. 单词搜索 II
- 10 分钟掌握 BAT 面试中常考的字符串问题
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。