數據結構與算法
數據結構定義
數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下,精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。
- 數組:物理存儲單元上連續、順序的存儲結構
- 鏈表:鏈表是一種物理存儲單元上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。
- 隊列:隊列(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號