写在前面
- 本系列包含《剑指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>() {
@Overridepublic 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题
希望这篇文章对你有帮助~