C++基础面试题

一、vector和list的区别
1.1 底层数据结构
vector 使用动态数组作为底层数据结构，元素在内存中是连续存储的；
list 使用双向链表作为底层数据结构，元素在内存中通过节点相互连接。
1.2 插入和删除操作
vector 在尾部插入或删除元素效率高，但在中间或头部插入/删除元素时需要移动后续元素，效率较低；
list 在任意位置插入或删除元素的效率都很高，因为它只需修改相邻节点的指针。
1.3 随机访问
vector允许通过下标进行快速随机访问，因为元素在内存中是连续的；
list不支持随机访问，访问元素需要从头结点开始遍历列表，效率较低。
1.4 内存分配
vector需要预先分配一块连续内存，如果元素数量动态增长，可能需要重新分配内存，导致内存浪费或复制操作；
list在插入或释放时只需分配或释放对应节点的内存，内存占用相对较小。
二、vector删除元素、删除区间的理解，erase返回什么？
C++的标准库中，std::vector是一个动态数组容器，你可以使用erase函数来删除单个元素或一个区间内的元素。erase函数的返回值是指向被删除元素之后的迭代器，或者如果删除的是最后一个元素，则返回end()。
如下例子所示：

#include <iostream>
#include <vector>int main() {std::vector<int> numbers = {1, 2, 3, 4, 5};// 删除单个元素std::vector<int>::iterator it = numbers.begin() + 2;it = numbers.erase(it); // 删除索引为2的元素（值为3）for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl;// 删除一个区间std::vector<int>::iterator first = numbers.begin() + 1;std::vector<int>::iterator last = numbers.begin() + 3;numbers.erase(first, last); // 删除区间[1, 3)for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

首先删除了索引为2的元素（值为3），erase返回的迭代器指向被删除元素之后的位置，所以此时it指向了原来的索引为3的元素。然后，我们删除了区间[1, 3)内的元素，即索引1和2的元素，最终得到修改后的numbers。

三、数组和链表区别（相当于是对第一题的详细解释）？
3.1 存储方式
a. 数组：数组是一种连续的存储结构，元素在内存中按线性顺序排列，这使得数组支持随机访问，可以通过索引快速访问任何元素；
b.链表：链表是一种非连续的存储结构，元素以节点的形式存在，每个节点包含数据和指向下一个节点的指针；链表不支持随机访问，必须从头节点开始遍历才能找到特定元素。
3.2 大小固定性
a.数组：数组的大小通常是固定的，一旦分配内存空间，极不容易动态扩展或缩小，此时可通过动态数组来解决，如std::vector；
b.链表 链表大小可以动态增减，节点可以根据需要进行动态分配和释放。
3.3 插入和删除
a.数组：在数组中插入或删除元素通常需要移动其他元素，这可能涉及到大量的数据搬迁，导致性能下降；
b.链表：在链表中插入或删除元素只需要调整节点的指针，不需要移动大量的数据，因此插入和删除操作通常更高效。
四、单向链表，如何找到中间的节点
可使用双指针技巧，其中一个指针每次移动一个节点，另一个指针每次移动两个节点。当快指针到达链表尾部时，慢指针就会指向链表的中间节点。
参考代码如下：

#include <iostream>struct ListNode {int data;ListNode* next;ListNode(int val) : data(val), next(nullptr) {}
};ListNode* findMiddle(ListNode* head) {if (head == nullptr) {return nullptr;}ListNode* slow = head;ListNode* fast = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;        // 慢指针每次移动一个节点fast = fast->next->next;  // 快指针每次移动两个节点}return slow;
}int main() {// 创建一个单链表：1 -> 2 -> 3 -> 4 -> 5ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);head->next->next->next->next = new ListNode(5);// 找到中间节点ListNode* middle = findMiddle(head);if (middle != nullptr) {std::cout << "中间节点的值为: " << middle->data << std::endl;} else {std::cout << "链表为空或长度为偶数，没有中间节点。" << std::endl;}// 释放链表内存while (head != nullptr) {ListNode* temp = head;head = head->next;delete temp;}return 0;
}

五、时间复杂度的概念，如何计算
时间复杂度通常用大O符号（O）来表示，表示算法的运行时间与输入规模之间的增长关系。常见的时间复杂度包括 O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(2n) 等。
5.1：O(1) - 常数时间复杂度：算法的运行时间是常数，与输入规模无关。例如，访问数组中的元素。
5.2：O(log n) - 对数时间复杂度：算法的运行时间随输入规模呈对数增长。例如，二分查找。
5.3：O(n) - 线性时间复杂度：算法的运行时间与输入规模成正比。例如，遍历数组。
5.4：O(n log n) - 线性对数时间复杂度：算法的运行时间随输入规模呈 n log n 增长。例如，快速排序和归并排序。
5.5：O(n^2) - 平方时间复杂度：算法的运行时间与输入规模的平方成正比。例如，简单的嵌套循环。
5.6：O(2^n) - 指数时间复杂度：算法的运行时间随输入规模成指数级增长。例如，暴力解法。
计算时间复杂度通常涉及分析算法中的循环和递归结构。你需要考虑算法中执行次数最多的那部分代码，并用输入规模 n 来表示。在分析过程中，通常忽略常数因子和低阶项，只关注增长最快的项，因为它们在大规模数据下占主导地位。
六、归并排序算法的实现
流程：
6.1、将待排序数组分为两半，直到每个子数组只包含一个元素。
6.2、递归地对左半部分和右半部分进行排序。
6.3、合并两个有序子数组为一个大的有序数组。
例：

#include <iostream>
#include <vector>// 合并两个有序数组为一个有序数组
void merge(std::vector<int>& arr, int left, int middle, int right) {int n1 = middle - left + 1;int n2 = right - middle;std::vector<int> leftArr(n1);std::vector<int> rightArr(n2);// 将数据拷贝到左右两个子数组中for (int i = 0; i < n1; i++) {leftArr[i] = arr[left + i];}for (int i = 0; i < n2; i++) {rightArr[i] = arr[middle + 1 + i];}// 归并过程int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;}k++;}// 处理剩余元素while (i < n1) {arr[k] = leftArr[i];i++;k++;}while (j < n2) {arr[k] = rightArr[j];j++;k++;}
}// 归并排序主函数
void mergeSort(std::vector<int>& arr, int left, int right) {if (left < right) {int middle = left + (right - left) / 2;// 递归排序左右两半mergeSort(arr, left, middle);mergeSort(arr, middle + 1, right);// 合并已排序的两部分merge(arr, left, middle, right);}
}int main() {std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};int n = arr.size();std::cout << "Original Array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;mergeSort(arr, 0, n - 1);std::cout << "Sorted Array: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

七、如何对排好序的数组去除重复元素？
流程：
7.1 初始化两个指针，一个指向当前元素，另一个指向下一个元素。
7.2 检查当前元素和下一个元素是否相等。
7.3 如果相等，将下一个元素删除，继续检查下一个元素，直到找到不同的元素。
7.4 如果不同，将第一个指针移到下一个位置，继续检查下一个元素。

#include <vector>std::vector<int> removeDuplicates(std::vector<int>& sortedArray) {int n = sortedArray.size();if (n <= 1) {return sortedArray; // 如果数组为空或只有一个元素，无需去重}int index = 0; // 用于记录非重复元素的位置for (int i = 1; i < n; i++) {if (sortedArray[i] != sortedArray[index]) {index++;sortedArray[index] = sortedArray[i];}}sortedArray.resize(index + 1); // 调整数组大小，去除重复元素后的大小return sortedArray;
}int main() {std::vector<int> sortedArray = {1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 6};std::cout << "原始数组：";for (int num : sortedArray) {std::cout << num << " ";}std::cout << std::endl;sortedArray = removeDuplicates(sortedArray);std::cout << "去除重复后的数组：";for (int num : sortedArray) {std::cout << num << " ";}std::cout << std::endl;return 0;
}