1-3算法基礎-標準模板庫STL

1.pair
pair用于存儲兩個不同類型的值(元素)作為一個單元。它通常用于將兩個值捆綁在一起,以便一起傳遞或返回。

#include <iostream>
#include <utility>
using namespace std;
int main() {pair<int, string> person = make_pair(25, "jack");//存儲一對值并初始化
//可簡寫為  pair<int, string> person(25, "jack");cout << person.first << " " << person.second;//25 jack
}

嵌套

#include <iostream>
#include <utility>
using namespace std;
int main() {pair<int, pair<int, int>> people=make_pair(3, make_pair(4, 5));cout << people.second.first;//4return 0;
}

排序規則
優先考慮first,若相等再比較second…

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
int main() {pair<int, std::string> people[] = {make_pair(25, "Alice"),make_pair(30, "Bob"),};sort(people, people + 2);for (int i = 0; i < 2; i++) {cout << people[i].first<< people[i].second << endl;}return 0;
}

2.vector
提供了動態數組(可變大小數組)的實現,存儲的事一系列相同類型的元素

#include <iostream>
#include <vector>
using namespace std;
int main() {vector<int> a;//定義整型a容器a.push_back(1);a.push_back(2);a.push_back(3);cout << a[0]<<endl;//首元素:1a.pop_back();//刪除尾部元素cout << a.size();//元素個數:2
}

元素插入操作

#include <iostream>
#include <vector>
using namespace std;
int main() {vector<int> a = { 5,4,3 };a.insert(a.begin() + 1, 999);cout << a[1];//999
}

初始化與排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {//初始化vector<int> a(5, 1);//對容器a初始化為{1,1,1,1,1}vector<int> b = { 5,4,3,2,1 };//排序sort(b.begin(), b.end());for (int i = 0; i < b.size(); i++) {cout << b[i];//12345}
}

去重排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {vector<int> a = { 5,4,3,2,1,5,5 };sort(a.begin(), a.end());//unique只能去掉相鄰重復元素,所以先sort//auto用于自動推導 unique 函數返回的迭代器類型auto b = unique(a.begin(), a.end());auto n = distance(a.begin(), b);for (int i = 0; i < n; i++) {cout << a[i];//12345}
}

另一種去重排序方式

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {vector<int> a = { 5,4,3,2,1,5,5 };sort(a.begin(), a.end());//1 2 3 4 5 5 5auto b = unique(a.begin(), a.end());//b指向了多余元素的起始位置(排序完成后的第二個5的位置)a.erase(b, a.end());//擦除從b到末尾的元素,a的大小也同時修改了。即刪除了后面的兩個5for (int i = 0; i < a.size(); i++) {cout << a[i];//12345}
}

輸出可以使用以下方式
循環變量 i 依次取 a 容器中的每個元素的值
const 保證了元素不會被修改
auto 使編譯器自動推斷元素的類型
& 表示使用引用來避免不必要的復制

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {vector<int> a = { 5,4,3,2,1,5,5 };sort(a.begin(), a.end());auto b = unique(a.begin(), a.end());a.erase(b, a.end());for (const auto& i : a) {cout << i;//12345}
}

3.list
較少使用
以節點存儲,以指針鏈接的鏈表結構

#include <iostream>
#include <list>
using namespace std;
int main() {// 創建一個空的 list,存儲整數list<int> myList;// 在列表末尾插入元素myList.push_back(1);myList.push_back(2);myList.push_back(3);//列表元素為123// 在列表開頭插入元素myList.push_front(6);//列表元素為6123// 遍歷列表并打印元素for (const auto& i : myList) {cout << i << " ";}cout << endl;//輸出了:6 1 2 3// 刪除列表中的元素myList.pop_back();myList.pop_front();//列表元素為12
}

在這里插入圖片描述
4.stack

#include <iostream>
#include <stack>
using namespace std;
int main() {stack<int> myStack;// 壓棧操作myStack.push(1);myStack.push(2);myStack.push(3);//棧內(從下到上):123// 訪問棧頂元素cout << myStack.top();//3// 彈棧操作myStack.pop();//3被彈出// 再次訪問棧頂元素cout <<  myStack.top();//2//棧內(從下到上):12// 獲取棧中元素的數量cout << "Stack size: " << myStack.size() << endl;//2// 檢查棧是否為空if (myStack.empty()) {cout << "Stack is empty." << endl;}else {cout << "Stack is not empty." << endl;}
}

在這里插入圖片描述
5.queue
(1)普通隊列

#include <iostream>
#include <queue>
using namespace std;
int main() {queue<int> myQueue;// 入隊操作myQueue.push(1);myQueue.push(2);myQueue.push(3);//隊列(從頭到尾):123// 訪問隊頭元素cout << myQueue.front();//1// 出隊操作myQueue.pop();//1出// 再次訪問隊頭元素cout <<myQueue.front();//2//隊列(從頭到尾):23// 獲取隊列中元素的數量cout << myQueue.size();//2// 檢查隊列是否為空if (myQueue.empty()) {cout << "Queue is empty." << endl;}else {cout << "Queue is not empty." << endl;}
}

(2)優先隊列/堆
隊列中的元素是按照一定優先級進行排序的,默認情況下是從小到大排序的,即最大元素位于隊列的前面。在插入元素時會插入到指定位置,確保隊內有序。(大根堆)

在這里插入圖片描述

#include <iostream>
#include <queue>
using namespace std;
int main() {priority_queue<int> maxHeap;// 插入元素maxHeap.push(3);maxHeap.push(1);maxHeap.push(4);maxHeap.push(2);while (!maxHeap.empty()) {cout << maxHeap.top()<<" ";maxHeap.pop();}//4 3 2 1
}
#include <iostream>
#include <queue>
using namespace std;
int main() {priority_queue<int> maxHeap;// 插入元素maxHeap.push(3);maxHeap.push(1);maxHeap.push(4);maxHeap.push(2);隊列元素:4 3 2 1// 訪問隊頭元素(最大元素)cout << maxHeap.top();//4// 彈出隊頭元素maxHeap.pop();//4出//隊列元素:3 2 1// 再次訪問隊頭元素cout << maxHeap.top();//3// 獲取隊列中元素的數量cout << maxHeap.size();//3// 檢查隊列是否為空if (maxHeap.empty()) {cout << "Priority queue is empty." << endl;}else {cout << "Priority queue is not empty." << endl;}
}

小根堆

priority_queue<int, vector<int>, greater<int>> minHeap

(3)雙端隊列
#include <deque>

#include <iostream>
#include <deque>
using namespace std;
int main() {// 創建一個雙端隊列deque<int> deque;// 向雙端隊列的尾部添加元素deque.push_back(1);//隊列元素:1deque.push_back(2);//隊列元素:1(頭) 2(尾)// 向雙端隊列的頭部添加元素deque.push_front(3);//隊列元素:3 1 2deque.push_front(4);//隊列元素:4 3 1 2// 打印雙端隊列的元素for (int n : deque) {cout << n;}// 4 3 1 2// 從雙端隊列的尾部刪除元素deque.pop_back();//隊列元素:4 3 1// 從雙端隊列的頭部刪除元素deque.pop_front();//隊列元素:3 1
}

在這里插入圖片描述

[例1] CLZ銀行問題
在這里插入圖片描述
在這里插入圖片描述
評測系統

#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {int num;cin >> num;//操作數量queue<string> vipQueue;queue<string> normalQueue;for (int i = 0; i < num; ++i) {string operation,name;cin >> operation;if (operation == "IN") {cin >> name;char type;cin >> type;if (type == 'V') {vipQueue.push(name);}else {normalQueue.push(name);}}else {char type;cin >> type;if (type == 'V'&&!vipQueue.empty()) {vipQueue.pop();}else if(type=='N'&&!normalQueue.empty()) {normalQueue.pop();}}}while (!vipQueue.empty()) {cout << vipQueue.front()<<endl;vipQueue.pop();}while (!normalQueue.empty()) {cout << normalQueue.front() << endl;normalQueue.pop();}
}

[例2] 合并果子
在這里插入圖片描述
在這里插入圖片描述
評測系統

每次選擇兩個最小的數合并(貪心),并將合并后的新數重新放入堆中

#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {int kind;cin >> kind;priority_queue<int, vector<int>, greater<int>> minHeap;for (int i = 0; i < kind; ++i) {int num;cin >> num;minHeap.push(num);}int sum = 0;while (minHeap.size() > 1) {int heapone=minHeap.top();minHeap.pop();int heaptwo = minHeap.top();minHeap.pop();sum += heapone + heaptwo;minHeap.push(heapone + heaptwo);}cout << sum;
}

[例3] 建筑搶修
在這里插入圖片描述
在這里插入圖片描述

評測系統

我們對建筑按照截止時間進行排序,并使用一個最大堆(優先隊列)來動態管理當前的修理計劃。每次當總修理時間超過當前考慮的建筑的截止時間時,我們從堆中移除修理時間最長的建筑。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct building {int repairtime;int deadline;
};
int cmp(building a, building b) {return a.deadline < b.deadline;
}
int main()
{int total = 0;int n;cin >> n;vector<building> a(n);for (int i = 0; i < n; ++i) {cin >> a[i].repairtime >> a[i].deadline;}sort(a.begin(), a.end(), cmp);priority_queue<int> q;for (int i = 0; i < n; i++) {q.push(a[i].repairtime);//一定修,因為馬上deadline了total += a[i].repairtime;if (total > a[i].deadline) {//如果超時,那么根據大根堆,隊列中維修時長最大的移除total -= q.top();q.pop();}}cout << q.size();return 0;
}

6.set
set存儲唯一元素,默認升序

#include <iostream>
#include <set>
using namespace std;int main() {set<int> s;s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(2); // 這個操作沒有效果,因為 2 已存在cout << "Set contains:";for (int x : s) {cout << " " << x;}cout << endl;//輸出:1 2 3 4
}

降序排列

#include <iostream>
#include <set>
using namespace std;int main() {set<int,greater<int>> s;//改為降序排列s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(2);cout << "Set contains:";for (int x : s) {cout << " " << x;}cout << endl;//輸出:4 3 2 1
}

在這里插入圖片描述
在這里插入圖片描述

multiset允許重復元素

#include <iostream>
#include <set>using namespace std;int main() {multiset<int> ms;ms.insert(3);ms.insert(1);ms.insert(4);ms.insert(2);ms.insert(2);  // 可以插入重復元素// 輸出 multiset 的內容cout << "Multiset contains:";for (int x : ms) {cout << " " << x;}//輸出:1 2 2 3 4// 計算某個值在 multiset 中出現的次數int count = ms.count(2);cout <<count;//2
}

在這里插入圖片描述
在這里插入圖片描述

7.map
map存儲鍵值對,鍵是唯一的,鍵值對是根據鍵排序的(自動排序,默認升序排列),可以直接使用鍵訪問對應的值;在插入新元素時,若鍵已存在,則更新其對應的值

#include <iostream>
#include <map>
using namespace std;int main() {// 創建一個 mapmap<string, int> marks;// 插入鍵值對marks["Alice"] = 88;marks["Bob"] = 95;marks["Charlie"] = 72;// 更新鍵對應的值marks["Alice"] = 91;// 遍歷并打印 mapfor (const auto& pair : marks) {cout << pair.first << pair.second << endl;}/*輸出Alice91Bob95Charlie72*/// 查找并訪問元素if (marks.find("Bob") != marks.end()) {cout << marks["Bob"];//95}
}

在這里插入圖片描述
8.練習
(1)寶藏排序
在這里插入圖片描述
評測系統

#include <iostream>
#include<queue>
using namespace std;
int main() {int n;cin >> n;priority_queue<int,vector<int>,greater<int>> pq;while (n--) {int x;cin >> x;pq.push(x);}while(!pq.empty()) {cout<<pq.top()<<" ";pq.pop();}
}

(2)小藍吃糖果
在這里插入圖片描述
評測系統

找出糖果數量最多的種類,其余糖果進行插空。
若最多種類的糖果數量是max,一共有max-1個空,第二大種類的糖果數一定不超過max-1,越插空越多,以此類推。只有當所有糖果加起來也沒有填滿max-1個空時,失敗。

#include <iostream>
#include <queue>
using namespace std;
int main() {int n;cin >> n;long long int total=0;priority_queue<int> a;for (int i = 0; i < n; i++) {int x;cin >> x;a.push(x);total += x;}int max = a.top();total -= max;if (max - 1 <= total)cout << "Yes";elsecout << "No";
}

(3)小藍的括號串
在這里插入圖片描述
在這里插入圖片描述
評測系統

#include <iostream>
#include <stack>
using namespace std;
int main() {stack<char> s;int n;cin >> n;while (n--) {char x;cin >> x;if (x == '(') {s.push(x);}else {if (!s.empty()) {s.pop();}else {cout << "No";return 0;}}}if (!s.empty()) {cout << "No";}else {cout << "Yes";}
}

(4)快遞分揀
在這里插入圖片描述
在這里插入圖片描述
評測系統

#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {int n;cin >> n;map<string, vector<string>> m;//一對多的關系,一個鍵對應多個值vector<string> vm;//記錄城市出現順序while (n--) {string s, p;cin >> s >> p;if (m.find(p) == m.end()) {//當前城市首次出現,可改為if(m.count(p)==0)vm.push_back(p);}m[p].push_back(s);}for (const auto& x : vm) {cout << x <<" " << m[x].size() << endl;for (const auto& x2 : m[x]) {cout << x2 << endl;}}
}

(5)順子日期
在這里插入圖片描述
答案:14

#include<iostream>
#include<string>
using namespace std;
int panduanmonth(int x) {if (x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12)return 31;else if (x == 4 || x == 6 || x == 9 || x == 11)return 30;else {return 28;}
}
string formatDate(int a, int b, int c) {string s = "2022";if (b < 10) {s+= "0"+to_string(b);}else {s+= to_string(b);}if (c < 10) {s += "0" + to_string(c);}else {s += to_string(c);}return s;
}
bool isSequentialDate(string s) {for (int i = 0; i <= 5; ++i) {if (s[i] + 1 == s[i + 1] && s[i + 1] + 1 == s[i + 2])return true;}return false;
}
int main() {int count = 0;for (int month = 1; month <= 12; month++) {for (int day = 1; day <= panduanmonth(month); day++) {string date = formatDate(2022, month, day);if (isSequentialDate(date)) {count++;}}}cout << count;
}

(6)小明和完美序列
在這里插入圖片描述
評測系統
對于序列中的每個數字,計算它出現的次數。比較其值和出現的次數。如果出現次數大于數字的值,則需要刪除多余的出現。如果出現次數小于數字的值,則需要全部刪除。計算總共需要刪除的數字數量。

#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main() {int n;cin >> n;map<int, int> count;int num;for (int i = 0; i < n; ++i) {cin >> num;count[num]++;}int deletecount = 0;for (const auto& x : count) {int a = x.first;int b = x.second;if (a > b) {deletecount += b;}else if (a < b) {deletecount += b - a;}}cout << deletecount;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/212882.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/212882.shtml
英文地址,請注明出處:http://en.pswp.cn/news/212882.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

TailwindCSS 多主題色配置

TailwindCSS 多主題色配置 現在大多數網站都支持主題色變換&#xff0c;比如切換深色模式。那么我們該如何進行主題色配置呢&#xff1f; tailwind dark tailwind 包含一個 dark變體&#xff0c;當啟用深色模式時&#xff0c;可以為網站設置不同樣式 <div class"bg-whi…

ThingWorx 9.2 Windows安裝

參考官方文檔安裝配置 1 PostgreSQL 13.X 2 Java, Apache Tomcat, and ThingWorx PTC Help Center 參考這里安裝 數據庫 C:\ThingworxPostgresqlStorage 設置為任何人可以full control 數據庫初始化 pgadmin4 創建用戶twadmin并記錄口令password Admin Userpostgres Thin…

漏刻有時百度地圖API實戰開發(9)Echarts使用bmap.js實現軌跡動畫效果

Bmap.js是Echarts和百度地圖相結合開發的一款JavaScript API&#xff0c;它可以幫助用戶在web應用中獲取包括地圖中心點、地圖縮放級別、地圖當前視野范圍、地圖上標注點等在內的地圖信息&#xff0c;并且支持在地圖上添加控件&#xff0c;提供包括智能路線規劃、智能導航(駕車…

C# WPF上位機開發(通訊協議的編寫)

【 聲明&#xff1a;版權所有&#xff0c;歡迎轉載&#xff0c;請勿用于商業用途。 聯系信箱&#xff1a;feixiaoxing 163.com】 作為上位機&#xff0c;它很重要的一個部分就是需要和外面的設備進行數據溝通的。很多時候&#xff0c;也就是在這個溝通的過程當中&#xff0c;上…

PyQt下使用OpenCV實現人臉檢測與識別

背景&#xff1a; 一 數字圖像處理與識別警務應用模型 基于前期所學知識&#xff0c;與公安實踐相結合&#xff0c;綜合設計數字圖像處理與識別警務應用模型,從下列4個研究課題中選擇2個進行實驗實現&#xff1a;圖像增強與復原、人臉檢測與識別、虹膜內外圓檢測與分割、車牌…

Html轉PDF,前端JS實現Html頁面導出PDF(html2canvas+jspdf)

Html轉PDF&#xff0c;前端JS實現Html頁面導出PDF&#xff08;html2canvasjspdf&#xff09; 文章目錄 Html轉PDF&#xff0c;前端JS實現Html頁面導出PDF&#xff08;html2canvasjspdf&#xff09;一、背景介紹二、疑問三、所使用技術html2canvasjspdf 四、展示開始1、效果展示…

C語言----文件操作(一)

一&#xff1a;C語言中文件的概念 對于文件想必大家都很熟悉&#xff0c;無論在windows上還是Linux中&#xff0c;我們用文件去存儲資料&#xff0c;記錄筆記&#xff0c;常見的如txt文件&#xff0c;word文檔&#xff0c;log文件等。那么&#xff0c;在C語言中文件是什么樣的存…

threadpool github線程池學習

參考項目 https://github.com/progschj/ThreadPool 源碼分析 // 常規頭文件保護宏, 避免重復 include #ifndef THREAD_POOL_H #define THREAD_POOL_H// 線程池, 存儲線程對象; #include <vector>// 任務隊列, 雙向都可操作隊列, queue 不能刪除首個元素 #include <…

微信小程序制作-背單詞的小程序制作

微信小程序–背單詞的 好久沒有發過文章了&#xff0c;但是不代表著我不去學習了嘍&#xff0c;以下是我最近做的東西&#xff0c;前端的UI由朋友設計的&#xff0c;目前這個是前端使用的是微信小程序后端是Python的一個輕量型框架&#xff0c;FastApi&#xff0c;嗯&#xff…

MyBatis 四大核心組件之 Executor 源碼解析

&#x1f680; 作者主頁&#xff1a; 有來技術 &#x1f525; 開源項目&#xff1a; youlai-mall &#x1f343; vue3-element-admin &#x1f343; youlai-boot &#x1f33a; 倉庫主頁&#xff1a; Gitee &#x1f4ab; Github &#x1f4ab; GitCode &#x1f496; 歡迎點贊…

List 接口

1 List 接口 java.util 中的集合類包含 Java 中某些最常用的類。最常用的集合類是 List 和 Map。 List是一種常用的集合類型&#xff0c;它可以存儲任意類型的對象&#xff0c;也可以結合泛型來存儲具體的類型對象&#xff0c;本質上就是一個容器。 1.1 List 類型介紹 有序性…

06-React組件 Redux React-Redux

React組件化&#xff08;以Ant-Design為例&#xff09; 組件化編程&#xff0c;只需要去安裝好對應的組件&#xff0c;然后通過各式各樣的組件引入&#xff0c;實現快速開發 我們這里學習的是 Ant-design &#xff08;應該是這樣&#xff09;&#xff0c;它有很多的組件供我們…

計算機網絡測試題第二部分

前言:如果沒有做在線測試請自主獨立完成&#xff0c;本篇文章只作為學習計算機網絡的參考&#xff0c;題庫中的題存在一定錯誤和不完整&#xff0c;請學習時&#xff0c;查找多方書籍論證&#xff0c;獨立思考&#xff0c;如果存在疑慮可以評論區討論。查看時&#xff0c;請分清…

pytorch debug 常用工具

自動辨識圖像格式可視化 import numpy as np import matplotlib.pyplot as plt from PIL import Imagedef convert_to_numpy(image_input):"""自動檢測輸入圖像類型&#xff0c;并將其轉換為NumPy數組。"""if isinstance(image_input, np.ndarr…

7-3 Left-pad

根據新浪微博上的消息&#xff0c;有一位開發者不滿NPM&#xff08;Node Package Manager&#xff09;的做法&#xff0c;收回了自己的開源代碼&#xff0c;其中包括一個叫left-pad的模塊&#xff0c;就是這個模塊把javascript里面的React/Babel干癱瘓了。這是個什么樣的模塊&a…

物聯網IC

物聯網IC 電子元器件百科 文章目錄 物聯網IC前言一、物聯網IC是什么二、物聯網IC的類別三、物聯網IC的應用實例四、物聯網IC的作用原理總結前言 物聯網IC的功能和特性可以根據不同的物聯網應用需求來選擇和配置,以滿足物聯網設備在連接、通信、感知和控制方面的需求。 一、物…

猜數字游戲Ⅱ

你和朋友一起玩猜數字游戲&#xff0c;你寫出一個秘密數字&#xff0c;請朋友猜這個數字是多少。朋友每猜測一次&#xff0c;你就會給他一個包含下述信息的提示&#xff1a; 猜測數字中有多少位屬于數字和確切位置都猜對了&#xff08;稱為 "Bulls"&#xff0c;公牛&…

VOL-vue 框架 文件上傳控件關于大文件上傳等待的修改

我的項目在測試voltable列表組件中對阿里云OSS做附件上傳時&#xff0c;幾十M的文件可能就會需要一段時間來上傳&#xff0c;才能有OSS的狀態和鏈接返回。 但是控件VolUpload.vue并沒有去在這方面做任何交互體驗上的控制&#xff0c;而且VolUpload.vue本身寫的幾個上傳函數都是…

SpringBoo在項目停止(服務停止/關閉退出)之后執行的方法

SpringBoo在項目停止/服務停止/關閉退出之后執行的方法 1.實現DisposableBean接口2.使用PreDestroy注解 SpringApplication會向JVM注冊一個關閉鉤子(hook)&#xff0c;以確保ApplicationContext在退出時正常關閉。 可以使用所有標準的Spring生命周期回調&#xff08;例如Dispos…

內測分發是什么?十年的前端開發者帶你了解

內測分發是軟件開發過程中的一個階段&#xff0c;特別指軟件還未完全完成或準備對外廣泛發布前&#xff0c;向一定范圍的用戶群體提供該軟件版本的測試機會&#xff0c;以便收集反饋和修復潛在的問題。在講解內測分發之前&#xff0c;我們需要明確幾個相關概念&#xff1a; 軟件…