數(shù)組
定義
數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間盐欺，來存儲(chǔ)一組具有相同類型的數(shù)據(jù)泊柬。
關(guān)鍵點(diǎn)
線性表
數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)，每個(gè)數(shù)據(jù)最多只有前和后兩個(gè)方向杂曲。包含 數(shù)組庶艾、鏈表、隊(duì)列擎勘、棧等咱揍。
非線性表：數(shù)據(jù)之間并不是簡(jiǎn)單的前后關(guān)系。比如 二叉樹棚饵、堆煤裙、圖等。連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)
正是因?yàn)檫@兩個(gè)限制噪漾，數(shù)組才有了 根據(jù)下標(biāo)隨機(jī)訪問 的特性积暖。
但也由于這兩個(gè)限制，也讓刪除怪与、插入數(shù)據(jù)操作變得低效夺刑，為了保證連續(xù)性，需要做大量的數(shù)據(jù)搬移工作。
時(shí)間復(fù)雜度
根據(jù)下標(biāo)隨機(jī)訪問：O(1)
查找：依算法不同二不同（ 比如數(shù)組元素有序遍愿，使用二分查找存淫，為O(logn) ）
插入：平均O(n)
刪除：平均O(n)
鏈表
不需要一塊連續(xù)的內(nèi)存空間，通過“指針”將零散的內(nèi)存塊串聯(lián)起來使用沼填。
常見的鏈表結(jié)構(gòu)有：?jiǎn)捂湵砦ε亍㈦p向鏈表、循環(huán)鏈表坞笙。
單鏈表
由許多節(jié)點(diǎn)串聯(lián)而成岩饼，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)地址的后繼指針，第一個(gè)節(jié)點(diǎn)叫頭節(jié)點(diǎn)薛夜、最后一個(gè)節(jié)點(diǎn)叫尾節(jié)點(diǎn)籍茧，尾節(jié)點(diǎn)的后繼指針指向一個(gè)空地址NULL，表示這是鏈表的最后一個(gè)節(jié)點(diǎn)梯澜。
循環(huán)鏈表
和單鏈表基本一樣寞冯，唯一區(qū)別在于循環(huán)鏈表尾節(jié)點(diǎn)的指針指向了頭節(jié)點(diǎn)。
和單鏈表相比晚伙，優(yōu)點(diǎn)在于從鏈尾到鏈頭比較方便吮龄。當(dāng)要處理的數(shù)據(jù)具有環(huán)形結(jié)構(gòu)特點(diǎn)時(shí)，就比較適合用循環(huán)鏈表咆疗。
雙向鏈表
不僅有后繼指針漓帚，還有指向前一個(gè)節(jié)點(diǎn)地址的前驅(qū)指針。
時(shí)間復(fù)雜度
隨機(jī)訪問：平均O(n)
插入：O(1)
刪除：O(1)
這里插入和刪除的 O(1) 是理論上的午磁，實(shí)際情況并不是尝抖，比如下面兩個(gè)要求：
（1）刪除值等于給定值的節(jié)點(diǎn)
（2）刪除給定指針指向的節(jié)點(diǎn)
第一個(gè)得先找到節(jié)點(diǎn)，然后再進(jìn)行刪除操作漓踢，所以時(shí)間復(fù)雜度是 O(n)。
第二個(gè)雖然不用查找了漏隐，但是必須獲得該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)喧半，所以對(duì)于單鏈表還是 O(n) ，雙向鏈表就是 O(1) 了青责。
知識(shí)問答
問：數(shù)組根據(jù)下標(biāo)隨機(jī)訪問是如何實(shí)現(xiàn)的呢挺据？
計(jì)算機(jī)會(huì)給每個(gè)內(nèi)存單元分配一個(gè)地址，計(jì)算機(jī)通過地址來訪問內(nèi)存中的數(shù)據(jù)脖隶。當(dāng)計(jì)算機(jī)想要隨機(jī)訪問數(shù)組中的某個(gè)元素時(shí)扁耐，會(huì)先根據(jù)下面的尋址公式，計(jì)算出該元素的內(nèi)存地址产阱，然后根據(jù)地址訪問元素婉称。
a[i]_address = base_address + i * data_type_size-
問：數(shù)組和鏈表的區(qū)別？
- 數(shù)組的缺點(diǎn)就是大小固定，一經(jīng)聲明就要占用整塊的連續(xù)內(nèi)存空間王暗，如果聲明的數(shù)組過大悔据，可能會(huì)沒有內(nèi)存可以分配給它，導(dǎo)致內(nèi)存不足俗壹，如果聲明的數(shù)組過小科汗，可能不夠用，需要再聲明一個(gè)更大的內(nèi)存空間绷雏，把原數(shù)組拷貝過去头滔，比較費(fèi)時(shí)；而鏈表本身沒有大小限制涎显，天然支持動(dòng)態(tài)擴(kuò)容坤检。
- 數(shù)組支持隨機(jī)訪問，根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度為O(1)棺禾，插入缀蹄、刪除操作的平均時(shí)間復(fù)雜度為O(n)。
- 鏈表適合插入膘婶、刪除缺前，時(shí)間復(fù)雜度為O(1)，隨機(jī)訪問的平均時(shí)間復(fù)雜度為O(n)悬襟。
算法編程
- 反轉(zhuǎn)一個(gè)單鏈表衅码。示例：
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
答：
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function reverseList($head) {
$cur = $head;
$prev = null;
while ($cur) {
$nextTmp = $cur->next;
$cur->next = $prev;
$prev = $cur;
$cur = $nextTmp;
}
return $prev;
}
}
- 兩兩交換鏈表中的節(jié)點(diǎn)。
給定一個(gè)鏈表脊岳，兩兩交換其中相鄰的節(jié)點(diǎn)逝段，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值割捅，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換奶躯。
示例：
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
答：
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function swapPairs($head) {
$newHead = new ListNode();
$pre = $newHead;
$pre->next = $head;
while ($pre->next && $pre->next->next) {
$a = $pre->next;
$b = $a->next;
$a->next = $b->next;
$b->next = $a;
$pre->next = $b;
$pre = $a;
}
return $newHead->next;
}
}
- 給定一個(gè)鏈表，判斷鏈表中是否有環(huán)亿驾。
解法思路：- 不斷判斷下一個(gè)節(jié)點(diǎn)是否存在嘹黔，如果有環(huán)，就死循環(huán)了
- 用一個(gè)Set記錄節(jié)點(diǎn)的地址莫瞬，不斷判斷下一個(gè)節(jié)點(diǎn)的地址是否在Set中儡蔓，這樣時(shí)間和空間都是 O(n)
- 龜兔賽跑，拿出兩個(gè)指針疼邀，一個(gè)每次走一步（慢）喂江，一個(gè)每次走兩步（快），如果有環(huán)旁振，兩個(gè)指針肯定會(huì)相遇
答：
class Solution {
/**
* @param ListNode $head
* @return Boolean
*/
function hasCycle($head) {
$slow = $fast = $head;
while ($slow && $fast && $fast->next) {
$slow = $slow->next;
$fast = $fast->next->next;
if ($slow == $fast) {
return true;
}
}
return false;
}
}
