o(n),n代表num大小

o(1)常量，與num無瓜

左：時(shí)間復(fù)雜度O(n)空間O(1) 右：空間復(fù)雜度O(n)時(shí)間O(1)

看空間復(fù)雜度，找變量，如果變量始終是常量，則是O(1)

常用空間復(fù)雜度

遞歸也是O(n)

時(shí)間復(fù)雜度一樣，空間復(fù)雜度越小越好；空間復(fù)雜度一樣，時(shí)間復(fù)雜度越小越好。

面試時(shí)把時(shí)間最好的方法和空間最好的方法都告訴他，工作時(shí)選最快的那個(gè)

數(shù)組的定義

區(qū)分1：元素和索引

區(qū)分2：數(shù)組訪問和數(shù)組搜索

對任意數(shù)據(jù)結(jié)構(gòu)都會(huì)涉及四種方法

數(shù)組訪問例子

數(shù)組自帶屬性：第一個(gè)元素所帶位置

搜索例子

插入例子

刪除例子

數(shù)組特點(diǎn)：適合讀，不適合寫

數(shù)組常用操作

練習(xí)題

創(chuàng)建數(shù)組

添加元素

1、直接把4添加到3后面 O(1)

2、3后面的位置被另一個(gè)變量占領(lǐng)，在內(nèi)存空間中另外找一塊能存4個(gè)元素的空間，把1、2、3挪過來，再添加4 O(n)

O(n)：在中間添加元素

訪問元素

更新元素

刪除元素：三種方法

獲取數(shù)組長度

遍歷數(shù)組：3種方法

查找某元素

數(shù)組排序

偽代碼

鏈表

每一個(gè)節(jié)點(diǎn)：當(dāng)前元素+指針（指向下一元素）

最后一個(gè)指針指向null節(jié)點(diǎn)，代表當(dāng)前鏈表結(jié)束

兩種鏈表：單鏈表、雙端鏈表（力扣不需要）

鏈表的四個(gè)重要功能

特點(diǎn)：寫得快、讀得慢

鏈表的常用操作

鏈表練習(xí)題

創(chuàng)建鏈表

添加元素

訪問元素

搜索元素：找索引

更新元素

刪除元素

僅僅一個(gè)刪除操作是O(1)，但我們要先找到元素位置，所以是O(N)

獲取鏈表長度

203移除鏈表元素

隊(duì)列特點(diǎn)：先到先得

兩種：單端隊(duì)列、雙端隊(duì)列（用不多）

隊(duì)列四種操作

隊(duì)列常用操作

推薦練習(xí)題

單端隊(duì)列的操作方法

創(chuàng)建隊(duì)列

添加元素

獲取元素

刪除元素

隊(duì)列為空判斷

遍歷隊(duì)列

933題思路

偽代碼

棧在計(jì)算機(jī)中的應(yīng)用 瀏覽器后退

棧的操作復(fù)雜度分析

棧的常用操作

練習(xí)題

創(chuàng)建、添加

獲取、刪除棧頂元素

棧的大小、是否為空

棧的便利（重點(diǎn)）

chua一下

哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以chua一下

數(shù)組可以根據(jù)索引chua一下定位

編程語言里的哈希表

哈希碰撞

解決方法：變成鏈表

數(shù)據(jù)結(jié)構(gòu)分析

哈希表常用操作

練習(xí)題

496是上一章節(jié)刷過的，用了2個(gè)棧，這里用1個(gè)棧+1個(gè)哈希表

哈希表創(chuàng)建（直接用字典也可以）

添加元素（分?jǐn)?shù)組和字典）

修改元素

刪除元素

獲取元素

檢查key存在？

哈希表長度

集合作用

集合的分類

哈希集合

集合的分析

集合的常用操作

習(xí)題

創(chuàng)建集合、添加元素

搜索、刪除元素

長度

樹的高度、深度、層（易混淆）

二叉樹

二叉樹的遍歷

習(xí)題

什么樣的完全二叉樹是堆

分析數(shù)據(jù)結(jié)構(gòu)

堆的添加和刪除為啥是logn

堆的常用操作

練習(xí)題

堆的刪除

堆化操作：一組數(shù)-->完全二叉樹

時(shí)間復(fù)雜度分析：轉(zhuǎn)二叉樹O(n)，將二叉樹轉(zhuǎn)化為最小堆也是O(n)

首先導(dǎo)入模塊heapq

創(chuàng)建堆，使用函數(shù)heapify()

添加元素，使用函數(shù)heappush()

堆頂元素，打印第一個(gè)元素

刪除堆頂元素heappop()

堆的遍歷（邊刪除邊遍歷）

樹和圖節(jié)點(diǎn)關(guān)系

有向圖

權(quán)重圖

雙指針是什么

case 1：有序數(shù)組

普通雙指針:時(shí)間復(fù)雜度n方

利用有序特性：對撞雙指針,時(shí)間復(fù)雜度n

快慢雙指針舉例

case 2

習(xí)題

二分查找法：0-100找23

怎么遇到呢

使用條件：必須是有序數(shù)組

如果無序

習(xí)題

經(jīng)典題，反復(fù)刷，強(qiáng)化記憶

索引中間值

滑動(dòng)窗口目的：減少while循環(huán)

常規(guī)方法的問題（重合的數(shù)相加）

滑動(dòng)窗口思路

定長問題：滑動(dòng)窗口

遞歸4要素

舉例子：斐波那契

習(xí)題

分治法主要思想

舉例子

多數(shù)元素

分治法思路

偽代碼

回溯法一個(gè)生活中的例子

經(jīng)典的回溯

偽代碼

深度優(yōu)先DFS

DFS主要應(yīng)用和例子

例子：子集

DFS和回溯法的區(qū)別

遞歸法

BFS方法

BFS思想

例子

union find：一直找根節(jié)點(diǎn)

生活中的例子

編程如何實(shí)現(xiàn)

模板

quick find

quick union

比較兩棵樹的高，矮的樹連接到高的樹

核心思想

例子：零錢兌換問題

例子：不能湊整

回溯：不取5，取次優(yōu)解3

目的：減少重復(fù)計(jì)算

入門例子

動(dòng)態(tài)規(guī)劃三要素和整個(gè)過程

動(dòng)態(tài)規(guī)劃能干嘛

前綴樹的應(yīng)用：百度自動(dòng)匹配

操作