版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
关注@霍格沃兹测试学院公众号,回复「⾯试」,领取BAT⼤⼚测试⾯试真题专辑。复制“下⽅链接”,提升测试核⼼竞争⼒! 更多技术⽂章分享和免费资料领取1.时间复杂度问题 已知AList=[1,2,3],BSet={1,2,3}(1)从AList和BSet中查找4,最坏时间复杂度哪个⼤?(2)从AList和BSet中插⼊4,最坏时间复杂度哪个⼤?答:1.对于查找,列表和集合的最坏时间复杂度都是O(n),所以⼀样的。2.列表操作插⼊的最坏时间复杂度为o(n),集合为o(1),所以Alist⼤。set是哈希表所以操作的复杂度基本上都是o(1)。2.⽤Python实现⼀个⼆分查找的函数答:n=len(arr)left=0right=n-1whileleft<=right:mid=(left+right)//2ifarr[mid]<target:left=mid+1elifarr[mid]>target:right=mid-1else:print(f"index:{mid},value:{arr[mid]}")returnTruereturnFalseif__name__=='__main__':l=[1,3,4,5,6,7,8]binary_search(l,8)3.Python单例模式的实现⽅法3.Python单例模式的实现⽅法 公众号【大学百科资料】整理,有超百科复习资料答:实现单例模式的⽅法有多种,之前再说元类的时候⽤call⽅法实现了⼀个单例模式,另外Python的模块就是⼀个天然的单例模式,这⾥我们使⽤new关键字来实现⼀个单例模式。通过new函数实现简单的单例模式。classBook:def__new__(cls,title):ifnothasattr(cls,"_ins"):cls._ins=super().__new__(cls)print('in__new__')returncls._insdef__init__(self,title):print('in__init__')super().__init__()self.title=titleif__name__=='__main__':b=Book('TheSpiderBook')b2=Book('TheFlaskBook')print(id(b))print(id(b2))print(b.title)print(b2.title)4.使⽤Python实现⼀个斐波那契数列答:斐波那契数列:数列从第3项开始,每⼀项都等于前两项之和。deffibonacci(num):a,b=0,1l=[a,b]a,b=b,a+bl.append(b)returnlif__name__=='__main__':print(fibonacci(10))5.找出列表中的重复数字答:思路:从头扫到尾,只要当前元素值与下标不同,就做⼀次判断,numbers[i]与numbers[numbers[i]]相等就认为找到了重复元素,返回true;否则就交换两者,继续循环。直到最后还没找到认为没找到重复元素。#-*-coding:utf-8-*-classSolution:defduplicate(self,numbers):ifnumbersisNoneorlen(numbers)<=1:returnFalseuse_set=set()duplication={}forindex,valueinenumerate(numbers):ifvaluenotinuse_set:use_set.add(value)else:duplication[index]=valuereturnduplicationif__name__=='__main__':s=Solution()d=s.duplicate([1,2,-3,4,4,95,95,5,2,2,-3,7,7,5])print(d)答:deffind_single(l:list):result=0forvinl:result^=vifresult==0:print("没有落单元素")else:print("落单元素",result)if__name__=='__main__':l=[1,2,3,4,5,6,2,3,4,5,6]find_single(l)7.写⼀个冒泡排序答:defbubble_sort(arr):n=len(arr)foriinrange(n-1):forjinrange(n-i-1):.ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]if__name__=='__main__':l=[1,2,3,4,5,55,6,3,4,5,6]bubble_sort(l)print(l)8.写⼀个快速排序答:iffirst>=last:returnmid_value=arr[first]low=firsthigh=lastwhilelow<high:whilelow<highandarr[high]>=mid_value:high-=1#游标左移arr[low]=arr[high]whilelow<highandarr[low]<mid_value:low+=1arr[high]=arr[low]arr[low]=mid_valuequick_sort(arr,first,low-1)quick_sort(arr,low+1,last)if__name__=='__main__':l=[1,2,3,4,5,55,6,3,4,5,6]quick_sort(l,0,len(l)-1)print(l)9.写⼀个拓扑排序答:对应于该图的拓扑排序。每⼀个有向⽆环图都⾄少存在⼀种拓扑排序。importpysnooperfromtypingimportMapping@pysnooper.snoop()deftopological_sort(graph:Mapping):#in_degrees={'a':0,'b':0,'c':0,'d':0,'e':0,'f':0}in_degrees=dict((u,0)foruingraph)foruingraph:forvingraph[u]:#根据键找出值也就是下级节点in_degrees[v]+=1#对获取到的下级节点的⼊度加1#循环结束之后的结果:{'a':0,'b':1,'c':1,'d':2,'e':1,'f':4}Q=[uforuingraphifin_degrees[u]==0]#⼊度为0的节点in_degrees_zero=[]whileQ:u=Q.pop()#默认从最后⼀个移除in_degrees_zero.append(u)#存储⼊度为0的节点forvingraph[u]:in_degrees[v]-=1#删除⼊度为0的节点,以及移除其指向ifin_degrees[v]==0:Q.append(v)returnin_degrees_zeroif__name__=='__main__':#⽤字典的键值表⽰图的节点之间的关系,键当前节点。值是后续节点。graph_dict={'a':'bf',#表⽰a指向b和f'b':'cdf','c':'d','d':'ef','e':'f','f':''}t=topological_sort(graph_dict)10.Python实现⼀个⼆进制计算答:⼆进制加法defbinary_add(a:str,b:str):returnbin(int(a,2)+int(b,2))[2:]if__name__=='__main__':num1=input("输⼊第⼀个数,⼆进制格式:
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年度年福建省高校教师资格证之高等教育法规提升训练试卷B卷附答案
- 2023年重铬酸钠资金筹措计划书
- 中级经济师(运输经济)《专业知识与实务》考前冲刺必会试题及答案
- 三年级数学(上)计算题专项练习附答案集锦
- 办公用品质量保证书
- 2024年公司迁移服务协议模板
- 村会议决议模板5篇
- 2024详细土建工程承揽协议模板
- 2024年事业单位正式协议样式
- 岗位聘任职责与权益详解协议样本
- 公务员2021年国考《申论》真题(地市级)及参考答案
- 新教科版小学1-6年级科学需做实验目录
- 2024秋期国家开放大学专科《高等数学基础》一平台在线形考(形考任务一至四)试题及答案
- DPtech-FW1000系列防火墙系统操作手册
- 部门服务满意度评分表
- 慢支慢性阻塞性肺疾病9版.ppt
- 细纱机设备维护维修说明书
- 地方课程六年级上册
- (完整版)PD、QC有限快充的知识讲解
- 浅论构建高效课堂研究的意义
- 习惯一积极主动
评论
0/150
提交评论