【测试面试】测试开发面试算法高频题，这些题你会多少？

---

前言

测试开发是近几年行业中一个流行词，既然是测试开发工程师，那么代码开发能力是最基本的要求，所以面试时必然少不了一些算法题考验你的编程功底。

斐波那契数列？
青蛙爬楼梯就是斐波那契数列的演化，解题思路一样。

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。
斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1 
F(N) = F(N - 1) + F(N - 2), 其中 N > 1
1
2

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

方法一：递归

import functools 
class Solution: 
    @functools.lru_cache(maxsize=None) 
    def fib(self, n: int) -> int: 
        if n < 2: 
            return n 
        return self.fib(n-1) + self.fib(n-2) 
1
2
3
4
5
6
7

直接使用递归的话，容易造成超时。一个为函数提供缓存功能的装饰器，缓存 maxsize 组传入参数，在下次以相同参数调用时直接返回上一次的结果，避免传入相同的参数时重复计算。用以节约高开销或I/O函数的调用时间。

方法二：动态规划

class Solution: 
    def fib(self, n: int) -> int: 
       if n < 2: 
           return n 
       else: 
           dp = {} 
           dp[0] = 0 
           dp[1] = 1 
           for i in range(2,n+1): 
               dp[i] = dp[i-1] + dp[i-2] 
           return dp[n] 
1
2
3
4
5
6
7
8
9
10
11

状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表 斐波那契数列第 i 个数字
转移方程：dp[i + 1] = dp[i] + dp[i - 1] ，即对应数列定义 f(n + 1) = f(n) + f(n - 1)
初始状态：dp[0]=0, dp[1]=1 ，即初始化前两个数字
返回值：dp[n] ，即斐波那契数列的第 n 个数字

方法三：动态规划优化

class Solution: 
    def fib(self, n: int) -> int: 
        if n==0 or n==1: 
			return n 
        a, b, temp = 0, 1, 0 
        for i in range(2,n+1): 
            temp = a + b 
            a = b 
            b = temp 
        return temp 
1
2
3
4
5
6
7
8
9
10

若新建长度为 n 的 dp 列表，则空间复杂度为 O(N) 。由于 dp 列表第 i 项只与第 i－1 和第 i－2 项有关，因此只需要初始化三个整形变量 temp, a, b ，利用辅助变量 temp 使 a, b 两数字交替前进 。节省了 dp 列表空间，因此空间复杂度降至 O(1) 。

链表中倒数第k个节点？
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

给定一个链表: 1->2->3->4->5, 和 k = 2
返回链表 4->5
1
2

方法一：双指针
第一时间想到的解法：

先遍历统计链表长度，记为 n ；设置一个指针走 (n-k) 步，即可找到链表倒数第 k 个节点。

使用双指针则可以不用统计链表长度。

算法流程：
初始化：前指针 fast 、后指针 slow ，双指针都指向头节点 head 。
构建双指针距离：前指针 fast 先向前走 k 步（结束后，双指针 fast 和 slow 间相距 k 步）。
双指针共同移动：循环中，双指针 fast 和 slow 每轮都向前走一步，直至fast走过链表尾节点时跳出（跳出后，slow与尾节点距离为 k-1，即slow指向倒数第 k 个节点）。
返回值：返回 slow 即可。
复杂度分析：
时间复杂度 O(N)：N 为链表长度；总体看，fast 走了 N 步， slow 走了 (N－k) 步。
空间复杂度 O(1)：双指针 fast , slow 使用常数大小的额外空间。
注：如果k大于链表长度，会发生越界问题

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
         fast = head
        slow = head
        for i in range(k):
            if not fast: # 考虑 k大于链表长度的情况 
                return 
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        return slow
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

连续子数组的最大和？

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为6。
1
2
3

方法一：动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[i] = nums[i] + max(nums[i-1],0)
        return max(nums)
1
2
3
4
5

状态定义： 设动态规划列表 dp ，dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。
转移方程：若 dp[i-1] ≤ 0 ，说明 dp[i - 1]对 dp[i] 产生负贡献，即 dp[i-1] + nums[i]还不如 nums[i] 本身大。
初始状态：dp[0]=nums[0]，即以 nums[0] 结尾的连续子数组最大和为 nums[0]。
返回值： 返回 dp 列表中的最大值，代表全局最大值。

空间复杂度降低：

由于 dp[i] 只与 dp[i－1] 和 nums[i] 有关系，因此可以将原数组 nums 用作 dp 列表，即直接在 nums 上修改即可。由于省去dp 列表使用的额外空间，因此空间复杂度从 O(N) 降至 O(1) 。

复杂度分析：
时间复杂度 O(N)：线性遍历数组nums 即可获得结果，使用 O(N) 时间。
空间复杂度 O(1) ：使用常数大小的额外空间。

字符串的排列？
跟判断回文和汉诺塔一样，很经典的递归问题

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

输入：s = "abc" 
输出：["abc","acb","bac","bca","cab","cba"]
1
2

方法一：递归
排列方案数量：对于一个长度为 n 的字符串（假设字符互不重复），其排列共有 n! 种方案。

排列方案的生成方法：根据字符串排列的特点，考虑深度优先搜索所有排列方案。即通过字符交换，先固定第 1 位字符（ n 种情况）、再固定第 2 位字符（ n－1 种情况）、… 、最后固定第 n 位字符（ 1 种情况）。

class Solution: 
    def permutation(self, s: str) -> List[str]: 
        if len(s) <= 1: 
            return list(s) 
        else: 
            result = [] 
            for i in range(len(s)): 
                ch = s[i] 
                rest = s[0:i] + s[i+1:len(s)] 
                for j in self.permutation(rest): 
                    result.append(ch+j) 
            return list(set(result)) 
1
2
3
4
5
6
7
8
9
10
11
12

合并两个排序的链表?

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

输入：1->2->4, 1->3->4 
输出：1->1->2->3->4->4 
1
2

方法一：递归
返回 l1指向的结点和 l2指向的结点中，值较小的结点；
并将从下级函数获得的返回值，链接到当前结点尾部。
终止条件：至少有一个为空，返回剩下的那个。

# Definition for singly-linked list. 
# class ListNode: 
#     def __init__(self, x): 
#         self.val = x 
#         self.next = None 
class Solution: 
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: 
            return l2 
        if not l2: 
            return l1 
        if l1.val < l2.val: 
            l1.next = self.mergeTwoLists(l1.next, l2) 
            return l1 
        l2.next = self.mergeTwoLists(l1, l2.next) 
        return l2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

一、Python编程入门到精通

二、接口自动化项目实战

三、Web自动化项目实战

四、App自动化项目实战

五、一线大厂简历

六、测试开发DevOps体系

七、常用自动化测试工具

八、JMeter性能测试

九、总结（尾部小惊喜）

如果青春是醺人欲醉的海风，那么自信就是这和风前行的路标；如果青春是巍峨入云的高耸，那么拼搏就是这山脉层层拔高的动力；如果青春是高歌奋进的谱曲，那么坚强就是这旋律奏响的最强音！

在人生中，有时最好走的路不一定是大路，而是小路；在现实中，有时最便捷的路不一定是直路，而是折路。

每一天的努力，只是为了让远方变得更近一些。再苦再累，只要坚持往前走，属于你的风景终会出现。