知識點

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\le 2\times 10^6)$ 名同學(xué)陸陸續(xù)續(xù)進(jìn)入教室。我們知道每名同學(xué)的學(xué)號（在 $1$ 到 $10^9$ 之間），按進(jìn)教室的順序給出。上課了，老師想知道第 $i$ 個進(jìn)入教室的同學(xué)的學(xué)號是什么（最先進(jìn)入教室的同學(xué) $i=1$），詢問次數(shù)不超過 $10^5$ 次。

輸入格式

第一行 $2$ 個整數(shù) $n$ 和 $m$，表示學(xué)生個數(shù)和詢問次數(shù)。

第二行 $n$ 個整數(shù)，表示按順序進(jìn)入教室的學(xué)號。

第三行 $m$ 個整數(shù)，表示詢問第幾個進(jìn)入教室的同學(xué)。

輸出格式

輸出 $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\le n\le 10^5)$ 個寄包柜。每個寄包柜格子數(shù)量不一，第 $i$ 個寄包柜有 $a_i(1\le a_i\le 10^5)$ 個格子，不過我們并不知道各個 $a_i$ 的值。對于每個寄包柜，格子編號從 1 開始，一直到 $a_i$?，F(xiàn)在有 $q(1\le q\le 10^5)$ 次操作：

• 1 i j k：在第 $i$ 個柜子的第 $j$ 個格子存入物品 $k(0\le k\le 10^9)$。當(dāng) $k=0$ 時說明清空該格子。
• 2 i j：查詢第 $i$ 個柜子的第 $j$ 個格子中的物品是什么，保證查詢的柜子有存過東西。

已知超市里共計不會超過 $10^7$ 個寄包格子，$a_i$ 是確定然而未知的，但是保證一定不小于該柜子存物品請求的格子編號的最大值。當(dāng)然也有可能某些寄包柜中一個格子都沒有。

輸入格式

第一行 2 個整數(shù) $n$ 和 $q$，寄包柜個數(shù)和詢問次數(shù)。

接下來 $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];}}
};