寫在前面
- 本系列包含《劍指Offer》66道算法題，一周刷完，這是完結篇，撒花！
系列匯總：劍指Offer 66題 Java 刷題筆記匯總 - 所有題目均可在?？途W(wǎng)在線編程平臺進行調(diào)試。
網(wǎng)址：https://www.nowcoder.com/ta/coding-interviews - 本系列包含題目，解題思路及代碼（Java）。
代碼同步發(fā)布在GitHub：https://github.com/JohnnyJYWu/offer-Java
上一篇：算法 | 一周刷完《劍指Offer》 Day5：第50~60題
Day6：第60~66題
6天搞定！感覺還是有點進步的。
- T61. 序列化二叉樹
- T62. 二叉搜索樹的第k個結點
- T63. 數(shù)據(jù)流中的中位數(shù)
- T64. 滑動窗口的最大值
- T65. 矩陣中的路徑
- T66. 機器人的運動范圍
T61. 序列化二叉樹
題目描述
請實現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹
解題思路
基本的序列化思想就可以。
此題每個人方法都不一樣，需要注意的是：
1.對于二叉樹來說，節(jié)點為null時最好采用一個字符來替代表示（這里用的 # 字符）；
2.該題二叉樹的value為int型，在序列化成字符串時最好用字符分隔開（這里用的逗號），不然int和String轉(zhuǎn)換過程中容易出錯。
public String Serialize(TreeNode root) {
if(root == null) return "";
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private void serialize(TreeNode root, StringBuilder sb) {
if(root == null) {
sb.append("#,");
return;
}
sb.append(root.val);
sb.append(",");
serialize(root.left, sb);
serialize(root.right, sb);
}
public TreeNode Deserialize(String str) {
if(str == null || str.length() == 0) return null;
String[] strs = str.split(",");
index = 0;
return deserialize(strs);
}
private int index;
private TreeNode deserialize(String[] strs) {
if(!strs[index].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(strs[index]));
index ++;
node.left = deserialize(strs);
node.right = deserialize(strs);
return node;
} else {
index ++;
}
return null;
}
T62. 二叉搜索樹的第k個結點
題目描述
給定一棵二叉搜索樹，請找出其中的第k小的結點。例如， （5，3，7，2，4，6，8） 中，按結點數(shù)值大小順序第三小結點的值為4。
解題思路
注意題意。二叉搜索樹：左子結點 < 根結點 < 右子結點
因此對二叉搜索樹進行中序遍歷，得到的即為從小到大排序序列。
private ArrayList<TreeNode> list = new ArrayList<>();
public TreeNode KthNode(TreeNode pRoot, int k) {//二叉搜索樹，中序遍歷即為從小到大的排序
if(pRoot == null || k <= 0) return null;
inOrder(pRoot);
TreeNode kthNode = null;
if(k <= list.size()) {
kthNode = list.get(k - 1);
}
return kthNode;
}
private void inOrder(TreeNode root) {//中序遍歷
if(root == null) return;
//左
if(root.left != null) inOrder(root.left);
//根
list.add(root);
//右
if(root.right != null) inOrder(root.right);
}
T63. 數(shù)據(jù)流中的中位數(shù)
題目描述
如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當前讀取數(shù)據(jù)的中位數(shù)。
解題思路
畫了張草圖（如上）。這是一個比較巧妙的方法，用到了PriorityQueue，一個能自動排序的隊列，排序方式也可以自定義。解題思路寫在注釋里了，對著代碼和圖片容易理解一些。
private int count = 0;//計數(shù)，判斷奇偶
//使用自動排序的PriorityQueue,兩個堆詳情見圖片
//小頂推：默認從小到大排序，堆頂為最小數(shù)，用于存儲后半部分較大的數(shù)，堆頂用于計數(shù)中位數(shù)
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//大頂堆：聲明從大到小排序，堆頂為最大數(shù)，用于存儲前半部分較小的數(shù)，堆頂用于計數(shù)中位數(shù)
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
public void Insert(Integer num) {
//分奇偶次插入，一半入小頂堆，一半入大頂堆，保證兩個堆數(shù)量一半一半
if(count % 2 == 0) {//注意這里0為第1個數(shù)，所以插入時奇數(shù)次對應的count為偶數(shù)
//奇數(shù)次插入時，最終入小頂堆
//注意插入時是先入大頂堆，由大頂堆排序后取大頂堆最大的插入小頂堆
//插入大頂堆
maxHeap.offer(num);
//取大頂堆堆頂
int maxInMaxHead = maxHeap.poll();
//堆頂插入小頂堆
minHeap.offer(maxInMaxHead);
} else {
//偶數(shù)次插入時，最終入大頂堆
//原理同上
//插入小頂堆
minHeap.offer(num);
//取小頂堆堆頂
int minInMinHead = minHeap.poll();
//堆頂入大頂堆
maxHeap.offer(minInMinHead);
}
count ++;
}
@SuppressWarnings("deprecation")
public Double GetMedian() {
//由于先入小頂堆，小頂堆數(shù)量總是比大頂堆多1或相等
//所以這里，count為奇次時，插入了奇數(shù)次，中位數(shù)是小頂堆堆頂
//count為偶次時，插入了偶數(shù)次，中位數(shù)是兩堆堆頂平均數(shù)
if(count % 2 == 0) {
return new Double(minHeap.peek() + maxHeap.peek()) / 2;
} else {
return new Double(minHeap.peek());
}
}
T64. 滑動窗口的最大值
題目描述
給定一個數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數(shù)組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[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]}。
解題思路
使用到了Deque，一個雙端隊列，可從兩端彈出，用來模擬窗口，儲存當前窗口顯示的元素在num數(shù)組的下標。每當移動窗口時，要判斷隊列頭是否超出窗口范圍，同時要將新加入的隊尾的數(shù)與隊中最大數(shù)比較，小則直接退出，大則退出最大數(shù)。（這樣做實質(zhì)上始終只有一個最大元素在窗口中）
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> result = new ArrayList<>();
if(num == null || num.length == 0 || size == 0 || size > num.length) {
return result;
}
//雙端隊列，可從兩端彈出，模擬窗口，用于存當前窗口最大值在num數(shù)組下標
Deque<Integer> deque = new ArrayDeque<>();
for(int i = 0; i < num.length; i ++) {
if(!deque.isEmpty() && (i - deque.peekFirst()) >= size) {//當隊列頭已超出窗口范圍時移除隊列頭
deque.pollFirst();
}
while(!deque.isEmpty() && num[i] >= num[deque.peekLast()]) {//如果，要進隊列的新的數(shù)比隊列尾部大，移除隊尾，直到隊列中只剩最大的一個數(shù)
deque.pollLast();
}
deque.offer(i);
if(i >= (size - 1)) {//過濾前幾個，當遍歷到第一個窗口大小時開始存結果
result.add(num[deque.peekFirst()]);
}
}
return result;
}
T65. 矩陣中的路徑
題目描述
請設計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子，則之后不能再次進入這個格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。
解題思路
動態(tài)規(guī)劃應用題，思路是邊走邊找，具體見注釋。
注意：
定義輔助數(shù)組，用于記錄矩陣中各位置是否被訪問過；
二維數(shù)組在一維數(shù)組形式中的表示：index = i * cols + j;
此題求多種解，記得回溯。
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
int[] flag = new int[matrix.length];//輔助數(shù)組，用于記錄矩陣中各位置是否被訪問過
for(int i = 0; i < rows; i ++) {
for(int j = 0; j < cols; j ++) {
int index = i * cols + j;//二維數(shù)組在一維數(shù)組形式中的表示
if(matrix[index] == str[0]) {//找到str在矩陣的開始位置
if(findPath(matrix, rows, cols, i, j, str, 0, flag)) {
return true;
}
}
}
}
return false;
}
//動態(tài)規(guī)劃求解
private boolean findPath(char[] matrix, int rows, int cols, int i, int j,
char[] str, int strIndex,
int[] flag) {
int index = i * cols + j;
if(i < 0 || i >= rows || j < 0 || j >= cols //數(shù)組越界
|| matrix[index] != str[strIndex] //矩陣該點與字符串相應位置值不同
|| flag[index] == -1) {//矩陣該點已使用過
return false;
}
if(strIndex == str.length - 1) {//該點符合要求且已是字符串最后一位
return true;
}
flag[index] = -1;
//對該點上下左右遞歸求解
if(findPath(matrix, rows, cols, i - 1, j, str, strIndex + 1, flag)
|| findPath(matrix, rows, cols, i + 1, j, str, strIndex + 1, flag)
|| findPath(matrix, rows, cols, i, j - 1, str, strIndex + 1, flag)
|| findPath(matrix, rows, cols, i, j + 1, str, strIndex + 1, flag)) {
return true;//任一符合即可
}
flag[index] = 0;//記得回溯時將該點標記為未使用過
return false;
}
T66. 機器人的運動范圍
題目描述
地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數(shù)位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？
解題思路
動態(tài)規(guī)劃應用題，同上一題，相比要簡單很多，具體見注釋。
public int movingCount(int threshold, int rows, int cols) {
int[] flags = new int[rows * cols];//輔助數(shù)組，用于記錄矩陣中各位置是否被訪問過
return moving(threshold, rows, cols, 0, 0, flags);
}
//動態(tài)規(guī)劃
private int moving(int k, int rows, int cols,
int i, int j, int[] flags) {
int index = i * cols + j;
if(i < 0 || i >= rows || j < 0 || j >= cols || flags[index] == -1) {//數(shù)組越界或該點被訪問過
return 0;
}
int sum = 0;
int tmp = i;
while(tmp != 0) {//橫坐標各位和
sum += tmp % 10;
tmp /= 10;
}
tmp = j;
while(tmp != 0) {//縱坐標各位和
sum += tmp % 10;
tmp /= 10;
}
if(sum <= k) {
flags[index] = -1;//訪問過，與上題不同的是，這里不需回溯
int steps = 1;//計入當前點
//對該點右邊和下邊的點遞歸求解，左邊與上邊在前面的迭代過程中已訪問過，無需再次訪問
steps += moving(k, rows, cols, i + 1, j, flags);
steps += moving(k, rows, cols, i, j + 1, flags);
return steps;
}
return 0;
}
項目地址：https://github.com/JohnnyJYWu/offer-Java
上一篇：算法 | 一周刷完《劍指Offer》 Day5：第50~60題
希望這篇文章對你有幫助~
