數據結構與算法
數據結構定義
數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。
- 數組：物理存儲單元上連續、順序的存儲結構
- 鏈表：鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。
- 隊列：隊列（queue）是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。隊列的實現方式如下：
- 基于鏈表來實現隊列。
- 使用linkedList來實現隊列。
- 使用兩個棧來實現一個隊列。
- 棧：棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。
- 堆：堆通常是一個可以被看做一棵完全二叉樹的數組對象。將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆。建堆時間復雜度O（n），堆總是滿足下列性質：堆總是一棵完全二叉樹；堆中某個結點的值總是不大于或不小于其父結點的值；
- 散列表：（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構
- 樹：是元素的集合。樹有多個節點(node)，用以儲存元素。某些節點之間存在一定的關系，用連線表示，連線稱為邊(edge)。邊的上端節點稱為父節點，下端稱為子節點。樹像是一個不斷分叉的樹根。嚴格定義：
- 樹是元素的集合。
- 該集合可以為空。這時樹中沒有元素，我們稱樹為空樹 (empty tree)。
- 如果該集合不為空，那么該集合有一個根節點，以及0個或者多個子樹。根節點與它的子樹的根節點用一個邊(edge)相連。
- 二叉樹（binary tree）是指樹中節點的度不大于2的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹。
- 圖：是由頂點的有窮非空集合和頂點之間邊的集合組成，通過表示為G(V,E)，其中，G標示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。
堆的創建、插入、刪除、堆排序
- 堆的插入：在已經建成的最小堆的后面插入元素，堆的結構可能被破壞，再向上調整使其滿足性質。
- 堆的刪除：刪除時每次刪除堆頂元素
??刪除方法：
- 將堆中最后一個元素代替堆頂元素。
- 將堆中元素個數減少一個，相當于將堆中最后一個元素刪除。
- 此時堆的結構可能被破壞，在向下調整使其滿足性質。
- 堆排序：
- 將堆頂元素與第size-1個元素交換。
- hp->size–
- 將其余的元素調整為最小堆
- 重復1、2、3步hp->size-1次。
樹
- AVL樹
平衡二叉搜索樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。查詢logN、增刪的復雜度N。
- 哈夫曼樹
給定N個權值作為N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
跳表
跳表，是基于鏈表實現的一種類似"二分"的算法。它可以快速地實現增，刪，改，查操作。這種鏈表加多級索引的結構，就叫做跳表。跳表的查詢時間復雜度可以達到O(logn)。跳表也可以實現高效的動態更新，定位到要插入或者刪除數據的位置需要的時間復雜度為O(logn)，最壞O(N)。
在插入的時候，我們需要考慮將要插入的數據也插入到索引中去。在這里使用的策略是通過隨機函數生成一個隨機數K，然后將要插入的數據同時插入到k級以下的每級索引中。https：//www.jianshu.com/p/43039adeb122
排序算法
見網址（https：//www.rzrgm.cn/onepixel/articles/7674659.html）
- 排序算法穩定性
- 定義：指待排序的序列中有兩相鄰元素相等，排序之后它們的先后順序不變。
- 不同條件下，排序方法的選擇
- 若n較小(如n≤50)，可采用直接插入或直接選擇排序。當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插入，應選直接選擇排序為宜。
- 若文件初始狀態基本有序(指正序)，則應選用直接插入、冒泡或隨機的快速排序為宜；
- 若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。
- 快速排序是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
- 堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
- 若要求排序穩定，則可選用歸并排序。
- TopK或優先隊列通常用堆排序來實現
- 快速排序基準值的選取及優化：三數取中+插排+聚集相等元素（在一次分割結束后，可以把與Key相等的元素聚在一起，繼續下次分割時，不用再對與key相等元素分割）
void QSort(int arr[],int low,int high) { int first = low; int last = high;
int left = low; int right = high;
int leftLen = 0; int rightLen = 0;
//待排序序列的長度小于10使用插入排序 if (high - low + 1 < 10) { InsertSort(arr,low,high); return; }
//一次分割 int key = SelectPivotMedianOfThree(arr,low,high);//使用三數取中法選擇樞軸
while(low < high) { while(high > low && arr[high] >= key) { //處理相等元素 if (arr[high] == key) { swap(arr[right],arr[high]); right--; rightLen++; } high--; } arr[low] = arr[high]; while(high > low && arr[low] <= key) { if (arr[low] == key) { swap(arr[left],arr[low]); left++; leftLen++; } low++; } arr[high] = arr[low]; } arr[low] = key;
//一次快排結束 //把與樞軸key相同的元素移到樞軸最終位置周圍 int i = low - 1; int j = first; while(j < left && arr[i] != key) { swap(arr[i],arr[j]); i--; j++; } i = low + 1; j = last; while(j > right && arr[i] != key) { swap(arr[i],arr[j]); i++; j--; } QSort(arr,first,low - 1 - leftLen); QSort(arr,low + 1 + rightLen,last); }
/*函數作用：取待排序序列中low、mid、high三個位置上數據，選取他們中間的那個數據作為樞軸*/ int SelectPivotMedianOfThree(int arr[],int low,int high) { //計算數組中間的元素的下標 int mid = low + ((high - low) >> 1); //使用三數取中法選擇樞軸 //目標: arr[mid] <= arr[high] if (arr[mid] > arr[high]) { swap(arr[mid],arr[high]); } //目標: arr[low] <= arr[high] if (arr[low] > arr[high]) { swap(arr[low],arr[high]); } //目標: arr[mid] >= arr[low] if (arr[low] > arr[mid]) { swap(arr[low],arr[mid]); } //此時，arr[low] <= arr[mid] <= arr[high] return arr[mid]; } |
- Bitmap位圖算法
https：//blog.csdn.net/lucky52529/article/details/90172264
位圖是指內存中連續的二進制位，用于對大量的整型數據做去重和查詢。Bit-map就是用一個bit位來標記某個元素對應的Value，而Key即是該元素。由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。
- bitmap應用
1）可進行數據的快速查找、判重、刪除，一般來說數據范圍是int的10倍以下。
2）去重數據而達到壓縮數據
位圖只是可以映射數字類型的數據，變成字符串以及其他文件好像就不再那么得心應手了，這時就要使用布隆過濾器
布隆過濾器
bloom算法類似一個位圖，用來判斷某個元素（key）是否在某個集合中。和一般的位圖不同的是，這個算法無需存儲key的值，對于每個key，只需要k個比特位，每個存儲一個標志，用來判斷key是否在集合中。
應用場景：比如網絡爬蟲抓取時url去重，郵件提供商反垃圾黑名單Email地址去重，之所以需要k個比特位是因為我們大多數情況下處理的是字符串，那么不同的字符串就有可能映射到同一個位置，產生沖突。
優點：不需要存儲key，節省空間
缺點：算法判斷key在集合中時，有一定的概率key其實不在集合中，已經映射的數據無法刪除
（Tire）字典樹
定義：又稱單詞查找樹，Tire樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和保存大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
- 3個基本性質：
- 根節點不包含字符，除根節點外每一個節點都只包含一個字符；
- 從根節點到某一節點路徑上經過的字符連接起來，為該節點對應的字符串；
- 每個節點的所有子節點包含的字符都不相同。
海量數據找出前K大的數
top K類問題，通常比較好的方案是分治+Tire樹/hash+小頂堆，即先將數據集按照Hash方法分解成多個小數據集，然后使用Trie樹或者Hash統計每個小數據集中的query詞頻，之后用小頂堆求出每個數據集中出現頻率最高的前K個數，最后在所有top K中求出最終的top K。
2個2T文件qq號交集
- 布隆過濾器（有兩個文件，分別有20億個QQ號（bigint類型，8字節），我們只有2G內存，如何找到兩個文件交集？）
- 步驟1: 使用hash函數將第一個文件的所有整數映射到10個文件中，每個文件有2億個整數，大約1600M內存，2G的內存就可以放下了，把10個文件記為a1,a2,....,a10;
- 步驟2：用同樣的hash函數映射第二個文件到10個文件中，這10個文件記為b1,b2,b3,......,b10；
- 步驟3：由于使用的是相同的hash函數，所以兩個文件中一樣的數字會被分配到文件下標一致的文件中，分別對a1和b1求交集，a2和b2求交集，ai和bi求交集；
- 步驟4：最后將步驟3的結果匯總，即為兩個文件的交集。
- Bit位枚舉
直接用bit位來枚舉，假設QQ號最長11個號碼，那么就是2^37的大小，就是用37位bit表示所有QQ。然后我們再對應每個37bit之外用2bit記錄，第一個文件和第二個文件有沒有
- 00 表示都沒有
- 10 表示僅第一個文件有
- 01 同理僅第二個文件有
- 11 表示兩個文件都有此QQ號
所以就是39個bit位，我們可以用一個int 32位，和一個char 8 位來一個記錄
海量數據排序——1TB的數據需要排序，但只有32GB的內存如何排序處理？
- 把磁盤上的1TB數據分割為40塊（chunks），每份25GB。（注意，要留一些系統空間！）
- 順序將每份25GB數據讀入內存，使用quick sort算法排序。
- 把排序好的數據（也是25GB）存放回磁盤。
- 循環40次，現在，所有的40個塊都已經各自排序了。（剩下的工作就是如何把它們合并排序！）
- 從40個塊中分別讀取25G/40=0.625G入內存（40 input buffers）。
- 執行40路合并，并將合并結果臨時存儲于2GB 基于內存的輸出緩沖區中。當緩沖區寫滿2GB時，寫入硬盤上最終文件，并清空輸出緩沖區；當40個輸入緩沖區中任何一個處理完畢時，寫入該緩沖區所對應的塊中的下一個0.625GB，直到全部處理完成。
- 優化
磁盤I/O通常是越少越好（最好完全沒有），那么如何降低磁盤I/O操作呢？關鍵就在第5和第6步中的40路輸入緩沖區，我們可以先做8路merge sort，把每8個塊合并為1路，然后再做5-to-1的合并操作。
五大查找方式
常見搜索算法
- 廣度優先搜索（BFS）：是一種盲目搜尋法，目的是系統地展開并檢查圖中的所有節點，以尋找結果。換句話說，它并不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。
- 能夠解決的問題：
- 第一類問題：從節點A出發，有前往節點B的路徑嗎？
- 第二類問題：從節點A出發，前往節點B的哪條路徑最短？
- 工作原理
- Peggy既是Alice的朋友又是Bob的朋友，因此她將被加入隊列兩次：檢查完一個人后，應將其標記為已檢查，且不再檢查他。
![]()
- 算法實現：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.concurrent.LinkedBlockingQueue;
public class BFS {
/**
* 打印出到達節點target所經過的各個節點信息
* @param target
*/
static void printSearPath(Node target) {
if (target != null) {
System.out.print("找到了目標節點:" + target.id + "\n");
List<Node> searchPath = new ArrayList<Node>();
searchPath.add(target);
Node node = target.parent;
while(node!=null) {
searchPath.add(node);
node = node.parent;
}
String path = "";
for(int i=searchPath.size()-1;i>=0;i--) {
path += searchPath.get(i).id;
if(i!=0) {
path += "-->";
}
}
System.out.print("步數最短："+path);
} else {
System.out.print("未找到了目標節點");
}
}
static Node findTarget(String startId,String targetId,HashMap<String,String[]> map) {
List<String> hasSearchList = new ArrayList<String>();
LinkedBlockingQueue<Node> queue=new LinkedBlockingQueue<>();
queue.offer(new Node(startId,null));
while(!queue.isEmpty()) {
Node node = queue.poll();
if(hasSearchList.contains(node.id)) {
continue;
}
System.out.print("判斷節點:" + node.id +"\n");
if (targetId.equals(node.id)) {
return node;
}
hasSearchList.add(node.id);
if (map.get(node.id) != null && map.get(node.id).length > 0) {
for (String childId : map.get(node.id)) {
queue.offer(new Node(childId,node));
}
}
}
return null;
}
static class Node{
public String id;
public Node parent;
public Node(String id,Node parent) {
this.id = id;
this.parent = parent;
}
}
public static void main(String[] args) {
HashMap<String,String[]> hashMap=new HashMap<>();
hashMap.put("YOU",new String[]{"CLAIRE","ALICE","BOB"});
hashMap.put("CLAIRE",new String[]{"YOU","JONNY","THON"});
hashMap.put("JONNY",new String[]{"CLAIRE"});
hashMap.put("THOH",new String[]{"CLAIRE"});
hashMap.put("ALICE",new String[]{"YOU","PEGGY"});
hashMap.put("BOB",new String[]{"YOU","PEGGY","ANUJ"});
hashMap.put("PEGGY",new String[]{"BOB","ALICE"});
hashMap.put("ANUJ",new String[]{"BOB"});
Node target = findTarget("YOU","ANUJ",hashMap);
//打印出最短路徑的各個節點信息
printSearPath(target);
}
}
- 深度優先搜索（DFS）：深度優先搜索是圖論中的經典算法，利用深度優先搜索算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。
- 對于下面的樹而言，DFS方法首先從根節點1開始，其搜索節點順序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中優先選擇左分枝）。
![]()
- 從stack中訪問棧頂的點；
![]()
- 找出與此點鄰接的且尚未遍歷的點，進行標記，然后放入stack中，依次進行；
![]()
- 如果此點沒有尚未遍歷的鄰接點，則將此點從stack中彈出，再按照（3）依次進行；
![]()
![]()
- 直到遍歷完整個樹，stack里的元素都將彈出，最后棧為空，DFS遍歷完成。
![]()
![]()
- 爬山法（Hill Climbing）：DFS的變形，不同的是每次選擇的是最優的一個子結點，即局部最優解
- 建立一個棧，將根結點放入棧
- 判斷棧頂元素是否是目標結點，如果是，算法結束，如果不是，進入第三步
- 棧頂元素出棧，根據評估函數計算的順序將此結點的子結點入棧
- 如果棧空，則輸出失敗，否則，進入第二步
- 最佳優先算法（Best-first search strategy） ：是DFS和BFS的結合，每次找到的是所有結點中最好估計值的那個結點，找到的是全局最優解
- 根據評估函數建立一個堆（或用優先隊列），將根結點放入堆中
- 判斷棧頂元素是否是目標結點，如果是，算法結束，如果不是，進入第三步
- 移出堆頂元素結點，將此結點的所有子結點加入堆
- 如果堆空，輸出失敗，否則，進入第二步
- 回溯法 （Backtracking）：找到所有選擇，走不通則回溯
- 建立一個問題的部分解v=(a1,a2,...,ak)
- 若這個部分解是可行解，則繼續，若不是可行解，刪除ak，加入ak情況的另一種可能
- 若ak的可能已經遍歷完，回溯并尋找ak-1的下一個可能
- 分支限界算法（Branch-and-bound Search Algorithm）：分支限界算法可以用來尋找最優解，在平均情況下不必窮盡搜索。用一種方法預測一系列解的最小界（lower bound），用一種方法預測最優解的最大界（upper bound）。如果一個解的最小界超出了整個解空間的最大界，那么這個解不可能是最優的，我們就可以提前終止此分支，分支界限適合最小化問題
- A*算法：對于優先隊列，每取出一個結點n，將他的所有兒子結點n'放入優先隊列，優先級由函數f(n)計算出
BFS、DFS優缺點
- 深搜優缺點
- 優點
- 能找出所有解決方案
- 優先搜索一棵子樹，然后是另一棵，所以和廣搜對比，有著內存需要相對較少的優點
- 缺點
- 要多次遍歷，搜索所有可能路徑，標識做了之后還要取消。
- 在深度很大的情況下效率不高
- 廣搜優缺點
- 優點
- 對于解決最短或最少問題特別有效，而且尋找深度小
- 每個結點只訪問一遍，結點總是以最短路徑被訪問，所以第二次路徑確定不會比第一次短
- 缺點
- 內存耗費量大（需要開大量的數組單元用來存儲狀態）
動態規劃
- 核心思想：將大問題分為小問題進行解決，從而一步步獲得最優解的處理算法，與分治算法不同的是適合于動態規劃求解的問題，經分解得到的子問題往往不是相互獨立的。
- 求解方式：填表
- 思想：w[i]為第i個商品的重量，v[i]代表第i個商品的價值，v[i][j]表示在前i個物品中能夠裝入容量為j的背包中的最大價值
- v[i][0]=v[0][j]=0；//使得i和j剛好和第幾個商品對應
- 當w[i]>j時：v[i][j]=v[i-1][j]；//當準備加入新增的商品的容量w[i]大于當前背包的容量j時就直接使用上一單元格的裝入策略
- 當w[i]<=j時：v[i][j]=max{v[i-1][j]， v[i]+v[i-1][j-w[i]]}；
//上一個單元格的裝入的最大值v[i-1][j]
//v[i]當前商品的價值
//v[i-1][j-w[i]]裝入i-1個商品剩余空間j-w[i]的最大值
//根據前面得到公式來動態規劃處理
for(int i = 1; i < v.length; i++) {//不處理第一行i是從1開始的
for(int j=1; j < v[0].length; j++){//不處理第一列，j是從1開始的
//公式
if(w[i-1]> j){//因為我們程序i是從1開始的，因此原來公式中的w[i]修改成w[i-1]
v[][j]=v[i-1][j];
}else{
//說明:
//因為我們的i從1開始的,因此公式需要調整成
//v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
v[][j]=Math.max(v[i-1][j], val[i]+v[i-1][j-w[i-1]]);
}
}
}
什么樣的題適合用動態規劃？
- 最值型動態規劃，比如求最大，最小值是多少
- 計數型動態規劃，比如換硬幣，有多少種換法
- 坐標型動態規劃，比如在m*n矩陣求最值型，計數型，一般是二維矩陣
- 區間型動態規劃，比如在區間中求最值
暴力匹配算法
public static int ViolenceMatch(String str1， String str2) {
char[] s1 = str1.toCharArray()；
char[] s2 = str2.toCharArray()；
int i = 0；
int j = 0；
while (i < s1.length && j < s2.length) {
if (s1[i] == s2[j]) {
i++；
j++；
} else {
i = i - (j - 1)；
j = 0；
}
}
if (j == s2.length) {
return i - j；
}
return -1；
}
KMP算法
- 建立部分匹配表
搜索詞 | A | B | C | D | A | B | D |
部分匹配值 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
移動位數 = 已匹配的字符數 – 對應的部分匹配值
public static int[] KmpMatchTable(String str) {
int[] matchTable = new int[str.length()]；
matchTable[0] = 0；
for (int i = 1， j = 0； i < str.length()； i++) {
//不等時重新獲取前一個的值，kmp算法核心
while (j > 0 && str.charAt(i) != str.charAt(j)) {
j = matchTable[j - 1]；
}
//部分匹配則值+1
if (str.charAt(i) == str.charAt(j)) {
j++；
}
matchTable[i] = j；
}
return matchTable；
}
- KMP搜索
public static int KMPMatch(String str1， String str2) {
int[] matchTable=KmpMatchTable(str2)；
for (int i = 0，j=0； i < str1.length()； i++) {
//處理不等情況
while(j>0&&str1.charAt(i)!=str2.charAt(j)){
j = matchTable[j-1]；
}
if (str1.charAt(i)==str2.charAt(j)){
j++；
}
if (j==str2.length()){
return i-j+1；
}
}
return -1；
}
貪心算法
- 概念：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，它所做出的僅僅是在某種意義上的局部最優解。
- 基本思路
- 建立數學模型來描述問題
- 把求解的問題分成若干個子問題
- 對每個子問題求解，得到子問題的局部最優解
- 把子問題的解局部最優解合成原來問題的一個解
- 存在的問題
- 不能保證求得的最后解是最佳的
- 不能用來求最大值或最小值的問題
- 只能求滿足某些約束條件的可行解的范圍
普利姆算法（prim）
- 求最小生成樹
- 普里姆算法介紹
- 普利姆(Prim)算法求最小生成樹，也就是在包含n個頂點的連通圖中，找出只有(n-1)條邊包含所有n個頂點的連通子圖，也就是所謂的極小連通子圖
- 普利姆的算法如下:
- 設G=(V,E)是連通網，T=(U,D)是最小生成樹，V,U是頂點集合，E,D是邊的集合
- 若從頂點u開始構造最小生成樹，則從集合V中取出頂點u放入集合U中，標記頂點v的visited[u]=1
- 若集合U中頂點ui與集合V-U中的頂點vj之間存在邊，則尋找這些邊中權值最小的邊，但不能構成回路，將頂點vj加入集合U中，將邊（ui,vj）加入集合D中，標記visited[vj]=1
- 重復步驟②，直到U與V相等，即所有頂點都被標記為訪問過，此時D中有n-1條邊
- 提示：單獨看步驟很難理解，我們通過代碼來講解，比較好理解.
二叉樹的中序遍歷
List<Integer> list = new ArrayList<>()；
public TreeNode increasingBST(TreeNode root) {
if(null==root)return null；
Deque<TreeNode> queue = new ArrayDeque<>()；
while(root!=null||!queue.isEmpty()){
while(root!=null){
queue.add(root)；
root = root.left；
}
root = queue.pollLast()；
list.add(root.val)；
root=root.right；
}
return list；
}
二叉樹層序遍歷
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>()；
Queue<TreeNode> queue = new ArrayDeque<>()；
if (root != null) {
queue.add(root)；
}
while (!queue.isEmpty()) {
int n = queue.size()；//記錄節點個數
List<Integer> level = new ArrayList<>()；
//遍歷每個節點的左右子節點
for (int i = 0； i < n； i++) {
TreeNode node = queue.poll()；
level.add(node.val)；
if (node.left != null) {
queue.add(node.left)；
}
if (node.right != null) {
queue.add(node.right)；
}
}
res.add(level)；
}
return res；
}
二叉樹之字形打印
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>()；
if (root == null){
return res；
}
//創建隊列，保存節點
Queue<TreeNode> queue = new LinkedList<>()；
queue.add(root)；//先把節點加入到隊列中
boolean leftToRight = true；//第一步先從左邊開始打印
while (!queue.isEmpty()) {
//統計這一層有多少個節點
int count = queue.size()；
//記錄每層節點的值
List<Integer> level = new ArrayList<>()；
//遍歷這一層的所有節點，把他們全部從隊列中移出來，順便
//把他們的值加入到集合level中，接著再把他們的子節點（如果有）
//加入到隊列中
for (int i = 0； i < count； i++) {
//poll移除隊列頭部元素（隊列在頭部移除，尾部添加）
TreeNode node = queue.poll()；
//判斷是從左往右打印還是從右往左打印。
if (leftToRight) {
//如果從左邊打印，直接把訪問的節點值加入到列表level的末尾
level.add(node.val)；
} else {
//如果是從右邊開始打印，每次要把訪問的節點值加入到列表的最前面
level.add(0， node.val)；
}
//左右子節點如果不為空會被加入到隊列中
if (node.left != null){
queue.add(node.left)；
}
if (node.right != null){
queue.add(node.right)；
}
}
//把這一層的節點值加入到集合res中
res.add(level)；
//改變下次訪問的方向
leftToRight = !leftToRight；
}
return res；
}
判斷A是否是B的子樹
public class Solution {
//分為兩個函數，一個用于遍歷節點當做子樹的根節點，
public boolean hasSubtree(TreeNode root1，TreeNode root2) {
if(root1==null||root2==null) return false；
//直接判斷isSubTree(root1，root2)，并且采取||的方式確定結果。
return isSubTree(root1，root2)||hasSubtree(root1.left，root2)
||hasSubtree(root1.right，root2)；
}
//另一個用于判斷是否是子樹（必須要root2先空）
public boolean isSubTree(TreeNode root1，TreeNode root2){
if(root2==null) return true；
if(root1==null) return false；
if(root1.val==root2.val){
return isSubTree(root1.left，root2.left)&&
isSubTree(root1.right，root2.right)；
}else{
return false；
}
}
}
最小硬幣數
- 動態規劃算法題：給定不同面額的硬幣數組coins和總額amounts，求能夠組成總額的最小硬幣數。如coins=[1，2，5]，amounts=11，那么最少硬幣數為5+5+1=3.
public static int CoinsChange(int[] coins， int amount， int coinSize) {
if (null == coins || amount == 0) return -1；
int[] temp = new int[amount + 1]；
for (int i = 0； i <= amount； i++) {
temp[i] = amount + 1；
}
temp[0] = 0；
for (int i = 1； i <= amount； i++) {
for (int j = 0； j < coinSize； j++) {
if (i >= coins[j]) {
temp[i] = Math.min(temp[i]， 1 + temp[i - coins[j]])；
}
}
}
return temp[amount] > amount ? -1 ： temp[amount]；
}
二叉樹反轉左右子樹
public class Solution {
public TreeNode InvertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode tmp = root.left;
root.left = InvertTree(root.right);
root.right = InvertTree(tmp);
return root;
}
}
查找鏈表的倒數第k個節點
/**
*通過兩個指針p1,p2，首先讓p1往前走k-1步，然后讓p1,p2一起往前走，當p1走到尾的時候，p2即為倒數第k個。總共走了n次。時間復雜度為O(n).
*/
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode p1 = head;
ListNode p2 = head;
int temp=0;
while(p1.next!=null){
if(temp==k-1){
break;
}
p1=p1.next;
temp++;
}
while(p1.next!=null){
p1=p1.next;
p2=p2.next;
}
return p2;
}
判斷數組是否為搜索二叉樹的后序遍歷
二叉樹的后序遍歷：左孩子—>右孩子—> 父結點
- step1:如果一個數組arr是搜索二叉樹的后序遍歷結果，那arr的最后一個元素就是樹的根結點root
- step2:去掉最后一個元素arr[End]=root后, arr可以分成兩段，(前一段 = 左子樹）小于root，(后一段 = 右子樹)大于root
- step3: 分別遞歸前后兩段，如果這（兩段 = 子樹）都是符合上述規則的。則輸出true，否則輸出false
public class verifySquenceOfBSTpostOrder {
public boolean solve(int[] arr){
if(arr == null || arr.length == 0){
return true;
}
return judge(arr,0,arr.length-1);
}
boolean judge(int[] arr, int Start, int End){
if(Start >= End){return true;}
//找到，根節點位置
int i = End ;
//找到左右子樹臨界位置
while (i > 0 && arr[i-1] > arr[End]){
--i;
}
//判斷左邊部分是不是都小于根節點
for( int j = i-1; j > 0; --j){
if(arr[j] > arr[End])
return false;
}
//分別遞歸左右子樹
return judge(arr, Start, i-1) && judge(arr, i, End-1);
}
}
刪除鏈表中重復的元素（leetcode82）
public ListNode deleteDuplicates(ListNode head) {
if(head==null||head.next==null){
return head;
}
if(head.val==head.next.val){
ListNode move = head.next;
while(move!=null&&head.val==move.val){
move = move.next;
}
head = deleteDuplicates(move);
}else{
head.next = deleteDuplicates(head.next);
}
return head;
}
浙公網安備 33010602011771號