首页 > 9.9 华为笔试
头像
江湖一夜雨
编辑于 2020-09-09 21:16
+ 关注

9.9 华为笔试

三道笔试题,第一道类似一个字符串的最早子串匹配的位置,不过换成了二维数组的匹配,用暴力检验的方法,80%,最后超时也是正常的,暂时没想到好的办法,可能可以用动态规划吧。第二题是给一个图,然后求递减序列的最大长度,这个题型很常见,用图搜索就可以了,第三题是求树的任意两个连通节点路径的最大异或和,我也是用暴力dfs的方法,没有优化,本以为会超时,但是最后100%通过了。我把第三题答案贴出来分享一下,也求大家指导下第一题的好的思路。
import java.util.Scanner;

public class Main {
    public static int max = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        boolean[] visited = new boolean[n+1];
        int[][] value = new int[n+1][4];
        for(int i=0;i<n;i++){
            int key = scanner.nextInt();
            value[key][0] = scanner.nextInt(); //值
            value[key][1] = scanner.nextInt(); //左儿子
            value[key][2] = scanner.nextInt(); //右儿子
        }
        for(int i=1;i<=n;i++){
            if(!visited[i]){
                dfs(i, value[i][0], value, visited);
                visited[i] = true;
            }
        }
        System.out.println(max);
    }
    // 暴力
    public static void dfs(int i, int count, int[][] value, boolean[] visited){
        if(value[i][1]==-1 && value[i][2]==-1){
            max = Math.max(max, count);
            return;
        }
        if(value[i][1]!=-1){
            int temp = value[value[i][1]][0];
            max = Math.max(max, temp ^ count);
            dfs(value[i][1], count, value, visited);
        }
        if(value[i][2]!=-1){
            int temp = value[value[i][2]][0];
            max = Math.max(max, temp ^ count);
            dfs(value[i][2], count, value, visited);
        }
    }
}


全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐