测试开发是近几年行业中一个流行词,既然是测试开发工程师,那么代码开发能力是最基本的要求,所以面试时必然少不了一些算法题考验你的编程功底。
本文列举几道面试的高频算法题,作者也是算法小白一枚,很多思路都是借鉴leetcode大神的解题过程来写的,不完全属于自己的成果。
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
以后还会陆陆续续更新高频算法题,谢谢支持~