三道笔试题，第一道类似一个字符串的最早子串匹配的位置，不过换成了二维数组的匹配，用暴力检验的方法，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) 回帖