劍指offer61到66題總覽：
- 序列化二叉樹
- 二叉搜索樹的第k個(gè)結(jié)點(diǎn)
- 數(shù)據(jù)流中的中位數(shù)
- 滑動窗口的最大值
- 矩陣中的路徑
- 機(jī)器人的運(yùn)動范圍
61、序列化二叉樹
題目描述
請實(shí)現(xiàn)兩個(gè)函數(shù)叫挟，分別用來序列化和反序列化二叉樹
解題思路
序列化指的是遍歷二叉樹為字符串掂恕；所謂反序列化指的是依據(jù)字符串重新構(gòu)造成二叉樹。沒有說根據(jù)什么遍歷方法障本，所以選擇前序遍歷什么遍歷都可以教届。只要序列化之后再反序列化的樹是一樣的。
public class Solution {
String Serialize(TreeNode root) {
StringBuffer str = new StringBuffer();
if(root==null){return "#,";}
str.append(root.val+",");//前序遍歷樹驾霜，先根
str.append(Serialize(root.left));//遍歷左子樹案训，加到str的后面
str.append(Serialize(root.right));//遍歷完左子樹，再遍歷右子樹粪糙，加到str的后面
return str.toString();//返回遍歷結(jié)果
}
int index = 0;
TreeNode Deserialize(String str) {
String[] arr = str.split(",");//如果這個(gè)split可以在外面就好一些
TreeNode root = null;//先建一個(gè)空結(jié)點(diǎn)
if(index < arr.length){
if(arr[index].equals("#")){//如果遇到的是#强霎，則返回空結(jié)點(diǎn)
index++;//讀了一個(gè)結(jié)點(diǎn)，index++
return root;//返回空結(jié)點(diǎn)
}else{//如果遇到的字符不是#
root = new TreeNode(Integer.valueOf(arr[index]));//new一個(gè)新結(jié)點(diǎn)蓉冈，并初始化val的值
index++;//讀了一個(gè)結(jié)點(diǎn)城舞，index++
root.left = Deserialize(str);//先遍歷左邊的字符
root.right = Deserialize(str);//遍歷完左邊的字符之后，index會指向相應(yīng)的右子樹的根節(jié)點(diǎn)洒擦，遍歷右邊的字符
}
}
return root;
}
}
62椿争、二叉搜索樹的第k個(gè)結(jié)點(diǎn)
題目描述
給定一棵二叉搜索樹，請找出其中的第k小的結(jié)點(diǎn)熟嫩。例如秦踪， （5，3，7椅邓，2柠逞，4，6景馁，8） 中板壮，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4。
解題思路
二叉搜索樹中序遍歷遞增合住，二叉搜索樹中數(shù)值第k小的點(diǎn)就是中序遍歷的第k個(gè)點(diǎn)绰精。
import java.util.Stack;
public class Solution {
int index = 0;
TreeNode KthNode(TreeNode pRoot, int k){
if(pRoot == null){return null;}
if(k<=0){return null;}
Stack<TreeNode> stack = new Stack<>();
stack.push(pRoot);//根節(jié)點(diǎn)入棧
while(pRoot.left!=null){//根節(jié)點(diǎn)的所有左結(jié)點(diǎn)入棧
pRoot = pRoot.left;
stack.push(pRoot);
}
while(!stack.empty()){
TreeNode node = stack.pop();//每出棧一個(gè)數(shù)，index+1
index++;
if(index < k){//當(dāng)還沒找到第k個(gè)數(shù)時(shí)
if(node.right!=null){如果有右結(jié)點(diǎn)透葛，則將右結(jié)點(diǎn)入棧笨使，并將右結(jié)點(diǎn)的所有左結(jié)點(diǎn)入棧
stack.push(node.right);
node = node.right;
while(node.left!=null){//右結(jié)點(diǎn)的所有左結(jié)點(diǎn)入棧
node = node.left;
stack.push(node);
}
}
}else{//如果找到了第k個(gè)數(shù)
pRoot = node;//將第k個(gè)數(shù)賦值給pRoot，并break
break;
}
}
if(stack.empty() && index < k){return null;}//如果是椓藕Γ空了跳出的循環(huán)硫椰，且還沒到第k個(gè)數(shù)，則k大于數(shù)的總結(jié)點(diǎn)數(shù)萨蚕，返回null
return pRoot;//如果是break跳出的循環(huán)靶草，則返回pRoot
}
}
63、數(shù)據(jù)流中的中位數(shù)
題目描述
如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)岳遥？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值奕翔，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值寒随，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值糠悯。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)妻往。
解題思路
一個(gè)非常直接的思想是互艾，每次插入一個(gè)數(shù)，都找到新插入的數(shù)應(yīng)該在的位置讯泣，使插入的所有數(shù)都是有序的纫普，則取中位數(shù)的時(shí)候很方便。但這種方法的缺點(diǎn)時(shí)好渠，在每次插入的時(shí)候昨稼，都要對之前插入的數(shù)據(jù)進(jìn)行遍歷。
參考湃客網(wǎng)https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1的方法假栓，我們設(shè)置兩個(gè)優(yōu)先隊(duì)列，也就是兩個(gè)堆霍掺。我們設(shè)置一個(gè)大頂堆匾荆，一個(gè)小頂堆拌蜘。而大頂堆存儲插入數(shù)據(jù)中較小的那一半，小頂堆存儲插入數(shù)據(jù)中較大的那一半牙丽。在后續(xù)過程中简卧，我們會將大頂堆中的最大元素移出，移到小頂堆中烤芦；會將小頂堆中的最小元素移出举娩，移到大頂堆中。所以大頂堆中存的數(shù)都比小頂堆中的數(shù)小构罗。
為了平衡兩個(gè)優(yōu)先隊(duì)列中的數(shù)铜涉，插入第一個(gè)數(shù)的時(shí)候，我們可以任意選擇先加入小頂堆或者先加入大頂堆中绰播。這個(gè)先后順序只決定了最后我們?nèi)≈形粩?shù)的時(shí)候骄噪，如果我們插入了奇數(shù)個(gè)數(shù)，哪一個(gè)優(yōu)先隊(duì)列中存的數(shù)會多一個(gè)蠢箩，我們就pop出那一個(gè)優(yōu)先隊(duì)列中存的數(shù)，它就是我們要的中位數(shù)事甜。如果插入的個(gè)數(shù)為偶數(shù)個(gè)谬泌，則我們就同時(shí)pop出小頂堆和大頂堆中的數(shù)，并取平均值逻谦，得到中位數(shù)掌实。
假設(shè)我們約定，當(dāng)插入數(shù)據(jù)個(gè)數(shù)為奇數(shù)時(shí)邦马，小頂堆的個(gè)數(shù)要多一個(gè)贱鼻，則整個(gè)插入過程如下：(我們設(shè)置count，表示已經(jīng)插入的數(shù)據(jù)的個(gè)數(shù)滋将，初始值為0)
- 當(dāng)count為偶數(shù)時(shí)邻悬，我們將新插入的數(shù)先加入大頂堆maxHeap，然后maxHeap再pop出maxHeap中最大的數(shù)随闽，將這個(gè)最大的數(shù)加入到minHeap父丰。這樣minHeap就比maxHeap多了一個(gè)數(shù)。
- 當(dāng)count為奇數(shù)時(shí)掘宪，minHeap比maxHeap多一個(gè)數(shù)蛾扇。我們將新插入的數(shù)先加入小頂堆minHeap，然后minHeap再poop出minHeap中最小的數(shù)魏滚，將這個(gè)最小的數(shù)加入到maxHeap镀首。這樣minHeap和maxHeap的個(gè)數(shù)就一樣了。
這樣做鼠次，能夠保證minHeap中的數(shù)總是大于maxHeap中的數(shù)更哄，而且我們可以不關(guān)心兩個(gè)堆中數(shù)的順序芋齿，只需要關(guān)心minHeap中最小的數(shù)，和maxHeap中最大的數(shù)竖瘾。同時(shí)沟突，minHeap中存的數(shù)的個(gè)數(shù)總是比minHeap中存的數(shù)的個(gè)數(shù)多一個(gè)，或者相等捕传。這樣就非常方便取中位數(shù)了惠拭。
取中位數(shù)過程如下：
- 當(dāng)count為偶數(shù)時(shí)，兩個(gè)堆的個(gè)數(shù)是一樣的庸论，則取minHeap中最小的數(shù)职辅，并取maxHeap中最大的數(shù)，取他們的平均值即為中位數(shù)聂示。
- 當(dāng)count為偶數(shù)時(shí)域携，minHeap比maxHeap多一個(gè)數(shù)，只需要取minHeap中最小的數(shù)鱼喉，即為中位數(shù)秀鞭。
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
int count = 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();//小頂堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){//大頂堆
return b-a;
}
});
public void Insert(Integer num) {
if(count%2==0){//當(dāng)插入了偶數(shù)個(gè)數(shù)據(jù)的時(shí)候
count++;
maxHeap.offer(num);//先將數(shù)加入大頂堆
minHeap.offer(maxHeap.poll());//pop出大頂堆中最大的數(shù)，并加入小頂堆
}else{
count++;
minHeap.offer(num);//先將數(shù)加入小頂堆
maxHeap.offer(minHeap.poll());//pop出小頂堆中最小的數(shù)扛禽，并加入大頂堆
}
}
public Double GetMedian() {
if(count%2 == 1){//minHeap比maxHeap多一個(gè)數(shù)锋边，pop出minHeap的頂即可
return (double)minHeap.peek();
}else{//minHeap和maxHeap個(gè)數(shù)一樣，取他們的頂编曼，平均即可
return ((double)minHeap.peek()+(double)maxHeap.peek())/2;
}
}
}
64豆巨、滑動窗口的最大值
題目描述
給定一個(gè)數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值掐场。例如往扔，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個(gè)滑動窗口熊户，他們的最大值分別為{4,4,6,6,6,5}萍膛； 針對數(shù)組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個(gè)： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}敏弃， {2,3,[4,2,6],2,5,1}卦羡， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}麦到， {2,3,4,2,6,[2,5,1]}绿饵。
解題思路
參考牛客網(wǎng)https://www.nowcoder.com/questionTerminal/1624bc35a45c42c0bc17d17fa0cba788的方法瓶颠。我們維護(hù)一個(gè)雙端隊(duì)列拟赊，并存儲數(shù)組的下標(biāo)。隊(duì)頭元素下標(biāo)對應(yīng)的數(shù)是當(dāng)前滑動窗口中最大的數(shù)粹淋，隊(duì)中元素下標(biāo)對應(yīng)的數(shù)從隊(duì)頭到隊(duì)尾是遞減的吸祟。
具體的操作如下：(隊(duì)列中存儲的是對應(yīng)元素的下標(biāo)瑟慈，為了下面表述方便，我們說對應(yīng)的元素)屋匕。
對num數(shù)組每個(gè)數(shù)進(jìn)行遍歷葛碧，將num[i]加入到雙端隊(duì)列queue中。
- 如果隊(duì)列為空过吻，則直接將num[i]對應(yīng)的下標(biāo)i加入到queue中进泼，加入到隊(duì)頭隊(duì)尾都是一樣的。
- 如果隊(duì)列非空纤虽，則從隊(duì)尾開始乳绕，逐個(gè)向前檢查隊(duì)中下標(biāo)對應(yīng)的元素是否小于num[i]，如果小于num[i]逼纸，則全部刪除洋措，直到遇到比num[i]大的元素即停止。
將隊(duì)尾中比num[i]小的元素全部刪除的原因是杰刽，加入了num[i]后菠发，比它小的元素且不說會不會失效，有num[i]在贺嫂，比num[i]小的元素都不會成為滑動窗口中的最大值雷酪，全部刪除即可。
另一方面涝婉，我們要維護(hù)的雙端隊(duì)列是有序的，加入num[i]前蔗怠，將比num[i]小的元素全部刪除墩弯，這樣才能使隊(duì)列有序，才能使隊(duì)頭元素成為我們要找的滑動窗口的最大值寞射。 - 要加入i渔工，則滑動窗口向后滑一位，我們要判斷隊(duì)頭元素是否過期桥温。如果隊(duì)頭元素對應(yīng)的下標(biāo)j<=i-size引矩，即該隊(duì)頭元素已經(jīng)出了滑動窗口，已經(jīng)過期侵浸，則removeFirst旺韭，將隊(duì)頭移出就好。
- 刪除了比num[i]小的結(jié)點(diǎn)后掏觉，并移除了過期隊(duì)頭区端，然后將num[i]對應(yīng)的下標(biāo)i加入到隊(duì)尾。
- 滑動窗口更新完畢澳腹，取隊(duì)頭元素但不remove织盼，加入到list就行杨何。(前size-1個(gè)元素不用加入list)
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size){
ArrayList<Integer> list = new ArrayList<>();
if(size <= 0){return list;}
LinkedList<Integer> queue = new LinkedList<>();
for(int i=0; i<num.length; i++){
if(queue.size()==0){//隊(duì)為空，不用判斷是否比num[i]更小沥邻，直接加入queue
queue.addFirst(i);//加入下標(biāo)i
}else{
while(!queue.isEmpty() && num[queue.peekLast()]<num[i]){//從隊(duì)尾開始危虱，刪除隊(duì)尾中比num[i]小的數(shù)
queue.removeLast();
}
if(!queue.isEmpty() && queue.peekFirst() <= i-size){//如果隊(duì)頭元素過期了
queue.removeFirst();//移出隊(duì)頭元素
}
queue.addLast(i);//將新元素加入到隊(duì)尾
}
if(i >= size-1){//前size-1個(gè)元素不用加入list
list.add(num[queue.peekFirst()]);
}
}
return list;
}
}
65、矩陣中的路徑
題目描述
請?jiān)O(shè)計(jì)一個(gè)函數(shù)唐全，用來判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑埃跷。路徑可以從矩陣中的任意一個(gè)格子開始，每一步可以在矩陣中向左芦瘾，向右捌蚊，向上，向下移動一個(gè)格子近弟。如果一條路徑經(jīng)過了矩陣中的某一個(gè)格子缅糟，則之后不能再次進(jìn)入這個(gè)格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑祷愉，但是矩陣中不包含"abcb"路徑窗宦，因?yàn)樽址牡谝粋€(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入該格子二鳄。
解題思路
遞歸以及回溯赴涵。這個(gè)題是可以從matrix中任意一個(gè)點(diǎn)開始走的，所以與下一題的機(jī)器人路徑不一樣订讼，這一題的可選方向是上下左右四向髓窜，而下一題機(jī)器人從(0,0)開始走，可選方向是右和下兩向欺殿。
判斷該方向是否可走寄纵，出了判斷該點(diǎn)是否出界之外，還要判斷該點(diǎn)是否已經(jīng)存在于已經(jīng)走過的路徑中脖苏。一種方法可以將路徑保存下來程拭，判斷是否存在于已走的路徑中。這種方法可以輸出可行路徑棍潘。另一種方法是設(shè)置一個(gè)visited數(shù)組恃鞋，判斷該點(diǎn)是否已經(jīng)訪問過。這種方法能比較快地判斷該點(diǎn)是否存在于已經(jīng)走過的路徑中亦歉。
如果該點(diǎn)上下左右四向都不通恤浪，則該點(diǎn)是錯誤走法，此時(shí)就需要回溯鳍徽。我們退回走錯的前一步资锰，此題的退回即是將visited數(shù)組還原為false。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
if(str.length == 0 || matrix.length == 0){return false;}
boolean visited[] = new boolean[rows*cols];//visited數(shù)組標(biāo)志該位是否被訪問
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){//遍歷matrix的每一位阶祭，從該位開始匹配字符串
if(isHashPath(matrix, str, visited, rows, cols, i, j, 0)){
return true;
}
}
}
return false;
}
public boolean isHashPath(char[] matrix, char[] str, boolean[] visited, int rows, int cols, int i, int j, int str_index){
if(str_index >= str.length){return true;}//str已經(jīng)全部找到
if(i<0 || i>=rows || j<0 || j>=cols || visited[i*cols+j] || matrix[i*cols+j]!=str[str_index]){
//如果(i,j)點(diǎn)出了邊界绷杜，或者(i,j)已經(jīng)被訪問直秆，或者(i,j)點(diǎn)對應(yīng)的字符并不是str_index對應(yīng)的字符，則返回false
return false;
}
visited[i*cols+j] = true;
//如果沒有出邊界鞭盟，也沒有被訪問圾结，也是str_index對應(yīng)的字符，則訪問該結(jié)點(diǎn)齿诉，(i,j)點(diǎn)visited設(shè)置為true
boolean flag = isHashPath(matrix, str, visited, rows, cols, i, j-1, str_index+1)
|| isHashPath(matrix, str, visited, rows, cols, i, j+1, str_index+1)
|| isHashPath(matrix, str, visited, rows, cols, i-1, j,str_index+1)
|| isHashPath(matrix, str, visited, rows, cols, i+1, j, str_index+1);
//向左筝野，向右，向上粤剧，向下遞歸
if(flag == false){//四向不通
visited[i*cols+j] = false;//四向不通歇竟，則說明當(dāng)前點(diǎn)走錯了，回溯抵恋，將該點(diǎn)的visited還原為false
}
return flag;
}
}
66 焕议、機(jī)器人的運(yùn)動范圍
題目描述
地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開始移動弧关，每一次只能向左盅安，右，上世囊，下四個(gè)方向移動一格别瞭，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 例如株憾，當(dāng)k為18時(shí)蝙寨，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18嗤瞎。但是籽慢，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19猫胁。請問該機(jī)器人能夠達(dá)到多少個(gè)格子？
解題思路
這題不用回溯跛锌，比上一題相對簡單一些弃秆。機(jī)器人從坐標(biāo)(0,0)開始走，每次只需要向右和向下走即可髓帽，如果向左或向上一定是被訪問過的點(diǎn)菠赚。每次走的時(shí)候，只需要判斷向左是否能走郑藏，向右是否能走衡查，能走就走，不能走就不走必盖。
public class Solution {
int count = 0;//計(jì)數(shù)器
public int movingCount(int threshold, int rows, int cols){
if(threshold<=0){return 0;}
boolean visited[][] = new boolean[rows][cols];//是否訪問數(shù)組
go(threshold, rows, cols, 0, 0, visited);//從坐標(biāo)(0,0)開始走
return count;
}
public void go(int threshold, int rows, int cols, int i, int j, boolean[][] visited){
if(i<0 || i>=rows || j<0 || j>=cols || visited[i][j]){return;}//如果出了邊界或者改點(diǎn)已經(jīng)訪問過拌牲，則返回
visited[i][j] = true;//如果沒有出邊界俱饿，且該點(diǎn)沒有被訪問過，則訪問該點(diǎn)塌忽，將該點(diǎn)visited設(shè)置為true拍埠。
count++;//訪問該點(diǎn)，計(jì)數(shù)器count+1
if(canGo(threshold, i, j+1)){go(threshold, rows, cols, i, j+1, visited);}//如果向右走滿足threshold土居，則向右走
if(canGo(threshold, i+1, j)){go(threshold, rows, cols, i+1, j, visited);}//如果向下走滿足threshold枣购，則向下走
}
public boolean canGo(int threshold, int i, int j){//判斷該點(diǎn)是否滿足threshold
int sum = 0;//數(shù)位之和
do{
sum += i%10;//先取余，再取商
i = i/10;
}while(i!=0);
do{
sum += j%10;
j = j/10;
}while(j!=0);
if(sum>threshold){return false;}//不滿足threshold擦耀，返回false
else{return true;}//滿足threshold棉圈，返回true
}
}
結(jié)尾
如果您發(fā)現(xiàn)我的文章有任何錯誤，或?qū)ξ业奈恼掠惺裁春玫慕ㄗh眷蜓，請聯(lián)系我分瘾！如果您喜歡我的文章，請點(diǎn)喜歡~*我是藍(lán)白絳账磺，感謝你的閱讀芹敌！
