京东2019年春暑期实习笔试

 1 package testJD;
 2 import java.util.ArrayList;
 3 import java.util.HashMap;
 4 import java.util.List;
 5 import java.util.Scanner;
 6 
 7 public class test1 {
 8     public static void main(String[] args) {
 9         Scanner sc = new Scanner(System.in);
10         int N = sc.nextInt();
11         HashMap<Integer, List<Integer>> map = new HashMap<>();
12         for (int i = 0; i < N - 1; i++) {
13             int a = sc.nextInt();
14             int b = sc.nextInt();
15             if (a < b) {
16                 List<Integer> list = map.get(a);
17                 if (list == null) {
18                     list = new ArrayList<>();
19                     map.put(a, list);
20                 }
21                 list.add(b);
22             } else {
23                 List<Integer> list = map.get(b);
24                 if (list == null) {
25                     list = new ArrayList<>();
26                     map.put(b, list);
27                 }
28                 list.add(a);
29             }
30 
31         }
32 
33         List<Integer> children = map.get(1);
34         int len = children.size();
35         int max = 0;
36         for (int i = 0; i < len; i++) {
37             int child = children.get(i);
38             max = Math.max(max, minTime(map, child));
39         }
40         System.out.println(max);
41 
42     }
43 
44 
45     public static int minTime(HashMap<Integer, List<Integer>> map, int root) {
46         List<Integer> children = map.get(root);
47         if (children == null || children.size() == 0) {
48             return 1;
49         }
50         int len = children.size();
51         int sum = 1;
52         for (int i = 0; i < len; i++) {
53             int child = children.get(i);
54             sum += minTime(map, child);
55         }
56         return sum;
57 
58     }
59 
60 }

package testJD;

import java.util.ArrayList;
import java.util.Scanner;

public class test2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();
        ArrayList<String> input = new ArrayList<>();
        for(int i=0;i<num;i++){
            input.add(sc.nextLine());
        }
        String target = sc.nextLine();
        int count = 0;
        for(int i=0;i<input.size();i++){
            int[] next = kmpnext(input.get(i));
            while(kmp(target,input.get(i),next)!=-1){
                int res = kmp(target, input.get(i),next);
                target=target.substring(0,res)+target.substring(res+input.get(i).length());
//                System.out.println("target: "+target);
                count++;
            }
        }
        System.out.println(count);
    }

    public static int kmp(String str, String dest,int[] next){//str文本串  dest 模式串
        for(int i = 0, j = 0; i < str.length(); i++){
            while(j > 0 && str.charAt(i) != dest.charAt(j)){
                j = next[j - 1];
            }
            if(str.charAt(i) == dest.charAt(j)){
                j++;
            }
            if(j == dest.length()){
                return i-j+1;
            }
        }
        return -1;
    }
    public static int[] kmpnext(String dest){
        int[] next = new int[dest.length()];
        next[0] = 0;
        for(int i = 1,j = 0; i < dest.length(); i++){
            while(j > 0 && dest.charAt(j) != dest.charAt(i)){
                j = next[j - 1];
            }
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}