蒋豆芽

2021-04-01 19:27 已编辑五邑大学 C++

关注

算法与数据结构-1

C++软件与嵌入式软件面经解析大全（蒋豆芽的秋招打怪之旅）

本章讲解知识点

1.1 算法的时间复杂度和空间复杂度
1.2 数组
1.3 链表
1.4 递归
1.5 栈与队列
1.6 树与二叉树
1.7 二叉堆与最小堆
1.8 哈希表
1.9 红黑树
1.10 Trie（前缀树）
1.11 排序算法
1.12 查找算法
1.13 算法思想——DFS和BFS
1.14 算法思想——回溯
1.15 算法思想——分治法
1.16 算法思想——贪心法
1.17 算法思想——动态规划

受众：本教程适合于C/C++已经入门的学生或人士，有一定的编程基础。

本教程适合于互联网、嵌入式软件求职的学生或人士。

故事背景

蒋豆芽：小名豆芽，芳龄十八，蜀中人氏。卑微小硕一枚，科研领域苟延残喘，研究的是如何炒好一盘豆芽。与大多数人一样，学习道路永无止境，间歇性踌躇满志，持续性混吃等死。会点编程，对了，是面对对象的那种。不知不觉研二到找工作的时候了，同时还在忙论文，豆芽都秃了，不过豆芽也没头发啊。

隔壁老李：大名老李，蒋豆芽的好朋友，技术高手，代码女神。给了蒋豆芽不少的人生指导意见。

导师：蒋豆芽的老板，研究的课题是每天对豆芽嘘寒问暖。

故事引入

豆芽正在紧张的面试中。。。。。。

面试官：哟，又是你啊，豆芽，老熟人了。

蒋豆芽：（不好意思）嘿嘿，那就不用自我介绍了吧。

面试官：行，这轮面试我们主要考手撕代码。

蒋豆芽：（自信满满）这我可不怕，我之前一直就在准备。

面试官：（笑容邪魅）好，豆芽，我们考得很简单的。第一道请你手撕反转链表。

蒋豆芽：五分钟立成。

面试官：不错啊豆芽！第二道请你手撕二叉树前序遍历。

蒋豆芽：这个我知道，看我五分钟解决！

面试官：豆芽，我再问你最后一个问题，你来说说，链表的插入时间复杂度是多少？

蒋豆芽：嗯，O(1) 的复杂度！

面试官：豆芽，你还有什么想问的吗？

蒋豆芽：阿巴阿巴阿巴阿巴阿巴

面试官：豆芽，后面有通知我们会再联系你的。

蒋豆芽：老李啊，经过我前期的认真准备，手撕代码对我来说已经不难了啊。

隔壁老李：（会心一笑）优秀啊，豆芽！

蒋豆芽：（笑容邪魅）老李，你还有什么要教我的吗？

隔壁老李：豆芽，在一开始，我推荐你的数据结构与算法入门书籍，你看了吗？

蒋豆芽：那当然了，经过快速入门后，刷起编程题来简直事半功倍！

隔壁老李：那就太好了，这样我们就轻松了。豆芽，数据结构与算法也有很多考点，既然你已经有了基础，我们就采用启发式的方法来总结常考面试题。

1.1 时间复杂度与空间复杂度

隔壁老李：豆芽，你知道算法是什么吗？

蒋豆芽：算法就是解决问题的方法！

隔壁老李：你说的对，你来说说算法有哪些特点？

蒋豆芽：算法特点如下：

有限性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止，并且每个步骤在可接受时间内完成；
确切性（Definiteness）：算法的每一步骤必须有确切的定义，无歧义
输入项（Input）：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性（Effectiveness）：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步都可以在有限步骤内完成（也称之为有效性）。

隔壁老李：豆芽我问你，那我们应该如何计算算法时间复杂度呢？

蒋豆芽：计算算法时间复杂度时，我们不要纠结于算乘除法、加减法有多少次，因为这并不容易。

比如下面代码，laugh计算了多少次？

for (i=1; i<=n; i*=2)
    for (j=1; j<=i; j++)
        laugh++;

要数清楚laugh的计算次数并不容易。

同时对于5n+3和5n+4+3*3，现在的计算机很快了，少一个加法或多一个乘法没有什么区别

因此，不要纠结多少次乘除法、多少次加减法。

计算时间复杂度，我们更看重的是数量级的区别。

比如5n+3和5n*n

一个是n，一个是n*n，当我们的输入数据n=1000时，那差距可就大了。

我们给出定义：若存在函数f(n)，使得当n趋近于无穷大时， T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))， O为算法的渐进时间复杂度，简称为时间复杂度。

因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

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

我们给出更多的算法时间复杂度：

隔壁老李：不错啊，豆芽。那算法空间复杂度呢？

蒋豆芽：算法空间复杂度很好理解，就是一个算法在实施过程中，借助了额外的内存空间，那么这个算法就存在一定的空间复杂度，我们举个例子。

void mergeSort(vector<int>& nums, vector<int>& temp, int l, int r){
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(nums, temp, l, mid);
    mergeSort(nums, temp, mid+1, r);
    int i=l,j=mid+1; int t = 0;
    while (i<=mid && j<=r){
        if (nums[i] <= nums[j]) temp[t++] = nums[i++];
        else temp[t++] = nums[j++];
    }
    while (i <= mid) temp[t++] = nums[i++];
    while (j <= r) temp[t++] = nums[j++];

    for (int i=l,t=0; i<=r; i++)
        nums[i] = temp[t++];
}
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)

比如这个归并排序的算法，目标排序数组是nums，而整个算法的过程又借助了中间数组temp，所以归并排序的空间复杂度为O(n)。

1.2 数组

隔壁老李：豆芽，你来总结一下数据结构——数组。

蒋豆芽：数组在C/C++中，不仅是一种数据类型，同时也是一种数据结构。

数组的特点是：

整齐：存储的是相同数据类型的元素
有序：所有元素在内存中是紧挨着的、连续的。
高效：正因为数组是有序的，可以直接通过下标访问元素，十分高效。

我们定义一个数组int a[8] = {3, 1, 2, 5, 4, 9, 7, 6}; 如下图所示

所有元素在内存中是紧挨着的、连续的。数组a[8]内存分布如下图，sizeof(a) / sizeof(int) = 8

隔壁老李：那豆芽你说说，插入元素和删除元素的时间复杂度是多少？

蒋豆芽：因为所有元素在内存中是紧挨着的、连续的。如果我们要插入元素，就必须把插入位置后面的元素，往后移动一个位置；如果是删除一个元素，就必须把删除位置后面的元素，往前移动一个位置。

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

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

隔壁老李：哎哟，豆芽不错嘛。

隔壁老李：那行，我们来讲一道面试常考手撕题——反转字符串。

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

题目来源：LeetCode

蒋豆芽：不用讲了，老李，这个我会！本来我们这里可以使用一个额外数组来帮忙，但是题目不允许。那么我们就只能原地操作。这里要给你介绍一个技巧——双指针。只要是数组，就要想到这个技巧。我们直接给出代码说明双指针。

void reverseString(char* s, int sSize){
    for (int i = 0, j = sSize - 1; i < j; ++i, --j) {
        /* 不断 swap(s[i], s[j]) */
        char c = s[i];
        s[i] = s[j];
        s[j] = c;
    }    
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)

这里我们就定义了一个左指针 i 和一个右指针 j ，分别指向数组两端，那么我们就交换两者，然后两个指针往数组中间走。不就实现反转了吗？

隔壁老李：行，那我没什么好讲的了。豆芽，之前跟你说过，练题上LeetCode，一定要练啊，那上面技巧可多了。

隔壁老李：豆芽，我问你，如果现在我有一个数组 a[10]，那我想往数组后面插入一个数怎么办？

蒋豆芽：那没办法了呀，我只能再申请一个新数组 b[11]，然后将 a 的内容复制过来，再释放掉 a。

隔壁老李：那我频繁往数组后面插入元素不就很低效了吗？

蒋豆芽：这个我确实不知道了。那怎么办？

隔壁老李：（笑容邪魅）你终于不知道了？哈哈。这里我们就要讲讲vector，C++为了提升数组效率，于是封装了数组，推出了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_

蒋豆芽：vector的做法确实聪明了不少啊。那到底 push_back() 的时间复杂度是多少呢？

隔壁老李：这个在《STL源码剖析》侯捷译里面讲得很清楚，采用均摊分析的方法，公式如下：

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

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

蒋豆芽：设计容器的前辈们真是太厉害了！

隔壁老李：多多阅读STL源码，会大有好处的。

1.3 链表

隔壁老李：好了，豆芽你再来总结一下链表吧。

蒋豆芽：链表（ linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（ node）所组成。

单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。

struct ListNode {
    int data;
    ListNode *next;
};

链表形式如下：

链表的特点是：

整齐：存储的是相同数据类型的元素
无序：所有元素在内存中是随机的、不连续的。

图中的箭头代表链表节点的next指针。

隔壁老李：那豆芽你说说，插入元素和删除元素的时间复杂度是多少？

蒋豆芽：因为所有元素在内存中是随机的、不连续的。如果我们要插入元素，只需要在相应位置插入就可以了；如果是删除一个元素，只需要在相应位置删除就可以了。

所以从渐进趋势来看，插入和删除操作的时间复杂度是O(1)。而链表是无序的，不可以直接通过下标访问元素，需要通过next指针逐次访问下一个元素才能找到目标元素，访问时间复杂度是O(n)。

如果某些场景需要频繁插入和删除元素时，这时候宜选用链表作为数据结构。但是如果需要高效访问元素时，不宜采用链表。

隔壁老李：不错不错！

蒋豆芽：因为链表实在是很重要，我们必须学会手写一个链表，所以这里我们要讲讲。

链表的创建和遍历

初始化链表首先要做的就是创建链表的头结点或者首元结点。创建的同时，要保证有一个指针永远指向的是链表的表头，这样做不至于丢失链表。

例如创建一个链表（1，2，3，4）:

ListNode * initLink(){
    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;
}

向链表中插入结点

链表中插入头结点，根据插入位置的不同，分为3种：

插入到链表的首部，也就是头结点和首元结点中间；
插入到链表中间的某个位置；
插入到链表最末端；

虽然插入位置有区别，都使用相同的插入手法。分为两步，如图所示：

将新结点的next指针指向插入位置后的结点；
将插入位置前的结点的next指针指向插入结点；

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) //

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

校招面试考点全解析——C++软件与嵌入式篇(蒋豆芽的秋招打怪之旅) 文章被收录于专栏

- 本专刊适合于C/C++已经入门的学生或人士，有一定的编程基础。 - 本专刊适合于互联网C++软件开发、嵌入式软件求职的学生或人士。 - 本专刊囊括了C语言、C++、操作系统、计算机网络、嵌入式、算法与数据结构等一系列知识点的讲解，并且最后总结出了高频面试考点（附有答案）共近400道，知识点讲解全面。不仅如此，教程还讲解了简历制作、笔试面试准备、面试技巧等内容。