# 剑指offer（61-67）题解

### 剑指offer（61-67）题解

• 61题解--序列化二叉树
• 62题解--二叉搜索树的第K个结点
• 63题解--数据流中的中位数
• 64题解--滑动窗口的最大值
• 65题解--矩阵中的路径
• 66题解--机器人的运动范围
• 67题解--剪绳子

# 61题解–序列化二叉树

```/*
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个结点

```/*
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);
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题解–数据流中的中位数

```import java.util.ArrayList;
import java.util.Collections;
public class Solution {
ArrayList<Integer>list=new ArrayList<Integer>();
public  void Insert(Integer 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题解–滑动窗口的最大值

```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++)
return list;
}
}```

# 65题解–矩阵中的路径

```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题解–机器人的运动范围

```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题解–剪绳子

```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;
}
}```

0 条评论

• ### 蓝桥杯 k好数 java版

如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有...

• ### 剑指offer（41-50）题解

既然有了通项公式，那么其实我们也能推出这样一个结论，sum如果在n区间长的连续区间内满足，那么这个n区间长的区间是唯一的，不会存在第二个n长的连续区间满足，...

• ### 2015年javaB组1-4题解析与理解

X老板脾气古怪，他们公司的电话分机号都是3位数，老板规定，所有号码必须是降序排列，且不能有重复的数位。比如：

• ### BZOJ3624: [Apio2008]免费道路(最小生成树)

这棵树上有一些0边是必须要选的，我们先把他们找出来，如果数量\$\geqslant k\$显然无解

• ### 1019 数字黑洞 (20 分)

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一...

• ### LWC 61：738. Monotone Increasing Digits

LWC 61：738. Monotone Increasing Digits 传送门：738. Monotone Increasing Digits Probl...

• ### 欧拉计划 Problem7

题目： 第10001个素数 列出前6个素数，它们分别是2、3、5、7、11和13。我们可以看出，第6个素数是13。

• ### 湖南大学程序设计竞赛新生赛（重现赛）

题目链接—点我开启传送门哦！ A.题意：就是求任意两个斐波那契数列的最大公约数！