常见算法面试题及答案

掌握这些，面试算法不再难

在算法面试中，常常会遇到一些经典的问题。下面为大家详细介绍常见算法面试题及答案。

排序算法类

排序算法是面试中的常客。常见的面试题是让你实现一种排序算法，比如快速排序。快速排序的基本思想是分治法，选择一个基准值，将数组分为两部分，小于基准值的放在左边，大于基准值的放在右边，然后递归地对左右两部分进行排序。

示例代码如下：

python

def quick_sort(arr):

if len(arr) <= 1:

return arr

pivot = arr[0]

left = [x for x in arr[1:] if x <= pivot]

right = [x for x in arr[1:] if x > pivot]

return quick_sort(left) + [pivot] + quick_sort(right)

查找算法类

查找算法中，二分查找是重点。题目可能会要求在一个有序数组中查找某个元素的位置。二分查找的时间复杂度是 o(log n)。它的基本步骤是：先确定数组的中间位置，比较中间元素和目标元素的大小，如果中间元素等于目标元素，就返回中间位置；如果中间元素大于目标元素，就在左半部分继续查找；如果中间元素小于目标元素，就在右半部分继续查找。

示例代码如下：

python

def binary_search(arr, target):

left, right = 0, len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == target:

return mid

elif arr[mid] > target:

right = mid - 1

else:

left = mid + 1

return -1

链表操作类

链表操作的面试题也很常见。比如反转链表，要求将一个链表反转。可以使用迭代的方法，遍历链表，将每个节点的 next 指针指向前一个节点。

示例代码如下：

python

class listnode:

def __init__(self, val=0, next=none):

self.val = val

self.next = next

def reverse_list(head):

prev = none

curr = head

while curr:

next_node = curr.next

curr.next = prev

prev = curr

curr = next_node

return prev

树结构类

树结构的面试题通常围绕二叉树展开。比如求二叉树的最大深度。可以使用递归的方法，递归地计算左子树和右子树的最大深度，然后取最大值加 1。

示例代码如下：

python

class treenode:

def __init__(self, val=0, left=none, right=none):

self.val = val

self.left = left

self.right = right

def max_depth(root):

if not root:

return 0

left_depth = max_depth(root.left)

right_depth = max_depth(root.right)

return max(left_depth, right_depth) + 1

动态规划类

动态规划问题在面试中也有一定的难度。比如斐波那契数列，要求计算第 n 个斐波那契数。可以使用动态规划的思想，通过保存中间结果来避免重复计算。

示例代码如下：

python

def fibonacci(n):

if n <= 1:

return n

dp = [0] * (n + 1)

dp[1] = 1

for i in range(2, n + 1):

dp[i] = dp[i - 1] + dp[i - 2]

return dp[n]

以上就是常见的算法面试题及答案，希望对大家有所帮助。