C++面试知识点总结

一、怎么实现一个set容器？
std::set 是一个有序的关联容器，它以红黑树（Red-Black Tree）作为底层数据结构来存储元素，确保元素按照升序排列。在C++中，可以直接使用std::set。
例：

#include 
#include 

int main() {
    // 创建一个空的 Set 容器
    std::set<int> mySet;

    // 添加元素到 Set 中
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(5);

    // 删除元素
    mySet.erase(1);

    // 检查元素是否存在
    if (mySet.count(3) > 0) {
        std::cout << "3 存在于 Set 中" << std::endl;
    } else {
        std::cout << "3 不在 Set 中" << std::endl;
    }

    // 获取 Set 的大小
    std::cout << "Set 的大小：" << mySet.size() << std::endl;

    // 遍历 Set 中的元素
    std::cout << "Set 中的元素：";
    for (const int& element : mySet) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}
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

std::set 会自动保持元素的有序性，因此元素将按升序排列。

二、红黑树怎么实现的，介绍下红黑树的结构，为什么查询的时间复杂度比较稳定？
（1）实现：红黑树（Red-Black Tree）是一种自平衡二叉搜索树，它在二叉搜索树的基础上引入了额外的规则和属性来保持树的平衡。红黑树的平衡性质使得查询操作的时间复杂度比较稳定，通常为 O(log n)，其中 n 是树中节点的数量。
（2）结构：
红黑树的每个节点包含以下属性：
1）颜色属性（Color）：每个节点都有颜色，可以是红色（Red）或黑色（Black）。
2）键（Key）：每个节点都包含一个键，它用于进行搜索、插入和删除操作。
3）左子树（Left Subtree）和右子树（Right Subtree）：每个节点都有两个子树，分别是左子树和右子树，它们也是红黑树。
4）父节点（Parent）：每个节点都有一个父节点，指向其父节点。
5）特性（Properties）：红黑树必须满足一组特性，确保树的平衡性。这些特性包括：
a、每个节点要么是红色，要么是黑色。
b、根节点是黑色。
c、每个叶子节点（NIL 节点或空节点）都是黑色。
d、若一个节点是红色，那么它的子节点必须是黑色。
e、从任意节点到其每个叶子节点的路径都包含相同数量的黑色节点（黑高相同）。

查询时间复杂度的稳定性：
红黑树的查询操作具有稳定的时间复杂度，原因如下：
1、平衡性：红黑树通过特性的约束来保持平衡。由于黑高相同的特性，从根节点到任意叶子节点的路径长度是相等的。这确保了树的高度保持在可控制的范围内。
2、二叉搜索树性质：红黑树本质上是一棵二叉搜索树，因此具有二叉搜索树的性质。根据二叉搜索树性质，左子树的所有节点都小于父节点，右子树的所有节点都大于父节点。这使得在搜索操作中，可以通过比较键值来确定向左子树还是向右子树搜索，从而加速查询过程。
3、平均深度有限：由于红黑树的平衡性，树的高度是有限的，不会出现极端的情况。因此，平均情况下，查询的深度是对数级别的，时间复杂度为 O(log n)，其中 n 是树中节点的数量。

三、栈和队列的区别，栈的pop和remove有什么区别？
栈：
1、特点：栈是一种线性数据结构，遵循后进先出（Last-In-First-Out，LIFO）原则。这意味着最后进栈的元素将是第一个出栈的元素，而最早进栈的元素将是最后出栈的元素。
2、操作：栈支持两个基本操作：
push：将元素压入栈顶。
pop：从栈顶弹出元素。
3、应用：栈常用于需要回溯或撤销操作的情况，如函数调用栈、表达式求值、括号匹配等。

队列：
1、特点：队列是一种线性数据结构，遵循先进先出（First-In-First-Out，FIFO）原则。这意味着最早入队的元素将是最早出队的元素，而最晚入队的元素将是最晚出队的元素。
2、操作：队列支持两个基本操作：
enqueue：将元素添加到队列的末尾。
dequeue：从队列的头部移除元素。
3、应用：队列常用于任务调度、广度优先搜索（BFS）、缓冲数据、消息传递等需要按顺序处理的情况。

栈的pop和remove区别：
1、pop 操作：pop 是栈的基本操作之一，用于移除并返回栈顶的元素。它会将栈顶元素出栈，同时修改栈的结构。
2、remove 操作：remove 不是栈的标准操作，而是一个通用的数据结构操作。它用于从数据结构中删除指定元素，而不仅仅是栈。在栈中，remove 通常不是一个常见的操作，因为栈的主要操作是 push 和 pop，而不是删除特定元素。

四、说一下list,map,set的区别？
list（双向链表）：
1、特点：list 是一个双向链表，可以容纳重复元素。每个元素包含了一个值以及指向前一个元素和后一个元素的指针。因为是链表，插入和删除元素的操作是高效的，但随机访问元素的效率较低。
2、常见操作：list 通常支持以下操作：

push_back()：在列表末尾添加元素。
push_front()：在列表开头添加元素。
insert()：在指定位置插入元素。
erase()：删除指定位置的元素。
size()：获取列表大小。
迭代器遍历等操作。
1
2
3
4
5
6

map（关联数组）：
1、特点：map 是一种关联数组，也被称为字典或键值对容器。它存储键值对，其中每个键关联一个唯一的值。map 使用红黑树作为底层数据结构，确保了键的唯一性和自动排序。
2、常见操作：map 通常支持以下操作：

insert()：插入键值对。
find()：查找指定键对应的值。
erase()：删除指定键值对。
size()：获取 map 大小。
迭代器遍历等操作。
1
2
3
4
5

set（集合）：
1、特点：set 是一种集合容器，存储唯一的元素，不允许重复。它使用红黑树作为底层数据结构，确保了元素的唯一性和自动排序。
2、常见操作：set 通常支持以下操作：

insert()：插入元素。
find()：查找指定元素。
erase()：删除指定元素。
size()：获取集合大小。
迭代器遍历等操作。
1
2
3
4
5

五、C/C++的struct有什么区别？
在C中的struct：
1、没有访问控制：在C中，struct 中的数据成员默认是公有的，即所有数据成员可以在结构体外部访问。C中没有访问控制关键字（如private、protected、public），因此无法限制对结构体成员的访问权限。
2、没有构造函数和析构函数：C中的struct没有构造函数和析构函数的概念。结构体的创建和销毁通常由程序员手动管理。
3、无法继承：在C中，struct不能被继承，因为C中没有类的概念。结构体只是一组数据成员的集合。
4、无法拥有成员函数：C中的struct不能包含成员函数（或方法），只包含数据成员。

在C++中的struct：
1、有访问控制：在C++中，struct 和 class 的主要区别是默认的访问控制。在struct中，成员默认是公有的，而在class中，成员默认是私有的。这意味着在struct中的成员可以直接访问，而在class中的成员需要通过公有成员函数进行访问控制。
2、可以拥有构造函数和析构函数：在C++中，struct可以拥有构造函数和析构函数，用于初始化和清理对象的状态。这使得struct可以像类一样具有更多的行为。
3、可以继承：在C++中，struct可以像class一样进行继承，可以通过派生类继承并扩展基类的成员。
4、可以拥有成员函数：C++中的struct可以包含成员函数，使其更接近于类的概念。这意味着struct可以具有数据成员和成员函数，可以实现更复杂的行为。

六、手撕，旋转排序数组？
问题描述：给定一个旋转排序数组 nums，其中的元素按升序排序，并在某个位置上进行了旋转。例如，[0, 1, 2, 4, 5, 6, 7] 可以通过旋转操作变成 [4, 5, 6, 7, 0, 1, 2]。

一种高效解决这个问题的方法是使用修改过的二分查找算法。正常的二分查找算法假设数组是完全有序的，但在旋转数组中，数组的一部分是有序的。

1、初始化两个指针 left 和 right 分别指向数组的首尾元素。
2、在每一步中，计算中间元素的索引 mid，即：mid = (left + right) / 2
3、比较中间元素 nums[mid] 与目标值 target：
a、如果 nums[mid] == target，则找到了目标，返回 mid；
b、否则，分两种情况讨论：
1）、如果 nums[left] <= nums[mid]，说明左半段是有序的。这时可以判断 target 是否在左半段，如果在，则更新 right = mid - 1，否则更新 left = mid + 1。
2）、如果 nums[mid] < nums[left]，说明右半段是有序的。这时可以判断 target 是否在右半段，如果在，则更新 left = mid + 1，否则更新 right = mid - 1。
4、重复步骤 2 和 3，直到 left > right。如果没有找到目标值，返回 -1。

#include 
#include 
using namespace std;

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int target;
    cin >> target;
    int result = search(nums, target);
    cout << result << endl;
    return 0;
}
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

结果：