2020 年最全 Python 面试题汇总 （四）

@Author：Runsen

文章目录

前言

61、01背包

62、完全背包

63、多重背包

64、多重背包的二进制

65、混合背包

66、Vivio面试真题

67、二维费用的背包问题

68、买卖股票的最佳时机（买一次）

69、买卖股票的最佳时机（买N次）

70、买卖股票的最佳时机（买2次）

71、买卖股票的最佳时机（买k次）

72、买卖股票的最佳时机（买N次加CD冷却时间）

73、买卖股票的最佳时机（买N次加手续费）

74、冒泡排序

75、插入排序

76、选择排序

77、希尔排序

78、归并排序

79、快速排序

80、查找和为定值的两个数

前言

求职季在即，技巧千万条，硬实力才是关键，听说今年疫情大环境不好，更要好好准备才行。于是 Runsen 在牛客网，Leetcode，九章算法，不断地寻找面试真题，共计 100 题，包括 Python基础、算法、SQL。

此次写作的一个明确目标是能够让 90% 以上的 Python 技术面试题都能覆盖到。更重要的目的是让我提升硬实力，在毕业之际，拿下offer。

本次 GitChat，分享辛苦总结了100 道 Python 基本算法面试题超强汇总，基本全部来自牛客网和最近的 2020 大厂的校招题目。

61、01背包

动态规划需要搞定三个系列：分别是背包，打劫问题和股票问题。

对应的题目：https://www.acwing.com/problem/content/2/

01背包问题就是物品只有一件。

输入格式 : 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式 : 输出一个整数，表示最大价值。

数据范围 : 0

输入样例

4 5 1 2 2 4 3 4 4 6

1

2

3

4

5

输出样例：

8 # 4+4 2+6

1

在解决这类问题先，dp怎么定义和状态转移方程怎么搞就是重要，搞定了就是半分钟的事情。搞不定了可能半小时的事情。

很多人和Runsen一样，都会把状态定义二维数组： d p [ i ] [ v ] dp[i][v] dp[i][v] 为前 i i i 「个」 物品中，体积恰好为 v v v 时的最大价值。

状态转移方程也是顺便搞定： 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 个物品」，那么前 i 个背包的最大价值就是前 i-1 个物品的价值，即 dp[i][j] = dp[i-1][j]；

如果 「选择了第 i 个物品」，前 i-1 个物品的体积就是j - weight[i]，状态方程为 dp[i - 1][j - weight[i]] + value[i]，注意这时的价值是前i-1个物品的价值，因此少了 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

上面的代码是状态定义二维数组，可以把状态定义一维数组，这样空间就节省了。

一维数组就是去掉了状态 i i i，且 j j j的遍历方式改为 「倒序」 遍历到 c[i]。

因此，Runsen们可以将求解空间进行优化，将二维数组压缩成一维数组，此时，转移方程变为：

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、完全背包

题目来源：https://www.acwing.com/problem/content/3

先上代码，和01背包问题的解法有略微的改动，区别在于遍历体积 j j j时从逆序改为顺序，在上一篇博客中有Runsen关于01背包问题的理解。

# 代码基本一样 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]) # 测试代码 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、多重背包

题目来源：https://www.acwing.com/problem/content/4/

多重背包问题每件物品件数都有上限。

下面是多重背包问题的输入样例和输出样例

输入样例 4 5 1 2 3 # 体积、价值和数量 2 4 1 3 4 3 4 5 2 输出样例： 10

1

2

3

4

5

6

7

8

多重背包问题的思路跟完全背包的思路非常类似，只是取值是有限制的，因为每件物品的数量是有限制的，状态转移方程为：dp [j] = max(dp [j], dp [j - k*b] + k*w) 这里的b和w指的是当前遍历的体积和价值。

这里一维动态规划和01背包基一样，就是多了一个k的循环，具体的查看下面代码。

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

除了上面的方法，还有用最原始的方法，将多个同一物品转化成不同物品，再用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、多重背包的二进制

多重背包有三层循环，如果数据非常的大，那么程序就会运行很慢。有一种优化方式叫做二进制优化

二进制是一个非常神奇的进制，譬如说7这个数，分开就是 1 + 2 + 4 （ 2 0 + 2 1 + 2 2 ） 1+2+4（2^0+2^1+2^2） 1+2+4（20+21+22）。

进行完二进制拆分之后，这个问题就转化成了零一背包。

下面就是一个二进制解决多重背包的示例，其中items 表示次数，体积 价值。

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、混合背包

混合背包问题混合了这三者。

题目来源：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

最简单的方法就是直接转化为多重背包。-1变成1，0变成V，这样就是最简单最高效的方法。对于多重背包问题，可以同样采用二进制的方法。

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面试真题

二维费用的背包问题。直接让我想起了Vivo的面试题，具体链接

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

输出：31000

说明组合部署服务5,2,15000、10,4,16000 ，可以让单台服务器承载最大用户数31000

其实就是二维费用的背包问题，变汤不变药的。

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、二维费用的背包问题

题目来源：https://www.acwing.com/problem/content/8/

只要知道了三维的dp的状态转移方程：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直接进行空间优化成二维dp，其原理就是斐波那契数列的从底向顶的做法，逆向思维。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

68、买卖股票的最佳时机（买一次）

这是Leetcode的第121题： 买卖股票的最佳时机（买一次）

题目不说了，就是只能买一次，

class Solution: def maxProfit(self, prices: List[int]) -> int: # dp的状态转移方程：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、买卖股票的最佳时机（买N次）

这是Leetcode的第122题： 买卖股票的最佳时机（买N次）

那么dp就需要开一个维度来表示当天是买还是卖。

class Solution: def maxProfit(self, prices: List[int]) -> int: ''' 可以买卖多次 dp[i][j] dp[i][0] 表示前 i天的最大利润，第i天不买，那么dp转移方程取决于i-1天是有股票还是没有股票 dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]) dp[i][1] 表示前 i天的最大利润，第i天必须买, 那么dp转移方程取决于i-1天是有股票还是没有股票 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] # 找到所有的上升区间，计算每个上升区间的价格差,直接节约了空间复杂度 为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 # 最好的做法就是有一个变量储存没有股票的最大利润和有股票的最大利润，然后不断地维护 # cash表示第i天结束，没有股票的最大利润 # hold表示第i天结束，有股票的最大利润 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、买卖股票的最佳时机（买2次）

这是Leetcode的第123题： 买卖股票的最佳时机（买2次）

class Solution: def maxProfit(self, prices: List[int]) -> int: ''' dp[i][k][XX] i 表示第i的最大利润，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) # 初始化状态 dp = [[[0]*2 for _ in range(3)] for _ in range(n)] for k in range(3): # 第一天买入股票 dp[0][k][1] = -prices[0] # 从 i=1 处开始迭代 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、买卖股票的最佳时机（买k次）

这是Leetcode的第188题： 买卖股票的最佳时机（买k次）

注释写得很详细了。

class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: # @Author：Runsen #dp[i][j][0] 今天是第i天 进行 j次 交易 手上没有股票 #dp[i][j][1] 今天是第i天 进行 j次 交易 手上有股票 if k == 0 or len(prices) < 2: return 0 n = len(prices) res = [] # 如果k的次数大于n//2，那么就是直接计算利润，第一天买，第二天就卖，然后第二天在买。 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] 的最大，这里我直接开数组 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、买卖股票的最佳时机（买N次加CD冷却时间）

这是Leetcode的第309题： 买卖股票的最佳时机（买N次加CD冷却时间）

注释写得很详细了。

class Solution: def maxProfit(self, prices: List[int]) -> int: # 如果设置dp的状态？ 就是关键。冷冻期其实就是CD技能的时间。 # dp[i][0]表示第i天结束之后，我有股票的最大收益。那么有可能i-1天我本来就有股票，今天的价不好，我不卖了，或者昨天我没有股票，但我今天可以买了股票，说明今天不是冷冻期。 # dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]) # dp[i][1]表示第i天结束之后，我没有股票，明天就是冷冻期，也就是昨天有股票，今天运气好，价格高，我刚刚卖了股票这一种可能。 # dp[i][1] = dp[i-1][0] + prices[i] # dp[i][2]表示第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]要买是第一个股 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、买卖股票的最佳时机（买N次加手续费）

这是Leetcode的第714题： 买卖股票的最佳时机（买N次加手续费）

注释写得很详细了。

# 就是在dp[i][0]减去手续费而已 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天结束，没有股票的最大利润 # hold表示第i天结束，有股票的最大利润 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、冒泡排序

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。具体的查看代码

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、插入排序

插入排序的实现思路顾名思义，就是不断地在一个已经是有序的数组中，寻找合适位置并插入新元素。

从后往前依次进行比较，如果待插入元素大于当前元素，则将待插入元素插入到当前元素的后一位，如果待插入元素小于当前元素，则将当前元素后移一位。不断重复该过程直至到数组的最后一位

def insert_sort(a): length = len(a) if length <= 1: return a # 从数组的第二个数开始 for i in range(1, length): # 从后向前扫描 j = i - 1 # value指的是插入元素 value = a[i] while j >= 0: if a[j] < value: # 插入元素大于当前元素，则将待插入元素插入到当前元素的后一位 a[j + 1] = value break else: # 插入元素小于当前元素，则将当前元素后移一位 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、选择排序

选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

def selection_sort(arr): """选择排序""" # 第一层for表示循环选择的遍数 for i in range(len(arr) - 1): # 将起始元素设为最小元素 min_index = i # 第二层for表示最小元素和后面的元素逐个比较 for j in range(i + 1, len(arr)-1): if arr[j] < arr[min_index]: # 如果当前元素比最小元素小，则把当前元素角标记为最小元素角标 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、希尔排序

希尔排序的基本思想是：把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。

def shell_sort(list): n = len(list) # 步长一般为 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、归并排序

归并排序基本思想：将数组array[0,...,n-1]中的元素分成两个子数组：array1[0,...,n/2]和array2[n/2+1,...,n-1]。分别对这两个数组单独排序，然后将已排序的 两个子数组归并成一个含有n个元素的有序数组

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、快速排序

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。

快速排序用递归来写，代码非常简单。

def quicksort(array): if len(array) < 2: # 基本情况下，具有0或1个元素的数组是已经“排序”的 return array else: # 递归情况 pivot = array[len(array)//2] # 小于基准值的所有元素的子数组 less = [i for i in array[1:] if i <= pivot] # 大于基准值的所有元素的子数组 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、查找和为定值的两个数

查找和为定值的两个数，这道题可以说是Leetcode第一题的变体。比如array = [0, 1, 2, 3, 4, 5, 6]，求所有等于7的两个数的列表总和。

def two_sum2(array, s): # 时间复杂度是O(N),空间复杂度是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 数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。