京东笔试第一道编程题，求逃生最少用时，附java代码

我的思路是对根节点的子树遍历，求节点数最多的子树。就是逃生的最少时间

 package leetcode.jd_test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;

/**
 * Main
 * create by chenshihang on 2019/4/13
 */
public class Main {


    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int)in.nval;
        int a,b;
        Node[] nodes = new Node[n+1];
        for(int i=1;i<=n;i++){
            Node node = new Node(i);
            nodes[i] = node;
        }
        for(int i=1;i<n;i++){
            in.nextToken();a=(int)in.nval;
            in.nextToken();b=(int)in.nval;
            nodes[a].integers.add(b);
            nodes[b].integers.add(a);
        }

        int max = 0;
        List<Integer> integers = nodes[1].integers;
        for(Integer item:integers){
            int count = getNodeEdge(nodes,item,1);
            max = Math.max(max,count);
        }

        System.out.println(max+1);

    }

    /**
     * 求unBL 边忽略后，node[i]节点连通的节点数
     * @param nodes
     * @param i
     * @param unBL 忽略的节点
     * @return
     */
    static int getNodeEdge(Node[] nodes,int i,int unBL){
        int count = 0;
        List<Integer> integers = nodes[i].integers;
        count +=integers.size()-1;
        for(Integer item:integers){
            if(item == unBL)
                continue;
            count+=getNodeEdge(nodes,item,nodes[i].val);
        }

        return count;
    }

    static class Node{
        int val;
        List<Integer> integers;

        public Node(int val){
            this.val = val;
            integers = new ArrayList<>();
        }
    }

}

第二题代码，没考虑最优组合，只过了73%

package leetcode.youyong.str_match;

import java.util.Scanner;

public class KMP {

    /**
     * 求出一个字符数组的next数组
     * @param t 字符数组
     * @return next数组
     */
    public static int[] getNextArray(char[] t) {
        int[] next = new int[t.length+1];
        next[0] = -1;
        next[1] = 0;
        int k;
        for (int j = 2; j < t.length; j++) {
            k=next[j-1];
            while (k!=-1) {
                if (t[j - 1] == t[k]) {
                    next[j] = k + 1;
                    break;
                }
                else {
                    k = next[k];
                }
                next[j] = 0;  //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
            }
        }
        return next;
    }

    /**
     * 对主串s和模式串t进行KMP模式匹配
     * @param s 主串
     * @param t 模式串
     * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1
     */
    public static int kmpMatch(String s, String t){
        char[] s_arr = s.toCharArray();
        char[] t_arr = t.toCharArray();
        int[] next = getNextArray(t_arr);
        int i = 0, j = 0;
        while (i<s_arr.length && j<t_arr.length){
            if(j == -1 || s_arr[i]==t_arr[j]){
                i++;
                j++;
            }
            else
                j = next[j];
        }
        if(j == t_arr.length)
            return i-j;
        else
            return -1;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = Integer.valueOf(in.nextLine());
        String[] strings = new String[m];
        for(int i=0;i<m;i++){
            strings[i]=in.nextLine();
        }
        String t = in.nextLine();
        int count = 0;
        for(int i=0;i<m;i++){
            int matchIndex = kmpMatch(t,strings[i]);
            while (matchIndex>=0){
                StringBuilder stringBuilder = new StringBuilder(t.substring(0,matchIndex));
                int le = strings[i].length();
                while (le>0){
                    stringBuilder.append('1');
                    le--;
                }
                stringBuilder.append(t.substring(matchIndex+strings[i].length(),t.length()));
                t = stringBuilder.toString();
                count++;
                matchIndex = kmpMatch(t,strings[i]);
            }

        }
        System.out.println(count);
    }
}