写在前面
- 本系列包含《剑指Offer》66道算法题，一周刷完，这是完结篇，撒花！
系列汇总：剑指Offer 66题 Java 刷题笔记汇总 - 所有题目均可在牛客网在线编程平台进行调试。
网址：https://www.nowcoder.com/ta/coding-interviews - 本系列包含题目，解题思路及代码（Java）。
代码同步发布在GitHub：https://github.com/JohnnyJYWu/offer-Java
上一篇：算法 | 一周刷完《剑指Offer》 Day5：第50~60题
Day6：第60~66题
6天搞定！感觉还是有点进步的。
- T61. 序列化二叉树
- T62. 二叉搜索树的第k个结点
- T63. 数据流中的中位数
- T64. 滑动窗口的最大值
- T65. 矩阵中的路径
- T66. 机器人的运动范围
T61. 序列化二叉树
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树
解题思路
基本的序列化思想就可以。
此题每个人方法都不一样，需要注意的是：
1.对于二叉树来说，节点为null时最好采用一个字符来替代表示（这里用的 # 字符）；
2.该题二叉树的value为int型，在序列化成字符串时最好用字符分隔开（这里用的逗号），不然int和String转换过程中容易出错。
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） 中，按结点数值大小顺序第三小结点的值为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. 数据流中的中位数
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解题思路
画了张草图（如上）。这是一个比较巧妙的方法，用到了PriorityQueue，一个能自动排序的队列，排序方式也可以自定义。解题思路写在注释里了，对着代码和图片容易理解一些。
private int count = 0;//计数，判断奇偶
//使用自动排序的PriorityQueue,两个堆详情见图片
//小顶推：默认从小到大排序，堆顶为最小数，用于存储后半部分较大的数，堆顶用于计数中位数
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//大顶堆：声明从大到小排序，堆顶为最大数，用于存储前半部分较小的数，堆顶用于计数中位数
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) {
//分奇偶次插入，一半入小顶堆，一半入大顶堆，保证两个堆数量一半一半
if(count % 2 == 0) {//注意这里0为第1个数，所以插入时奇数次对应的count为偶数
//奇数次插入时，最终入小顶堆
//注意插入时是先入大顶堆，由大顶堆排序后取大顶堆最大的插入小顶堆
//插入大顶堆
maxHeap.offer(num);
//取大顶堆堆顶
int maxInMaxHead = maxHeap.poll();
//堆顶插入小顶堆
minHeap.offer(maxInMaxHead);
} else {
//偶数次插入时，最终入大顶堆
//原理同上
//插入小顶堆
minHeap.offer(num);
//取小顶堆堆顶
int minInMinHead = minHeap.poll();
//堆顶入大顶堆
maxHeap.offer(minInMinHead);
}
count ++;
}
@SuppressWarnings("deprecation")
public Double GetMedian() {
//由于先入小顶堆，小顶堆数量总是比大顶堆多1或相等
//所以这里，count为奇次时，插入了奇数次，中位数是小顶堆堆顶
//count为偶次时，插入了偶数次，中位数是两堆堆顶平均数
if(count % 2 == 0) {
return new Double(minHeap.peek() + maxHeap.peek()) / 2;
} else {
return new Double(minHeap.peek());
}
}
T64. 滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{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数组的下标。每当移动窗口时，要判断队列头是否超出窗口范围，同时要将新加入的队尾的数与队中最大数比较，小则直接退出，大则退出最大数。（这样做实质上始终只有一个最大元素在窗口中）
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数组下标
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()]) {//如果，要进队列的新的数比队列尾部大，移除队尾，直到队列中只剩最大的一个数
deque.pollLast();
}
deque.offer(i);
if(i >= (size - 1)) {//过滤前几个，当遍历到第一个窗口大小时开始存结果
result.add(num[deque.peekFirst()]);
}
}
return result;
}
T65. 矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
解题思路
动态规划应用题，思路是边走边找，具体见注释。
注意：
定义辅助数组，用于记录矩阵中各位置是否被访问过；
二维数组在一维数组形式中的表示：index = i * cols + j;
此题求多种解，记得回溯。
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
int[] flag = new int[matrix.length];//辅助数组，用于记录矩阵中各位置是否被访问过
for(int i = 0; i < rows; i ++) {
for(int j = 0; j < cols; j ++) {
int index = i * cols + j;//二维数组在一维数组形式中的表示
if(matrix[index] == str[0]) {//找到str在矩阵的开始位置
if(findPath(matrix, rows, cols, i, j, str, 0, flag)) {
return true;
}
}
}
}
return false;
}
//动态规划求解
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 //数组越界
|| 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的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
解题思路
动态规划应用题，同上一题，相比要简单很多，具体见注释。
public int movingCount(int threshold, int rows, int cols) {
int[] flags = new int[rows * cols];//辅助数组，用于记录矩阵中各位置是否被访问过
return moving(threshold, rows, cols, 0, 0, flags);
}
//动态规划
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) {//数组越界或该点被访问过
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题
希望这篇文章对你有帮助~
