image
- 来源 | 愿码(ChainDesk.CN)内容编辑
- 愿码Slogan | 连接每个程序员的故事
- 网站 | http://chaindesk.cn
- 愿码愿景 | 打造全学科IT系统免费课程，助力小白用户、初级工程师0成本免费系统学习、低成本进阶，帮助BAT一线资深工程师成长并利用自身优势创造睡后收入。
- 官方公众号 | 愿码 | 愿码服务号 | 区块链部落
- 免费加入愿码全思维工程师社群 | 任一公众号回复“愿码”两个字获取入群二维码
本文阅读时长：5min
当下，谷歌的面试时常被程序员提及。有时，面试能让我们发挥最好的一面，从而获得我们想要的职位。
本文我们将讨论一个可能出现在Google面试中的经典问题。
- 愿码提示：如果您是编码老手，您可能已经知道如何解决这个问题！如果你经验较浅，那么你一定会从本文中受益。
问题
给定一个字符串作为输入，删除任何重复出现的字符，并返回新字符串。
image
正如我们从上面的例子中看到的那样，输出是“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)。
网友评论