數組和鏈表

C++的數組和鏈表分別是什么？分別有什么種類？它們都有什么特性？針對這些特征，使用情形是什么？

數組

什么是數組？

一個數組就像是一個變量，它可以存儲一組值，但是所有值都是相同的數據類型。?

一個int數組定義：int hours [6]

該數組類型為int型，即存儲元素是整數。

該數組的名稱是hours，方括號內為數組的大小，它表示數組可以容納的元素或值的數量，必須是一個常量整數，其值大于0.（也可以是命名常數）

初始化數組：int hours[6] = { 1, 2, 3, 4, 5, 6}.

訪問數組元素

數組的元素可以根據下標作為單獨的變量進行訪問和使用，C++中的下標編號從0開始，數組中最后一個元素的下標比數組中元素的總數少1.

如果采用全局定義的方式定義一個包含數值的數組，則默認情況下，所有元素初始化為0.但是，如果定義的是局部變量，則沒有默認的初始值。?

上面hours數組的每個元素在被下標訪問時都可以用做int變量賦值：hours[0] = 20

可變長的動態數組：vector

vector是順序容器的一種，是可變長的動態數組。所以vector具備數組的性質：在vector容器中，根據下標隨機訪問某個元素的時間是常數，在尾部添加一個元素的時間大多數情況也是常數。

但是，在中間插入或刪除元素，需要移動多個元素，速度較慢，平均花費時間和容器中的元素個數成正比。

Vector基本用法

#include <vector>
using namespace std;
int main(){
	int a[5] = {1, 2, 3, 4, 5}
	vector <int> v(a, a+5); //將數組a的內容放入v
	cout << v.end() - v.begin() << endl; //兩個迭代器相減，輸出：5
	v.insert(v.begin()+2, 13); // 在begin()+2 位置插入13， v變為：1，2,13,3，4,5
	v.eraser(v.begin()+2); // 刪除位于begin()+2 位置上的元素，v變為：1,2,3,4，5
	vector <int> v2(4, 100); // v2有4個元素，都是100
	v2.insert(v2.begin(), v.begin() + 1, v.begin() +3); // 將v的一段插入v2開頭，v2： 2,3,100,100,100,100
	v.erase(v.begin()+1, v.begin()+3); // 刪除v上的區間，即[2,3),v:1,4,5
	// 遍歷
	int sum = 0;
	// 迭代器遍歷
	for(std::vector<int>::iterator it = v.begin(); it !=v.end(); it++){
		sum += *it;
	}
	//索引遍歷(不適用list)
	for(int i = 0; i < v.size(); i++){
		sum += v[i];
	}
}

鏈表

什么是鏈表？

鏈表是由一系列連接在一起的結點構成，其中的每一個結點都是一個數據結構。

鏈表的結點是動態分配、使用和刪除的。相對于數組來說，鏈表可以容易地擴大或縮小，無需知道鏈表有多少個結點；相對于矢量（vector）來說，鏈表插入或刪除結點的速度更快，因為要將值插入vector的中間，需要將插入點后的所有元素都向后移動一個位置，而鏈表插入結點，其他結點不必移動。

鏈表的結構：鏈表中的每個結點都包含一個或多個保存數據的成員，和一個后繼指針指向鏈表的下一個結點。單節點組成如下：

在c++中表示鏈表，需要有一個表示鏈表中單個結點的數據類型。

struct ListNode
{
	double value;  // 數據
	ListNode *next; // 指向另一個相同類型結點的指針
}

非空鏈表的第一個結點成為鏈表的頭。要訪問鏈表中的結點，需要有一個指向鏈表頭的指針。從鏈表頭開始，可以按照存儲在每個結點中的后繼指針訪問鏈表中的其余結點。最后一個結點的后繼指針被設置為nullptr。

已經聲明一個數據類型來表示結點后，可定義一個初始為空的鏈表。即定義一個用作鏈表頭的指針并將其初始化為nullptr：ListNode *head = nullptr;

創建一個鏈表。其中包含一個結點，存儲值為12.5

head = new ListNode; //分配新結點
head->value = 12.5; 
head->next = nullptr; // 鏈表的結尾

在單向鏈表中，頭head指向最先節點的前一個，尾end指向最后節點，新加入一個點，即加在未加入結尾時的鏈表的結尾的后一個。

  1 - 5 - 2 - 9 - 8
h                 e
這是原來的鏈表(h=head,e=end) 
新讀入3,要把3加入鏈表的最后面
那么就要加在8的后面  
  1 - 5 - 2 - 9 - 8 -   3
h                 e   e->next
                       tmp
這樣子end->next就指向3,也就是tmp
因為end是指向point類型的指針
新加入3后我們發現end不在結尾上,那么我們要調整
即end=tmp
  1 - 5 - 2 - 9 - 8 - 3
h                     e

創建一個新結點，在其中存儲13.5的值，并將其作為鏈表中的第二個結點。

ListNode *secondPtr = new ListNode;
secondPtr->value = 13.5;
secondPtr->next = nullptr;
head->next = secondPtr; //第一個結點指向第二個

鏈表的操作

1.使用構造函數初始化結點 ——結點在創建時可初始化

struct ListNode
{
	double value;
	ListNode *next;
	//構造函數
	ListNode(double value1; ListNode *next1 = nullptr){
		value = value1;
		next = next1;
	}
};

2.創建鏈表——讀取文件中的值并將每個新讀取的值添加到已經累積的值鏈表的開頭

ListNode *numberList = nullptr;
double number;
while(numberFile >> number){
	// 創建一個結點以保存該數字
	numberList = new ListNode(number, numberList);
};

3.遍歷鏈表——從鏈表頭開始，涉及整個鏈表，并在每個結點上執行一些處理操作

ListNode *ptr = numberList; // 一個指針ptr指向鏈表的開頭
while(ptr != nullptr){
		cout << ptr->value; // 打印結點的值；
		ptr = ptr->next; // 移動到下一個結點
};

雙向鏈表（list）

list是順序容器的一種，是一個雙向鏈表。雙向鏈表的每個元素中都有一個指針指向后一個元素，一個指針指向前一個元素。

在list容器中，在已經定位到要增刪元素的位置的情況下，增刪元素能在常數時間內完成。如圖2所示，在ai和ai+1之間插入一個元素，只需要修改ai和ai+1中的指針即可。

但是list容器不支持根據下標隨機存取元素。

list的成員函數

list的構造函數和許多成員函數的用法都與vector類似，初此之外，還有獨特接口。（以下省略與vector相同的接口）

void push_front(const T &val); //在頭部添加元素
void pop_front(); //刪除頭部元素
void sort(); //排序
void remove(const T &val); // 刪除值為val的所有元素
void remove_if(bool (*pred)(const T &val)); // 刪除滿足條件的所有元素
void unique(); // 刪除連續的重復元素（只保留第一個）
void merge(list < T> &x); // 在自身有序的前提下，與另一個有序鏈表x合并，并保持有序。
void splice(iterator i, list < T> &x, iterator i); //在位置i前插入鏈表x中的一個結點（剪切操作）
void splice(iterator i, list < T> &x, iterator first, iterator last); // 在位置i前插入鏈表x中的區間[first, last)，并在鏈表x中刪除該區間。鏈表自身和鏈表x可以是同一個鏈表，只要i不在[first，last)中即可

哈希表

什么是哈希表？

散列圖（Hash table，也叫哈希表），是根據關鍵碼值（Key value）而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

給定表M，存在函數f(key),對任意給定的關鍵字值key，代入函數后若能得到包含該關鍵詞的記錄在表中的地址，則稱表M為哈希（Hash）表，函數f(key)為哈希(Hash)函數。

數據的哈希地址 = f(關鍵字key的值)

通俗解釋：哈希表是一種數據結構，可以直接根據給定的key值計算出目標位置。在工程中，哈希表結構通常采用數組實現。

普通列表僅能通過下標來獲取目標位置的值，而哈希表可以根據給定的key計算得到目標位置的值。

列表查找中，二分查找算法，復雜度為O(log2n),只能用于有序列表；普通無序列表只能采用遍歷查找，復雜度為O(n);而用哈希函數實現的哈希表，對任意元素查找速度始終是常數級別，即O(1).

哈希碰撞

一個哈希值會對應多種值。即不同的key值，哈希函數結果一樣，都指向同一個value地址，出現重復。

對于哈希表而言，沖突只能盡可能地少，無法完全避免。通常用順序表存一堆鏈表來解決這個問題：

哈希表應用場景

哈希表的優點是可以通過關鍵值計算直接獲取目標位置，對于海量數據的精確查找有顯著速度提升，理論上即使有無限的數據量，一個良好的哈希表依舊可以保持O(1)的查找速度。

在工程上，經常用于通過名稱制定配置信息、通過關鍵詞傳遞參數、建立對象與對象的映射關系等。總而言之，所有使用鍵值對的地方，都用到了哈希表思想。

構建哈希表

在構建哈希表時，最重要的是哈希函數的設計。常用的哈希函數的構造方法有6種：直接定址法、數字分析法、平方取中法、折疊法、除留余數法和隨機數法。

1.直接定址法：哈希函數為一次函數，即一下兩種形式：

?H(key) = key / ?H(key) = ?a * key + b

2.數字分析法：如果關鍵字由多位字符或數字組成，可以考慮抽取其中的2位或者多位作為該關鍵字對應的哈希地址，在取法上盡量選擇變化較多的位，避免沖突發生。

3.平方取中：對關鍵字做平方操作，取中間的幾位作為哈希地址。適合關鍵字位數較短

4.折疊法：將關鍵字分割成位數相同的幾部分（最后一部分的位數可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址。此方法適合關鍵字位數較多的情況。

5.除留余數法：若一直整個哈希表的最大長度m，可以取一個不大于m的數p，然后對該關鍵字key做取余運算：H(key) = key % p。此方法中，p的取值非常重要，由經驗得p可以為不大于m的質數或不包含小于20的質因數的合數。

6.隨機數法：去關鍵字的一個隨機函數值作為它的哈希地址，即H(key) = random(key).適合關鍵字長度不等的情況。?

set和map都可以由哈希表和二叉搜索樹實現。

在C++STL中，哈希表對應的容器是unordered_map，訪查插刪時間復雜度為O(1)，但內部是無序的，額外空間復雜度高出許多。map對應的數據結構是紅黑樹，訪查插刪時間復雜度為O(logn),內部是有序的。對于需要高效率查詢的情況，使用unordered_map容器，對內存大小比較敏感或者數據要求有序的情況，可以用map容器。

哈希表基本使用

unordered_map的用法和map大同小異：

#include <iostream>
#include <unordered_map>
#include <string>
int main(int argc, char **argv){
	std::unordered_map<int, std::string> map;
	map.insert(std::make_pair(1, "Scale");
	map.insert(std::make_pair(2, "java");
	map.insert(std::make_pair(3, "python");
	map.insert(std::make_pair(6, "Erlang");
	map.insert(std::make_pair(13,"Haskell");
	
	std::unordered_map<int, std::string>::iterator it;
	if((it = map.find(6)) != map.end()){
		std::cout << it->second << std::endl;
	}
	return 0;
}

Leetcode對應題目

前綴和

前綴和技巧：對應題目：303、304、560（ 用到哈希表 ）

前綴和主要適用場景是：原始數組不會被修改的情況下，頻繁查詢某個區間的累加和。

差分數組

差分數組：對應題目：370、1109、1094

差分數組主要適用場景：頻繁對原始數組某個區間的元素進行增減

滑動窗口

滑動窗口：對應題目：76、567、438、3?

和子數組/子字符串相關的題目，很可能要考察滑動窗口，往這方面思考就行了

滑動窗口算法思路:

我們在字符串S中使用左右雙指針，初始化left = right = 0， 把索引左閉右開區間[left, right)稱為一個窗口；先不斷地增加right指針，擴大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）;（尋找可行解）此時，停止增加right，轉而不斷增加left指針縮小窗口[left， right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同時，每增加left，更新一次。（優化可行解，尋找最優解）重復2、3步，直到right到達字符串s的盡頭。

左右指針輪流前進，窗口大小增增減減，窗口不斷右滑。

關鍵問題：

• 1.當right擴大窗口，即加入字符時，需要更新哪些數據?
• 2.什么條件下，窗口應該暫停擴大，開始移動left縮小窗口？
• 3.當移動left縮小窗口，移出字符時，應該更新哪些數據？
• 4.我們要的結果應該在擴大窗口還是縮小窗口時更新？

二分查找

二分查找對應題目：704、34、875、1011

分析二分查找的一個技巧是:不要出現else，而是把所有情況用else if寫清楚，這樣可以清楚地展示所有細節。 另外需要聲明一下，計算mid時需要防止溢出，left + (right - left) / 2 和 (left + right) / 2 結果相同，但是有效防止了 left和right太大直接相加導致溢出。

什么問題可以運用二分搜索算法技巧？

首先，你要從題目中抽象出一個自變量x，一個關于x的函數f(x)，以及一個目標值target。

同時，f(x)必須是在x上的單調函數；題目是讓你計算滿足約束條件f(x) == target時的x的值。

具體來說，想要用二分搜索算法解決問題，分為以下幾步：

• 1.確定x， f(x)， target分別是什么，并寫出函數f的代碼；
• 2.找到x的取值范圍作為二分搜索的搜索區間，初始化left和right變量
• 3.根據題目要求，確定應該使用搜索左側還是右側的二分搜索算法，寫出解法代碼?