您现在的位置是:首页 > 正文

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

2024-01-30 20:29:35阅读 0

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

本文阅读时长:5min

当下,谷歌的面试时常被程序员提及。有时,面试能让我们发挥最好的一面,从而获得我们想要的职位。
本文我们将讨论一个可能出现在Google面试中的经典问题。

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

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


正如我们从上面的例子中看到的那样,输出是“abc”,因为我们删除了第二个’a’,‘b’和’c’。
首先,让我们在Python 2.7中设置我们的功能。

def deleteReoccurringCharacters(string):

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

一套

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

  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)。

网站文章

  • 装饰者模式

    装饰者模式

    设计模式:专门为解决某一类问题,而编写的固定格式的代码。装饰者模式一、职责1、动态的为一个对象增加新的功能2、装饰模式是一种用于替代继承的技术,无需通过继承增加子类就能扩展对象的新功能。使用对象的关联关系代替继承关系,更加灵活,同时避免类型体系的快速膨胀。二、实现细节1、Component抽象构件角色:真实对象和装饰对象有相同的接口。这样,客户端对象就能够以与真实...

    2024-01-30 20:29:29
  • JVM内存布局

    JVM内存布局

    Survivor区分为S0和S1两块内存空间,每次YGC时,它们将存活的对象复制到未使用的那块空间,然后将当前正在使用的空间完全清除,交换两块空间的使用状态。当大量本地方法出现时,势必会削弱JVM对系...

    2024-01-30 20:29:22
  • css固定定位

    css固定定位

    主要使用场景:可以在浏览器页面滚动元素时元素的位置不会改变。1、以浏览器的可视窗口作为参考点移动元素。4、不占有固定位置,浮起来了。3、不随滚动条的滚动而变化。2、和父元素没有关系。

    2024-01-30 20:28:51
  • 使用jQuery的ajax上传文件报错:Uncaught TypeError: Illegal invocation

    使用ajax上传文件,代码如下:$('#video-upload-btn').on('change', function(){ var file = this.files[0]; var data =...

    2024-01-30 20:28:44
  • Java代码审计之RCE(远程命令执行)

    Java代码审计之RCE(远程命令执行)

    Java代码审计系列课程(点我哦)漏洞原理:RCE漏洞,可让攻击者直接向后台服务器远程注入操做系统命令或者代码,从而控制后台系统。出现此类漏洞通常由于应用系统从设计上须要给用户提供指定的远程命令操做的...

    2024-01-30 20:28:37
  • Android面试题集-常见几个面试题详解

    Android面试题集-常见几个面试题详解

    跳槽,这在 IT 互联网圈是非常普遍的,也是让自己升职加薪,走上人生巅峰的重要方式。那么作为一个普通的Android程序猿,我们如何才能斩获大厂offer 呢? 疫情向好、面试在即,还在迷茫踌躇中的后...

    2024-01-30 20:28:06
  • 使用EasyExcel实现上传解析与导出下载

    使用EasyExcel实现上传解析与导出下载

    使用指南:https://www.yuque.com/easyexcel/doc/easyexcel 环境:jdk1.8、SpringBoot 2.2.2 准备工作: pom.xml 添加依赖jar包...

    2024-01-30 20:27:57
  • AF_INET 和PF_INET区别;AF_LOCAL PF_LOCAL 区别.

    从字面理解: AF_INET = Address Format, Internet = IP Addresses PF_INET = Packet Format, Internet = IP, TCP/IP or UDP 从linux的定义来看,两者无区别。 /* Supported address families. */#define AF_UNSPEC 0#define AF_UNI...

    2024-01-30 20:27:55
  • springboot和vue前后端分离部署微信公众号

    网上已经有很多vue打包后放到resources目录的解决方案,也有vue前台微信插件然后请求后台方案,我就不Ctrl+C加Ctrl+V了。说说我的分离部署的解决方案:nginx反响代理后台路径,后端验证通过后跳转前端路径通过response.sendRedirect("前台的路径"),如/api,原来http://localhost:8080/user/login,变成http://xx...

    2024-01-30 20:27:49
  • 负数在计算机中怎样存储

    负数在计算机中怎样存储

    一、什么是原码、反码、补码?分为:正数 和负数(包括正浮点数,和负浮点数)规定最高位位符号位正数为0,负数为1(原因下文解释)原码:10进制转换成2进制是原码,只不过正数的原码是本身符号位为0,负数的原码符号位为1(以下篇幅均以单字节为例:10进制1的原码是0000 0001,10进制-1的原码是1000 0001)。反码: 正数的反码是本身,负数的反码是负数的原码0变为1,1变为0 &...

    2024-01-30 20:27:16