算法与数据结构面试题-1

常见面试题

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

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

   归并算法时间复杂度是O(nlogn)

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

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

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

   频繁访问的场景下，可以使用数组。

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

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

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

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

4. 实现一个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_

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

   采用均摊分析的方法，公式如下：

   

   公式里面，假定有 n 个元素，倍增因子为 m（我们设定为2），那么完成这 n 个元素往一个 vector 中的push_back操作，需要重新分配内存的次数大约为 log2(n)，第 i 次重新分配将会导致复制 2^i (也就是当前的vector.size() 大小)个旧空间中元素，因此 n 次 push_back 操作所花费的总时间：

   

   然后 n 次push_back操作，每次分摊O(1)，即为常数时间复杂度了。

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

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

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

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