面试算法题

• • @[TOC](面试算法题)
• 有两个字符串a,b,求他们的公共字符串,并分析复杂度
• 实现链表的倒序
• 用列表表示栈、队列
• 实现列表的倒序
• 列表内字典排序
• 字符串的倒序
• 用数组实现一个栈,需要考虑并发
• 二叉树任选2个节点,求公共祖先
• 冒泡排序
• 快排
• 归并排序
• 二分查找
• 折半查找有序列表中的某个元素
• 洗牌算法
• 一个函数接受文件夹的名称作为输入参数,返回该文件夹中所有文件的全路径.请补充缺失的代码.
• '+'、'-'号置两边
• 总结

有两个字符串a,b,求他们的公共字符串,并分析复杂度

#以其中较短的字符串，从长到短依次循环匹配查找
str1="asdfghjkl"
str2="dfghj"
str1,str2=(str2,str1) if len(str1)>len(str2) else (str1,str2)
f=[]
for i in range(len(str1),0,-1):for j in range(len(str1)+1-i):e=str1[j:j+i]if e in str2:f.append(e)if f:break
f1=",".join(f)
print(f1)

实现链表的倒序

链表倒叙

用列表表示栈、队列

栈队列

实现列表的倒序

a[::-1]

列表内字典排序

数组多重排序

字符串的倒序

三种方法

用数组实现一个栈,需要考虑并发

二叉树任选2个节点,求公共祖先

二叉树公共祖先
二叉树排序

冒泡排序

各种排序

快排

归并排序

二分查找

折半查找有序列表中的某个元素

洗牌算法

一个函数接受文件夹的名称作为输入参数,返回该文件夹中所有文件的全路径.请补充缺失的代码.

def print_directory_contents(sPath):file_list = []for i,j,k in os.walk(sPath):for kk in k:print(i+’/’+kk)file_list.append(i+’/’+kk)return file_list

‘+’、'-'号置两边

data = ['+', '-', '-', '+', '-', '+', '+', '-', '-', '-', '-', '-', '+', '+', '+', '-', '-']
def StringSorted[data]:s=0e=0c=len(data)while s+e < c:if data[s] == '-':data[s], data[c-e-1] = data[c-e-1], data[s]e += 1else:s += 1return data

总结

给定一个有序数组,条件暗示: 有序 -->二分查找法
设计一个O(nlogn)的算法 nlogn八成离不开 分治算法, 要在搜索树中完成这个任务
无需考虑额外的空间 我们要考虑是不是需要开辟额外的空间,用空间换时间
数据规模大概是10000 设计O(n*n)就可以解决 nlogn可以处理百万级及千万级的数据

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！