C++ - vector 的相關練習

前言

1、題1 只出現一次的數字：

解法一：遍歷

參考代碼：

解法二：按位異或

參考代碼：

解法三：哈希表

參考代碼：

2、題2 楊輝三角：

參考代碼：

總結

前言

路漫漫其修遠兮，吾將上下而求索；

大家可以自己先嘗試做一下：

136. 只出現一次的數字 - 力扣（LeetCode）

118. 楊輝三角 - 力扣（LeetCode）

`1、題1` 只出現一次的數字 `：`

136. 只出現一次的數字 - 力扣（LeetCode）

解法一：遍歷

利用雙指針，一個指針定位一個指針去遍歷后續的數字看是否有重復的；

參考代碼：

    int singleNumber(vector<int>& nums) {int n = nums.size();if(n==1) return nums[0];//解法一：遍歷for(int i = 0;i<n;i++){int flag = 1;for(int j = 0;j<n;j++){if(j!=i && nums[i] == nums[j]) flag = 0; }if(flag) return nums[i];}return 0;//此處的返回沒有意義，隨便返回就可以了}

解法二：按位異或

按位異或的特點：相同為0，相異為1；非空數組nums 中只有一個數字出現了1次，其余的均出現了2次，將nums 中的數據全部進行按位異或，相同的數據抵消就會得到那個只出現一次的數；

參考代碼：

    int singleNumber(vector<int>& nums) {//按位異或int ret = 0;for(auto e: nums) {ret ^= e;}return ret;}

解法三：哈希表

將nums 中的數據放入hash 之中，看哪一個數字出現了一次即可；

參考代碼：

    int singleNumber(vector<int>& nums) {//hashunordered_map<int,int> hash;//<數據，出現的次數>for(auto e: nums){hash[e]++;}for(auto e:hash){if(e.second == 1) return e.first;}return 0;//隨便返回一個}

2、題2 楊輝三角：

118. 楊輝三角 - 力扣（LeetCode）

如果用C語言解決的話，需要返回一個二級指針：

本題用C語言做會非常惡心，可以將楊輝三角想象成二維數組，只是不同的是它不是 m*n 的每一行的數據個數均相等的，楊輝三角的每一行的個數是變化的；

用C語言不能直接靜態開辟一個二維數組，只能通過動態開辟的方式；

Q：如何動態開辟一個二維數組？

將楊輝三角想象成一個直角三角形；楊輝三角畫成等腰三角形其本質是一個邏輯結構(想象出來的結構)；

用C語言做動態開辟數組：先開辟指針數組，然后造一個循環開辟每一行；并且釋放的時候也要注意，不能直接釋放指針數組，需要寫一個循環先將指針數組中所指向的數組先釋放（先釋放局部再釋放整體）；

由于C語言只支持一次即返回一個值，而如果想要返回多個值，想讓別人拿到該數組的大小只能通過傳址傳參；在leetcode 之中要寫通用的代碼，凡是返回數組(返回指向該數組的指針)，就得告訴這個數組有多少行，此時寫測試用例的時候，每個題都要有每個題的情況；

因為返回一個一維數組需要知道這個一維數組中有多少個數據，同理，返回一個二維數組就需要知道二維數組有多少行，并且一行中有多少個數據；所以其第三個參數，指的是所要返回這個二維數組每一行中有多少個數據；

Q：第三個參數為什么是二級指針呢？

二維數組中每一行的數據個數可能是不同的，需要開辟一塊空間來記錄每一行的數據個數；所以就需要傳一個地址的地址，即二級指針；

我們此處用C++來解決：

Q: 如何理解 vector<vector<int>> ?

在vector 中存放vector<int> ; vector 的底層：

template<class T>
class vector
{
private:T* _a;size_t _size;size_t _capacity;
};

Q： vector<vector<int>>是如何開辟需求的二維數組？

	vector<vector<int>> vv(numRows);//開辟numRows行for (int i = 0; i < numRows; ++i)//開辟每一行{vv[i].resize(i + 1, i);}

vector<vector<int>> 會實例化出兩個類，vector<int> 是一個類，而vector<vector<int>> 是另外一個類；

vector<int> 實例化：

vector<vector<int>> 實例化：

類模板給不同的模板參數就會生成不同的類型；這兩個雖然是從同一個模板中實例化出來的，但是他們的類型不同，一個是 int? ，一個是 vector<int>；

vector<vector<int>> 是一個對象數組，其每一個位置上是一個 vector<int> 對象；

我們在開辟每一行的時候用resize 進行初始化，而并非使用reserve , 這是因為reserve 只會開辟空間而并未插入數據；而resize ，當 n>capacity? 或 size<n<capacity 的時候會插入數據，相當于用resize 既可以開辟空間又會初始化；

需要注意的是，已經存在的對象想要初始化就只能使用resize；

一個vector 想要初始化有兩種方式：

1、在構造的時候進行初始化；
2、構造之后利用resize 進行初始化；

基于楊輝三角的特點，我們需要將開辟的二維數組中的空間均初始化為1，如下：

而接下來就需要處理楊輝三角中其他剩余的值了；訪問 vector<vector<int>> 中的數據可以通過二維數組的訪問形式進行訪問: vv[i][j] , 但是其底層與二維數組的訪問完全不同；

在回答“ vv[i][j]的底層與二維數組的訪問完全不同” 的問題之前，我們先了解一下C語言中二維數組的兩種開辟方式：

對于二維數組：eg.int aa[10][5] , 10 行 5 列的二維數組本質上也是一維數組；

1、動態開辟二維數組需要進行轉換；

	int* aa = (int*)malloc(sizeof(int*) * N);for(int i = 0; i < N; ++i){aa[i] = (int*)malloc(sizeof(int) * (i + 1));}

aa 作為二維數組數組名，表示該數組的首元素地址，即指向該指針數組；aa[i] 則是訪問指針數組中的所對應的數據，而指針數組的元素本身就是一級指針，那么 aa[i][j] 就是兩次解引用，訪問到了二維數組中的數據；動態開辟的二維數組是兩次指針的解引用，先進行第一層的解引用拿到指針數組中的元素，再進行第二層的解引用，拿到真實存放的數據；

2、靜態開辟的二維數組，是轉換成一個一維數組；

eg.int aa[10][5];

C語言中的靜態二維數組其實在底層其實是一個一維數組，那么?int aa[10][5];是一個有50個int 類型空間的一維數組，即一次解引用就可以解決（會通過一些計算來實現一次解引用）；

總之，動態開辟和靜態開辟是不一樣的；

在C++中，對于vv[i][j]而言，是兩次函數調用；對于C語言來說，靜態開辟的一維數組或者二維數組均是一次解引用實現數據的訪問，數組的訪問本質上均會轉換成指針的訪問，所以C語言的訪問數組中的元素一定會轉換成對指針的解引用；

Q:vv[i][j] 如何轉換成兩個函數調用？

首先，vv[i][j] 會轉化成 vv.operator[](i).operator[](j) ；其中 vv.operator[](i) 返回的是 vector<int> 的對象，而vector<int>.operator[](j) 返回值為 int 對象；相當于第一個 operator[] 的調用返回了vector<int> 對象又會作為下一次調用 operator[] 的左操作數，此時返回值為 int 類型的對象；于是乎就相當于拿到了第 i 行第 j 個對象；

Q：相較于我們之前使用的二維數組(C語言中的二維數組)，此處使用vector<vector<int>> 的好處是什么？

vector<vector<T>> 的功能更加強大；在C語言中以前定義的靜態數組，靜態數組中的每一行的數據個數均是固定的，由于C語言不支持變長數組，其行、列必須是常量，且無論是申請還是釋放都需要親歷親為，比較麻煩；但是倘若使用 vector<vector<>> ，便就不存在這樣的問題，無需管釋放(C++中會自動調用析構函數)，并且其每一行的數據個數為多少均無所謂, 即不會強制每一行的數據個數均需要一樣；

vv[i][j] 看似有兩個[ ], 實際上結合底層的角度它是調用了兩個類實例化出來的operator[] ,而這兩個類又是由 vector<T> 實例化出來的。由 vector<T> 實例化出來兩個類 vector<int> 和 vector<vector<int>> ,然后再實例化其成員函數；

解題：

需要從第2行開始遍歷，而一有 vv.size() 行；

對于每一行元素訪問的控制：j ; 每一行的數據個數是不固定的，從每一個 vector<vector<int>> 對象的 _size 可以得知每一行中數據的個數，即 vv[i].size() 為第 i 行中的數據個數；對于楊輝三角來說，其每一行的第一個和最后一個無需進行訪問，我們在開辟空間初始化的時候就可以完成；

楊輝三角的計算規則：

將楊輝三角看作是一個直角三角形：

通過觀察楊輝三角的計算規則和下標的關系，我們可以得到： [i,j] = [i-1 , j] + [i-1 , j-1];

參考代碼：

    vector<vector<int>> generate(int numRows) {vector<vector<int>> vv(numRows);for(size_t i = 0;i<numRows;++i){vv[i].resize(i+1,1);}//填for(int i = 2;i<vv.size();++i)//從2行開始{for(int j = 1; j<vv[i].size()-1;++j){//第一個和最后一個不用填vv[i][j] = vv[i-1][j] + vv[i-1][j-1];}}return vv;}

總結

1、在C++中中，vector<vector<int>> 用vv[i][j] 訪問數據會轉化調用兩個函數，即?vv.operator[](i).operator[](j) ；

2、其中 vv.operator[](i) 返回的是 vector<int> 的對象，而vector<int>.operator[](j) 返回值為 int 對象；相當于第一個 operator[] 的調用返回了vector<int> 對象又會作為下一次調用 operator[] 的左操作數，此時返回值為 int 類型的對象；于是乎就相當于拿到了第 i 行第 j 個對象；