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

junbaor 发布于2019-07-31 10:20 / 1014人阅读

摘要：本文我们将讨论一个可能出现在面试中的经典问题。问题给定一个字符串作为输入，删除任何重复出现的字符，并返回新字符串。为了解决这个问题，我们将使用一个名为的特定数据结构。空间复杂性最糟糕的情况是，我们得到一个包含所有唯一字符的字符串。

来源 | 愿码(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)。

云服务器私有云删除重复字符串 python字符串的使用详解 cdn的出现问题云主机可能出现的问题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43649.html

Python面试问题指南：如何编码链表

摘要：单身联系与双重联系在链接列表方面，有两种主要类型。代码是如何工作的呢编码链接列表可能是行问题或行问题。这将继续，直到指向，在这种情况下循环停止。现在您已经掌握了处理链表面试问题所需的基本知识 showImg(https://segmentfault.com/img/remote/1460000019127546?w=1200&h=797); 什么是链表？链表是一种数据结构，由许多称...

Cheriselalala 2019-07-31 10:23 评论0 收藏0
「真®全栈之路」Web前端开发的后端指南

前言在若干次前的一场面试，面试官看我做过python爬虫/后端的工作，顺带问了我些后端相关的问题：你觉得什么是后端？送命题。当时脑瓦特了，答曰：逻辑处理和数据增删改查。。。 showImg(https://user-gold-cdn.xitu.io/2019/4/24/16a4ed4fc8c18078); 当场被怼得体无完肤，羞愧难当。事后再反思这问题，结合资料总结了一下。发现自己学过的Re...

chuyao 2019-05-23 16:27 评论0 收藏0
Tools - 收藏集 - 掘金

摘要：个高级多线程面试题及回答后端掘金在任何面试当中多线程和并发方面的问题都是必不可少的一部分。默认为提供了年杭州面试经历掘金想换个环境试试觉得做的不是自己想要的。源码网站安居客项目架构演进掘金本文已授权微信公众号独家发布。 15 个高级 Java 多线程面试题及回答 - 后端 - 掘金在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分。如果你想获得任何股票投资银行的前台资讯职...

KitorinZero 2019-08-15 10:44 评论0 收藏0