今天参加某公司的专业面试，让手撕两个代码题，都不难但是考验细节处理。

一面题：实现快速排序

题目描述

输入一个整数数组，使用快速排序算法对其进行升序排序，并输出排序后的数组。要求使用递归实现快速排序算法。（提示：快速排序算法的基本思想是，选择一个基准元素，将数组分为两个子数组，左边的子数组都小于等于基准元素，右边的子数组都大于等于基准元素。）

思路

首先，需要了解快速排序的原理。

快速排序是一种分而治之的排序算法，其工作原理是递归地将输入数组划分为较小的子数组，直到每个子数组仅包含一个元素或为空。然后，算法合并已排序的子数组以获得排序的输出。快速排序中的分区过程包括从数组中选择一个基准元素并重新排列数组元素，以便所有小于基准的元素都放置在基准的左侧，并且所有大于基准的元素都放置在基准的右侧。在基准两侧的两个子数组上递归地重复此过程，直到整个数组排序完毕。

以下是分区过程的更详细说明：

  1. 从数组中选择一个基准。这可以是第一个元素、最后一个元素或两者之间的任何元素；
  2. 初始化两个索引 i 和 j，以标记基准两侧子数组的边界。 i 被初始化为数组中第一个元素的索引，j 被初始化为数组中最后一个元素的索引；
  3. 基准之后的元素开始，从左到右迭代数组。对于每个元素，将其与基准元素进行比较。
  4. 如果当前元素小于基准，则将其与索引 i 处的元素交换并增加 i值；
  5. 如果当前元素大于或等于主元，则将其保留在原处并继续迭代；
  6. 重复步骤 3-5，直到 j 到达基准点的索引；
  7. 将基准元素与索引 i 处的元素交换。这会将枢轴置于正确的排序位置；
  8. 分区过程现已完成。基准左侧的元素小于基准，基准右侧的元素大于或等于基准。

分区过程有效地将输入数组分为两个子数组，其中一个包含小于基准元素，另一个是包含大于或等于基准的元素。然后可以使用相同的分区过程对这些子数组进行递归排序。快速排序的时间复杂度平均为 O(n log n)，其中 n 是数组中元素的数量。然而，在最坏的情况下，当数组已经排序或反向排序时，时间复杂度可能是 O(n^2)。

答案

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
#include <iostream>
#include <vector>

using namespace std;

// 交换数组中两个元素的位置
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 找到基准元素的正确位置，并返回其索引
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1; // 初始化较小元素的索引

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 递归实现快速排序
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // 找到基准元素的正确位置
        int pivotIndex = partition(arr, low, high);

        // 递归对基准元素左右两部分进行排序
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 输出数组的函数
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {5,3,8,2,3,1,3,6,3};
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 调用快速排序算法进行排序
    quickSort(arr, 0, n - 1);

    // 输出排序后的数组
    cout << "Sorted array: ";
    printArray(arr);

    return 0;
}

看到这里可能还是有点迷惑，下面介绍一下分区的原理：

快速排序中的分区过程通过将重复元素全部放置在基准的一侧来处理重复元素。这可确保重复元素相对于彼此以及相对于数组中的其他元素正确排序。
以下是分区过程处理重复元素的方式：

  1. 当一个元素与基准进行比较时，如果该元素与基准相等，则将其放置在主元的右侧。
  2. 这意味着所有重复元素将被放置在基准的右侧，因为它们都等于基准。
  3. 分区过程完成后，基准与索引“i”处的元素交换。这会将基准放置在正确的排序位置，即所有重复元素的左侧。
  4. 然后可以使用相同的分区过程对基准两侧的两个子数组进行递归排序。

结果，所有重复元素将被放置在排序数组中，并且它们将相对于彼此以及数组中的其他元素正确排序。例如，考虑以下数组：

1
[5,3,8,2,3,1,3,6,3]

如果我们选择主元为 3，则分区过程将如下进行：

  1. 比较 5 和 3。由于 5 大于 3，因此将其保留在原处。
  2. 比较 8 和 3。由于 8 大于 3，因此将其保留在原处。
  3. 比较 2 和 3。由于 2 小于 3，因此将其与索引“i”处的元素（当前为 3）交换并递增“i”。
  4. 比较 3 和 3。由于 3 等于基准，因此将其放在基准的右侧。
  5. 比较 1 和 3。由于 1 小于 3，因此将其与索引“i”处的元素（当前为 4）交换并递增“i”。
  6. 比较 3 和 3。由于 3 等于基准，因此将其放在基准的右侧。
  7. 比较 6 和 3。由于 6 大于 3，因此将其保留在原处。
  8. 比较 3 和 3。由于 3 等于基准，因此将其放在基准的右侧。
  9. 将基准 (3) 与索引“i”处的元素（当前为 5）交换。
    分区过程完成后，数组将如下所示：
    1
    [2,1,3,3,3,3,6,8,5]
    现在，所有重复元素 (3) 都一起放置在枢轴的右侧，并且它们相对于彼此以及相对于数组中的其他元素正确排序。
    分区过程可以处理数组中任意数量的重复元素，并且始终能够正确地对它们进行排序。

二面题：链表整数加法

使用一个链表表示一个非负整数，每一个节点是一个0-9的整数且逆序存储，如：123 表示为（3->2->1）），除了首位之外不会有0 存在。求用上述链表表示的两个 整数的和，并以同样的方式表示出来。示例（321 + 654 = 975） 如下： (1->2->3) +（4->5->6) 输出：5->7->9。

思路

使用双指针，分别遍历两个链表，逐位相加即可。但是要注意进位，例如：1+9->9->9->9->9。我开始用的 while 循环条件是：while (l1 || l2)，这样就造成当两个数位数不同时，一个没遍历完，我会直接把链表链接上去。没考虑到进位，修改之后，可以看到这个是增加了一个进位的判断，能够保证后续一个数字链表也能接受进位。

此外，还需要注意的一点是，我原本是直接把新链表dummyHead对接到另一条没遍历完的链表，类似执行 1->2->4 + 3->5 = 4->7->4时候，我最终会把(1+3)–>(2+5)–>(5)，此时 5 还在 lb 那个链表上。这样可能带来的一个后果是，之后回收 lb 链表时，会把数值为(5)的那个节点直接回收，导致链表之和的链表会出现缺失，导致问题。

解决方法是，重新申请一个指针指向(5)，然后再把和链指向它。

实现

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
73
74
75
76
77
78
79
80
81
82
#include <iostream>

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int val) : value(val), next(nullptr) {}
};

ListNode* addLinkedLists(ListNode* l1, ListNode* l2) {
    ListNode* dummyHead = new ListNode(0);
    ListNode* current = dummyHead;
    int carry = 0;

    while (l1 || l2 || carry) {
        // 获取当前节点的值，如果链表已经遍历完则为0
        int value1 = l1 ? l1->value : 0;
        int value2 = l2 ? l2->value : 0;

        // 计算当前位的和以及进位
        int currentSum = value1 + value2 + carry;
        carry = currentSum / 10;
        int remainder = currentSum % 10;

        // 创建新的节点，连接到链表尾部
        current->next = new ListNode(remainder);
        current = current->next;

        // 移动到下一个节点
        if (l1) {
            l1 = l1->next;
        }
        if (l2) {
            l2 = l2->next;
        }
    }

    return dummyHead->next;
}

// 释放链表内存
void deleteLinkedList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

// 输出链表
void printLinkedList(ListNode* head) {
    while (head) {
        std::cout << head->value;
        if (head->next) {
            std::cout << "->";
        }
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    // 示例
    ListNode* l1 = new ListNode(3);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(1);

    ListNode* l2 = new ListNode(6);
    l2->next = new ListNode(5);
    l2->next->next = new ListNode(4);

    ListNode* result = addLinkedLists(l1, l2);

    // 输出结果
    printLinkedList(result);

    // 释放内存
    deleteLinkedList(l1);
    deleteLinkedList(l2);
    deleteLinkedList(result);

    return 0;
}

计算机相关知识

栈溢出

栈溢出是指程序运行时使用的栈空间超出了其分配的范围，导致发生错误。在C++中，栈溢出通常发生在递归调用深度过大或局部变量占用空间过多的情况下。以下是与栈溢出相关的一些知识点：

  1. 栈的概念： 在计算机内存中，栈是一种线性数据结构，遵循先进后出（LIFO）的原则。在函数调用时，局部变量、函数参数和返回地址等信息被存储在栈上。

  2. 栈溢出原因： 主要原因是栈空间不足以容纳当前函数调用的所有信息。这可能是由于递归调用过深、局部变量占用空间过多或者函数调用的参数过多导致的。

  3. 递归调用： 如果递归深度很大，每次递归都会在栈上创建一个新的函数调用帧，如果栈空间不够大，就会导致栈溢出。可以考虑使用迭代或尾递归来减小递归深度。

  4. 局部变量和数组： 如果函数内有大量的局部变量或者数组，它们会占用栈空间。如果这些变量过多或者过大，就可能导致栈溢出。

  5. 函数调用参数： 函数调用时，参数也会被压入栈中。如果函数的参数过多，可能会导致栈空间不足。

  6. 栈大小限制： 操作系统和编译器通常限制每个线程的栈大小。如果超过这个限制，就会触发栈溢出。可以通过调整编译器或操作系统的设置来增大栈大小，但这并不是解决根本问题的好方法。

  7. 异常处理： 如果程序中有异常处理机制，例如使用try-catch块，异常也可能在栈溢出时被抛出，但这并不总是可靠的。

为了避免栈溢出，可以采取以下措施：

  • 优化递归算法： 尽量减小递归深度，或者考虑使用迭代代替递归。

  • 减小局部变量和数组的大小： 合理使用局部变量，尽量避免过多的占用栈空间的变量。

  • 限制函数调用参数的数量： 如果可能，尽量减小函数参数的数量。

  • 使用堆内存： 将大量数据放在堆上而不是栈上，通过动态分配内存来避免栈空间不足的问题。

总的来说，栈溢出是由于栈空间不足导致的，合理设计算法和数据结构，以及注意栈空间的使用是避免栈溢出的关键。

数组和链表的优缺点

下面是数组和链表的主要优缺点：

数组：
优点：

  1. 随机访问： 数组支持常量时间内的随机访问，因为元素在内存中是连续存储的，可以通过索引直接访问。

  2. 内存利用效率高： 相对于链表，数组在存储元素时不需要额外的指针空间，因此内存利用效率较高。

  3. 缓存友好： 数组的元素在内存中是相邻的，这有利于缓存的预取和利用，使得数组在一些计算密集型任务中性能较好。

缺点：

  1. 大小固定： 数组的大小在创建时就确定，并且不容易动态改变大小，这导致可能浪费内存或者无法满足动态数据的需求。

  2. 插入和删除操作慢： 在数组中插入或删除元素通常需要移动其他元素，时间复杂度为O(n)，其中n是元素的数量。

链表：
优点：

  1. 动态大小： 链表的大小可以动态增长或缩小，不需要预先分配空间，因此适用于动态数据结构。

  2. 插入和删除操作快： 在链表中插入或删除元素的时间复杂度通常为O(1)，只需要调整指针的指向。

  3. 不浪费内存： 链表可以灵活地使用内存，不会浪费额外的空间。

缺点：

  1. 随机访问慢： 链表不支持常量时间内的随机访问，需要从头开始遍历，时间复杂度为O(n)，其中n是元素的数量。

  2. 额外的指针空间： 链表中每个节点都需要额外的指针来指向下一个节点，占用了额外的存储空间。

  3. 缓存不友好： 由于链表的节点在内存中不一定相邻，可能导致缓存不命中，性能相对较差。

综合来说，根据具体的应用场景和操作需求，选择数组或链表有不同的合适情况。数组适用于需要频繁随机访问的场景，而链表适用于需要频繁插入和删除操作的动态数据结构。

内存泄露

内存泄露是指在程序运行过程中，由于一些错误或疏忽，未能正确释放已经分配的内存空间，导致程序在运行时持续占用内存，最终导致系统的可用内存减少，甚至在长时间运行后可能导致程序崩溃。

检测内存泄露：

  1. 静态分析工具： 使用一些静态代码分析工具，例如Valgrind（对于C/C++）或Clang Static Analyzer，它们可以在编译时或运行时检测内存泄露。

  2. 动态分析工具： 内存调试工具，例如AddressSanitizer、Valgrind等，可以在程序运行时检测内存泄露。

  3. 手动检查： 通过编写代码，在对象生命周期结束时检查是否正确释放了内存。在C++中，可以使用智能指针等自动内存管理机制，减少手动释放内存的错误。

避免内存泄露：

  1. 使用智能指针： 在C++中，使用std::shared_ptr、std::unique_ptr等智能指针可以自动管理内存，避免手动释放的问题。

    1
    2
    std::shared_ptr<int> ptr = std::make_shared<int>(42);
    // 不需要手动释放内存

  2. RAII（资源获取即初始化）原则： 通过对象的生命周期管理资源的获取和释放，确保在对象销毁时资源得到正确释放。

  3. 注意循环引用： 在使用引用计数智能指针时，要注意可能导致循环引用的情况，这会导致对象无法正常释放。

  4. 释放动态分配的内存： 对于每次动态分配的内存，都要确保在不再需要的时候正确释放。使用delete或者delete[]。

    1
    2
    3
    int* arr = new int[10];
    // 使用 arr
    delete[] arr; // 释放内存

  5. 使用容器和算法库： 在C++中，使用标准库提供的容器和算法，如std::vector、std::list等，它们会自动处理内存管理，避免手动操作带来的问题。

  6. 谨慎使用全局变量： 全局变量的内存分配和释放由系统管理，但如果滥用全局变量，可能导致程序结束时无法释放一些资源，从而造成内存泄露。

  7. 测试和代码审查： 定期进行内存泄露检测，进行代码审查，并使用单元测试和集成测试来确保程序的稳定性。

  8. 了解并使用内存管理工具： 学习并使用内存管理工具，如valgrind、AddressSanitizer等，它们可以帮助检测和定位内存泄漏问题。

哈希表

哈希表（Hash Table）是一种数据结构，用于实现字典（Dictionary）或关联数组（Associative Array）。它通过哈希函数将关键字映射到数组中的一个位置，从而实现快速的插入、删除和查找操作。

哈希表的基本原理：

  1. 哈希函数： 将关键字映射到数组的索引位置。良好设计的哈希函数应该尽量避免冲突，即不同的关键字映射到相同的索引位置。

  2. 数组： 存储元素的数组，每个位置称为桶（Bucket）。每个桶可以存储一个或多个元素，具体取决于哈希表的实现。

解决哈希冲突的方法：

  1. 链地址法（Separate Chaining）： 每个桶维护一个链表，哈希冲突时将元素插入链表中。这是一种简单有效的方法，但可能会导致链表过长，影响性能。

  2. 开放地址法（Open Addressing）： 当哈希冲突发生时，通过一定的探测方式（线性探测、二次探测等）找到下一个可用的位置。这种方法避免了链表的使用，但需要更多的探测逻辑。

  3. 再哈希（Rehashing）： 当哈希表的负载因子达到一定阈值时，进行再哈希操作，即扩大数组并重新哈希。这有助于减少冲突，但也增加了操作的开销。

实际编码中的应用：

  1. 字典和集合： 哈希表常用于实现字典（键值对存储）和集合（不重复元素存储）。

  2. 缓存实现： 用于缓存系统，通过哈希表存储缓存项，加速数据的访问。

  3. 数据索引： 在数据库中，哈希表可用于实现索引，提高数据检索效率。

  4. 编译器符号表： 用于存储变量名、函数名等符号信息，加速编译过程中的查找。

  5. 密码学中的应用： 一些密码学算法使用哈希表来存储散列值，如消息摘要算法。

  6. 哈希集合和哈希映射： 在编程语言中，常见的集合和映射数据结构通常基于哈希表实现。

在实际编码中，哈希表是一种非常常用且高效的数据结构，因为它提供了快速的查找和插入操作。然而，需要注意选择合适的哈希函数和解决冲突的方法，以及在动态数据集合中及时处理再哈希操作，以维护哈希表的性能。