版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
关注@霍格沃兹测试学院公众号,回复「⾯试」,领取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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 淮阴师范学院《体育课程与学科教学论》2021-2022学年第一学期期末试卷
- 淮阴师范学院《绿色化工》2023-2024学年第一学期期末试卷
- 淮阴师范学院《钢琴弹唱(2)》2021-2022学年第一学期期末试卷
- 淮阴师范学院《Hadoop大数据技术》2023-2024学年期末试卷
- 淮阴工学院《仪器分析》2021-2022学年第一学期期末试卷
- 淮阴工学院《土木工程材料》2021-2022学年第一学期期末试卷
- DB3711-T 152-2024荒山造林技术规程
- 文书模板-人才培养计划的制订方案
- 人事行政培训企业文化塑造与践行考核试卷
- 未来教育中的在线测评与反馈考核试卷
- 公务员2021年国考《申论》真题(地市级)及参考答案
- 新教科版小学1-6年级科学需做实验目录
- 2024秋期国家开放大学专科《高等数学基础》一平台在线形考(形考任务一至四)试题及答案
- DPtech-FW1000系列防火墙系统操作手册
- 图像学完整分
- 思想道德与法治课件:第五章 第二节 吸收借鉴优秀道德成果
- 时栅位移传感技术讲解
- 灯具施工方案(完整版)
- TKT-Glossary中译版
- 西安作文800字
- (完整版)小学英语教师个人专业发展规划(最新整理)
评论
0/150
提交评论