Ch22 容器版陣列 - Vector

搭配 Leetcode 解題系統
回目錄：國立科學園區實驗中學C++程式語言自學講義

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 的總和了！

【學生練習題】

• Leetcode 268: 消失的數字

題目給我們 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 裡面的值，最後剩下的就是答案了！

【學生練習題】

• Leetcode 2535: 數字和與位數和的差距

題目給我們一個名為 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;

【學生練習題】

• Leetcode 1295: 偶數位數的數字

題目給我們一個名為 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 裡的最大值了！

【學生練習題】

• Leetcode 1979: 最大與最小的公因數

題目給我們一個名為 nums 的 vector，請問裡面的"最大值"和"最小值"的最大公因數是多少呢？

找出陣列裡的最大值和最小值後
我們可以直接呼叫 gcd(a, b) 這個內建的函數來算出最大公因數

【學生練習題】

• Leetcode 2733: 不是最大也不是最小

題目給我們一個名為 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;

【學生練習題】

• Leetcode 1920: Build Array from Permutation
  

題目給我們一個名為 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;

【學生練習題】

• Leetcode 905: 偶數在前，奇數在後
  

題目給我們一個名為 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;

【學生練習題】

• Leetcode 2149: 正負交錯
  

題目給我們一個名為 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;

【學生練習題】

• Leetcode 2824: 有幾對小於目標
  

題目給我們一個名為 nums 的 vector，和一個整數 target
請問裡面有幾對數字的和小於 target 呢？

【學生練習題】

• Leetcode 2006: 有幾對差值為k
  

題目給我們一個名為 nums 的 vector，和一個整數 k
請問裡面有幾對數字的差值（絕對值）等於 k 呢？

回目錄：國立科學園區實驗中學C++程式語言自學講義