一個好的網(wǎng)站應(yīng)該具有什么西安百度推廣競價托管
文章目錄
- 知識點
- 創(chuàng)建
- 增刪查改
- 習(xí)題1
- 習(xí)題2
- 習(xí)題3
- 習(xí)題4:
- 習(xí)題5:
知識點
C++的STL提供已經(jīng)封裝好的容器vector,也可叫做可變長的數(shù)組,vector底層就是自動擴容的順序表,其中的增刪查改已經(jīng)封裝好
創(chuàng)建
const int N=30;
vector<int> a1;//創(chuàng)建叫a1的空的可變長的數(shù)組
vector<int> a2(N);//創(chuàng)建大小為30的可變長的數(shù)組,里面每個元素為0
vector<int> a3(N,2);//創(chuàng)建大小30的可變長的數(shù)組,里面每個元素為2
vector<int> a4={1,2,3,4,5};//初始化列表的創(chuàng)建方式
以上4種更為常用
<> 里面可以放任意的數(shù)據(jù)類型,
這就體現(xiàn)模板的作用,也體現(xiàn)了模板的強大之處
這樣,vector就可以放所有數(shù)據(jù)類型,包括STL本身
struct Node{int a,b;string s;
}
vector<string> a5;//存字符串
vector<Node> a6;//存結(jié)構(gòu)體
vector<vector> <int>a7//創(chuàng)建二維可變長數(shù)組
vector<int> a[N];//創(chuàng)建大小為N的可變長數(shù)組,也是二維,注意小括號和中括號的區(qū)別
增刪查改
size求數(shù)組大小empty檢查數(shù)組是否為空,是bool類型的返回值begin和end遍歷數(shù)組push_back尾插pop_back尾刪front/back返回頭/尾元素resize擴容,擴的比原來大,大的部分為0,擴的小的話則刪除多余的部分clear清空數(shù)組
直接上代碼 簡單易懂 !!!!!!!!!
#include <iostream>
#include <vector>
using namespace std;
const int N = 5;
vector<int> a(N);
void print()
{for (int i = 0;i < a.size();i++){cout << a[i] << " ";}cout << endl;
}
int main()
{for (int i = 1;i < 5;i++){a.push_back(i);}print();a.pop_back();a.pop_back();a.pop_back();print();int t = a.back();cout << t << endl;a.resize(3);print();a.clear();if (a.empty()){cout << "空"<<endl;}return 0;
}
習(xí)題1
常言道:學(xué)再久 不如多寫題理解得快
詢問學(xué)號
題目描述
有 n ( n ≤ 2 × 1 0 6 ) n(n \le 2 \times 10^6) n(n≤2×106) 名同學(xué)陸陸續(xù)續(xù)進(jìn)入教室。我們知道每名同學(xué)的學(xué)號(在 1 1 1 到 1 0 9 10^9 109 之間),按進(jìn)教室的順序給出。上課了,老師想知道第 i i i 個進(jìn)入教室的同學(xué)的學(xué)號是什么(最先進(jìn)入教室的同學(xué) i = 1 i=1 i=1),詢問次數(shù)不超過 1 0 5 10^5 105 次。
輸入格式
第一行 2 2 2 個整數(shù) n n n 和 m m m,表示學(xué)生個數(shù)和詢問次數(shù)。
第二行 n n n 個整數(shù),表示按順序進(jìn)入教室的學(xué)號。
第三行 m m m 個整數(shù),表示詢問第幾個進(jìn)入教室的同學(xué)。
輸出格式
輸出 m m m 個整數(shù)表示答案,用換行隔開。
樣例輸入
10 3
1 9 2 60 8 17 11 4 5 14
1 5 9
樣例輸出
1
8
5
思路:兩個vector即可解決
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e6;
int n, m;
vector<int> q(N);
vector<int> e(N);
int main()
{cin >> n >> m;for (int i = 1;i <= n;i++){cin >> q[i];}for (int i = 1;i <= m;i++){cin >> e[i];cout << q[e[i]] << endl;}return 0;
}
習(xí)題2
寄包柜
題目描述
超市里有 n ( 1 ≤ n ≤ 1 0 5 ) n(1\le n\le10^5) n(1≤n≤105) 個寄包柜。每個寄包柜格子數(shù)量不一,第 i i i 個寄包柜有 a i ( 1 ≤ a i ≤ 1 0 5 ) a_i(1\le a_i\le10^5) ai?(1≤ai?≤105) 個格子,不過我們并不知道各個 a i a_i ai? 的值。對于每個寄包柜,格子編號從 1 開始,一直到 a i a_i ai??,F(xiàn)在有 q ( 1 ≤ q ≤ 1 0 5 ) q(1 \le q\le10^5) q(1≤q≤105) 次操作:
1 i j k
:在第 i i i 個柜子的第 j j j 個格子存入物品 k ( 0 ≤ k ≤ 1 0 9 ) k(0\le k\le 10^9) k(0≤k≤109)。當(dāng) k = 0 k=0 k=0 時說明清空該格子。2 i j
:查詢第 i i i 個柜子的第 j j j 個格子中的物品是什么,保證查詢的柜子有存過東西。
已知超市里共計不會超過 1 0 7 10^7 107 個寄包格子, a i a_i ai? 是確定然而未知的,但是保證一定不小于該柜子存物品請求的格子編號的最大值。當(dāng)然也有可能某些寄包柜中一個格子都沒有。
輸入格式
第一行 2 個整數(shù) n n n 和 q q q,寄包柜個數(shù)和詢問次數(shù)。
接下來 q q q 個行,每行有若干個整數(shù),表示一次操作。
輸出格式
對于查詢操作時,輸出答案,以換行隔開。
樣例輸入
5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1
樣例輸出
118014
1
思路:有柜子,柜子還帶有格子,說明是二維的。柜子用的時候擴容出格子,再加上選擇語句可做
#include <iostream>
#include <vector>
using namespace std;
const int N = 100000;
vector<int> e[N];
int n, q;
int num,i,j, k;
int main()
{cin >> n >> q;while (q--){cin >> num >> i >> j;if (num == 1){cin >> k;e[i].resize(j+1);e[i][j] = k;}else{cout << e[i][j] << endl;}}return 0;
}
習(xí)題3
移動零
給定一個數(shù)組 nums,編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾,同時保持非零元素的相對順序。
請注意 ,必須在不復(fù)制數(shù)組的情況下原地對數(shù)組進(jìn)行操作。
示例 1:
輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]
示例 2:
輸入: nums = [0]
輸出: [0]
思路:把一個數(shù)組分兩部分,前面非0,后面是0;用雙指針,遍歷數(shù)組判斷條件,交換或指針++
class Solution {
public:void moveZeroes(vector<int>& nums) {int cur=-1;int i=0;for(auto x:nums){if(x==0)i++;else{swap(nums[cur+1],nums[i]);cur++;i++;}}}
};
習(xí)題4:
顏色分類
給定一個包含紅色、白色和藍(lán)色、共 n 個元素的數(shù)組 nums ,原地 對它們進(jìn)行排序,使得相同顏色的元素相鄰,并按照紅色、白色、藍(lán)色順序排列。
我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。
必須在不使用庫內(nèi)置的 sort 函數(shù)的情況下解決這個問題。
示例 1:
輸入:nums = [2,0,2,1,1,0]
輸出:[0,0,1,1,2,2]
示例 2:
輸入:nums = [2,0,1]
輸出:[0,1,2]
思路:與上題類似,將數(shù)組分3份,最后一份從后面定義,記得循環(huán)里面只操作一次,否則i可能越界
class Solution {
public:void sortColors(vector<int>& nums) {int left=-1;int right=nums.size();int i=0;for(i=0;i<nums.size();){if(nums[i]==2){swap(nums[i],nums[right-1]);right--;}else if(nums[i]==0){swap(nums[left+1],nums[i]);i++;left++;}else if(nums[i]==1)i++;if(i==right)break;}}
};
習(xí)題5:
合并兩個有序數(shù)組
給你兩個按 非遞減順序 排列的整數(shù)數(shù)組 nums1 和 nums2,另有兩個整數(shù) m 和 n ,分別表示 nums1 和 nums2 中的元素數(shù)目。
請你 合并 nums2 到 nums1 中,使合并后的數(shù)組同樣按 非遞減順序 排列。
注意:最終,合并后數(shù)組不應(yīng)由函數(shù)返回,而是存儲在數(shù)組 nums1 中。為了應(yīng)對這種情況,nums1 的初始長度為 m + n,其中前 m 個元素表示應(yīng)合并的元素,后 n 個元素為 0 ,應(yīng)忽略。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] 。
合并結(jié)果是 [1,2,2,3,5,6] ,其中斜體加粗標(biāo)注的為 nums1 中的元素。
示例 2:
輸入:nums1 = [1], m = 1, nums2 = [], n = 0
輸出:[1]
解釋:需要合并 [1] 和 [] 。
合并結(jié)果是 [1] 。
示例 3:
輸入:nums1 = [0], m = 0, nums2 = [1], n = 1
輸出:[1]
解釋:需要合并的數(shù)組是 [] 和 [1] 。
合并結(jié)果是 [1] 。
注意,因為 m = 0 ,所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。
思路:創(chuàng)建新的數(shù)組,將兩個數(shù)組復(fù)制給新數(shù)組,最后新數(shù)組再賦值回去
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int>nums3(m+n);int i=0,j=0;int k=0;while(i<m&&j<n){if(nums1[i]<=nums2[j]){nums3[k++]=nums1[i++];}elsenums3[k++]=nums2[j++];}while(i<m)nums3[k++]=nums1[i++];while(j<n)nums3[k++]=nums2[j++];for(i=0;i<nums1.size();i++){nums1[i]=nums3[i];}}
};