Ch22 容器版陣列 - Vector

# Ch22 容器版陣列 - Vector > 搭配 [Leetcode 解題系統](https://leetcode.com/) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z) ## vector - 容器版的陣列 比起在第九章教過的 [陣列](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格，或是超出長度範圍的位置！ ## 拜訪每個值 - 求和 【例題】 > 題目給一個 vector 名為 nums，請問裡面所有數字加起來的總和是多少呢？我們可以用一個變數來記錄總和，拜訪 nums 裡的數字時一一加上去 ```cpp= int ans = 0; for (int i=0;i<nums.size();i++){ ans = ans + nums[i]; } return ans; ``` 如此一來 ans 就是 nums 的總和了！ 【學生練習題】 > - [ ] [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 裡面的值，最後剩下的就是答案了！ 【學生練習題】 > - [ ] [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) 裡面教過的做法 ## 拜訪每個值 - 有幾個符合條件？ 【例題】 > 題目給一個 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; ``` 【學生練習題】 > - [ ] [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) 裡面教過的做法 ## 拜訪每個值 - 找最大最小值 【例題】 > 題目給一個 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 裡的最大值了！ 【學生練習題】 > - [ ] [Leetcode 1979: 最大與最小的公因數 ](https://leetcode.com/problems/find-greatest-common-divisor-of-array/) > > 題目給我們一個名為 nums 的 vector，請問裡面的"最大值"和"最小值"的最大公因數是多少呢？找出陣列裡的最大值和最小值後我們可以直接呼叫 gcd(a, b) 這個內建的函數來算出最大公因數 【學生練習題】 > - [ ] [Leetcode 2733: 不是最大也不是最小 ](https://leetcode.com/problems/neither-minimum-nor-maximum/) > > 題目給我們一個名為 nums 的 vector，請任意回傳一個數字，他既不是陣列裡的最大值，也不是最小值。若這樣的值不存在，就回傳 -1 找出陣列裡的最大值和最小值後我們可以再拜訪一次陣列裡的數字們看哪個數字不等於最大值也不等於最小值，就直接回傳它 ## 建立 vector - 複製一份 有些題目不只會給我們一個 vector 讓我們做算數，還有可能會要我們造出 vector 並回傳為答案 【例題】 > 題目給一個 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; ``` 【學生練習題】 > - [ ] [Leetcode 1920: Build Array from Permutation ](https://leetcode.com/problems/build-array-from-permutation/) > > 題目給我們一個名為 nums 的 vector > 我們要造出一個 vector，且我們的每個第 i 格都是 nums[nums[i]] ## 建立 vector - 依序存入數字 【例題】 > 題目給一個名為 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 圖解說明如下：第一步 ![image](https://hackmd.io/_uploads/rJOoQXuvT.png) 第二步 ![image](https://hackmd.io/_uploads/Hkpj77dvp.png) 第三步 ![image](https://hackmd.io/_uploads/Hymhm7dwp.png) ```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; ``` 【學生練習題】 > - [ ] [Leetcode 905: 偶數在前，奇數在後 ](https://leetcode.com/problems/sort-array-by-parity/) > > 題目給我們一個名為 nums 的 vector > 我們要造出一個 vector，偶數通通在前半段，奇數通通在後半段 ## 建立 vector - 先固定 vector 長度再填入數字 【例題】 > 題目給一個名為 nums 的 vector，裡面有 2n 個數字 > 請造出一個 vector，使得 nums 裡面的前半段 n 個數字和後半段 n 個數字交錯排放 ![image](https://hackmd.io/_uploads/Sy3mHQuPT.png) 這是 Leetcode 上的題目，連結是 [Leetcode 1470](https://leetcode.com/problems/shuffle-the-array/) 類似上一個主題，我們可以分兩次拜訪 nums 拿取需要的數字第一步 ![image](https://hackmd.io/_uploads/r1wKHXdv6.png) 第二步 ![image](https://hackmd.io/_uploads/SyQ5SX_P6.png) ```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; ``` 【學生練習題】 > - [ ] [Leetcode 2149: 正負交錯 ](https://leetcode.com/problems/rearrange-array-elements-by-sign/) > > 題目給我們一個名為 nums 的 vector > 我們要造出一個 vector，正數和負數交錯排放，且是先從正數開始 ## 雙重迴圈枚舉數對 【例題】 > 題目給一個名為 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; ``` 【學生練習題】 > - [ ] [Leetcode 2824: 有幾對小於目標 ](https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/) > > 題目給我們一個名為 nums 的 vector，和一個整數 target > 請問裡面有幾對數字的和小於 target 呢？ 【學生練習題】 > - [ ] [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)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.