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; } }
全部评论
(3) 回帖