HackMDCh22 容器版陣列 - Vector
vector - 容器版的陣列
比起在第九章教過的 陣列 ，另一種 C++ 常用的，類似陣列的「容器」，叫做 vector
他就像是一個可以「伸縮」的陣列一樣，我們在裡面放幾個數字，他就是一個多麼長的陣列
宣告 vector 的方法如下
vector<int> a;
這樣一來 a 就是一個空的 vector 了
我們可以開始往裡面放東西
a.push_back(3);
a.push_back(5);
a.push_back(10);
這樣一來 a 就變成了一個 size 為 3 的 vector，裡面的值是 {3, 5, 10}！
使用 vector 的好處就是我們一開始不需要知道到底需要多少格
反正他能夠隨著我們塞東西進去而增加容器的 size!
但如果我們想要一次就設定好 vector 的長度
也是可以的
vector<int> a(5, 0);
這樣一來 a 就是一個 size 為 5 的 vector，裡面的 5 個值都是 0！
若我們之後需要再往裡面放新的東西，也可以繼續對它 push_back！
如果我們需要清空，只需要用 clear 就行了：
a.clear();
這樣一來 a 又變回了一個空的 vector，size 是 0
如果我們需要知道一個 vector 目前有多長（也就是裡面目前有幾個東西），可以用 size
int count = a.size();
這樣一來 count 這個數字就是 a 這個 vector 的長度
其餘像是對某一格取值、改值等等的操作，都和一般陣列是一樣的
也一樣要注意，不可以觸碰到不存在的格子，像是第-1格，或是超出長度範圍的位置！
拜訪每個值 - 求和
【例題】
題目給一個 vector 名為 nums，請問裡面所有數字加起來的總和是多少呢？
我們可以用一個變數來記錄總和，拜訪 nums 裡的數字時一一加上去
int ans = 0;
for (int i=0;i<nums.size();i++){
ans = ans + nums[i];
}
return ans;
如此一來 ans 就是 nums 的總和了！
【學生練習題】
題目給我們 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 裡面的值，最後剩下的就是答案了！
【學生練習題】
題目給我們一個名為 nums 的 vector，請問裡面所有的數字的"值"加起來，和裡面所有數字的"位數"加起來，相差多少呢？
舉例來說，若 nums = [1,15,6,3]，那麼就是 (1+15+6+3) 減去 (1+1+5+6+3)，答案是 9
提示：將一個數字拆解成位數有點麻煩，我們可以參考 while 迴圈 裡面教過的做法
拜訪每個值 - 有幾個符合條件？
【例題】
題目給一個 vector 名為 hour，代表每個員工分別工作了多少個小時
還有一個整數 target，代表老闆希望他們每個人至少工作幾個小時
請問總共有幾個員工符合了老闆的期望呢？
這是 Leetcode 上的題目，連結是 Leetcode 2798
我們可以用一個變數來記錄總共有幾個員工符合條件
int ans = 0;
for (int i=0;i<hours.size();i++){
if(hours[i]>=target) ans ++;
}
return ans;
【學生練習題】
題目給我們一個名為 nums 的 vector，請問裡面有幾個數字是"偶數"位數的呢？
舉例來說，nums = [12, 345, 2, 6, 7896]
- 12 是二位數，符合條件
- 345 是三位數，不符合
- 2 和 6 都是一位數，都不符合
- 7896 是四位數，符合條件
因此總共有兩個數字符合條件
提示：算一個數字有幾個位數有點麻煩，我們可以參考 while 迴圈 裡面教過的做法
拜訪每個值 - 找最大最小值
【例題】
題目給一個 vector 名為 nums，請問裡面最大的數字是多少呢？
我們可以用一個變數代表最大值
並且把 nums 裡面每個數字都看過一遍
如果比目前的最大值還要大，就更新它
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 裡的最大值了！
【學生練習題】
題目給我們一個名為 nums 的 vector，請問裡面的"最大值"和"最小值"的最大公因數是多少呢？
找出陣列裡的最大值和最小值後
我們可以直接呼叫 gcd(a, b) 這個內建的函數來算出最大公因數
【學生練習題】
題目給我們一個名為 nums 的 vector，請任意回傳一個數字，他既不是陣列裡的最大值，也不是最小值。若這樣的值不存在，就回傳 -1
找出陣列裡的最大值和最小值後
我們可以再拜訪一次陣列裡的數字們
看哪個數字不等於最大值也不等於最小值，就直接回傳它
建立 vector - 複製一份
有些題目不只會給我們一個 vector 讓我們做算數，還有可能會要我們造出 vector 並回傳為答案
【例題】
題目給一個 vector 名為 nums，請造出一個 vector，裡面是 nums 重複兩次
這是 Leetcode 上的題目，連結是 Leetcode 1929
舉例來說，如果 nums 是 [1, 3, 2, 1]，我們就要回傳 [1, 3, 2, 1, 1, 3, 2, 1]
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;
【學生練習題】
題目給我們一個名為 nums 的 vector
我們要造出一個 vector，且我們的每個第 i 格都是 nums[nums[i]]
建立 vector - 依序存入數字
【例題】
題目給一個名為 nums 的 vector，以及一個數字 pivot
請造出一個 vector，他的前半段全是比 pivot 小的數字，中半段全是等於 pivot 的數字，後半段全是比 pivot 大的數字
這是 Leetcode 上的題目，連結是 Leetcode 2161
舉例來說，如果 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
圖解說明如下：
第一步
第二步
第三步
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;
【學生練習題】
題目給我們一個名為 nums 的 vector
我們要造出一個 vector，偶數通通在前半段，奇數通通在後半段
建立 vector - 先固定 vector 長度再填入數字
【例題】
題目給一個名為 nums 的 vector，裡面有 2n 個數字
請造出一個 vector，使得 nums 裡面的前半段 n 個數字和後半段 n 個數字交錯排放
這是 Leetcode 上的題目，連結是 Leetcode 1470
類似上一個主題，我們可以分兩次拜訪 nums 拿取需要的數字
第一步
第二步
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;
【學生練習題】
題目給我們一個名為 nums 的 vector
我們要造出一個 vector，正數和負數交錯排放，且是先從正數開始
雙重迴圈枚舉數對
【例題】
題目給一個名為 nums 的 vector，請問裡面有幾個數對是相同的數字
這是 Leetcode 上的題目，連結是 Leetcode 1512
我們可以用雙層的迴圈來枚舉數對
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;
【學生練習題】
題目給我們一個名為 nums 的 vector，和一個整數 target
請問裡面有幾對數字的和小於 target 呢？
【學生練習題】
題目給我們一個名為 nums 的 vector，和一個整數 k
請問裡面有幾對數字的差值（絕對值）等於 k 呢？
