2020.8.22猿辅导开发笔试 第一题
1.逆时针打印完全二叉树的边界节点
边界节点包括：根节点，最左最右节点，叶节点
输入：
5
1 2 3 4 5
5:节点个数
1 2 3 4 5：完全二叉树的层序遍历
输出:
1 2 4 5 3
思想：递归，利用完全二叉树的性质（参考堆排序写法）
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;
//33333333333333
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N=in.nextInt();
a=new int[N];
for (int i = 0; i < N; i++) {
a[i]=in.nextInt();
}
new Main().dfs(0);
}
static int[] a;
static int N;
static HashSet<Integer> set=new HashSet<>();//记录是否访问过
public void dfs(int i){
if(i>=N) return;
System.out.print(a[i]+" ");
set.add(i);
int l=2*i+1;//左子节点
int r=2*i+2;//右子节点
int r_bro=i+1;//右兄弟
int fa=(i-1)/2;//父亲节点
//以下按照左子 右子 右兄弟 父亲的顺序进行dfs
if(0<=l&&l<N&&!set.contains(l)){
dfs(l);
}
else if(0<=r&&r<N&&!set.contains(r)){
dfs(r);
}
else if(0<=r_bro&&r_bro<N&&!set.contains(r_bro)){
dfs(r_bro);
}
else {//这里注意区分当前节点的父节点是不是最靠右的节点
//先判断父节点的右边节点有没有被访问（排序父亲节点是内部节点的情况）
if(!set.contains(fa+1)) dfs(fa+1);
else if(!set.contains(fa)) dfs(fa);
else return;
}
}
}
2.最大子矩阵和
输入输出：
说明：第一行：行数 列数
以下：矩阵值
输出：11，因为第一列与第三列首尾相连且最大，所以为1+3+2+5=11
思想：参照leecode面试题14：最大子矩阵。
本题特殊处理：将输入的矩阵反转，并且将第一行复制到最后一行，枚举长度时注意控制子矩阵的长度
import java.io.*;
import java.util.*;
/*
思想：将所有子矩阵的和求出，取最大。这个过程要转为一维的求最大连续子数组。
*/
public class Main {
public static void main(String[] args) throws IOException {
Scanner in=new Scanner(System.in);
int n=in.nextInt(),m=in.nextInt();
int[][] a=new int[m+1][n];//要点，将原矩阵逆时针转90度，然后将第一行复制到最后一行，来解决首尾链接的情况
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[j][i]=in.nextInt();
}
}
for (int i = 0; i <n; i++) {
a[m][i]=a[0][i];//将第一行复制变为最后一行
}
System.out.println(new Main().getMaxMatrix(a));
}
public int getMaxMatrix(int[][] matrix) {
int x=matrix.length;
int y=matrix[0].length;
int[][] a=new int[x][y];
int mmax=Integer.MIN_VALUE;//记录最大值
//以下开始枚举子矩阵
for(int i=0;i<x;i++){//枚举起点
int[] b=new int[y];//因为是从上开始逐级向下扩展，所以不必重复计算和，只要在上次长度拓展的基础上+就可以了
for(int j=i,t=0;j<x&&t<x-1;j++,t++){//枚举终点：要点：用t来控制子矩阵的上下长度不超过原来矩阵的长度
int sum=Integer.MIN_VALUE;
for(int k=0;k<y;k++){
b[k]+=matrix[j][k];
if(sum<=0){
sum=b[k];
}
else{
sum=b[k]+sum;
}
if(sum>mmax){
mmax=sum;
}
}
}
}
return mmax;
}
} 
