大厂手撕算法

Posted on Edited on In
这篇笔记整理了大厂手撕算法，主要记录了快速排序、编辑距离、岛屿数量等经典算法题。

1.实现快速排序代码

快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它是一种分治法（Divide and Conquer）策略的典型应用。

快速排序的原理：

  1. 选择基准值（Pivot）：
    快速排序首先从数组中选择一个元素作为基准值，这个值称为“pivot”。选择的方法可以多样，如选择第一个元素、最后一个元素、中间元素或随机元素。

  2. 分区操作：
    数组被分为两个部分，使得：

    • 左边部分的所有元素都不大于基准值，
    • 右边部分的所有元素都不小于基准值。

    此时，基准值处于整个数组中的最终位置。

  3. 递归排序：
    递归地对基准左侧和右侧的两个子数组进行快速排序，直到子数组的长度为1或0，此时数组已经完全排序。

快速排序主要有两种实现方式，分别是递归方式和迭代方式。

下面我们首先来看一下递归方式实现的快速排序的代码：

Python代码实现（递归版本）：

以下是快速排序的一个简单Python实现，其中使用了Lomuto分区方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def quick_sort(arr):
    def partition(low, high):
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    def quick_sort_recursive(low, high):
        if low < high:
            pi = partition(low, high)
            quick_sort_recursive(low, pi - 1)
            quick_sort_recursive(pi + 1, high)

    quick_sort_recursive(0, len(arr) - 1)
    return arr

# 测试用例
test_cases = [
    [10, 7, 8, 9, 1, 5],
    [1, 2, 3, 4, 5],
    [5, 4, 3, 2, 1],
    [],
    [1],
    [11, 11, 11, 11]
]

# 展示排序结果
for case in test_cases:
    print(f"Original: {case}")
    print(f"Sorted: {quick_sort(case)}\n")

# 代码运行结果
Original: [10, 7, 8, 9, 1, 5]
Sorted: [1, 5, 7, 8, 9, 10]

Original: [1, 2, 3, 4, 5]
Sorted: [1, 2, 3, 4, 5]

Original: [5, 4, 3, 2, 1]
Sorted: [1, 2, 3, 4, 5]

Original: []
Sorted: []

Original: [1]
Sorted: [1]

Original: [11, 11, 11, 11]
Sorted: [11, 11, 11, 11]

测试用例及其输出：

上面的代码对包含多种情况的测试用例进行了排序，包括：

  • 普通未排序数组，
  • 已排序数组，
  • 逆序数组，
  • 空数组，
  • 单元素数组，
  • 所有元素相同的数组。

这些测试用例涵盖了快速排序可能面临的一些典型情况，并显示了算法处理这些情况的能力。每个测试用例的输出将展示原始数组和排序后的数组，以验证排序过程的正确性。

非递归（迭代）版本的快速排序可以使用一个显式的栈来模拟递归过程。这种方法避免了递归可能带来的栈溢出问题，并直观地展示了算法的控制流程。下面是如何使用栈实现快速排序的迭代版本：

Python代码实现（迭代版本）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
def quick_sort_iterative(arr):
    if arr == []:
        return arr
    # 创建一个栈
    stack = []
    # 初始范围从0到数组长度减一
    stack.append(0)
    stack.append(len(arr) - 1)

    # 只要栈非空，就继续运行
    while stack:
        # 弹出 high 和 low
        high = stack.pop()
        low = stack.pop()

        # 使用Lomuto分区方案
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        # 交换pivot到正确位置
        i += 1
        arr[i], arr[high] = arr[high], arr[i]
        pi = i

        # 如果有左子数组，将其范围入栈
        if pi - 1 > low:
            stack.append(low)
            stack.append(pi - 1)
        
        # 如果有右子数组，将其范围入栈
        if pi + 1 < high:
            stack.append(pi + 1)
            stack.append(high)

    return arr

# 测试用例
test_cases = [
    [10, 7, 8, 9, 1, 5],
    [1, 2, 3, 4, 5],
    [5, 4, 3, 2, 1],
    [],
    [1],
    [11, 11, 11, 11]
]

# 展示排序结果
for case in test_cases:
    print(f"Original: {case}")
    print(f"Sorted: {quick_sort_iterative(case)}\n")

# 代码运行结果
Original: [10, 7, 8, 9, 1, 5]
Sorted: [1, 5, 7, 8, 9, 10]

Original: [1, 2, 3, 4, 5]
Sorted: [1, 2, 3, 4, 5]

Original: [5, 4, 3, 2, 1]
Sorted: [1, 2, 3, 4, 5]

Original: []
Sorted: []

Original: [1]
Sorted: [1]

Original: [11, 11, 11, 11]
Sorted: [11, 11, 11, 11]

在迭代版本的快速排序中，我们使用了栈来保存将要处理的子数组的索引。这种方法模拟了递归调用栈的行为：

  • 首先，将整个数组的起始和结束索引推入栈中。
  • 然后，使用一个循环，直到栈为空，在每次迭代中：
    • 从栈中弹出一个子数组的界限（high 和 low）。
    • 执行分区操作，确定 pivot 的最终位置。
    • 根据 pivot 的位置，决定是否将左子数组或右子数组的索引范围推回栈中。

这种迭代方法避免了递归的深度调用，特别是对于那些可能导致递归深度很深的大数组来说，是一个更稳定的选择。

迭代版本的快速排序在时间复杂度和空间复杂度上的表现与递归版本相似，但有一些关键的实现细节差异：

时间复杂度

  • 最佳和平均情况：对于平均分布的数据，快速排序的时间复杂度通常是 $O(n \log n)$。这是因为每次分区大约将数组分成两半，需要递归或迭代地应用这一过程大约 $\log n$ 次。
  • 最坏情况：在最坏的情况下，如果每次选择的基准都是最小或最大的元素，快速排序的时间复杂度会退化到 $O(n^2)$。这种情况在数组已经基本有序的情况下可能发生（完全正序或完全逆序），每次分区操作只能减少一个元素。

空间复杂度

  • 递归版本：递归版本的快速排序在最坏情况下的空间复杂度可以达到 $O(n)$，这是由递归调用栈深度决定的。在平均情况下，由于递归的深度接近 $\log n$，其空间复杂度是 $O(\log n)$。
  • 迭代版本：迭代版本使用一个显式的栈来存储未处理的子数组的界限。虽然这避免了函数调用的开销，但栈的空间使用仍然可以在最坏情况下达到 $O(n)$，特别是当数组几乎有序时，可能需要将许多小的子数组范围推入栈。在平均情况下，空间复杂度通常也是 $O(\log n)$，因为每次都将数组大致分成两部分。

稳定性

  • 不稳定排序：相等的元素可能由于分区而交换其原始顺序。

实用性和选择

尽管迭代版本避免了递归的潜在栈溢出问题，它在空间和时间上的复杂度与递归版本相似。选择递归还是迭代版本通常取决于具体的应用场景以及对栈溢出的考虑。迭代版本更适合于那些对栈空间使用有严格限制的环境，例如嵌入式系统或者非常大的数据集处理。

在实际应用中，可以通过随机选择基准值或使用“三数取中”法来选择基准值，以避免最坏情况的发生，从而使得快速排序的性能更加稳定。此外，对于小数组，可以切换到插入排序以提高效率，因为小数组上的插入排序可能比快速排序更快。这种组合策略在实际库中如C++的STL中被广泛应用。

2.实现Self_Attention（百度实习一面）

import torch
import torch.nn as nn
import torch.nn.functional as F

class SelfAttention(nn.Module):
def __init__(self, embed_size, heads):
    super(SelfAttention, self).__init__()
    self.embed_size = embed_size
    self.heads = heads
    self.head_dim = embed_size // heads

    assert self.head_dim * heads == embed_size, "Embed size needs to be divisible by heads"

    self.values = nn.Linear(self.head_dim, self.head_dim, bias=False)
    self.keys = nn.Linear(self.head_dim, self.head_dim, bias=False)
    self.queries = nn.Linear(self.head_dim, self.head_dim, bias=False)
    self.fc_out = nn.Linear(heads * self.head_dim, embed_size)

def forward(self, values, keys, query, mask):
    N = query.shape[0]
    value_len, key_len, query_len = values.shape[1], keys.shape[1], query.shape[1]

    # Split the embedding into self.heads different pieces
    values = values.reshape(N, value_len, self.heads, self.head_dim)
    keys = keys.reshape(N, key_len, self.heads, self.head_dim)
    queries = query.reshape(N, query_len, self.heads, self.head_dim)

    values = self.values(values)
    keys = self.keys(keys)
    queries = self.queries(queries)

    energy = torch.einsum("nqhd,nkhd->nhqk", [queries, keys])
    if mask is not None:
        energy = energy.masked_fill(mask == 0, float("-1e20"))

    attention = torch.softmax(energy / (self.embed_size ** (1 / 2)), dim=3)
    out = torch.einsum("nhql,nlhd->nqhd", [attention, values]).reshape(N, query_len, self.heads * self.head_dim)
    out = self.fc_out(out)
    return out

# Example usage:
embed_size = 256
heads = 8
attention_layer = SelfAttention(embed_size, heads)

# Dummy data
N, value_len, key_len, query_len = 3, 50, 40, 30
value = torch.rand((N, value_len, embed_size))
key = torch.rand((N, key_len, embed_size))
query = torch.rand((N, query_len, embed_size))
mask = None  # Optional mask for padded tokens

# Forward pass
out = attention_layer(value, key, query, mask)
print(out.shape)  # Should be (N, query_len, embed_size)

3.查找数组元素三数之和

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个包含n个整数的数组`nums`，判断`nums`中是否存在三个元素`a`，`b`，`c`，使得`a + b + c = 0`？请找出所有和为0且不重复的三元组。

示例 1：
输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]

示例 2：
输入：nums = [-1, 2]
输出：[]

示例 3：
输入：nums = [0]
输出：[]

解题思路

  1. 排序：首先对数组进行排序，这样可以方便后续的去重和双指针查找。
  2. 遍历数组：固定一个元素，然后使用双指针法在剩余的元素中查找另外两个元素，使得它们的和为0。
  3. 去重：在遍历和查找过程中，需要注意去重，避免重复的三元组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i-1]:
            continue
        
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
    
    return result

4.编辑距离

题目内容

求两个单词的编辑距离：给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

已知你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

输入：

1
2
word1 = "horse"
word2 = "ros"

输出：

1
3

解释：

1
2
3
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

解题思路

这道题可以使用动态规划来解决。我们定义一个二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。

初始化：

  • dp[0][j] = j：将空字符串转换成 word2 的前 j 个字符需要 j 次插入操作。
  • dp[i][0] = i：将 word1 的前 i 个字符转换成空字符串需要 i 次删除操作。

状态转移方程：

  • 如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]。
  • 如果 word1[i-1] != word2[j-1]，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，分别对应删除、插入和替换操作。

最终结果：

  • dp[m][n]，其中 m 是 word1 的长度，n 是 word2 的长度。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

    return dp[m][n]

# 测试
word1 = "horse"
word2 = "ros"
print(minDistance(word1, word2))  # 输出: 3

5.岛屿数量

题目内容

给你一个由‘1’（陆地）和‘0’（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入: grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]

输出: 1

解题思路

这道题可以使用深度优先搜索（DFS）算法来解决。具体步骤如下：

  1. 遍历整个网格，当遇到一个陆地（’1’）时，进行深度优先搜索，将与之相连的所有陆地都标记为已访问（可以将其值改为’0’）。
  2. 每次进行一次深度优先搜索，就意味着发现了一个新的岛屿，因此岛屿计数器加1。
  3. 最后返回岛屿计数器的值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def numIslands(grid):
    if not grid:
        return 0

    def dfs(grid, i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        dfs(grid, i + 1, j)
        dfs(grid, i - 1, j)
        dfs(grid, i, j + 1)
        dfs(grid, i, j - 1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(grid, i, j)
                count += 1
    return count

# 示例
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

print(numIslands(grid))  # 输出: 1

6.零钱兑换问题

###题目描述：

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3
输出：-1

解题思路

这是一个典型的动态规划问题。我们可以使用一个数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数。初始化时，dp[0] 设为 0，其他元素设为一个较大的值（例如 amount + 1），表示不可能凑成的金额。

然后，我们遍历每个金额 i 从 1 到 amount，对于每个金额 i，我们再遍历每个硬币面额 coin，如果 coin 小于等于 i，则更新 dp[i] 为 min(dp[i], dp[i - coin] + 1)。

最后，如果 dp[amount] 仍然是一个较大的值，说明无法凑成该金额，返回 -1；否则返回 dp[amount]。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def coinChange(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != amount + 1 else -1

# 测试用例
print(coinChange([1, 2, 5], 11))  # 输出：3
print(coinChange([2], 3))        # 输出：-1

7.二叉树的最近公共祖先

###题目描述：
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：
“对于有根树T的两个节点p、q，最近公共祖先表示为一个节点 x，满足x是p、q的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。’

示例 1：
输入：root = [3,5,1,6,2,0,8,null,7,4], p = 5, q = 1

解题思路

  1. 递归法：从根节点开始递归遍历二叉树，判断当前节点是否是p或q，如果是，则返回当前节点。
  2. 如果当前节点的左子树和右子树都返回非空节点，则当前节点就是最近公共祖先。
  3. 如果左子树或右子树返回非空节点，则返回该节点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root
    elif left:
        return left
    else:
        return right

# 示例用法
# 构建二叉树
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

p = root.left
q = root.right

result = lowestCommonAncestor(root, p, q)
print(result.val)  # 输出: 3

8.两数之和

题目内容

给定一个已按照升序排列的整数数组 numbers，请你从数组中找出两个数满足相加之和等于目标数 target。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 0 开始计数，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1:

输入: numbers = [1,2,4,6,10], target = 8
输出: [1,3]
解释: 2 与 6 之和等于目标数 8。因此 index1 = 1，index2 = 3。

示例 2:

输入: numbers = [2,3,4], target = 6
输出: [0,2]

示例 3:

输入: numbers = [-1,0], target = -1
输出: [0,1]

解题思路

由于数组是升序排列的，我们可以使用双指针法来解决这个问题。具体步骤如下：

  1. 初始化两个指针，一个指向数组的起始位置（left），另一个指向数组的末尾位置（right）。
  2. 计算两个指针所指向的元素之和。
  3. 如果和等于目标数 target，则返回这两个指针的下标。
  4. 如果和小于目标数 target，则将左指针向右移动一位（left++）。
  5. 如果和大于目标数 target，则将右指针向左移动一位（right–）。
  6. 重复步骤 2-5，直到找到符合条件的两个数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
            
    return []

# 示例测试
print(two_sum([1,2,4,6,10], 8))  # 输出: [1, 3]
print(two_sum([2,3,4], 6))       # 输出: [0, 2]
print(two_sum([-1,0], -1))       # 输出: [0, 1]