python面试题1

1.冒泡排序

https://www.cnblogs.com/bigdata-stone/p/10464243.html

'''冒泡排序'''
# coding:utf-8
lis = [1, 13, 5, 35, 6, 9, 10]
s = range(len(lis))[::-1] 
print(s)
for i in s:               #确定排序几次，第一次把7个数最大派最后，第二次剩下6个最大排最后，总共需要6次排序
    for j in range(i):    #确定比较次数，第一次7个数字需要比较6次，第二次剩下6个需要比较5次
        if lis[j] > lis[j +1 ]:
            lis[j], lis[j + 1] = lis[j + 1], lis[j]
print(list)

for i in range(len(lis) - 1):
    for j in range(len(lis) - i - 1):
        print(j)
        if lis[j] > lis[j + 1]:
            lis[j], lis[j + 1] = lis[j + 1], lis[j]

2.列表分组

https://www.cnblogs.com/yitao326/p/12515678.html

从大到小打印元素个数
l = [1, 2, 3, 'a', 'b', 'c', 1, 2, 'a', 'b', 3, 'c', 'd', 'a', 'b', 1]
s = set(l)
new_l = [(i, l.count(i)) for i in s]
new_l.sort(key=lambda x: x[1], reverse=True)
print(new_l)

3.海量数据top k

import random


def gen_num(n):
    for i in range(n):
        yield random.randint(0, n)


g = gen_num(1000)
print(list(set(g))[-10:])

4.两数之和

l = [1, 2, 3, 4, 5, 6, 7, 8]
target = 6
for i in l:
    for j in l:
        if i < j and i + j == target:
            print(l.index(i), l.index(j))

l = [1,2,3,4,5,6,7,8]
set1 = set(list1)   # 使用集合已方便查找
target = 6

result = []
for a in list1:
    b = target - a
    if a < b < target and b in set1:   # 在集合中查找,为避免重复，判断a为较小的那个值
        result.append((list1.index(a), list1.index(b)))   # 列表index取下标的操作为O(1)
print(result)

递归问题

1.阶乘

def factorial(n):
    if n == 1:  # 出口
        return 1
    return factorial(n-1) * n   # 自我调用求上一个结果，然后推导本层结果

2.斐波那切数列

def fib(n):
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)

3.跳台阶，疯狂跳台阶

跳台阶：一只青蛙，一次可以跳上1阶，也可以跳上2阶，问跳上n阶有多少种跳法。
变态跳台阶：一只青蛙，一次可以跳上1阶，可以一次跳上n阶，为跳上n阶有多少种跳法

跳台阶

jump1 = lambda n: n if n<=2 else jump1(n-2) + jump1(n-1)

变态跳台阶

jump2 = lambda n: n if n<=2 else jump2(n-1) * 2

4.快速排序

快速排序的是想是选一个基准数（如第一个数），将大于该数和小于该数的分成两块，然后在每一块中重复执行此操作，直到该块中只有一个数，即为有序。

出口：列表长度为1（<2）时，返回列表
选择一个数，（将小于该数的序列）排序结果 + 基准数 + （大于该数的序列）排序结果

def quick_sort(l):
    if len(l) < 2:
        return l
    index = 0
    low_part = [i for i in l if i < l[index]]
    equel_part = [i for i in l if i == l[index]]
    high_part = [i for i in l if i > l[index]]
    return quick_sort(low_part) + quick_sort(equel_part) + quick_sort(high_part)

其他

1.判断是否闭合

def is_closed(text):
    stack = []  # 使用list模拟栈, stack.append()入栈, stack.pop()出栈并获取栈顶元素
    brackets = {')':'(',']':'[','}':'{'}  # 使用字典存储括号的对应关系, 使用反括号作key方便查询对应的括号
    for char in text:
        if char in brackets.values():   # 如果是正括号,入栈
            stack.append(char)
        elif char in brackets.keys():  # 如果是反括号
            if brackets[char] != stack.pop():  # 如果不匹配弹出的栈顶元素
                return False
    if len(stack) != 0:
        return False
    return True

2.合并2个有序列表，并保持有序

list1 = [1, 5, 7, 9]
list2 = [2, 3, 4, 5, 6, 8, 10, 12, 14]
new_l = []
for i in range(len(list1) + len(list2)):
    if list1 and not list2:
        new_l.append(list1.pop())
    elif list2 and not list1:
        new_l.append(list2.pop())
    else:
        new_l.append(list1.pop()) if list1[-1] > list2[-1] else new_l.append(list2.pop())
new_l.reverse()
print(new_l)

python面试题1

相关

标签