首页 > 2020.8.22猿辅导开发笔试 第一题

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.最大子矩阵和

输入输出:image-20200822232609763

说明:第一行:行数 列数

            以下:矩阵值

输出: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) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐