- 時間復(fù)雜度問題
已知 AList = [1, 2, 3]，BSet = {1, 2, 3} (1)從AList和BSet中查找4，最壞時間復(fù)雜度哪個大？(2)從AList和BSet中插入4，最壞時間復(fù)雜度哪個大？
答:
對于查找，列表和集合的最壞時間復(fù)雜度都是O(n)，所以一樣的。
列表操作插入的最壞時間復(fù)雜度為o(n), 集合為o(1)，所以Alist大。set是哈希表所以操作的復(fù)雜度基本上都是o(1)。
- 用 Python 實現(xiàn)一個二分查找的函數(shù)
答:
def binary_search(arr, target):
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 單例模式的實現(xiàn)方法
答:
實現(xiàn)單例模式的方法有多種，之前再說元類的時候用 call 方法實現(xiàn)了一個單例模式，另外 Python 的模塊就是一個天然的單例模式，這里我們使用 new 關(guān)鍵字來實現(xiàn)一個單例模式。
通過 new 函數(shù)實現(xiàn)簡單的單例模式。
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 實現(xiàn)一個斐波那契數(shù)列
答:
斐波那契數(shù)列:數(shù)列從第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))
- 找出列表中的重復(fù)數(shù)字
答:
思路：從頭掃到尾，只要當前元素值與下標不同，就做一次判斷，numbers[i] 與 numbers[numbers[i]] 相等就認為找到了重復(fù)元素，返回 true；否則就交換兩者，繼續(xù)循環(huán)。直到最后還沒找到認為沒找到重復(fù)元素。
-- 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)
- 找出列表中的單個數(shù)字
答:
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)
- 寫一個拓撲排序
答:
對應(yīng)于該圖的拓撲排序。每一個有向無環(huán)圖都至少存在一種拓撲排序。
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]: # 根據(jù)鍵找出值也就是下級節(jié)點
in_degrees[v] += 1 # 對獲取到的下級節(jié)點的入度加 1
# 循環(huán)結(jié)束之后的結(jié)果: {'a': 0, 'b': 1, 'c': 1, 'd': 2, 'e': 1, 'f': 4}
Q = [u for u in graph if in_degrees[u] == 0] # 入度為 0 的節(jié)點
in_degrees_zero = []
while Q:
u = Q.pop() # 默認從最后一個移除
in_degrees_zero.append(u) # 存儲入度為 0 的節(jié)點
for v in graph[u]:
in_degrees[v] -= 1 # 刪除入度為 0 的節(jié)點，以及移除其指向
if in_degrees[v] == 0:
Q.append(v)
return in_degrees_zero
if name == 'main':
用字典的鍵值表示圖的節(jié)點之間的關(guān)系，鍵當前節(jié)點。值是后續(xù)節(jié)點。
graph_dict = {
'a': 'bf', # 表示 a 指向 b 和 f
'b': 'cdf',
'c': 'd',
'd': 'ef',
'e': 'f',
'f': ''}
t = topological_sort(graph_dict)
print(t)
- Python 實現(xiàn)一個二進制計算
答:
二進制加法
def binary_add(a:str, b: str):
return bin(int(a, 2) + int(b, 2))[2:]
if name == 'main':
num1 = input("輸入第一個數(shù)，二進制格式:\n")
num2 = input("輸入第二個數(shù)，二進制格式:\n")
print(binary_add(num1, num2))
更多 Python 編程常見面試題，我們后續(xù)繼續(xù)分享，敬請關(guān)注。
（文章來源于霍格沃茲測試學院）
更多技術(shù)文章可點擊獲取http://qrcode.testing-studio.com/f?from=jianshu&url=https://ceshiren.com/t/topic/3822
