C++ STL和几道经典的面试题

2024-05-04 04:18
文章标签 c++ 面试题 经典 stl 几道

本文主要是介绍C++ STL和几道经典的面试题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

https://blog.csdn.net/dingyahui123/article/details/78644235

 

C++ STL 的实现:

1.vector:  底层数据结构为数组 ,支持快速随机访问。

2.list:    底层数据结构为双向链表,支持快速增删。

3.deque:  底层数据结构为一个中央控制器和多个缓冲区,详细见STL源码剖析P146,支持首尾(中间不能)快速增删,也支持随机访问。

4.stack :  底层一般用23实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时

5.queue:   底层一般用23实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时(stack和queue其实是适配器,而不叫容器,因为是对容器的再封装)

6.priority_queue: 的底层数据结构一般为vector为底层容器,堆heap为处理规则来管理底层容器实现

7.set:  底层数据结构为红黑树,有序,不重复。

8.multiset: 底层数据结构为红黑树,有序,可重复。

9.map:      底层数据结构为红黑树,有序,不重复。

10.multimap: 底层数据结构为红黑树,有序,可重复。

11.hash_set: 底层数据结构为hash表,无序,不重复。

12.hash_multiset: 底层数据结构为hash表,无序,可重复 。

13.hash_map :     底层数据结构为hash表,无序,不重复。

14.hash_multimap: 底层数据结构为hash表,无序,可重复。

1)不用算术运算符进行求和不使用算术运算求和那么只能考虑直接在二进制位上进行位运算,事实上利用异或运算(^)和与运算(&)就能完成加法运算要做的事情,其中异或运算完成相加但是不进位,而与运算计算出哪些地方需要进位,在通过左移运算(<<)就可以完成进位操作了。

    #include"iostream.h"
     
    int sum(int a,int b){
    if(b == 0) return a;  
            int c = a ^ b;  
            int d = (a & b) << 1;  
            return sum(c, d);}
    int main(){
     cout<<sum(12,13);
    return 0;  
    }


2)利用位运算中异或运算的特点,两个相同的数异或的结果一定是0,那么将a和b中的所有元素做一次异或运算,最终的结果就是b比a多出的那个元素的值

    #include"iostream.h"
    int find(int a[],int b[],int n){
        int c = 0;  
            for(int i = 0; i <n; i++) {  
                c ^= a[i] ^ b[i];  
            }  
            c ^= b[n];  
       return c;
    }
    int main(){
    int a[6]={1, 3, 2, -4, 10, 18};  
    int b[]= {3, 55, 1, 2, 10, -4, 18};
     cout<<find(a,b,6);
    return 0;
    }


3)题目:有一个已经排好序的数组,其中存在重复元素,请将重复元素删除掉,例如,A = [1, 1, 2, 2, 3],处理之后的数组应当为A = [1, 2, 3]。

    public: int remove(int &A[],int n){
        if(n==0)
        return 0;
        int index=0;
        for(int i=1;i<n;i++)
        {
            if(A[index]!=A[i])
            A[++index]=A[i];
        }
        index++;
        return index;
    }

在O(n)的时间复杂度内完成数组移动,如abcde,左移三位变为cdeab,如果数组长度为l,移动位数为n,如果n大于l的话相当于移动n%l位,如果用一般的循环移位时间复杂度为O(n×l),不能在规定的要求内完成,所以只能考虑在数组本身上下功夫,如abcde,移动3位,可以理解为剩下的前两位翻转,后3位翻转然后整个数组翻转,abcde->bacde->baedc->cdeab,这样就可以在O(n)等级的时间复杂度内完成操作。大致功能函数如下

    int reverse(int i,int j,int *array)
    {  
        for(;i>m;i++,m--)
            {
            temp = array[i];  
            array[i] = array[j];   
            array[j] = temp;
           }
    }
    int main()
    {
        int n;//移动的位数
        reserve(0,n-1,A);
        reserve(n,L-n-1,A);
        reserve(0,n-1,A);
    }  


4)F(M,N)求解不大于N的和是M的所有组合个数。使用递归求解组合个数。

    #include "iostream"
    using namespace std;
    int f(int m,int n)
    {
         if(m==1)
              return 1;
         if(n==1)
         {
              return 1;
         }
         if(m<n)
        {
           return f(m,m);
        }
       if (m==n)
       {
          return 1+f(m,n-1);
       }
       return f(m,n-1)+f(m-n,f(m-n,n));
    }
    int main()
    {
        cout<<f(3,3);
    }


5)打靶算法:靶环有10个环,那么当打中时分数可为1-10,如果未打中得分为0,也就是11种可能,比如现在求6枪50分的概率

    #include <iostream>  
    #include <time.h>     
    using namespace std;   
    int sum;  
    int all=0;
    int n;
    int store[10];   
    void Output()   
    {   
        for(int i = 9; i>=0; --i)   
        {   
           cout<<store[i]<<" ";
        }  
       cout<<endl;   
        ++sum;   
    }   
    void Cumput(int score, int num)   
    {   
       if(score < 0 || score > (num+1)*10 ) //次数为0~9  
          return;  
       if(num == 0)    
         {     
            store[num] = score;   
            Output();    
            for(int i = 9; i>=10-num; --i)   
        {   
           all+=store[i];
        }  
           if(all==score){
               n++;
               all=0;
           }
            return;   
         }   
       for(int i = 0; i <= 10; ++i)  
         {  
            store[num] = i;  
            Cumput(score - i, num - 1);  
            
         }  
    }  
    int main()  
     {       
    const  double  begin=(double)clock();      
    Cumput(50, 6);  
        const  double  end=(double)clock();    
        cout<<"总的可能数量:"<<sum<<" ."<<"得分可能数量:"<<n<<endl;  
        cout<<"用时:"<<end-begin<<endl;   
        cout<<"概率"<<double(n)/sum;
        return 0;  
      }
    ......................
    ......................
    0 0 0 10 10 10 10 8 2 0
    0 0 0 10 10 10 10 9 0 1
    0 0 0 10 10 10 10 9 1 0
    0 0 0 10 10 10 10 10 0 0
    总的可能数量:195195 .得分可能数量:3003
    用时:339931
    概率0.0153846

如果不用递归的思想,使用循环的方式的话,要打几枪需要写几层循环,虽然思路简单,如果是打是几十或上百那要写死了。
---------------------  
作者:刀客123  
来源:CSDN  
原文:https://blog.csdn.net/dingyahui123/article/details/78644235  
版权声明:本文为博主原创文章,转载请附上博文链接!

这篇关于C++ STL和几道经典的面试题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/958324

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

荣耀嵌入式面试题及参考答案

在项目中是否有使用过实时操作系统? 在我参与的项目中,有使用过实时操作系统。实时操作系统(RTOS)在对时间要求严格的应用场景中具有重要作用。我曾参与的一个工业自动化控制项目就采用了实时操作系统。在这个项目中,需要对多个传感器的数据进行实时采集和处理,并根据采集到的数据及时控制执行机构的动作。实时操作系统能够提供确定性的响应时间,确保关键任务在规定的时间内完成。 使用实时操作系统的

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量,在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员,因为执行构造函数时,类对象已经创建完成,只有类对象创建完成才能调用成员函数,构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化,该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面,主要用于给