python 常见面试题

部分参考：原网址有动图，能更好的理解。

菲波那切数列

# 生成器方式生成 
def fib(max):   # 传入一个值，输出比它小的数
    a = 0
    b = 1
    while b<=max:  
        yield b
        b,a = a+b,b
for i in fib(3524577):
    print(i,end=' ')

二分查找

# 完整版  二分查找必须是有序的,
def find(l, aim, start=0, end=None):
    if end == None: end = len(l) - 1
    if start <= end:
        mid = (end - start) // 2 + start
        if l[mid] > aim:
            return find(l, aim, start=start, end=mid - 1)
        elif l[mid] < aim:
            return find(l, aim, start=mid + 1, end=end)
        elif l[mid] == aim:
            return mid
    else:
        return None
l = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
print('ret :', find(l, 66))

冒泡排序

l = [1, 2, 9, 34, 12, 5, 8]

def bubbleSort(l):
    n = len(l)
    for i in range(n):
        for j in range(0, n - i - 1): # 每次循环会排好一个，所以每次减 i
            if l[j] > l[j + 1]:
                l[j], l[j + 1] = l[j + 1], l[j]
    print(l)

bubbleSort(l)

快排

def partition(arr,low,high): 
    i = ( low-1 )         # 最小元素索引
    pivot = arr[high]     
  
    for j in range(low , high): 
  
        # 当前元素小于或等于 pivot 
        if   arr[j] <= pivot: 
          
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 
  
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 
  
 
# arr[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引
  
# 快速排序函数
def quickSort(arr,low,high): 
    if low < high: 
  
        pi = partition(arr,low,high) 
  
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 
  
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 
print ("排序后的数组:") 
for i in range(n): 
    print ("%d" %arr[i]),

插入排序

def insertionSort(arr): 
  
    for i in range(1, len(arr)): 
  
        key = arr[i] 
  
        j = i-1
        while j >=0 and key < arr[j] : 
                arr[j+1] = arr[j] 
                j -= 1
        arr[j+1] = key 
  
  
arr = [12, 11, 13, 5, 6] 
insertionSort(arr) 
print ("排序后的数组:") 
for i in range(len(arr)): 
    print ("%d" %arr[i])

选择排序


A = [64, 25, 12, 22, 11] 
  
for i in range(len(A)): 
      
   
    min_idx = i 
    for j in range(i+1, len(A)): 
        if A[min_idx] > A[j]: 
            min_idx = j 
                
    A[i], A[min_idx] = A[min_idx], A[i] 
  
print ("排序后的数组：") 
for i in range(len(A)): 
    print("%d" %A[i]),

两个队列实现栈参考

class StackWithTwoQueues(object):
    def __init__(self):
        self._stack1 = []
        self._stack2 = []

    def push(self,x):
        if len(self._stack1) == 0:
            self._stack1.append(x)
        elif len(self._stack2) == 0:
            self._stack2.append(x)
        if len(self._stack2) == 1 and len(self._stack1) >= 1:
            while self._stack1:
                self._stack2.append(self._stack1.pop(0))
        elif len(self._stack1) == 1 and len(self._stack2) > 1:
            while self._stack2:
                self._stack1.append(self._stack2.pop(0))

    def pop(self):
        if self._stack1:
            return self._stack1.pop(0)
        elif self._stack2:
            return self._stack2.pop(0)
        else:
            return None

两个栈实现队列

class QueueWithTwoStacks(object):
    def __init__(self):
        self._stack1 = []
        self._stack2 = []

    def appendTail(self,x):
        self._stack1.append(x)

    def deleteHead(self):
         if self._stack2:
             return self._stack2.pop()
         else:
             if self._stack1:
                while self._stack1:
                    self._stack2.append(self._stack1.pop())
                return self._stack2.pop()
             else:
                 return None

单向链表参考

# 首先看单链表
class Chain():
    def __init__(self):
        self.first = None
        self.length = 0
    def is_empty(self):
        """是否为空"""
        return self.first == None
    def add(self, val):
        """头部添加"""
        node = Node(val)
        temp = self.first
        node.next = temp
        self.first = node
        self.length += 1
    def append(self, val):
        """尾部添加"""
        node = Node(val)
        if self.first:
            temp = self.first
            mid = None
            while temp:
                mid = temp
                temp = temp.next
            mid.next = node
        else:
            self.first = node
        self.length += 1
    def __setitem__(self, item, val):
        """插入元素"""
        node = Node(val)
        temp, index = self.first, 0
        if item == 0:
            node.next, self.first = self.first, node
            self.length += 1
        else:
            while temp:
                if index+1 == item:
                    node.next, temp.next = temp.next, node
                    self.length += 1
                    break
                index += 1
                temp = temp.next
    def __len__(self):
        """链表长度"""
        return self.length
    @property
    def len_2(self):
        """链表长度（时间复杂度O(n)）"""
        if not self.first:
            return 0
        else:
            temp = self.first
            length = 1
            while temp.next:
                length += 1
                temp = temp.next
            return length
    def pop(self):
        """删除尾部元素（有错误）"""
        temp = self.first
        mid = None
        while temp.next:
            mid, temp = temp, temp.next
        if mid:
            mid.next = None
            self.length -= 1
    def __delitem__(self, item):
        """删除某一位置元素"""
        temp, index = self.first, 0
        if item == 0:
            if self.first:
                self.first = self.first.next
                self.length -= 1
        while temp:
            if index + 1 == item:
                temp.next = temp.next.next
                self.length -= 1
            index += 1
            temp = temp.next
    def bianli(self):
        """遍历链表"""
        temp = self.first
        while temp:
            print(temp.value)
            temp = temp.next
　　　def reverse1(self):
　　　　　　"""反转链表"""        　　　　　　
          temp = self.first        　　　　　　
          prev = None        　　　　　　
          while temp:            　　　　　　　　
            temp_next = temp.next            　　　　　　　　
            temp.next = prev            　　　　　　　　
            prev = temp            　　　　　　　　
            temp = temp_next        　　　　　　
            self.first =  prev
　　　def reverse2(self):
　　　　　　"""反转链表"""　　　　　　
          chain_list = []
　　　　　　temp = self.first
　　　　　　while temp:
　　　　　　　　chain_list.append(temp.value)
　　　　　　　　temp = temp.next
　　　　　  temp = self.first
　　　　　　while temp:
　　　　　　　　temp.val = chain_list.pop()
　　　　　　　　temp = temp.next

    def __iter__(self):
        pass
    def __next__(self):
        pass
class Node():
    def __init__(self, val):
        self.value = val
        self.next = None

双向链表

# 在来看双向链表
class Node():
    def __init__(self, val):
        self.value = val
        self.prev = None
        self.next = None
class Chain():
    def __init__(self):
        self.first = None
    def is_empty(self):
        """是否为空"""
        return self.first == None
    def add(self, val):
        """头部添加"""
        node = Node(val)
        self.first.prev = node
        temp = self.first
        node.next = temp
        self.first = node
    def append(self, val):
        """尾部添加"""
        node = Node(val)
        temp = self.first
        if not temp:
            self.first = node
        else:
            while temp.next:
                temp = temp.next
            node.prev = temp
            temp.next = node
    def __delitem__(self, item):
        """删除元素"""
        temp, index = self.first, 0
        while temp:
            if index == item:
                if temp.next:
                    temp.next.prev, temp.prev.next = temp.prev, temp.next
                else:
                    temp.prev.next = None
            index += 1
            temp = temp.next
    def travel(self):
        """遍历元素"""
        temp = self.first
        while temp:
            print(temp.value)
            temp = temp.next

合并两个有序链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        l3 = ListNode(None)
        l = l3
        while (l1 and l2):
            if (l1.val <= l2.val):
                l.next = l1
                l = l.next
                l1 = l1.next
            else:
                l.next = l2
                l = l.next
                l2 = l2.next
        if (l1 == None):
            l.next = l2
        else:
            l.next = l1
        return l3.next

递归合并

# Definition for singly-linked list.
 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:　　　　　　#假设l1当中啥都没有，则返回l2，因为l2当中的node一定是升序排列的
        if l1==None:
            return l2
        if l2==None:
            return l1
        
        if l1.val<l2.val:
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2

判断链表有没有交点


class NodeList:
    def __init__(self,val):
        self.val = val
        self.next = None


class solution:
    def func(self,l1,l2):

        while l1:
            l1 = l1.next
        while l2:
            if l1.val == l2.val:
                return True
            else:
                l2 = l2.next
        return False

二叉树遍历三种方式

前序遍历

def preorderTraversal(now, result=[]):
    if now == None:
        return result
    result.append(now.data)
    preorderTraversal(now.left, result)
    preorderTraversal(now.right, result)
    return result

print(preorderTraversal(binaryTree))

中序遍历

def intermediateTraversal(now, result=[]):
    if now == None:
        return result
    intermediateTraversal(now.left, result)
    result.append(now.data)
    intermediateTraversal(now.right, result)
    return result


print(intermediateTraversal(binaryTree))

后序遍历


def postorderTraversal(now, result=[]):
    if now == None:
        return
    postorderTraversal(now.left, result)
    postorderTraversal(now.right, result)
    result.append(now.data)
    return result

print(postorderTraversal(binaryTree))

最后编辑于：2021.09.18 16:48:15

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,826评论 6赞 506
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,968评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,234评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,562评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,611评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,482评论 1赞 302
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,271评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,166评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,608评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,814评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,926评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,644评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,249评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,866评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,991评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,063评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,871评论 2赞 354

python 常见面试题

菲波那切数列

二分查找

冒泡排序

快排

插入排序

选择排序

两个队列实现栈 参考

两个栈实现队列

单向链表 参考

双向链表

合并两个有序链表

判断链表有没有交点

二叉树遍历 三种方式

前序遍历

中序遍历

后序遍历

推荐阅读更多精彩内容

两个队列实现栈参考

单向链表参考

二叉树遍历三种方式