面试测试开发几道算法高频题(python)

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

本文列举几道面试的高频算法题,作者也是算法小白一枚,很多思路都是借鉴leetcode大神的解题过程来写的,不完全属于自己的成果。

面试测试开发几道算法高频题(python)

1、斐波那契数列

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

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

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

斐波那契数列由 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) 

直接使用递归的话,容易造成超时。一个为函数提供缓存功能的装饰器,缓存 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] 

状态定义: 设 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 

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

2、链表中倒数第k个节点

 输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

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

方法一:双指针

第一时间想到的解法:

先遍历统计链表长度,记为 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

3、连续子数组的最大和

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

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

方法一:动态规划

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)

状态定义: 设动态规划列表 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) :使用常数大小的额外空间。

4、字符串的排列

跟判断回文和汉诺塔一样,很经典的递归问题

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

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

输入:s = "abc" 
输出:["abc","acb","bac","bca","cab","cba"] 

方法一:递归  

排列方案数量:对于一个长度为 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)) 

5、合并两个排序的链表

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

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

方法一:递归  

返回 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

以后还会陆陆续续更新高频算法题,谢谢支持~



留言