文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

CPP 做算法题时常用的容器技巧

2024-12-03 00:31

关注

整理了一下 CPP 做算法题时常用的容器技巧。遇到一门新语言时,我首先都会思考如何实现下属功能。关于算法的笔记放在 GitHub[1] 上。

定长数组

变长数组

哈希表

优先队列

排序

定长数组

要求:

数组

  1. int dx[4] = {0, 1, 0, -1}; 
  2. int a[N]; 
  3.  
  4. dx[0]; 

变长数组

要求:

vector

  1. vector<int> ans(n);  // 初始长度 n ,默认值为 0 
  2.  
  3. // 取值:取头取尾取索引 
  4. ans.front(); 
  5. ans.back(); 
  6. ans[i] += 1; 
  7.  
  8. // 追加 
  9. // 为什么 std::vector 不支持 push_front? - Milo Yip的回答 - 知乎 
  10. // https://www.zhihu.com/question/51555037/answer/126373709 
  11. ans.push_back(5);  // O(1) 
  12.  
  13. // 去尾 
  14. ans.pop_back(); 

哈希表

要求:

  1. map<intint> S; 
  2. // 键值已存在 
  3. if (S.count(5)) 
  4.     // S[5] 被定义过 
  5. else 
  6.     // S[5] 未被定义过 

有序字典

优先队列

要求:

  1. // 默认是大根堆 
  2. priority_queue<int> heap; 
  3.  
  4. // 改为小根堆 
  5. priority_queue<int, vetor<int>, greater<int> > min_heap; 
  6.  
  7. // 空尺看存弹 
  8. heap.empty(); 
  9. heap.size(); 
  10. heap.top(); 
  11. heap.push(5); 
  12. heap.pop(); 

优先队列重载

  1. // 重载比较函数 
  2. struct cmp { 
  3.     template 
  4.     bool operator()(T const& left, U const &right) { 
  5.         if (left.second < right.secondreturn true
  6.         return false
  7.     } 
  8. }; 
  9.  
  10. int main() { 
  11.     unordered_map<intint> mp; 
  12.     mp[3] = 4; 
  13.     mp[2] = 44; 
  14.     mp[12] = 432; 
  15.     // 重载存储对象 pair<intint
  16.     priority_queueintint>, vectorintint>>, cmp>  pq(mp.begin(), mp.end());  //完成pq的初始化 
  17.  
  18. // 版权声明:本文为CSDN博主「leagalhigh」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 
  19. // 原文链接:https://blog.csdn.net/u014257954/article/details/78623215 

排序

要求:

  1. vector<int> ans; 
  2. sort(ans.begin(), ans.end());  // 默认从小到大 
  3.  
  4. vectorintint>> res; 
  5. sort(res.begin(), res.begin());  // 默认比较第一个元素 

排序返回索引

  1. vector<int> data = {5, 16, 4, 7};    
  2. vector<intindex(data.size(), 0); 
  3. for (int i = 0 ; i != index.size() ; i++) { 
  4.     index[i] = i; 
  5. sort(index.begin(), index.end(), 
  6.     [&](const int& a, const int& b) { 
  7.         return (data[a] < data[b]); 
  8.     } 
  9. ); 
  10. for (int i = 0 ; i != index.size() ; i++) { 
  11.     cout << index[i] << endl; 
  12. // 版权声明:本文为CSDN博主「liangbaqiang」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 
  13. // 原文链接:https://blog.csdn.net/qq_36523492/article/details/114122256 

参考资料

[1]算法的笔记: https://github.com/PiperLiu/ACMOI_Journey

 

来源:Piper蛋窝 内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯