百度笔试3/29 Java算法题目

//一开始一直30%，后来改用long就AC了
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long res = n * (n - 1) - 1;
        System.out.println(res);
    }
}

//剩20多分钟时候开始写的，过了60%超内存了
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeNode[] nodes = new TreeNode[n];
        for(int i = 0;i < n;i++){
            int t = sc.nextInt();
            nodes[i] = new TreeNode(t,n);
        }
        for(int i = 0;i < n - 1;i++){
            int u = sc.nextInt();
            u -= 1;
            int v = sc.nextInt();
            v -= 1;
            nodes[u].children[v] = nodes[v];
            nodes[v].children[u] = nodes[u];
        }
        int res = Integer.MIN_VALUE;
        for(int i = 0;i < n;i++){
            res = Math.max(res,getMax(nodes[i],Integer.MIN_VALUE,0));
        }
        System.out.println(res);
    }

    private static int getMax(TreeNode node,int pre,int cnt){
        if(node == null){
            return cnt;
        }
        if(node.val <= pre){
            return cnt;
        }
        cnt++;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i < node.children.length;i++){
            max = Math.max(max,getMax(node.children[i],node.val,cnt));
        }
        return max;
    }
}

class TreeNode{
    public int val;
    public TreeNode[] children;
    public TreeNode(){
    }
    public TreeNode(int val,int len){
        this.val = val;
        children = new TreeNode[len];
    }
}