# Ch22 容器版陣列 - Vector
> 搭配 [Leetcode 解題系統](https://leetcode.com/)
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
## <font color='darkblue'>vector - 容器版的陣列</font>
比起在第九章教過的 [陣列](https://hackmd.io/s/HJMbs-ARW) ，另一種 C++ 常用的，類似陣列的「容器」，叫做 vector
他就像是一個可以「伸縮」的陣列一樣，我們在裡面放幾個數字，他就是一個多麼長的陣列
宣告 vector 的方法如下
```cpp
vector<int> a;
```
這樣一來 a 就是一個空的 vector 了
我們可以開始往裡面放東西
```cpp
a.push_back(3);
a.push_back(5);
a.push_back(10);
```
這樣一來 a 就變成了一個 size 為 3 的 vector，裡面的值是 {3, 5, 10}！
使用 vector 的好處就是我們一開始不需要知道到底需要多少格
反正他能夠隨著我們塞東西進去而增加容器的 size!
但如果我們想要一次就設定好 vector 的長度
也是可以的
```cpp
vector<int> a(5, 0);
```
這樣一來 a 就是一個 size 為 5 的 vector，裡面的 5 個值都是 0！
若我們之後需要再往裡面放新的東西，也可以繼續對它 push_back！
如果我們需要清空，只需要用 clear 就行了：
```cpp
a.clear();
```
這樣一來 a 又變回了一個空的 vector，size 是 0
如果我們需要知道一個 vector 目前有多長（也就是裡面目前有幾個東西），可以用 size
```cpp
int count = a.size();
```
這樣一來 count 這個數字就是 a 這個 vector 的長度
其餘像是對某一格取值、改值等等的操作，都和一般陣列是一樣的
也一樣要注意，不可以觸碰到不存在的格子，像是第-1格，或是超出長度範圍的位置！
## <font color='darkblue'>拜訪每個值 - 求和</font>
<font color='darkorange'>【例題】</font>
> 題目給一個 vector 名為 nums，請問裡面所有數字加起來的總和是多少呢？
我們可以用一個變數來記錄總和，拜訪 nums 裡的數字時一一加上去
```cpp=
int ans = 0;
for (int i=0;i<nums.size();i++){
ans = ans + nums[i];
}
return ans;
```
如此一來 ans 就是 nums 的總和了！
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 268: 消失的數字 ](https://leetcode.com/problems/missing-number/)
>
> 題目給我們 n 個數字，存在名為 nums 的 vector 裡面，他們是從 0 到 n 這 n+1 個數字裡面缺了一個的組合，請問缺了哪個呢？
舉例來說，若 nums = [3,0,1] 就代表缺的是 2
若 nums = [9,6,4,2,3,5,7,0,1] 就代表缺的是 8
提示：我們可以先用一個迴圈算出 0+1+...+n 是多少，再把這個值逐一扣掉 nums 裡面的值，最後剩下的就是答案了！
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2535: 數字和與位數和的差距 ](https://leetcode.com/problems/difference-between-element-sum-and-digit-sum-of-an-array/)
>
> 題目給我們一個名為 nums 的 vector，請問裡面所有的數字的"值"加起來，和裡面所有數字的"位數"加起來，相差多少呢？
舉例來說，若 nums = [1,15,6,3]，那麼就是 (1+15+6+3) 減去 (1+1+5+6+3)，答案是 9
提示：將一個數字拆解成位數有點麻煩，我們可以參考 [while 迴圈](https://hackmd.io/@CLKO/Sk3nDNsiZ?type=view) 裡面教過的做法
## <font color='darkblue'>拜訪每個值 - 有幾個符合條件？</font>
<font color='darkorange'>【例題】</font>
> 題目給一個 vector 名為 hour，代表每個員工分別工作了多少個小時
> 還有一個整數 target，代表老闆希望他們每個人至少工作幾個小時
> 請問總共有幾個員工符合了老闆的期望呢？
這是 Leetcode 上的題目，連結是 [Leetcode 2798](https://leetcode.com/problems/number-of-employees-who-met-the-target/)
我們可以用一個變數來記錄總共有幾個員工符合條件
```cpp=
int ans = 0;
for (int i=0;i<hours.size();i++){
if(hours[i]>=target) ans ++;
}
return ans;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1295: 偶數位數的數字 ](https://leetcode.com/problems/find-numbers-with-even-number-of-digits/)
>
> 題目給我們一個名為 nums 的 vector，請問裡面有幾個數字是"偶數"位數的呢？
舉例來說，nums = [12, 345, 2, 6, 7896]
- 12 是二位數，符合條件
- 345 是三位數，不符合
- 2 和 6 都是一位數，都不符合
- 7896 是四位數，符合條件
因此總共有兩個數字符合條件
提示：算一個數字有幾個位數有點麻煩，我們可以參考 [while 迴圈](https://hackmd.io/@CLKO/Sk3nDNsiZ?type=view) 裡面教過的做法
## <font color='darkblue'>拜訪每個值 - 找最大最小值</font>
<font color='darkorange'>【例題】</font>
> 題目給一個 vector 名為 nums，請問裡面最大的數字是多少呢？
我們可以用一個變數代表最大值
並且把 nums 裡面每個數字都看過一遍
如果比目前的最大值還要大，就更新它
```cpp=
int ans = nums[0]; // 先假設第 0 格是最大值
for (int i=1;i<nums.size();i++){ // 從第 1 格依序往後看
if(nums[i]>ans) ans = nums[i];
}
return ans;
```
如此一來 ans 就是 nums 裡的最大值了！
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1979: 最大與最小的公因數 ](https://leetcode.com/problems/find-greatest-common-divisor-of-array/)
>
> 題目給我們一個名為 nums 的 vector，請問裡面的"最大值"和"最小值"的最大公因數是多少呢？
找出陣列裡的最大值和最小值後
我們可以直接呼叫 gcd(a, b) 這個內建的函數來算出最大公因數
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2733: 不是最大也不是最小 ](https://leetcode.com/problems/neither-minimum-nor-maximum/)
>
> 題目給我們一個名為 nums 的 vector，請任意回傳一個數字，他既不是陣列裡的最大值，也不是最小值。若這樣的值不存在，就回傳 -1
找出陣列裡的最大值和最小值後
我們可以再拜訪一次陣列裡的數字們
看哪個數字不等於最大值也不等於最小值，就直接回傳它
## <font color='darkblue'>建立 vector - 複製一份</font>
有些題目不只會給我們一個 vector 讓我們做算數，還有可能會要我們造出 vector 並回傳為答案
<font color='darkorange'>【例題】</font>
> 題目給一個 vector 名為 nums，請造出一個 vector，裡面是 nums 重複兩次
這是 Leetcode 上的題目，連結是 [Leetcode 1929](https://leetcode.com/problems/concatenation-of-array/)
舉例來說，如果 nums 是 [1, 3, 2, 1]，我們就要回傳 [1, 3, 2, 1, 1, 3, 2, 1]
```cpp=
vector<int> ans; // 答案會是一個 vector
// 重複兩次
for (int i=0;i<nums.size();i++){
ans.push_back(nums[i]);
}
for (int i=0;i<nums.size();i++){
ans.push_back(nums[i]);
}
return ans;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1920: Build Array from Permutation
](https://leetcode.com/problems/build-array-from-permutation/)
>
> 題目給我們一個名為 nums 的 vector
> 我們要造出一個 vector，且我們的每個第 i 格都是 nums[nums[i]]
## <font color='darkblue'>建立 vector - 依序存入數字</font>
<font color='darkorange'>【例題】</font>
> 題目給一個名為 nums 的 vector，以及一個數字 pivot
> 請造出一個 vector，他的前半段全是比 pivot 小的數字，中半段全是等於 pivot 的數字，後半段全是比 pivot 大的數字
這是 Leetcode 上的題目，連結是 [Leetcode 2161](https://leetcode.com/problems/partition-array-according-to-given-pivot/)
舉例來說，如果 nums = [9,12,5,10,14,3,10], pivot = 10，我們就要回傳 [9,5,3,10,10,12,14]，因為
- 9, 5, 3 比 10 小，要放到前面
- 12 和 14 比 10 大，要放到後面
- 中間就是兩個 10
我們可以分三次拜訪 nums
圖解說明如下：
第一步
第二步
第三步
```cpp=
vector<int> ans;
// 第一步
for(int i=0;i<nums.size();i++){
if(nums[i]<pivot) ans.push_back(nums[i]);
}
// 第二步
for(int i=0;i<nums.size();i++){
if(nums[i]==pivot) ans.push_back(nums[i]);
}
// 第三步
for(int i=0;i<nums.size();i++){
if(nums[i]>pivot) ans.push_back(nums[i]);
}
return ans;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 905: 偶數在前，奇數在後
](https://leetcode.com/problems/sort-array-by-parity/)
>
> 題目給我們一個名為 nums 的 vector
> 我們要造出一個 vector，偶數通通在前半段，奇數通通在後半段
## <font color='darkblue'>建立 vector - 先固定 vector 長度再填入數字</font>
<font color='darkorange'>【例題】</font>
> 題目給一個名為 nums 的 vector，裡面有 2n 個數字
> 請造出一個 vector，使得 nums 裡面的前半段 n 個數字和後半段 n 個數字交錯排放
這是 Leetcode 上的題目，連結是 [Leetcode 1470](https://leetcode.com/problems/shuffle-the-array/)
類似上一個主題，我們可以分兩次拜訪 nums 拿取需要的數字
第一步
第二步
```cpp=
vector<int> ans(2*n);
int position = 0;
for(int i=0;i<n;i++){
ans[position] = nums[i];
position+=2;
}
position = 1;
for(int i=n;i<n*2;i++){
ans[position] = nums[i];
position+=2;
}
return ans;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2149: 正負交錯
](https://leetcode.com/problems/rearrange-array-elements-by-sign/)
>
> 題目給我們一個名為 nums 的 vector
> 我們要造出一個 vector，正數和負數交錯排放，且是先從正數開始
## <font color='darkblue'>雙重迴圈枚舉數對</font>
<font color='darkorange'>【例題】</font>
> 題目給一個名為 nums 的 vector，請問裡面有幾個數對是相同的數字
這是 Leetcode 上的題目，連結是 [Leetcode 1512](https://leetcode.com/problems/number-of-good-pairs/)
我們可以用雙層的迴圈來枚舉數對
```cpp=
int ans = 0;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]==nums[j]) ans++;
}
}
return ans;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2824: 有幾對小於目標
](https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/)
>
> 題目給我們一個名為 nums 的 vector，和一個整數 target
> 請問裡面有幾對數字的和小於 target 呢？
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2006: 有幾對差值為k
](https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/)
>
> 題目給我們一個名為 nums 的 vector，和一個整數 k
> 請問裡面有幾對數字的差值（絕對值）等於 k 呢？
##
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
Sign in with Wallet
Connect another wallet