剑指offer（61-67）题解
剑指offer（61-67）题解
剑指offer（61-67）题解
- 61题解--序列化二叉树
- 62题解--二叉搜索树的第K个结点
- 63题解--数据流中的中位数
- 64题解--滑动窗口的最大值
- 65题解--矩阵中的路径
- 66题解--机器人的运动范围
- 67题解--剪绳子
61题解–序列化二叉树
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树
思路解析
这里其实方法有很多，你可以选择中序，前序，后序，层序遍历来保存当前树的结构 这里我选择的是通过前序遍历将节点存进来，并且在这个过程中，空节点也是要存进来的，否则还是不能序列化。举下面这个例子：
源代码
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
String Serialize(TreeNode root) {
if(root == null)
return "";
StringBuilder sb = new StringBuilder();
Serialize2(root, sb);
return sb.toString();
}
void Serialize2(TreeNode root, StringBuilder sb) {
if(root == null) {
sb.append("#,");
return;
}
sb.append(root.val);
sb.append(',');
Serialize2(root.left, sb);
Serialize2(root.right, sb);
}
int index = -1;
TreeNode Deserialize(String str) {
if(str.length() == 0)
return null;
String[] strs = str.split(",");
return Deserialize2(strs);
}
TreeNode Deserialize2(String[] strs) {
index++;
if(!strs[index].equals("#")) {
TreeNode root = new TreeNode(0);
root.val = Integer.parseInt(strs[index]);
root.left = Deserialize2(strs);
root.right = Deserialize2(strs);
return root;
}
return null;
}
}62题解–二叉搜索树的第K个结点
题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
思路解析
还是之前二叉排序树的中序序列是一个升序序列，所以我们完全可以将该二叉树的中序序列遍历出来，之后直接取出来即可。
源代码
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.ArrayList;
public class Solution {
ArrayList<TreeNode>list=new ArrayList<TreeNode>();
public void Print(TreeNode pRoot)
{
if(pRoot.left!=null)
Print(pRoot.left);
list.add(pRoot);
if(pRoot.right!=null)
Print(pRoot.right);
}
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot==null)
return null;
Print(pRoot);
if(k>list.size()||k==0)
return null;
return list.get(k-1);
}
}63题解–数据流中的中位数
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路解析
这里只要稍微注意一下，他是每次添加就计算一次中位值，所以必须每次添加完就进行排序操作，其他的计算中位数，大家都会的。
源代码
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
ArrayList<Integer>list=new ArrayList<Integer>();
public void Insert(Integer num)
{
list.add(num);
Collections.sort(list);
}
public Double GetMedian()
{
double num=0.0;
if(list.size()%2!=0)
{
num=list.get(list.size()/2);
}
else
{
num+=list.get(list.size()/2);
num+=list.get(list.size()/2-1);
num/=2;
}
return num;
}
}64题解–滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。 窗口大于数组长度的时候，返回空
思路解析
与上面一题一样的道理，每次操作完记得计算结果。
源代码
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public int max(int []num)
{
Arrays.sort(num);
return num[num.length-1];
}
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer>list=new ArrayList<Integer>();
if(size>num.length)
return list;
if(size==0)
return list;
for(int i=0;i<num.length-size+1;i++)
list.add(max(Arrays.copyOfRange(num, i, i+size)));
return list;
}
}65题解–矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路解析
这题本质上也是一道搜索的题目，和迷宫类似，只要有搜索的模板，然后判断是否越界以及把字符判断的条件加上就行了
源代码
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
boolean[] flag = new boolean[matrix.length];
if(hasPath(matrix, rows, cols, str, i, j, flag, 0)) return true;
}
}
return false;
}
public boolean hasPath(char[] matrix, int rows, int cols, char[] str, int i, int j, boolean[] flag, int k){
int index = i * cols + j;
if(i < 0 || j < 0 || i >= rows || j >= cols || flag[index] == true || matrix[index] != str[k]) return false;
if(k == str.length - 1) return true;
flag[index] = true;
if(hasPath(matrix, rows, cols, str, i - 1, j, flag, k + 1)
||hasPath(matrix, rows, cols, str, i + 1, j, flag, k + 1)
||hasPath(matrix, rows, cols, str, i, j - 1, flag, k + 1)
||hasPath(matrix, rows, cols, str, i, j + 1, flag, k + 1)) return true;
return false;
}
}66题解–机器人的运动范围
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路解析
这题本质就是一条搜索，搜索过程中不断判断是否越界，是否符合我们需要的条件。
源代码
public class Solution {
public int movingCount(int threshold, int rows, int cols) {
if (rows <= 0 || cols <= 0 || threshold < 0)
return 0;
boolean[][] isVisited = new boolean[rows][cols];
int count = movingCountCore(threshold, rows, cols, 0, 0, isVisited);
return count;
}
private int movingCountCore(int threshold,int rows,int cols,
int row,int col, boolean[][] isVisited) {
//是否上下左右越界以及位求和是不是满足我们的条件以及是否访问过了
if (row < 0 || col < 0 || row >= rows || col >= cols || isVisited[row][col]
|| cal(row) + cal(col) > threshold)
return 0;
//满足条件，将它标记为已经访问过
isVisited[row][col] = true;
return 1 + movingCountCore(threshold, rows, cols, row - 1, col, isVisited)
+ movingCountCore(threshold, rows, cols, row + 1, col, isVisited)
+ movingCountCore(threshold, rows, cols, row, col - 1, isVisited)
+ movingCountCore(threshold, rows, cols, row, col + 1, isVisited);
}
private int cal(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}67题解–剪绳子
题目描述
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 输入描述: 输入一个数n，意义见题面。（2 <= n <= 60） 输出描述: 输出答案。 示例1 输入 复制 8 输出 复制 18
思路解析
这里我想到的肯定是剪成每段相等，那样乘积应该是最大的吗，但是又不可能每次都出现相等的情况。 如果我们按照如下的策略来剪绳子，则得到的各个段绳子的长度的乘积将最大:当n>=5时，我们尽可能多的剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。
源代码
public class Solution {
public int cutRope(int target){
int a = 0;
int c = 0;
int maxValue = 2;
if (target == 2){
return 1;
}
if (target == 3) {
return 2;
}
if (target % 3 == 0){
maxValue = (int)Math.pow(3,target / 3);
} else{
a = target - 2;
c = a % 3;
maxValue = maxValue * (int)Math.pow(3,a / 3);
if(0 != c){
maxValue = maxValue *c;
}
}
return maxValue;
}
}