點擊進入我的博客
1 緒論
線性結(jié)構(gòu)的特點
- 在數(shù)據(jù)元素的非空有限集中艰赞，存在唯一的一個被稱為第一個的數(shù)據(jù)元素
- 存在唯一的一個被稱為最后一個的數(shù)據(jù)元素
- 除第一個之外佣谐，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)
- 除最后一個之外，集合中的每個數(shù)據(jù)元素均只有一個后驅(qū)
常用線性結(jié)構(gòu)
- 線性表
- 棧
- 隊列
- 雙隊列
- 數(shù)組
- 串
2 線性表
線性表是n個數(shù)據(jù)元素的有限隊列方妖，同一線性表中的元素必定具有相同的特性狭魂，即屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。
- 表中元素個數(shù)稱為線性表的長度
- 線性表沒有元素時雌澄，稱為空表
- 表起始位置稱表頭斋泄，表結(jié)束位置稱表尾
2.1 線性表的順序表示和實現(xiàn)
線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，通常是用數(shù)組實現(xiàn)掷伙。在Java語言中是己，主要是java.util.ArrayList實現(xiàn)又兵。
ArrayList初探
-
ArrayList實現(xiàn)了List接口任柜，繼承了AbstractList，一般我們把它認為是可以自增擴容的數(shù)組沛厨。 -
ArrayList是非線程安全的宙地。 - 它實現(xiàn)了
Serializable接口，因此它支持序列化逆皮。 - 實現(xiàn)了
RandomAccess接口宅粥，支持快速隨機訪問（只是個標(biāo)注接口，并沒有實際的方法）电谣，這里主要表現(xiàn)為可以通過下標(biāo)直接訪問（底層是數(shù)組實現(xiàn)的秽梅，所以直接用數(shù)組下標(biāo)來索引）。 - 實現(xiàn)了
Cloneable接口剿牺，能被克隆企垦。 - 底層實現(xiàn)：
ArrayList底層通過一個Object[]來實現(xiàn)的。 - 默認初始容量：
10 - 理論最大容量：
Integer.MAX_VALUE - 8晒来。之所以是理論最大容量是因為需要考慮JVM的內(nèi)存钞诡，如果超出內(nèi)存會報OutOfMemoryError的內(nèi)存溢出錯誤；之所以要減去8是因為數(shù)組對象有一個額外的元數(shù)據(jù)湃崩，用于表示數(shù)組的大小荧降。 - 默認擴容倍數(shù)：
1.5倍。int newCapacity = oldCapacity + (oldCapacity >> 1); -
size：size是數(shù)組中元素的數(shù)量 -
modCount：modCount是ArrayList的父類AbstractList中的變量攒读，默認值為0朵诫，記錄的是關(guān)于元素的數(shù)目被修改的次數(shù)。主要作用是快速失敗機制：由于ArrayList設(shè)計成非線程安全的薄扁，一個線程在對一個集合對象進行迭代操作的同時剪返，其他線程可以修改此ArrayList，如可能引起迭代錯誤的add()或remove()等危險操作泌辫。所以在AbstractList中随夸，使用了一個簡單的機制來規(guī)避這些風(fēng)險，這就是modCount和expectedModCount的作用所在震放。 -
Arrays.copyof()：在擴容等操作時宾毒，需要通過此方法復(fù)制原數(shù)組內(nèi)容到一個新容量的大數(shù)組里（Arrays.copyof方法實際是調(diào)用System.arraycopy方法）。
2.2 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)
線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這組存儲單元可以是連續(xù)的殿遂，也可以是不連續(xù)的）诈铛，所以對數(shù)據(jù)元素而言乙各，除了存儲其本身的信息之外，還需要一個指示其后繼數(shù)據(jù)元素的信息幢竹。
循環(huán)鏈表
- 循環(huán)鏈表：是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)耳峦，它的特點是表中最后一個結(jié)點的指針域指向頭節(jié)點。
- 附加表頭：因為不帶附加表頭在插入刪除時要分兩種情況焕毫，操作節(jié)點在表頭和不在表頭蹲坷；而帶了附加表頭便可以對所有節(jié)點一視同仁。
-
快慢指針（判斷單鏈表是否為循環(huán)鏈表邑飒、判斷鏈表中是否存在環(huán)）：使用快慢2個指針循签，2個指針都從鏈表頭開始遍歷，快指針每次移動2個結(jié)點疙咸，慢指針每次移動1個結(jié)點县匠。若鏈表中存在環(huán)，則快慢2指針后在鏈表的某一位置相遇撒轮，否則它們不會相遇乞旦。
循環(huán)鏈表.png
雙向鏈表
- 雙向鏈表的結(jié)點有兩個指針域，其一指向直接后繼元素题山，另一指向前驅(qū)元素兰粉。
- 雙向鏈表的目的是為了解決在鏈表中不同方向（前/后）訪問元素的問題。
LinkedList初探
-
LinkedList是一個繼承于AbstractSequentialList的雙向鏈表臀蛛。它也可以被當(dāng)作堆棧亲桦、隊列或雙端隊列進行操作。 -
LinkedList實現(xiàn)List接口浊仆，能對它進行隊列操作客峭。 -
LinkedList實現(xiàn)Deque接口，即能將LinkedList當(dāng)作雙端隊列使用抡柿。 -
LinkedList實現(xiàn)了Cloneable接口舔琅，即覆蓋了函數(shù)clone()，能克隆洲劣。 -
LinkedList實現(xiàn)java.io.Serializable接口备蚓，這意味著LinkedList支持序列化。 -
LinkedList是非線程安全的囱稽。 -
LinkedList的Node信息：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
- 由于
LinkedList由于同時實現(xiàn)了List和Deque接口郊尝，所以有多種添加方法的底層是一樣的。 -
Linked允許元素為null战惊。 -
Node<E> node(int index)：該方法返回雙向鏈表中指定位置處的節(jié)點流昏，而鏈表中是沒有下標(biāo)索引的，要指定位置出的元素，就要遍歷該鏈表况凉，從源碼的實現(xiàn)中谚鄙，我們看到這里有一個加速動作。源碼中先將index與長度size的一半比較刁绒，如果index<size/2闷营，就只從位置0往后遍歷到位置index處，而如果index>size/2知市，就只從位置size往前遍歷到位置index處傻盟。這樣可以減少一部分不必要的遍歷。
2.3 LinkedList與ArrayList的區(qū)別：
- ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)初狰，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)莫杈。
- 對于隨機訪問get()和set()互例，ArrayList覺得優(yōu)于LinkedList奢入，因為LinkedList要移動指針。
- 對于新增和刪除操作add和remove媳叨，LinedList比較占優(yōu)勢腥光，因為ArrayList要移動數(shù)據(jù)。
- ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾預(yù)留一定的容量空間糊秆，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗相當(dāng)?shù)目臻g武福，就存儲密度來說，ArrayList是優(yōu)于LinkedList的痘番。
- 當(dāng)操作是在一列數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間,并且需要隨機地訪問其中的元素時,使用ArrayList會提供比較好的性能捉片，當(dāng)你的操作是在一列數(shù)據(jù)的前面或中間添加或刪除數(shù)據(jù),并且按照順序訪問其中的元素時,就應(yīng)該使用LinkedList了。
2.4 其他鏈表
廣義表(Generalized List)
- 廣義表是線性表的推廣
- 對于線性表而言汞舱，n個元素都是基本的單元素
- 廣義表中伍纫，這些元素不僅可以是單元素也可以是另一個廣義表
多重鏈表
- 鏈表中的節(jié)點可能同時隸屬于多個鏈
- 多重鏈表中結(jié)點的指針域會有多個
- 但包含兩個指針域的鏈表并不一定是多重鏈表，比如雙向鏈表不是多重鏈表
- 多重鏈表有廣泛的用途: 基本上如樹昂芜、圖這樣相對復(fù)雜的數(shù)據(jù)結(jié)構(gòu)都可以采用多重鏈表方式實現(xiàn)存儲
3 棧
棧（Stack）是限定只能在表尾進行插入或刪除的線性表莹规。對棧來說，表尾稱為棧頂泌神，表頭稱為棧底良漱。棧又稱為后進先出線性表（LIFO，Last In First Out）欢际。Java中由于java.util.Stack和java.util.Vector先天的設(shè)計問題母市，并不推薦使用；一般使用LinkedList來當(dāng)作棧损趋。
[圖片上傳失敗...(image-b267ad-1582731953399)]
[圖片上傳失敗...(image-72fd67-1582731953399)]
3.1 括號匹配
假設(shè)一個算術(shù)表達式中可以包含兩種括號：圓括號和方括號患久，且這兩種括號可按任意的次序嵌套使用，編寫判別給定表達式中所含括號是否正確配對出現(xiàn)的算法。
步驟如下：
- 在算法中設(shè)置一個棧墙杯，每次讀入一個括號配并；
- 若是右括號，則或者使置于棧頂?shù)淖罴逼鹊钠诖靡韵飧吒洌藭r將棧頂?shù)淖罄ㄌ枏棾龈刃换蛘呤遣缓戏ǖ那闆r，此時將右括號壓入（此處可以優(yōu)化）嫉髓；
- 若是左括號观腊，則作為一個新的更急迫的期待壓入棧中，自然使原有的在棧中的所有未消解的期待的急迫性都降低一級算行；
- 在算法的開始和結(jié)束時梧油，棧應(yīng)該為空。
public static void main(String[] args) {
String str = "[([[]])]";
LinkedList<Character> stack = new LinkedList<>();
for(char ch : str.toCharArray()) {
if (stack.isEmpty()) {
stack.push(ch);
} else if((ch == ']' && stack.peek() == '[') || ch == ')' && stack.peek() == '(') {
stack.pop();
} else {
stack.push(ch);
}
}
System.out.println(stack.isEmpty());
}
3.2 迷宮問題
回溯算法
迷宮問題是棧的典型應(yīng)用州邢，棧通常也與回溯算法連用儡陨，回溯算法的基本描述是：
- 選擇一個起始點；
- 如果已達目的地量淌， 則跳轉(zhuǎn)到 (4)骗村； 如果沒有到達目的地， 則跳轉(zhuǎn)到 (3) ;
- 求出當(dāng)前的可選項呀枢；
3.1 若有多個可選項胚股，則通過某種策略選擇一個選項，行進到下一個位置裙秋，然后跳轉(zhuǎn)到 (2);
3.2 若行進到某一個位置發(fā)現(xiàn)沒有選項時琅拌，就回退到上一個位置，然后回退到 (2) ; - 退出算法摘刑。
迷宮問題偽代碼：
尚需說明一點的是进宝，所謂當(dāng)前位置可通，指的是未曾走到過的通道塊泣侮，即要求該方塊位置不僅是通道塊即彪，而且既不在當(dāng)前路徑上（否則所求路徑就不是簡單路徑），也不是曾經(jīng)納入過路徑的通道塊（否則只能在死胡同內(nèi)轉(zhuǎn)圈）活尊。
do {
若當(dāng)前位置可通隶校，
則 {
將當(dāng)前位置壓入棧頂； // 納入路徑
若當(dāng)前位置是出口位置蛹锰，則結(jié)束深胳；//求得的路徑已在棧中
否則切換當(dāng)前位置的東臨塊為新的當(dāng)前位置；
} 否則 {
若棧不空铜犬，且棧頂位置尚有其它方向未搜索轻庆，
則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一臨塊敛劝；
若棧不空但棧頂位置四周均不可通，
則 {
刪去棧頂位置夸盟；
若棧不空蛾方，則重新測試新的棧頂位置，
直到找到一個可通的相鄰塊或出棧至椛仙拢空桩砰；
}
}
}while(棧不空);
3.3 表達式求值
為實現(xiàn)算符優(yōu)先算法，可以使用兩個工作棧释簿。一個稱做OPTR亚隅，用以寄存運算符；另一個稱做OPND庶溶，用以寄存操作數(shù)或運算結(jié)果煮纵。算法的基本思想如下：
(1) 首先置操作數(shù)棧OPND為空棧渐尿，表達式起始符"#"為運算符棧OPTR的棧底元素砖茸；
(2) 依次讀入表達式中每個字符，若是操作數(shù)則進OPND棧凉夯，若是運算符則和OPTR的棧頂元素符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個表達式求值完畢(即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為"#")采幌。
3.4 遞歸&漢諾塔
遞歸函數(shù)
一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)劲够。
- 很多數(shù)學(xué)函數(shù)是遞歸定義的；
- 有的數(shù)據(jù)結(jié)構(gòu)休傍，如二叉樹征绎、廣義表等，由于結(jié)構(gòu)本身固有的遞歸特性，則它們的操作可遞歸地描述哥放；
- 雖然問題本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解更簡單，如八皇后問題、Hanoi塔問題等。
N階Hanoi塔
假設(shè)有3個分別命名為X击你、Y和Z的塔座鸿摇，在塔座X上插有n階Hanoi塔個直徑大小各不相同拙吉、依小到大編號1,2,...,n的圓盤。現(xiàn)要求將X軸上的n階Hanoi塔個圓盤移至塔座Z上并仍按同樣順序疊排揪荣，圓盤移動時必須遵循下列規(guī)則：
- 每次只能移動一個圓盤筷黔；
- 圓盤可以查在X、Y和Z中的任一塔座上仗颈；
- 任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上佛舱。
3.5 中綴表達式與后綴表達式
中綴表達式
- 運算符號位于兩個運算數(shù)之間
后綴表達式
- 運算符號位于兩個運算數(shù)之后
中綴轉(zhuǎn)后綴：
- 運算數(shù)相對順序不變
- 運算符號順序發(fā)生改變
中綴轉(zhuǎn)后綴方法：
- 運算數(shù)——直接輸出;
- 左括號——壓入堆棧:
- 右括號——將棧頂?shù)倪\算符彈出并輸出,直到遇到左括號（出棧,不輸出）
- 運算符——若優(yōu)先級大于棧頂運算符時，則把它壓棧挨决；若優(yōu)先級小于等于棧頂運算符時请祖，將棧頂運算符彈出并輸出，再比較新的棧頂運算符凰棉，直到該運算符大于棧頂運算符優(yōu)先級為止损拢，然后將該運算符壓棧
- 若各對象處理完畢，則把堆棧中存留的運算符一并輸出撒犀。
4 隊列
- 與棧相反福压，隊列是一種先進先出（FIFO）的線性表掏秩。
- 它只允許在表的一端進行插入，而在另一端刪除元素荆姆。
- 允許插入的一端叫隊尾蒙幻，允許刪除的一端叫隊頭。
鏈隊列——隊列的鏈?zhǔn)奖硎?/h5>
用鏈表表示的隊列簡稱為鏈隊列胆筒。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針（分別稱為頭指針和尾指針）才能唯一確定邮破。和線性表的單鏈表一樣，為了操作方便起見仆救，我們也給鏈隊列添加一個頭結(jié)點抒和，并令頭指針指向頭結(jié)點。由此彤蔽，空的鏈隊列的判斷條件為頭指針和尾指針均指向頭結(jié)點摧莽，如圖所示：
循環(huán)隊列——數(shù)組式隊列改進
在實際使用隊列時，為了使隊列空間能重復(fù)使用顿痪，往往對隊列的使用方法稍加改進：無論插入或刪除镊辕，一旦rear指針增1或front指針增1時超出了所分配的隊列空間，就讓它指向這片連續(xù)空間的起始位置蚁袭。自己真從MaxSize-1增1變到0征懈，可用取余運算rear%MaxSize和front%MaxSize來實現(xiàn)。這實際上是把隊列空間想象成一個環(huán)形空間揩悄，環(huán)形空間中的存儲單元循環(huán)使用卖哎，用這種方法管理的隊列也就稱為循環(huán)隊列。
在循環(huán)隊列中虏束，當(dāng)隊列為空時棉饶，有front=rear，而當(dāng)所有隊列空間全占滿時镇匀，也有front=rear。為了區(qū)別這兩種情況袜啃，規(guī)定循環(huán)隊列最多只能有MaxSize-1個隊列元素汗侵，當(dāng)循環(huán)隊列中只剩下一個空存儲單元時，隊列就已經(jīng)滿了群发。因此晰韵，隊列判空的條件時front=rear，而隊列判滿的條件時front=（rear+1）%MaxSize熟妓。隊空和隊滿的情況如圖：
雙端隊列
雙端隊列雪猪，是限定插入和刪除操作在表的兩端進行的線性表，盡管雙端隊列看起來比棧和隊列靈活起愈，但實際上在應(yīng)用程序中遠不及棧和隊列有用只恨。
5 字符串
- 字符串：是由零個或多個字符組成的有限序列译仗。
- 字串：串中任意個連續(xù)的字符組成的子序列成為該串的字串。
-
回文串：是一個正讀和反讀都一樣的字符串官觅，如
abcba或abba
一年又一年纵菌，字節(jié)跳動 Lark（飛書） 研發(fā)團隊又雙叒叕開始招新生啦！
【內(nèi)推碼】：GTPUVBA
【內(nèi)推鏈接】：https://job.toutiao.com/s/JRupWVj
【招生對象】：20年9月后~21年8月前 畢業(yè)的同學(xué)
【報名時間】：6.16-7.16（提前批簡歷投遞只有一個月抓住機會哦Ｐ莸印）
【畫重點】：提前批和正式秋招不矛盾咱圆！面試成功，提前鎖定Offer功氨；若有失利序苏，額外獲得一次面試機會，正式秋招開啟后還可再次投遞捷凄。
