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