2020年python的面試題整理數(shù)據(jù)結(jié)構(gòu)與大數(shù)據(jù)篇

1、2020年python的面試題整理數(shù)據(jù)結(jié)構(gòu)與 大數(shù)據(jù)篇數(shù)據(jù)結(jié)構(gòu)222 .數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字-Python版223 .求100以內(nèi)的質(zhì)數(shù)224 .無重復字符的最長子串-Python實現(xiàn)225 .通過2個5/6升得水壺從池塘得到3升水226 .什么是MD5加密，有什么特點？227 .什么是對稱加密和非對稱加密228 .冒泡排序的思想？229 .快速排序的思想？230 .如何判斷單向鏈表中是否有環(huán)？231 .你知道哪些排序算法（一般是通過問題考算法）232 .斐波那契數(shù)列數(shù)列定義:f 0 = f 1 = 1 f n = f (n-1) + f (n-2)根據(jù)定義速度很慢，另外(暴棧注意！

2、？?O(fibonacci n) def fibonacci (n):if n = 0 or n = 1:return 1return fibonacci(n -1) + fibonacci (n - 2)線性時間的狀態(tài)/循環(huán)def fibonacci (n):a, b = 1, 1for _ in range(n): a, b = b, a + breturn a遞歸def fibonacci (n):def fib (n_, s):if n_ = 0:return s0a, b = sreturn fib (n_ -1, (b, a+ b)return fib(n, (1, 1)map(z

3、ipwith)def fibs ():yield 1fibs = fibs ()yield next(fibs_)fibs_ = fibs ()for fib in map(lambad a, b: a + b, fibs_, fibs_): yield fibdef fibonacci (n): fibs_ = fibs () for _ in range(n):next(fibs_) return next(fibs)做緩存def cache(fn): cached = def wrapper(*args):if args not in cached cachecargS = fn(*ar

4、gs) return cachedargswrapper._name_ = fn._name_ return wrappercachedef fib(n):if n < 2:return 1return fib(n-1) + fib(n-2)利用 funtools.lru_cache 做緩存from functools import lru_cache lru_cache(maxsize= 32) def fib(n):if n < 2:return 1return fib(n-1) + fib(n-2)Logarithmic矩陣import numpy as npdef fibo

5、nacci (n):return (np.matrix(0, 1, 1, 1) * n) 1, 1不是矩陣def fibonacci (n):def fib (n):if n = 0:return (1,1)elif n = 1:return (1, 2)a, b = fib (n / 2 - 1) c = a + bif n % 2 = 0:return (a*a + b*b, c * c - a * a) return (c* c- a* a, b * b + c* c)return fib(n)0233.如何翻轉(zhuǎn)一個單鏈表?class Node:def _init_ (self,data

6、=None,next=None):self.data = dataself.next = nextdef rev(link): pre = link cur = link .next pre.next = None while cur:temp = cur.next cur.next = pre pre = cur cur = tmpreturn pre if _name_ = '_main_':link = Node(1,Node(2,Node(3,Node(4,Node(5,Node(6,Node7,Node(8.Node(9) root = rev(link) while

7、 root:print (roo.data)root = root.next234.青蛙跳臺階問題一只青蛙要跳上n層高的臺階，一次能跳一級，也可以跳兩級，請問這只青蛙 有多少種跳上這個n層臺階的方法？方法1:遞歸 設(shè)青蛙跳上n級臺階有f(n)種方法，把這n種方法分為兩大類，第一種最后一 次跳了一級臺階，這類共有f(n-1)種，第二種最后一次跳了兩級臺階，這種方 法共有f(n-2)種，則得出遞推公式f(n)=f(n-1) + f(n-2),顯然f(1)=1,f(2)=2 ,這種 方法雖然代碼簡單，但效率低，會超出時間上限class Solution:def climbStairs (self,n

8、):if n =1:return 1elif n=2:return 2else:return self.climbStairs (n-1) + self.climbStairs(n-2)方法2:用循環(huán)來代替遞歸class Solution:def climbStairs (self,n):if n=1 or n=2: return na,b,c = 1,2,3for i in range(3,n+1): c = a+ba = b b = c return c235 .兩數(shù)之和 Two Sum236 .搜索旋轉(zhuǎn)排序數(shù)組 Search in Rotated SortedArray237 .Python 實現(xiàn)一個Stack的數(shù)據(jù)結(jié)構(gòu)238 .寫一個二分查找239.set用in時間復雜度是多少，為什么?240 .列表中有n個正