蒋豆芽的面试题专栏（29/数据结构与算法）

说说一个算法有哪些时间复杂度？归并算法时间复杂度是多少？⭐⭐⭐
说说数组时间复杂度，什么场景下使用？⭐⭐⭐⭐⭐
说说vector的实现原理⭐⭐⭐⭐⭐
实现一个vector⭐⭐⭐⭐⭐
分析一下push_back() 的时间复杂度⭐⭐⭐⭐⭐
总结一下数组与链表的区别⭐⭐⭐⭐⭐
栈和队列的区别⭐⭐⭐⭐⭐
来手写一个链表⭐⭐⭐⭐⭐
用数组或链表来实现一个栈⭐⭐⭐⭐
用数组或链表来实现一个队列⭐⭐⭐⭐
说说二叉堆⭐⭐⭐⭐⭐
说说哈希表⭐⭐⭐⭐⭐
说说堆排序的时间复杂度，建堆的时间复杂度⭐⭐⭐⭐⭐
哈希表如何解决哈希冲突⭐⭐⭐⭐⭐
哈希表的初始数组容量一般为多少，为什么？⭐⭐⭐⭐⭐
哈希表的负载因子为什么是0.75？⭐⭐⭐⭐⭐
说说红黑树⭐⭐⭐⭐⭐

=========================================================================================================

本专栏适合于C/C++已经入门的学生或人士，有一定的编程基础。
本专栏适合于互联网C++软件开发、嵌入式软件求职的学生或人士。
本专栏针对面试题答案进行了优化，尽量做到好记、言简意赅。这才是一份面试题总结的正确打开方式。这样才方便背诵
针对于非科班同学，建议学习本人专刊文章《蒋豆芽的秋招打怪之旅》，该专刊文章对每一个知识点进行了详细解析。
如专栏内容有错漏，欢迎在评论区指出或私聊我更改，一起学习，共同进步。
相信大家都有着高尚的灵魂，请尊重我的知识产权，未经允许严禁各类机构和个人转载、传阅本专栏的内容。

=========================================================================================================

说说一个算法有哪些时间复杂度？归并算法时间复杂度是多少？⭐⭐⭐

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

归并算法时间复杂度是O(nlogn)
说说数组时间复杂度，什么场景下使用？⭐⭐⭐⭐⭐

从渐进趋势来看，数组插入和删除操作的时间复杂度是O(n)。而数组是有序的，可以直接通过下标访问元素，十分高效，访问时间复杂度是O(1)（常数时间复杂度）。

如果某些场景需要频繁插入和删除元素时，这时候不宜选用数组作为数据结构。

频繁访问的场景下，可以使用数组。
说说vector的实现原理⭐⭐⭐⭐⭐

vector是数组的进一步封装，它是一个类。可以比数组更加灵活的处理内存空间。

vector采用的数据结构是线性的连续空间，它以两个迭代器start和finish分别指向配置得来的连续空间中目前已将被使用的空间。迭代器end_of_storage指向整个连续的尾部。

vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新的元素。vector在增加元素时，如果超过自身最大的容量Capacity，vector则将自身的容量扩充为原来的两倍。扩充空间需要经过的步骤：重新配置空间，元素移动，释放旧的内存空间。一旦vector空间重新配置，则指向原来vector的所有迭代器都失效了，因为vector的地址改变了。

实现一个vector⭐⭐⭐⭐⭐

#ifndef _MY_VECTOR_HPP_
#define _MY_VECTOR_HPP_

template<typename T>
class MyVector{
public:
    // 构造函数
    MyVector(){
        //这里默认数组大小为10
        //但是vector文件中默认构造的方式是0，之后插入按照1 2  4  8  16 二倍扩容。注GCC是二倍扩容，VS13是1.5倍扩容
        data = new T[10];
        _capacity = 10;
        _size = 0;
    }
    ~MyVector(){
        delete[] data;
    }
    //reserve只是保证vector的空间大小(_capacity)最少达到它的参数所指定的大小n。在区间[0, n)范围内,预留了内存但是并未初始化
    void reserve(size_t n){
        if(n>_capacity){
            data = new T[n]; 
            _capacity = n;
        }
    }
    //向数组中插入元素
    void push_back(T e){
        //如果当前容量已经不够了，重新分配内存，均摊复杂度O(1)
        if (_size == _capacity){
            resize(2 * _capacity);//两倍扩容
        }
        data[_size++] = e;
    }
    //删除数组尾部的数据，同时动态调整数组大小，节约内存空间
    T pop_back(){
        T temp = data[_size];
        _size--;
        //如果容量有多余的，释放掉
        if (_size == _capacity / 4){
            resize(_capacity / 2);
        }
        return temp;
    }
    //获取当前数组中元素的个数
    size_t size(){
        return _size;
    }
    //判断数组是否为空
    bool empty(){
        return _size==0?1:0;
    }
    //重载[]操作
    int &operator[](int i){
        return data[i];
    }
    //获取数组的容量大小
    size_t capacity(){
        return _capacity;
    }
    //清空数组,只会清空数组内的元素，不会改变数组的容量大小
    void clear(){
        _size=0;
    }
private:
    T *data;    //实际存储数据的数组
    size_t _capacity; //容量
    size_t _size;  //实际元素个数
    //扩容
    void resize(int st){
        //重新分配空间，在堆区新开辟内存，然后将以前数组的值赋给他，删除以前的数组
        T *newData = new T[st];
        for (int i = 0; i < _size; i++){
            newData[i] = data[i];
        }
        //实际使用时是清除数据，但不会释放内存
        delete[] data;
        data = newData;
        _capacity = st;
    }
};

#endif //_MY_VECTOR_HPP_

分析一下push_back() 的时间复杂度⭐⭐⭐⭐⭐

采用均摊分析的方法，公式如下：公式里面，假定有 n 个元素，倍增因子为 m（我们设定为2），那么完成这 n 个元素往一个 vector 中的push_back操作，需要重新分配内存的次数大约为 log2(n)，第 i 次重新分配将会导致复制 2^i (也就是当前的vector.size() 大小)个旧空间中元素，因此 n 次 push_back 操作所花费的总时间：然后 n 次push_back操作，每次分摊O(1)，即为常数时间复杂度了。

来手写一个链表⭐⭐⭐⭐⭐

struct ListNode { // 链表结构体
    int data;
    ListNode *next;
};

ListNode * initLink(){  // 创建一个链表（1，2，3，4）
    ListNode * p=(ListNode*)malloc(sizeof(ListNode));//创建一个头结点
    ListNode * temp=p;//声明一个指针指向头结点，用于遍历链表
    //生成链表
    for (int i=1; i<5; i++) {
        ListNode *node=(ListNode*)malloc(sizeof(ListNode));
        node->data=i;
        node->next=NULL;
        temp->next=node;
        temp=temp->next;
    }
    return p;
}

int selectElem(ListNode * p,int elem){ // 链表中查找某结点
    ListNode * t=p;
    int i=1;
    while (t->next) {
        t=t->next;
        if (t->data==elem) {
            return i;
        }
        i++;
    }
    return -1;
}

ListNode * insertElem(ListNode * p,int elem,int add){ // 插入结点
    ListNode * temp=p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置无效\n");
            return p;
        }
        temp=temp->next;
    }    
    //创建插入结点node
    ListNode * node=(ListNode*)malloc(sizeof(ListNode));
    node->data=elem;
    //向链表中插入结点
    node->next=temp->next;
    temp->next=node;
    return  p;
}

ListNode * delElem(ListNode * p,int add){
    ListNode * temp=p;
    //temp指向被删除结点的上一个结点
    for (int i=1; i<add-1; i++) {
        temp=temp->next;
        if (temp->next == NULL) // 判断add的有效性
            return p;
    }
    ListNode *del=temp->next;//单独设置一个指针指向被删除结点，以防丢失
    temp->next=temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点，防止内存泄漏
    return p;
}

总结一下数组与链表的区别⭐⭐⭐⭐⭐
1. 数组内存连续、有序；链表内存可以不连续
2. 数组可以直接访问下标，访问时间复杂度O(1)；链表需要通过下一级指针层层递进访问，访问时间复杂度O(n)
3. 数组插入或删除元素时需要移动后面的元素，时间复杂度O(n)；而链表插入或删除元素时，时间复杂度O(1)
4. 频繁访问元素的场景用数组；频繁插入或删除的场景用链表
栈和队列的区别⭐⭐⭐⭐⭐

主要区别就是规定不同。

栈规定：元素先入后出（First In Last Out，简称FILO）。

队列规定：元素先入先出（First In First Out，简称FIFO）。

用数组或链表来实现一个栈⭐⭐⭐⭐

实现的原理都是类似的，用游标变量来控制元素的位置。

栈只需要设置一个游标变量来控制栈顶元素的位置

大家一定要掌握，面试很容易手撕代码。

数组实现栈：

#include<iostream>
using namespace std;

typedef int dataType;
class Stack{
private:
    dataType* arrays; // 成员数组
    int top;     // 栈顶
    int size_a;  // 数组大小
public:
    Stack();
    ~Stack();

    void push(dataType data); // 入栈
    void pop();               // 出栈
    dataType f_top();         // 访问栈顶元素
    bool isEmpty();           // 判空
    bool isFull();            // 判满
};

Stack::Stack():size_a(10), top(-1){      // 初始化
    arrays = new dataType[size_a];       // 申请10个内存大小的空间
}

Stack::~Stack(){
    delete[] arrays;
    arrays = nullptr;
}

void Stack::push(dataType data){
    if(isFull())
        cout << "The stack is full!" << endl;
    else
        arrays[++top] = data;
}

void Stack::pop(){
    if(isEmpty())
        cout << "The stack is empty!" << endl;
    else
		top--;
}

dataType Stack::f_top(){ // 返回栈顶元素
	if(isEmpty()){
        cout << "The stack is empty!" << endl;
		return -1;
	}
    else
    	return arrays[top];
}

bool Stack::isEmpty(){
    return (top == -1);
}

bool Stack::isFull(){
    return (top >= size_a-1); // 当top为9的时候栈已满
}

int main (){ // 测试用例
	Stack s;
	for (int i=0; i<11; i++){
		s.push(i);
		cout << s.f_top() << endl;
	}
	for (int i=0; i<11; i++){
		s.pop();
		cout << s.f_top() << endl;
	}
	return 0;
}

链表实现栈：

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef int dataType;
struct node{        //链栈节点
    dataType data;  //数值
    node *next;     //指针域
};

class Lstack{
public:
    Lstack();
    ~Lstack();
    void push(dataType var); //压栈
    void pop();              //出栈
    dataType f_top();        //取栈顶元素
    bool isEmpty();          //判断是否为空
private:
    node *top;               //栈顶指针，top等于NULL表示空栈
};

Lstack::Lstack(){
    top = NULL;              //top等于NULL表示栈为空
}

Lstack::~Lstack(){
    node *ptr = NULL;
    while(top != NULL){
        ptr = top->next;
        delete top;
        top = ptr;
    }
}

void Lstack::push(dataType a){
    node *ptr = new node;
    ptr->data = a;              //新栈顶存值
    ptr->next = top;            //新栈顶指向旧栈顶
    top = ptr;                  //top指向新栈顶
}

void Lstack::pop(){
    if (!isEmpty()){            //判空
    	node *ptr = top->next;  //预存下一节点的指针
    	delete top;             //释放栈顶空间
    	top = ptr;              //栈顶变化
    }
	else
		cout << "The stack is empty!" << endl;
}

dataType Lstack::f_top(){       //判空
	if(isEmpty()){
        cout << "The stack is empty!" << endl;
		return -1;
	}
    else
    	return top->data;       //返回栈顶元素
}

bool Lstack:: isEmpty(){
    return top == NULL;         //栈顶为NULL表示栈空
}

int main (){   // 测试代码
	Lstack s;
	for (int i=0; i<11; i++){
		s.push(i);
		cout << s.f_top() << endl;
	}
	for (int i=0; i<11; i++){
		s.pop();
		cout << s.f_top() << endl;
	}
	//system("Pause");
	return 0;
}

用数组或链表来实现一个队列⭐⭐⭐⭐

队列需要设置两个游标元素一前一后分别控制队头和队尾的位置。

数组实现队列：

#include<iostream>
using namespace std;

typedef int dataType;
class Queue{
private:
    dataType* arrays; // 成员数组
	int front;   // 队前
	int end;     // 队后
    int size_a;  // 数组大小
public:
    Queue();
    ~Queue();

    void push(dataType data);
    dataType pop();
    bool isEmpty();
    bool isFull();
};

Queue::Queue():size_a(10),front(0),end(0){ // 初始化
    arrays = new dataType[size_a];       // 申请10个内存大小的空间
}

Queue::~Queue(){
    delete[] arrays;
    arrays = nullptr;
}

void Queue::push(dataType data){
    if(isFull())
        cout << "The queue is full!" << endl;
    else{
        arrays[end] = data;
		end = (end+1) % size_a; // 循环队列，如果队前有空间，元素放队前
	}
}

dataType Queue::pop(){
    if(isEmpty()){
        cout << "The queue is empty!" << endl;
		return -1;
	}
    else{
		dataType t = arrays[front];
		front = (front+1) % size_a;
        return t;
	}
}

bool Queue::isEmpty(){
    return (front == end);
}

bool Queue::isFull(){
    return (front == ((end+1) % size_a));
}

int main (){ // 测试用例
	Queue q;
	for (int i=0; i<11; i++){
		q.push(i);
	}
	for (int i=0; i<11; i++){
		cout << q.pop() << endl;
	}
	return 0;
}

链表实现队列：

#include<iostream>
using namespace std;

typedef int dataType;
struct node{             //链栈节点
    dataType data;       //数值
    node *next;          //指针域
};

class Queue{
public:
    Queue();
    ~Queue();
	
    void push(dataType var); 
    dataType pop();           
    int size();       
    bool isEmpty();          
private:
    node* front;   // 队前
	node* end;     // 队后
    int size_a;    // 内存大小
};

Queue::Queue():size_a(0),end(NULL){ // 初始化
    front = new node;
	front->next = NULL;
}

Queue::~Queue(){
    node *ptr = NULL;
    while(front != NULL){
        ptr = front->next;
        delete front;
        front = ptr;
    }
}

void Queue::push(dataType a){ // end创建节点连接至front后面
	if (end == NULL){
		end = new node;
		end->data = a;
		end->next = NULL;
		front->next = end;
	}
	else{
		node* pTail = end; // 在end与front之间插入节点
		end = new node;
		end->data = a;
		pTail->next = end;
		end->next = NULL;
	}
	size_a++;                
}

dataType Queue::pop(){
    if (isEmpty()){
		cout << "The queue is empty!" << endl;
		return -1;
	}
	dataType data = front->next->data; // 删除front后一个节点
	node* pCurr = front->next;
	front->next = pCurr->next;
	delete pCurr;
	if (isEmpty()){
		end = NULL;
	}
	size_a--;
	return data;
}

int Queue::size(){
    return size_a;            //返回队列大小
}

bool Queue:: isEmpty(){
    return (size() == 0);
}

int main (){ // 测试用例
	Queue q;
	for (int i=0; i<11; i++){
		q.push(i);
	}
	for (int i=0; i<12; i++){
		cout << q.pop() << endl;
	}
	return 0;
}

说说二叉堆⭐⭐⭐⭐⭐

堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
1. 最大堆。最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。
2. 最小堆。最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值
说说哈希表⭐⭐⭐⭐⭐

哈希表是一个非常有用的数据结构。可以实现常数时间复杂度的查找。哈希表的做法是，将键值对放入数组中。因为数组可以通过下标实现常数时间复杂度的查找。这样相当于就找了键，也就找到了对应的值。键值对通过取模或位运算操作来获取哈希值，这个哈希值就对应数组的下标。数组一开始会申请一定数量的内存空间，当键值对多起来后，就需要两倍扩容。在获取哈希值的过程中，可能出现哈希冲突，解决办法有开发地址法、二次探测法、链地址法。

说说堆排序的时间复杂度，建堆的时间复杂度⭐⭐⭐⭐⭐

建堆过程的时间复杂度是O(n)，堆排序的时间复杂度是O(nlogn)
哈希表如何解决哈希冲突⭐⭐⭐⭐⭐
1. 开放地址法（线性探测法）：如果得到的哈希地址冲突(该位置上已存储数据)的话，我们就是将这个数据插到下一个位置，要是下个位置也已存储数据，就继续到下一个，直到找到正确的可以插入的数据。
2. 二次探测法：当遇到冲突后，下次所找到的位置为当前的位置加上n的二次方
3. 链地址法：如果得到的哈希地址冲突，只需要插入到对应的链表中即可。
哈希表的初始数组容量一般为多少，为什么？⭐⭐⭐⭐⭐

C++中哈希表的初始数组容量一般为质数，通常为2、3、5、7等小质数，以此为基数进行扩容。具体的初始容量可以根据实际应用需求和数据规模进行选择，通常建议选择一个适当的质数作为初始容量，然后根据负载因子的大小进行扩容。

假如我们写个代码来测试一下：
```
#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> map;
    std::cout << "Size of unordered_map with default initial bucket count: " << map.bucket_count() << std::endl;

    std::unordered_map<int, int> map2(100);
    std::cout << "Size of unordered_map with initial bucket count of 100: " << map2.bucket_count() << std::endl;

    return 0;
}
```
结果是：
```
Size of unordered_map with default initial bucket count: 1
Size of unordered_map with initial bucket count of 100: 103
```
从输出中我们可以看出，如果没有指定初始数组容量，哈希表的默认初始容量为 1。在第二个哈希表中，我们指定了初始容量为 100，但实际上容量是 103，这是因为哈希表实际上使用的是比指定值更大的质数来作为容量。

1还是太小了，所以我们在初始化哈希表时最好给一个合适的质数，建议给11。这是因为如果太小，扩容频繁；数值太大，浪费空间。
哈希表的负载因子为什么是0.75？⭐⭐⭐⭐⭐

哈希表的负载因子是指哈希表中已存储元素数量与哈希表数组容量的比值。通常情况下，哈希表的负载因子取值范围为 0.5 ~ 0.8，其中 0.75 是比较常见的一个值。

负载因子的取值与哈希表的性能有关。当负载因子太小时，哈希表的利用率不高，浪费空间；当负载因子太大时，哈希冲突的概率会增加，导致查询的效率下降。经过实践，当负载因子为 0.75 时，哈希表的空间利用率和查询效率都较为理想，因此被广泛采用。

当哈希表中已有元素数量达到哈希表容量的 75% 时，通常会触发哈希表扩容操作，将哈希表的容量扩大为原来的两倍，以保证哈希表的查询效率和空间利用率。
什么是平衡树？⭐⭐⭐

平衡树（Balanced Tree）是一种数据结构，也叫自平衡二叉搜索树（Self-Balancing Binary Search Tree）。它在二叉搜索树的基础上增加了自平衡的操作，保证在插入或删除节点时任意节点的子树的高度差都小于等于1。
说说红黑树⭐⭐⭐⭐⭐

图片来源：网络（侵删） 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：
1. 每个节点要么是红色，要么是黑色。
2. 根节点必须是黑色
3. 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
4. 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
5. 最长的路径长度不会超过任意路径的两倍。
在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。

##豆芽点评数据结构与算法太重要了，全是高频考点。

蒋豆芽的面试题专栏（29/数据结构与算法）

说说一个算法有哪些时间复杂度？归并算法时间复杂度是多少？⭐⭐⭐

说说数组时间复杂度，什么场景下使用？⭐⭐⭐⭐⭐

说说vector的实现原理⭐⭐⭐⭐⭐

实现一个vector⭐⭐⭐⭐⭐

分析一下push_back() 的时间复杂度⭐⭐⭐⭐⭐

总结一下数组与链表的区别⭐⭐⭐⭐⭐

栈和队列的区别⭐⭐⭐⭐⭐

来手写一个链表⭐⭐⭐⭐⭐

用数组或链表来实现一个栈⭐⭐⭐⭐

用数组或链表来实现一个队列⭐⭐⭐⭐

说说二叉堆⭐⭐⭐⭐⭐

说说哈希表⭐⭐⭐⭐⭐

说说堆排序的时间复杂度，建堆的时间复杂度⭐⭐⭐⭐⭐

哈希表如何解决哈希冲突⭐⭐⭐⭐⭐

哈希表的初始数组容量一般为多少，为什么？⭐⭐⭐⭐⭐

哈希表的负载因子为什么是0.75？⭐⭐⭐⭐⭐

说说红黑树⭐⭐⭐⭐⭐

说说一个算法有哪些时间复杂度？归并算法时间复杂度是多少？⭐⭐⭐

说说数组时间复杂度，什么场景下使用？⭐⭐⭐⭐⭐

说说vector的实现原理⭐⭐⭐⭐⭐

实现一个vector⭐⭐⭐⭐⭐

分析一下push_back() 的时间复杂度⭐⭐⭐⭐⭐

来手写一个链表⭐⭐⭐⭐⭐

总结一下数组与链表的区别⭐⭐⭐⭐⭐

栈和队列的区别⭐⭐⭐⭐⭐

用数组或链表来实现一个栈⭐⭐⭐⭐

用数组或链表来实现一个队列⭐⭐⭐⭐

说说二叉堆⭐⭐⭐⭐⭐

说说哈希表⭐⭐⭐⭐⭐

说说堆排序的时间复杂度，建堆的时间复杂度⭐⭐⭐⭐⭐

哈希表如何解决哈希冲突⭐⭐⭐⭐⭐

哈希表的初始数组容量一般为多少，为什么？⭐⭐⭐⭐⭐

哈希表的负载因子为什么是0.75？⭐⭐⭐⭐⭐

什么是平衡树？⭐⭐⭐

说说红黑树⭐⭐⭐⭐⭐