• 从C语言到C++_39(C++笔试面试题)next_permutation刷力扣


    目录

    笔试题1

    答案及解析1

    笔试题2

    答案及解析2

    力扣编程题

    88. 合并两个有序数组

    解析代码

    349. 两个数组的交集

    解析代码

    60. 排列序列

    解析代码

    46. 全排列

    解析代码

    本篇完。


    这篇就持续更新一些C++的选择题和编程题了。(想对答案可以打开两个网页)

    笔试题1

    1. 以下哪种STL容器中的对象是连续存储的:()

    A.list

    B.vector

    C.map

    D.set

    2. STL中的一级容器有:()

    A.vector、deque、list、set、multiset、map、multimap

    B.序列式容器、关联式容器、容器适配器

    C.set、multiset、map、multimap

    D.vector、deque、list

    3. 以下STL的容器存放的数据,哪个肯定是排好序的()

    A.vector

    B.deque

    C.list

    D.map

    4. 当很频繁地对序列中部进行插入和删除操作时,应该选择使用的容器是()

    A.vector

    B.list

    C.deque

    D.stack

    5. 下面有关vector和list的区别,描述错误的是? ()

    A.vector拥有一段连续的内存空间,支持随机存取,如果需要高效的随机存取,应该使用vector

    B.list拥有一段不连续的内存空间,如果需要大量的插入和删除,应该使用list

    C.vector::iterator支持“+”、“+=”、“<”等操作符

    D.list::iterator则不支持“+”、“+=”、“<”等操作符运算,但是支持了[ ]运算符

    6. 关于vector<>初始化问题下面那个是非法的? ()

    A.vector sVec;

    B.vector> ivvec;

    C.vector> svvec( "hello");

    7. T是一个数据类型,关于std::vector::at 和 std::vector::operator[] 描述正确的是: ()

    A.at总是做边界检查, operator[] 不做边界检查

    B.at不做边界检查, operator[] 做边界检查

    C.at和operator[] 是一样的

    D.at下标越界抛异常,operator[]下标越界触发断言

    8. STL中的unordered_map和priority_queue使用的底层数据结构分别是什么?()

    A.rbtree,queue

    B.hashtable,heap

    C.rbtree,heap

    D.hashtable,queue

    9. map和unordered_map的区别说法错误的是()

    A.map的底层是红黑树,unordered_map的底层结构是哈希表

    B.map是有序的,unordered_map不是,且map的查询效率更高

    C.map和unordered_map底层存储的都是键值对

    D.map和unordered_map的应用场景不同

    10. 下面关于deque说法正确的是()

    A.deque没有vector尾插效率高

    B.deque的底层是一段连续空间

    C.如果要对集合中的元素进行排序时,元素不适合放在deque中

    D.deque是priority_queue的底层默认容器


    答案及解析1

    1. B

      A:错误,list的底层结构为带头结点的双向循环链表,是链式结构

      B:正确,vector是动态类型顺序表,底层是一段连续空间

      C:错误,map底层是红黑树,树形结构

      D:错误,set底层是红黑树,树形结构

    2. D

      一级容器即序列式容器(存的不是)

      A:错误,set、multiset、map、multimap是关联式容器,不是序列式容器

      B:错误,非题目所问

      C:错误,都是关联式容器

      D:正确

    3. D

    map的底层是红黑树,红黑树是二叉搜索树,二叉搜索树中的元素如果按照中序遍历,可以得到一个有序序列

    4. B

    频繁的向序列中插入和删除元素时,应该选择链式结构

    list底层结构为:带头结点的双向循环链表

    5. C

      A:正确:构造了一个空的vector,里面放置的是string类型的对象

      B:正确:构造了一个空的动态二维数组

      C:错误,svvec是二维的,vector套vector,不能直接使用"hello"构造

    6. C

      A:正确:构造了一个空的vector,里面放置的是string类型的对象

      B:正确:构造了一个空的动态二维数组

      C:错误,svvec是二维的,vector套vector,不能直接使用"hello"构造

    7. D

      at和operator[]都是通过下标获取对应的元素,两个的不同是:

      at在下标越界时,抛异常

      operator[]在下标越界时,触发断言

    8. B

    unordered_map底层使用的是哈希表,priority_queue底层使用的是堆

    9. B

      A:正确

      B:错误,map底层是红黑树,查询效率为O(logN),unordered_map底层是哈希表,查询效率为 O(1), unordered_map查询的效率更高

      C:正确

      D:正确,map适合要求结果有序的常见,unordered_map适合是否有序无关,更关注查询效率的场景

    10. C

      A:错误,如果在不扩容的情况下deque和vector相同,需要扩容时就不同了,vector扩容需要搬移 大量的元素,deque不需要

      B:错误,deque是分段连续的,类似动态的二维数组

      C:正确,因为要排序就需要遍历,而deque不适合编译,因为其在遍历时,要不断的去检测迭代 器是否在空间边界

      D:错误,priority_queue底层的默认容器是vector


    笔试题2

    1. 下面关于适配器说法正确的是()

    A.在STL中,stack和queue与vector一样,都是容器

    B.STL中只有容器适配器

    C.适配器有自己独立的底层数据结构,不需要借助其他结构

    D.适配器是一种设计模式,该种模式是将一个接口包装成客户希望的另一个接口

    2. 下面哪一个不是适配器()

    A.stack

    B.queue

    C.反向迭代器

    D.以上都是

    3. 关于仿函数说法正确的是()

    A.仿函数就是一个函数

    B.仿函数可以是静态成员函数

    C.仿函数是函数对象,可以像函数调用方式使用的对象

    D.仿函数与函数指针作用不同

    4. 关于仿函数说法错误的是()

    A.仿函数可以使算法功能更加灵活

    B.如果想要让一个类的对象按照函数方式使用,只需在其中将()重载即可

    C.lambda表达式底层实际就是按照仿函数实现的

    D.仿函数与函数指针都可以增加算法的灵活性

    5. 填写下面空格

    1. merge()算法的功能是:_______________________________________________

    2. reverse()算法的功能是:_____________________________________________

    3. unique()算法的功能是:______________________________________________

    4. next_permutation()算法的功能是:____________________________________

    5. sort()算法的功能是:_______________________________________________


    答案及解析2

    1. D

      A:错误,在STL中stack和queue被认为是容器适配器,因为它们的底层结构是直接将deque封装 了一下

      B:错误,除了容器适配器,还有迭代器适配器,函数适配器

      C:错误,适配器没有自己独立的底层数据结构,是将其他结构拿过来重新包装的

      D:正确,迭代器模式概念

    2. D

      A:正确,stack是对deque的重新封装

      B:正确,queue是对deque的重新封装

      C:正确,反向迭代器失对正向迭代器的封装

      D:错误

    3. C

      A:错误,仿函数是一个类中重载了(),该类的对象可以像函数一样使用的对象

      B:错误,仿函数是依靠对象调用的,没有对象无法使用,因为不能是静态成员函数

      C:正确

      D:错误,作用基本是类似的,都是增加算法的灵活性,只不过C++中使用仿函数更多

    4. B

    A:正确,STL中的算法都是通用的,有些算法具体的做的事情需要用户通过仿函数方式定制

    B:错误,是重载()而不是(],注意看题

    C:正确,lambda表达式编译器在编译时会在底层将其转化为仿函数

    D:正确

    1. merge(first1, last1,first2,last2, resutl)算法的功能是:将两个有序序列合并成一个序列保存到result中,合并好之后依然有序
    2. reverse(first, last)算法的功能是:对[first, last)区间中的元素逆序
    3. unique(first, last)算法的功能是:对[first, last)区间中的元素去重
    4. next_permutation(first,last)算法的功能是:获取当前序列的下一个排列组合
    5. sort(first,last)算法的功能是:对[first, last)区间中的元素排序,重载版本可以指定排升序还是降序

    力扣编程题

    88. 合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

    请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

    注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

    示例 1:

    输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
    输出:[1,2,2,3,5,6]
    解释:需要合并 [1,2,3] 和 [2,5,6] 。
    合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
    

    示例 2:

    输入:nums1 = [1], m = 1, nums2 = [], n = 0
    输出:[1]
    解释:需要合并 [1] 和 [] 。
    合并结果是 [1] 。
    

    示例 3:

    输入:nums1 = [0], m = 0, nums2 = [1], n = 1
    输出:[1]
    解释:需要合并的数组是 [] 和 [1] 。
    合并结果是 [1] 。
    注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
    

    提示:

    • nums1.length == m + n
    • nums2.length == n
    • 0 <= m, n <= 200
    • 1 <= m + n <= 200
    • -109 <= nums1[i], nums2[j] <= 109

    解析代码

    C语言写过了,双指针

    1. class Solution {
    2. public:
    3. void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    4. int end = m + n - 1; // 双指针
    5. if(m == 0)
    6. {
    7. nums1[0] = nums2[0];
    8. }
    9. while(n > 0 && m > 0)
    10. {
    11. if(nums1[m-1] >= nums2[n-1]) // 小的放后面
    12. {
    13. nums1[end--] = nums1[m-1];
    14. m--;
    15. }
    16. else
    17. {
    18. nums1[end--] = nums2[n-1];
    19. n--;
    20. }
    21. }
    22. while(n > 0) // 第二个数组还有就拷贝过去
    23. {
    24. nums1[end--] = nums2[n-1];
    25. n--;
    26. }
    27. }
    28. };

    349. 两个数组的交集

    给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

    示例 1:

    输入:nums1 = [1,2,2,1], nums2 = [2,2]
    输出:[2]
    

    示例 2:

    输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出:[9,4]
    解释:[4,9] 也是可通过的
    

    提示:

    • 1 <= nums1.length, nums2.length <= 1000
    • 0 <= nums1[i], nums2[i] <= 1000

    解析代码

    1. class Solution {
    2. public:
    3. vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4. unordered_set s1(nums1.begin(),nums1.end()); // 去重
    5. unordered_set s2(nums2.begin(),nums2.end());
    6. vector<int> retV;
    7. if(s1.size() <= s2.size())
    8. {
    9. for(const auto& e : s1)
    10. {
    11. if(s2.find(e) != s2.end())
    12. {
    13. retV.push_back(e);
    14. }
    15. }
    16. }
    17. else
    18. {
    19. for(const auto& e : s2)
    20. {
    21. if(s1.find(e) != s1.end())
    22. {
    23. retV.push_back(e);
    24. }
    25. }
    26. }
    27. return retV;
    28. }
    29. };

    60. 排列序列

    给出集合 [1,2,3,...,n],其所有元素共有 n! 种排列。

    按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

    1. "123"
    2. "132"
    3. "213"
    4. "231"
    5. "312"
    6. "321"

    给定 n 和 k,返回第 k 个排列。

    示例 1:

    输入:n = 3, k = 3
    输出:"213"
    

    示例 2:

    输入:n = 4, k = 9
    输出:"2314"
    

    示例 3:

    输入:n = 3, k = 1
    输出:"123"
    
    

    提示:

    • 1 <= n <= 9
    • 1 <= k <= n!

    解析代码

    这题是困难题,和下面一题一样应该不提倡用next_permutation的,但没学高阶算法就先这样用了

            next_permutation函数在头文件中,作用是是生成给定序列的下一个较大排序,直到序列按降序排列为止。到这里还需要强调的一点是,如果你希望生成所有的排列方式,一定要先将序列按升序排列,这里可以与sort函数结合起来使用,先用sort升序排列,再调用next_permutation函数。

    1. class Solution {
    2. public:
    3. string getPermutation(int n, int k) {
    4. string str = string("123456789").substr(0,n);
    5. while(--k)
    6. {
    7. next_permutation(str.begin(), str.end());
    8. }
    9. return str;
    10. }
    11. };

    46. 全排列

    给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

    示例 1:

    输入:nums = [1,2,3]
    输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    

    示例 2:

    输入:nums = [0,1]
    输出:[[0,1],[1,0]]
    

    示例 3:

    输入:nums = [1]
    输出:[[1]]
    
    

    提示:

    • 1 <= nums.length <= 6
    • -10 <= nums[i] <= 10
    • nums 中的所有整数 互不相同

    解析代码

    提倡不用next_permutation的,但没学高阶算法就先这样用了,先用sort升序排列

    1. class Solution {
    2. public:
    3. vectorint>> permute(vector<int>& nums) {
    4. vectorint>> vv;
    5. sort(nums.begin(), nums.end());
    6. do
    7. {
    8. vv.push_back(nums);
    9. }while(next_permutation(nums.begin(), nums.end()));
    10. return vv;
    11. }
    12. };

    本篇完。

            C++到这基本介绍了,有时间可以回去复习复习,还有一两篇关于多线程的问题放到Linux操作系统之后再放出来了,到这C++也够用了。

    下一篇:零基础Linux_1(前期准备)Linux发展史和环境安装。

    下下篇:零基础Linux_2(基本指令_上)目录/文件的显示跳转创建删除。

  • 相关阅读:
    C++基础
    敏捷开发的优势
    【华为OD机试真题 python】竖直四子棋【2022 Q4 | 200分】
    基于JavaSwing开发贪吃蛇小游戏(简化版) 课程设计 大作业 毕业设计
    win10 下载
    Centos7安装宝塔面板8.0.3并实现公网远程登录宝塔面板【内网穿透】
    C++ STL: list使用及源码剖析
    SpringBoot博客论坛管理系统
    人家不卡学历,是自己真的没能力
    JavaScript的函数的形参与实参是怎么回事
  • 原文地址:https://blog.csdn.net/GRrtx/article/details/132730195