蒋豆芽的面试题专栏（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; } -
总结一下数组与链表的区别⭐⭐⭐⭐⭐
- 数组内存连续、有序；链表内存可以不连续
- 数组可以直接访问下标，访问时间复杂度O(1)；链表需要通过下一级指针层层递进访问，访问时间复杂度O(n)
- 数组插入或删除元素时需要移动后面的元素，时间复杂度O(n)；而链表插入或删除元素时，时间复杂度O(1)
- 频繁访问元素的场景用数组；频繁插入或删除的场景用链表
-
栈和队列的区别⭐⭐⭐⭐⭐
主要区别就是规定不同。
栈规定：元素先入后出（First In Last Out， 简称FILO）。
队列规定：元素先入先出（First In First Out， 简称FIFO）。
-
用数组或链表来实现一个栈⭐⭐⭐⭐
实现的原理都是类似的，用来控制元素
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
- 本专栏适合于C/C++已经入门的学生或人士，有一定的编程基础。 - 本专栏特点： 本专刊囊括了C语言、C++、操作系统、计算机网络、嵌入式、算法与数据结构、数据库等一系列知识点，总结出了高频面试考点（附有答案）共计309道，事半功倍，为大家春秋招助力。 - 本专栏内容分为七章：共计309道高频面试题（附有答案）
查看13道真题和解析
⑨✌们拿它练练面试愣是给他整出幻觉了