2020 年最全 Python 面試題匯總 （四）

@Author：Runsen

文章目錄

前言

61、01背包

62、完全背包

63、多重背包

64、多重背包的二進(jìn)制

65、混合背包

66、Vivio面試真題

67、二維費(fèi)用的背包問(wèn)題

68、買賣股票的最佳時(shí)機(jī)（買一次）

69、買賣股票的最佳時(shí)機(jī)（買N次）

70、買賣股票的最佳時(shí)機(jī)（買2次）

71、買賣股票的最佳時(shí)機(jī)（買k次）

72、買賣股票的最佳時(shí)機(jī)（買N次加CD冷卻時(shí)間）

73、買賣股票的最佳時(shí)機(jī)（買N次加手續(xù)費(fèi)）

74、冒泡排序

75、插入排序

76、選擇排序

77、希爾排序

78、歸并排序

79、快速排序

80、查找和為定值的兩個(gè)數(shù)

前言

求職季在即，技巧千萬(wàn)條，硬實(shí)力才是關(guān)鍵，聽(tīng)說(shuō)今年疫情大環(huán)境不好，更要好好準(zhǔn)備才行。于是 Runsen 在牛客網(wǎng)，Leetcode，九章算法，不斷地尋找面試真題，共計(jì) 100 題，包括 Python基礎(chǔ)、算法、SQL。

此次寫作的一個(gè)明確目標(biāo)是能夠讓 90% 以上的 Python 技術(shù)面試題都能覆蓋到。更重要的目的是讓我提升硬實(shí)力，在畢業(yè)之際，拿下offer。

本次 GitChat，分享辛苦總結(jié)了100 道 Python 基本算法面試題超強(qiáng)匯總，基本全部來(lái)自牛客網(wǎng)和最近的 2020 大廠的校招題目。

61、01背包

動(dòng)態(tài)規(guī)劃需要搞定三個(gè)系列：分別是背包，打劫問(wèn)題和股票問(wèn)題。

對(duì)應(yīng)的題目：https://www.acwing.com/problem/content/2/

01背包問(wèn)題就是物品只有一件。

輸入格式 : 第一行兩個(gè)整數(shù)，N，V，用空格隔開(kāi)，分別表示物品數(shù)量和背包容積。接下來(lái)有 N 行，每行兩個(gè)整數(shù) vi,wi，用空格隔開(kāi)，分別表示第 i 件物品的體積和價(jià)值。

輸出格式 : 輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍 : 0

輸入樣例

4 5 1 2 2 4 3 4 4 6

1

2

3

4

5

輸出樣例：

8 # 4+4 2+6

1

在解決這類問(wèn)題先，dp怎么定義和狀態(tài)轉(zhuǎn)移方程怎么搞就是重要，搞定了就是半分鐘的事情。搞不定了可能半小時(shí)的事情。

很多人和Runsen一樣，都會(huì)把狀態(tài)定義二維數(shù)組： d p [ i ] [ v ] dp[i][v] dp[i][v] 為前 i i i 「?jìng)€(gè)」 物品中，體積恰好為 v v v 時(shí)的最大價(jià)值。

狀態(tài)轉(zhuǎn)移方程也是順便搞定： d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ] , d p [ i ? 1 ] [ j ? w e i g h t [ i ] ] + v a l u e [ i ] ) dp[i][j] = max(dp[i-1][j],dp[i - 1][j - weight[i]] + value[i]) dp[i][j]=max(dp[i?1][j],dp[i?1][j?weight[i]]+value[i])

如果 「不選第 i 個(gè)物品」，那么前 i 個(gè)背包的最大價(jià)值就是前 i-1 個(gè)物品的價(jià)值，即 dp[i][j] = dp[i-1][j]；

如果 「選擇了第 i 個(gè)物品」，前 i-1 個(gè)物品的體積就是j - weight[i]，狀態(tài)方程為 dp[i - 1][j - weight[i]] + value[i]，注意這時(shí)的價(jià)值是前i-1個(gè)物品的價(jià)值，因此少了 weight[i]]的空間，所以 dp[i - 1][j - weight[i]] + value[i]。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

上面的代碼是狀態(tài)定義二維數(shù)組，可以把狀態(tài)定義一維數(shù)組，這樣空間就節(jié)省了。

一維數(shù)組就是去掉了狀態(tài) i i i，且 j j j的遍歷方式改為 「倒序」 遍歷到 c[i]。

因此，Runsen們可以將求解空間進(jìn)行優(yōu)化，將二維數(shù)組壓縮成一維數(shù)組，此時(shí)，轉(zhuǎn)移方程變?yōu)椋?/p>

d p ( j ) = m a x ( d p ( j ) , d p ( i ? w i ) + v i ) dp(j) = max(dp(j),dp(i - wi) + vi) dp(j)=max(dp(j),dp(i?wi)+vi)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

62、完全背包

題目來(lái)源：https://www.acwing.com/problem/content/3

先上代碼，和01背包問(wèn)題的解法有略微的改動(dòng)，區(qū)別在于遍歷體積 j j j時(shí)從逆序改為順序，在上一篇博客中有Runsen關(guān)于01背包問(wèn)題的理解。

# 代碼基本一樣 n, v = map(int, input().split()) goods = [] for i in range(n): goods.append([int(i) for i in input().split()]) dp = [0 for i in range(v+1)] for i in range(n): for j in range(v+1): # 從前往后 if j >= goods[i][0]: dp[j] = max(dp[j], dp[j-goods[i][0]]+goods[i][1]) print(dp[-1]) # 測(cè)試代碼 5 10 1 2 2 3 3 4 4 5 5 6 20

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

63、多重背包

題目來(lái)源：https://www.acwing.com/problem/content/4/

多重背包問(wèn)題每件物品件數(shù)都有上限。

下面是多重背包問(wèn)題的輸入樣例和輸出樣例

輸入樣例 4 5 1 2 3 # 體積、價(jià)值和數(shù)量 2 4 1 3 4 3 4 5 2 輸出樣例： 10

1

2

3

4

5

6

7

8

多重背包問(wèn)題的思路跟完全背包的思路非常類似，只是取值是有限制的，因?yàn)槊考锲返臄?shù)量是有限制的，狀態(tài)轉(zhuǎn)移方程為：dp [j] = max(dp [j], dp [j - k*b] + k*w) 這里的b和w指的是當(dāng)前遍歷的體積和價(jià)值。

這里一維動(dòng)態(tài)規(guī)劃和01背包基一樣，就是多了一個(gè)k的循環(huán)，具體的查看下面代碼。

n, v = map(int, input().split()) dp = [0 for _ in range(v+1)] for i in range(n): b, w, s = map(int, input().split()) for j in range(v, -1, -1): k = 1 while k <= s and j >= k * b: dp [j] = max(dp [j], dp [j - k*b] + k*w) k += 1 print(dp[v])

1

2

3

4

5

6

7

8

9

10

11

12

除了上面的方法，還有用最原始的方法，將多個(gè)同一物品轉(zhuǎn)化成不同物品，再用01背包求解

n,v = map(int, input().split()) goods = [] for i in range(n): goods.append([int(i) for i in input().split()]) new_goods = [] for i in range(n): for j in range(goods[i][2]): new_goods.append(goods[i][0:2]) goods = new_goods n = len(goods) dp = [0 for i in range(v+1)] for i in range(n): # 01背包倒序 for j in range(v,-1,-1): if j>= goods[i][0]: dp[j] = max(dp[j], dp[j - goods[i][0]] + goods[i][1]) print(dp[-1])

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

64、多重背包的二進(jìn)制

多重背包有三層循環(huán)，如果數(shù)據(jù)非常的大，那么程序就會(huì)運(yùn)行很慢。有一種優(yōu)化方式叫做二進(jìn)制優(yōu)化

二進(jìn)制是一個(gè)非常神奇的進(jìn)制，譬如說(shuō)7這個(gè)數(shù)，分開(kāi)就是 1 + 2 + 4 （ 2 0 + 2 1 + 2 2 ） 1+2+4（2^0+2^1+2^2） 1+2+4（20+21+22）。

進(jìn)行完二進(jìn)制拆分之后，這個(gè)問(wèn)題就轉(zhuǎn)化成了零一背包。

下面就是一個(gè)二進(jìn)制解決多重背包的示例，其中items 表示次數(shù)，體積 價(jià)值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

65、混合背包

混合背包問(wèn)題混合了這三者。

題目來(lái)源：https://www.acwing.com/problem/content/7/

# -1 表示01背包 0表示完全背包 大于0的表示多重背包 輸入樣例 4 5 1 2 -1 2 4 1 3 4 0 4 5 2 輸出樣例： 8

1

2

3

4

5

6

7

8

9

最簡(jiǎn)單的方法就是直接轉(zhuǎn)化為多重背包。-1變成1，0變成V，這樣就是最簡(jiǎn)單最高效的方法。對(duì)于多重背包問(wèn)題，可以同樣采用二進(jìn)制的方法。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

66、Vivio面試真題

二維費(fèi)用的背包問(wèn)題。直接讓我想起了Vivo的面試題，具體鏈接

輸入：15 10 5,1,1000#2,3,3000#5,2,15000#10,4,16000

輸出：31000

說(shuō)明組合部署服務(wù)5,2,15000、10,4,16000 ，可以讓單臺(tái)服務(wù)器承載最大用戶數(shù)31000

其實(shí)就是二維費(fèi)用的背包問(wèn)題，變湯不變藥的。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

67、二維費(fèi)用的背包問(wèn)題

題目來(lái)源：https://www.acwing.com/problem/content/8/

只要知道了三維的dp的狀態(tài)轉(zhuǎn)移方程：dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-V[i-1]][k-M[i-1]]+W[i-1])。就是一道在算法中送分題。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

下面是將三維dp直接進(jìn)行空間優(yōu)化成二維dp，其原理就是斐波那契數(shù)列的從底向頂?shù)淖龇ǎ嫦蛩季S。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

68、買賣股票的最佳時(shí)機(jī)（買一次）

這是Leetcode的第121題： 買賣股票的最佳時(shí)機(jī)（買一次）

題目不說(shuō)了，就是只能買一次，

class Solution: def maxProfit(self, prices: List[int]) -> int: # dp的狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i-1],prices[i]-minprice) n = len(prices) if n == 0: return 0 dp = [0] * n minprice = prices[0] for i in range(1,n): minprice = min(minprice,prices[i]) dp[i] = max(dp[i-1],prices[i]-minprice) return dp[-1]

1

2

3

4

5

6

7

8

9

10

11

69、買賣股票的最佳時(shí)機(jī)（買N次）

這是Leetcode的第122題： 買賣股票的最佳時(shí)機(jī)（買N次）

那么dp就需要開(kāi)一個(gè)維度來(lái)表示當(dāng)天是買還是賣。

class Solution: def maxProfit(self, prices: List[int]) -> int: ''' 可以買賣多次 dp[i][j] dp[i][0] 表示前 i天的最大利潤(rùn)，第i天不買，那么dp轉(zhuǎn)移方程取決于i-1天是有股票還是沒(méi)有股票 dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]) dp[i][1] 表示前 i天的最大利潤(rùn)，第i天必須買, 那么dp轉(zhuǎn)移方程取決于i-1天是有股票還是沒(méi)有股票 dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1]) ''' n = len(prices) if n == 0: return 0 dp = [[0]*2 for _ in range(n)] dp[0][0] = 0 dp[0][1] = -prices[0] for i in range(1,n): dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]) dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1]) return dp[-1][0] # 找到所有的上升區(qū)間，計(jì)算每個(gè)上升區(qū)間的價(jià)格差,直接節(jié)約了空間復(fù)雜度 為O(1) # 貪心做法 n = len(prices) profit = 0 if n == 0 : return 0 for i in range(1,n): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit # 最好的做法就是有一個(gè)變量?jī)?chǔ)存沒(méi)有股票的最大利潤(rùn)和有股票的最大利潤(rùn)，然后不斷地維護(hù) # cash表示第i天結(jié)束，沒(méi)有股票的最大利潤(rùn) # hold表示第i天結(jié)束，有股票的最大利潤(rùn) cash, hold = 0, -prices[0] for i in range(1,len(prices)): cash = max(cash,hold+prices[i]) hold = max(hold,cash-prices[i]) return cash

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

70、買賣股票的最佳時(shí)機(jī)（買2次）

這是Leetcode的第123題： 買賣股票的最佳時(shí)機(jī)（買2次）

class Solution: def maxProfit(self, prices: List[int]) -> int: ''' dp[i][k][XX] i 表示第i的最大利潤(rùn)，k表示第i天之前你買了多少次，X表示第i天是否有股票 0 ,1 p[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]) ''' if not prices: return 0 n = len(prices) # 初始化狀態(tài) dp = [[[0]*2 for _ in range(3)] for _ in range(n)] for k in range(3): # 第一天買入股票 dp[0][k][1] = -prices[0] # 從 i=1 處開(kāi)始迭代 for i in range(1, n): for k in range(1, 3): dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]) return dp[-1][2][0]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

71、買賣股票的最佳時(shí)機(jī)（買k次）

這是Leetcode的第188題： 買賣股票的最佳時(shí)機(jī)（買k次）

注釋寫得很詳細(xì)了。

class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: # @Author：Runsen #dp[i][j][0] 今天是第i天 進(jìn)行 j次 交易 手上沒(méi)有股票 #dp[i][j][1] 今天是第i天 進(jìn)行 j次 交易 手上有股票 if k == 0 or len(prices) < 2: return 0 n = len(prices) res = [] # 如果k的次數(shù)大于n//2，那么就是直接計(jì)算利潤(rùn)，第一天買，第二天就賣，然后第二天在買。 if k > n // 2: max_profit = 0 for i in range(1,n): profit = prices[i] - prices[i - 1] # 如果第二天比第一天高，那就直接加入 if profit > 0: max_profit += profit return max_profit # 下面就是Leetcode第123的代碼 dp[i][j][0] dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)] for i in range(k + 1): # 第一天買入股票 dp[0][i][1] = - prices[0] for i in range(1, n): for k in range(1, k+1): dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]) # 求dp[i][k][0] 的最大，這里我直接開(kāi)數(shù)組 for m in range(k + 1): res.append(dp[-1][m][0]) return max(res)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

72、買賣股票的最佳時(shí)機(jī)（買N次加CD冷卻時(shí)間）

這是Leetcode的第309題： 買賣股票的最佳時(shí)機(jī)（買N次加CD冷卻時(shí)間）

注釋寫得很詳細(xì)了。

class Solution: def maxProfit(self, prices: List[int]) -> int: # 如果設(shè)置dp的狀態(tài)？ 就是關(guān)鍵。冷凍期其實(shí)就是CD技能的時(shí)間。 # dp[i][0]表示第i天結(jié)束之后，我有股票的最大收益。那么有可能i-1天我本來(lái)就有股票，今天的價(jià)不好，我不賣了，或者昨天我沒(méi)有股票，但我今天可以買了股票，說(shuō)明今天不是冷凍期。 # dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]) # dp[i][1]表示第i天結(jié)束之后，我沒(méi)有股票，明天就是冷凍期，也就是昨天有股票，今天運(yùn)氣好，價(jià)格高，我剛剛賣了股票這一種可能。 # dp[i][1] = dp[i-1][0] + prices[i] # dp[i][2]表示第i天結(jié)束之后，我沒(méi)有股票，但是明天不在冷凍期，也就是今天我不買股票，有可能因?yàn)槲易蛱靹倓傎u了，今天就是冷凍期，我買不了。也有可能，昨天的我可能沒(méi)打算買，今天又不買。 # dp[i][2] = max(dp[i-1][1] ,dp[i-1][2]) if not prices: return 0 n = len(prices) # 第0天dp[0][0]要買是第一個(gè)股 dp = [[-prices[0], 0, 0]] + [[0] * 3 for _ in range(n - 1)] for i in range(1, n): dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]) dp[i][1] = dp[i-1][0] + prices[i] dp[i][2] = max(dp[i-1][1] ,dp[i-1][2]) return max(dp[-1][1], dp[-1][2])

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

73、買賣股票的最佳時(shí)機(jī)（買N次加手續(xù)費(fèi)）

這是Leetcode的第714題： 買賣股票的最佳時(shí)機(jī)（買N次加手續(xù)費(fèi)）

注釋寫得很詳細(xì)了。

# 就是在dp[i][0]減去手續(xù)費(fèi)而已 class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: n = len(prices) if n == 0: return 0 dp = [[0]*2 for _ in range(n)] dp[0][0] = 0 dp[0][1] = -prices[0] for i in range(1,n): dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]-fee) dp[i][1] = max(dp[i-1][0]-prices[i] ,dp[i-1][1]) return dp[-1][0] class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: # cash表示第i天結(jié)束，沒(méi)有股票的最大利潤(rùn) # hold表示第i天結(jié)束，有股票的最大利潤(rùn) cash, hold = 0, -prices[0] for i in range(1,len(prices)): cash = max(cash,hold+prices[i]-fee) hold = max(hold,.cash-prices[i]) return cash

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

74、冒泡排序

冒泡排序（英語(yǔ)：Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。具體的查看代碼

def bubble_sort(nums): for i in range(len(nums) - 1): for j in range(len(nums) - i - 1): if nums[j] > nums[j + 1]: nums[j], nums[j + 1] = nums[j + 1], nums[j] return nums if __name__ == '__main__': nums = [54, 26, 93, 17, 77, 31, 44, 55, 20] bubble_sort(nums) print(nums) # [17, 20, 26, 31, 44, 54, 55, 77, 93]

1

2

3

4

5

6

7

8

9

10

11

75、插入排序

插入排序的實(shí)現(xiàn)思路顧名思義，就是不斷地在一個(gè)已經(jīng)是有序的數(shù)組中，尋找合適位置并插入新元素。

從后往前依次進(jìn)行比較，如果待插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位，如果待插入元素小于當(dāng)前元素，則將當(dāng)前元素后移一位。不斷重復(fù)該過(guò)程直至到數(shù)組的最后一位

def insert_sort(a): length = len(a) if length <= 1: return a # 從數(shù)組的第二個(gè)數(shù)開(kāi)始 for i in range(1, length): # 從后向前掃描 j = i - 1 # value指的是插入元素 value = a[i] while j >= 0: if a[j] < value: # 插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位 a[j + 1] = value break else: # 插入元素小于當(dāng)前元素，則將當(dāng)前元素后移一位 a[j + 1] = a[j] if j == 0: a[j] = value j -= 1 return a if __name__ == '__main__': nums = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(insert_sort(nums)) # [17, 20, 26, 31, 44, 54, 55, 77, 93]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

76、選擇排序

選擇排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

def selection_sort(arr): """選擇排序""" # 第一層for表示循環(huán)選擇的遍數(shù) for i in range(len(arr) - 1): # 將起始元素設(shè)為最小元素 min_index = i # 第二層for表示最小元素和后面的元素逐個(gè)比較 for j in range(i + 1, len(arr)-1): if arr[j] < arr[min_index]: # 如果當(dāng)前元素比最小元素小，則把當(dāng)前元素角標(biāo)記為最小元素角標(biāo) min_index = j # 查找一遍后將最小元素與起始元素互換 arr[min_index], arr[i] = arr[i], arr[min_index] return arr if __name__ == '__main__': nums = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(selection_sort(nums)) # [17, 20, 26, 31, 44, 54, 55, 77, 93]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

77、希爾排序

希爾排序的基本思想是：把記錄按步長(zhǎng) gap 分組，對(duì)每組記錄采用直接插入排序方法進(jìn)行排序。

def shell_sort(list): n = len(list) # 步長(zhǎng)一般為 gap = n // 2 while gap >= 1: for j in range(gap, n): i = j while( i - gap ) >= 0: if list[i] < list[ i - gap ]: list[i], list[ i - gap ] = list[ i - gap ], list[i] i -= gap else: break gap //= 2 if __name__ == '__main__': alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] shell_sort(alist) print(alist) # [17, 20, 26, 31, 44, 54, 55, 77, 93]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

78、歸并排序

歸并排序基本思想：將數(shù)組array[0,...,n-1]中的元素分成兩個(gè)子數(shù)組：array1[0,...,n/2]和array2[n/2+1,...,n-1]。分別對(duì)這兩個(gè)數(shù)組單獨(dú)排序，然后將已排序的 兩個(gè)子數(shù)組歸并成一個(gè)含有n個(gè)元素的有序數(shù)組

def merge(left, right): i = 0 j = 0 temp = [] while i <= len(left) - 1 and j <= len(right) - 1: if left[i] <= right[j]: temp.append(left[i]) i += 1 else: temp.append(right[j]) j += 1 temp += left[i:] + right[j:] return temp def merge_sort(nums): if len(nums) <= 1: return nums num = len(nums) >> 1 left = merge_sort(nums[:num]) right = merge_sort(nums[num:]) return merge(left, right) if __name__ == '__main__': nums = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(merge_sort(nums))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

79、快速排序

快速排序的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分：分割點(diǎn)左邊都是比它小的數(shù)，右邊都是比它大的數(shù)。

快速排序用遞歸來(lái)寫，代碼非常簡(jiǎn)單。

def quicksort(array): if len(array) < 2: # 基本情況下，具有0或1個(gè)元素的數(shù)組是已經(jīng)“排序”的 return array else: # 遞歸情況 pivot = array[len(array)//2] # 小于基準(zhǔn)值的所有元素的子數(shù)組 less = [i for i in array[1:] if i <= pivot] # 大于基準(zhǔn)值的所有元素的子數(shù)組 greater = [i for i in array[1:] if i > pivot] return quicksort(less) + [pivot] + quicksort(greater) if __name__ == '__main__': nums = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(quicksort(nums))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

80、查找和為定值的兩個(gè)數(shù)

查找和為定值的兩個(gè)數(shù)，這道題可以說(shuō)是Leetcode第一題的變體。比如array = [0, 1, 2, 3, 4, 5, 6]，求所有等于7的兩個(gè)數(shù)的列表總和。

def two_sum2(array, s): # 時(shí)間復(fù)雜度是O(N),空間復(fù)雜度是O(N) d= dict() for a in array: d[a] = None result = [] for a in array: if s - a in d and s - a != a: result.append([a, s - a]) del d[a] return result if __name__ == '__main__': array = [0, 1, 2, 3, 4, 5, 6] print(two_sum2(array, 7)) # [[1, 6], [2, 5], [3, 4]]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Python 數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。