60、
public class FloorPrintTree_60 {
/**
* 把二叉树打印成多行
*
* 题目描述
* 从上到下按层打印二叉树，同一层结点从左至右输出。
* 每一层输出一行。
*
* 思路：
* 层序遍历二叉树， 前面也已经用过很多次了。
* mark Node 标记一下何时换行就OK了
*/
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (pRoot == null) return res;
TreeNode cur = pRoot;
TreeNode mark = new TreeNode(0);
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> floor = new ArrayList<>();
queue.add(cur);
queue.add(mark);
while (!queue.isEmpty()){
TreeNode tmp = queue.poll();
if (tmp == mark){
res.add(floor);
if (queue.isEmpty()) return res;
floor = new ArrayList<>();
queue.add(mark);
}else {
floor.add(tmp.val);
if (tmp.left != null) queue.add(tmp.left);
if (tmp.right != null) queue.add(tmp.right);
}
}
return res;
}
}
61、
public class SerializeTree_61 {
/**
* 序列化二叉树
*
* 题目描述
* 请实现两个函数，分别用来序列化和反序列化二叉树
*
* 二叉树的序列化是指：
* 把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，
* 从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，
* 序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
*
* 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。*
* 例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树
*
* 思路：
* 层序遍历太复杂，推荐使用先序遍历， 因为先序遍历 方便查找头结点。
* 必会题目。
*
* 注： 用 -> 效率很低
*/
public String Serialize(TreeNode root) {
return proSe(root);
}
private String proSe(TreeNode root){
if (root == null) return "#";
return root.val + "!" + proSe(root.left) + "!" + proSe(root.right);
}
public TreeNode Deserialize(String str) {
String[] s = str.split("!");
Queue<String> queue = new LinkedList<>();
Arrays.stream(s).forEach(e -> queue.add(e));
return proDe(queue);
}
private TreeNode proDe(Queue<String> queue){
String cur = queue.poll();
if (cur.equals("#")) return null;
TreeNode res = new TreeNode(Integer.valueOf(cur));
res.left = proDe(queue);
res.right = proDe(queue);
return res;
}
}
62、
public class KthNode_62 {
/**
* 二叉搜索树的第k个节点
*
* 题目描述
* 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，
* 按结点数值大小顺序第三小结点的值为4。
*
* 思路：
* bst的中序遍历是顺序的。 记录k即可。
*/
TreeNode res;
TreeNode KthNode(TreeNode pRoot, int k)
{
int[] state = {k};
process(pRoot, state);
return res;
}
private void process(TreeNode root, int[] state){
if (root == null) return;
process(root.left,state);
state[0]--;
if (state[0] == 0) res = root;
else process(root.right,state);
}
}
63、
public class Median_63 {
/**
* 数据流中的中位数
*
* 题目描述
* 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
* 那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
* 那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，
* 使用GetMedian()方法获取当前读取数据的中位数。
*
* 思路：
* 经典思路，将数据流拆分成 大根堆 与 小根堆， 大根堆用来存小的一半元素，小根堆用来存大的一半元素，
*
* 用两个堆的对顶来计算中位数。
* 注：
* 1、insert 元素的时候， 需要考虑 小根堆与大根堆 大小， 长度差距超过2 会丢失中位数。
* 2、判断插入元素大小
* 默认 插大根堆，奇数情况大根堆 多一个元素。
*/
PriorityQueue<Integer> heapMin = new PriorityQueue<>();
PriorityQueue<Integer> heapMax = new PriorityQueue<>((o1, o2) -> o2-o1);
public void Insert(Integer num) {
heapMax.add(num);
if (heapMin.size() != 0 && heapMax.peek() > heapMin.peek()) {
Integer temp = heapMin.poll();
heapMin.add(heapMax.poll());
heapMax.add(temp);
}
if (heapMax.size() > heapMin.size() + 1) heapMin.add(heapMax.poll());
}
public Double GetMedian() {
if (heapMin.size() == heapMax.size())return (heapMax.peek() + heapMin.peek()) / 2.0;
return (double) heapMax.peek();
}
}
64、
public class MaxInWindows_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]}。
*
* 思路 ： 经典滑动窗口问题
*
* 核心 ： 维护一个单调递减的最大长度为3的最大值队列
* 保证队列头始终为当前窗口的最大值， 新加入的元素e，
* e前面的元素（队尾元素）比e小，就弹出。直到跟e相等将e插入
* 队列头清空越界元素，超出长度，把头弹出。
*/
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> res = new ArrayList<>();
LinkedList<Integer> queue = new LinkedList<>();//存index ，方便控制元素是否在窗口内
if (size == 0)return res; // 特判！！
for (int i = 0; i < num.length; i++) {
if ( !queue.isEmpty() && queue.peek() + size -1 < i) queue.pop();//弹出队首
while (!queue.isEmpty() && num[queue.getLast()] < num[i]) queue.removeLast();
queue.add(i);
if (i >= size - 1) res.add(num[queue.peek()]);
}
return res;
}
}
65、
public class HasPath_65 {
/**
* 矩阵中的路径
*
* 题目描述
* 请设计一个函数，用来判断在一个矩阵中是否存在一条
* 包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，
* 每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
* 如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
* 例如
* a b c e
* s f c s
* a d e e
* 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
* 因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，
* 路径不能再次进入该格子
*
* 思路：
* 这是一道经典搜索问题
* 每个值都需要作为路径开始，向上下左右校验，能走通就继续走。
* flag数组 用来规避 已经走过的路径
*
*/
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
int k = 0;
boolean[] flag = new boolean[matrix.length];
for (int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if (judge(matrix, i, j, rows, cols, flag, str, 0)){
return true;
}
}
}
return false;
}
public boolean judge(char[] matrix, int i, int j,int rows, int cols, boolean[] flag,char[] str, int k){
int index = i * cols + j;
if(i<0 || j < 0 || i >= rows || j >= cols || str[k] != matrix[index] || flag[index] == true) return false;
if (k == str.length - 1) return true;
flag[index] = true;
if(judge(matrix, i+1, j, rows, cols, flag, str, k+1)||
judge(matrix, i-1, j, rows, cols, flag, str, k+1)||
judge(matrix, i, j+1, rows, cols, flag, str, k+1)||
judge(matrix, i, j-1, rows, cols, flag, str, k+1)
){
return true;
}
flag[index] = false;
return false;
}
}
66、
public class RobotMovingCount_66 {
/**
* 机器人运动范围
*
* 题目描述
* 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，
* 每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
* 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38）
* ，因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
*
* 思路
* 从左上角开始往 右边和下边前进，用二维数组将走过的位置标记为1。统计1的个数
*/
public int movingCount(int threshold, int rows, int cols)
{
int[][] arr = new int[rows][cols];
int count = 0;
process(arr, 0 ,0, threshold);
for (int i = 0; i < rows ; i++) {
for (int j = 0; j < cols; j++) {
if (arr[i][j] == 1) count++;
}
}
//PrintUtil.printMatrix(arr);
return count;
}
private void process(int[][] arr, int i, int j , int threshold){
if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || !judge(i,j,threshold) || arr[i][j] == 1) return;
arr[i][j] = 1;
process(arr,i+1,j,threshold);
process(arr,i,j+1,threshold);
}
private boolean judge( int i, int j, int threshold){
int sum = i%10 + i/10 + j%10 + j/10;
return sum <= threshold ? true : false;
}
}
67、
public class CutRope_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。
*
* 思路：
* 小学奥数题，贪心问题。核心就是凑 3 ， 余1时 2*2 ， 余 2时 3*2。
*
* 证明 m 与 （m-3）*3 比大小
* （m-3）*3 - m > 0 => m > 4.5 即 m > 5 恒成立
* 讨论 m = 4 ， 2*2 > 1*3
*
* 代码边界未处理： n = 2 时 ， 剪的话 return 1， 不剪 return 2
* n = 3 ， 同理 return 2，
* 这样也可以 AC
*/
public int cutRope(int n) {
int m = n%3;
if (m == 1){
return (int) Math.pow( 3, n/3 - 1) * 4;
}else if (m == 2){
return (int) Math.pow( 3, n/3) * 2;
}else {// m == 0
return (int) Math.pow( 3, n/3);
}
}
}
网友评论