- 工夫复杂度问题
已知 AList = [1, 2, 3]，BSet = {1, 2, 3} (1) 从 AList 和 BSet 中查找 4，最坏工夫复杂度哪个大？(2) 从 AList 和 BSet 中插入 4，最坏工夫复杂度哪个大？
答:
对于查找，列表和汇合的最坏工夫复杂度都是 O(n)，所以一样的。
列表操作插入的最坏工夫复杂度为 o(n), 汇合为 o(1)，所以 Alist 大。set 是哈希表所以操作的复杂度基本上都是 o(1)。
- 用 Python 实现一个二分查找的函数
答:
n = len(arr) left = 0 right = n – 1 while left <= right : mid = (left + right) // 2 if arr[mid] < target: left = mid + 1 elif arr[mid] > target: right = mid – 1 else : print(f”index:{mid},value:{arr[mid]}”) return True return False if name == ‘__main__’: l = [1, 3, 4, 5, 6, 7, 8] binary_search(l, 8)
- Python 单例模式的实现办法
答:
实现单例模式的办法有多种，之前再说元类的时候用 call 办法实现了一个单例模式，另外 Python 的模块就是一个人造的单例模式，这里咱们应用 new 关键字来实现一个单例模式。
通过 new 函数实现简略的单例模式。
class Book: def new__(cls, title): if not hasattr(cls, “_ins”): cls._ins = super().__new__(cls) print(‘in __new__’) return cls._ins def __init__(self, title): print(‘in __init__’) super().__init__() self.title = title if __name == ‘__main__’: b = Book(‘The Spider Book’) b2 = Book(‘The Flask Book’) print(id(b)) print(id(b2)) print(b.title) print(b2.title)
- 应用 Python 实现一个斐波那契数列
答:
斐波那契数列: 数列从第 3 项开始，每一项都等于前两项之和。
def fibonacci(num): a, b = 0, 1 l = [a, b] for i in range(num): a, b = b, a + b l.append(b) return l if name == ‘__main__’: print(fibonacci(10))
- 找出列表中的反复数字
答:
思路：从头扫到尾，只有以后元素值与下标不同，就做一次判断，numbers[i] 与 numbers[numbers[i]] 相等就认为找到了反复元素，返回 true；否则就替换两者，持续循环。直到最初还没找到认为没找到反复元素。
–– coding:utf-8 –– class Solution: def duplicate(self, numbers): if numbers is None or len(numbers) <= 1: return False use_set = set() duplication = {} for index, value in enumerate(numbers): if value not in use_set: use_set.add(value) else: duplication[index] = value return duplication if name == ‘__main__’: s = Solution() d = s.duplicate([1, 2, -3, 4, 4, 95, 95, 5, 2, 2, -3, 7, 7, 5]) print(d)
- 找出列表中的单个数字
答:
def find_single(l :list): result = 0 for v in l: result ^= v if result == 0: print(“ 没有落单元素 ”) else : print(“ 落单元素 ”, result) if name == ‘__main__’: l = [1, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6] find_single(l)
- 写一个冒泡排序
答:
def bubble_sort(arr): n = len(arr) for i in range(n – 1): for j in range(n – i – 1):. if arr[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)
- 写一个疾速排序
答:
def quick_sort(arr, first, last): if first >= last: return mid_value = arr[first] low = first high = last while low < high: while low < high and arr[high] >= mid_value: high -= 1 # 游标左移 arr[low] = arr[high] while low < high and arr[low] < mid_value: low += 1 arr[high] = arr[low] arr[low] = mid_value quick_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)
- 写一个拓扑排序
答:
对应于该图的拓扑排序。每一个有向无环图都至多存在一种拓扑排序。
import pysnooper from typing import Mapping @pysnooper.snoop() def topological_sort(graph:Mapping): # in_degrees = {‘a’: 0, ‘b’: 0, ‘c’: 0, ‘d’: 0, ‘e’: 0, ‘f’: 0} in_degrees = dict((u, 0) for u in graph) for u in graph: for v in graph[u]: # 依据键找出值也就是上级节点 in_degrees[v] += 1 # 对获取到的上级节点的入度加 1 # 循环完结之后的后果: {‘a’: 0, ‘b’: 1, ‘c’: 1, ‘d’: 2, ‘e’: 1, ‘f’: 4} Q = [u for u in graph if in_degrees[u] == 0] # 入度为 0 的节点 in_degrees_zero = [] while Q: u = Q.pop() # 默认从最初一个移除 in_degrees_zero.append(u) # 存储入度为 0 的节点 for v in graph[u]: in_degrees[v] -= 1 # 删除入度为 0 的节点，以及移除其指向 if in_degrees[v] == 0: Q.append(v) return in_degrees_zero if name == ‘__main__’: # 用字典的键值示意图的节点之间的关系，键以后节点。值是后续节点。graph_dict = {‘a’: ‘bf’, # 示意 a 指向 b 和 f ‘b’: ‘cdf’, ‘c’: ‘d’, ‘d’: ‘ef’, ‘e’: ‘f’, ‘f’: ”} t = topological_sort(graph_dict) print(t)
- Python 实现一个二进制计算
答:
二进制加法
def binary_add(a:str, b: str): return bin(int(a, 2) + int(b, 2))[2:] if name == ‘__main__’: num1 = input(“ 输出第一个数，二进制格局:\n”) num2 = input(“ 输出第二个数，二进制格局:\n”) print(binary_add(num1, num2))
更多 Python 编程常见面试题，咱们后续持续分享，敬请关注。