9月9日奇安信java笔试两道编程题：91 100

第一题最后9%的错误似乎是忘记判断要杀的进程不存在情况，如果不存在则输出0

import java.util.*;

/**
 *
 * 根据pid杀进程，查询杀了多少进程，90%
 * 先用Map<Integer,Set<Integer>>建立一个父进程与子进程的映射,父---一对多--->子，、
 * 注意处理ppid为0,根据题目要求这个表示无父进程
 * 然后用要杀的进程做深度优先，依次杀掉，看函数dfs的实现既可以明白
 * dfs时维护一个Set<Integer> 表示已经杀掉的进程id
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] line1 = in.nextLine().split(" ");
        String[] line2 = in.nextLine().split(" ");
        int killId = in.nextInt();
        int[] pids = new int[line1.length];
        int[] ppids = new int[line2.length];
        for (int i = 0; i < pids.length; i++) {
            pids[i] = Integer.parseInt(line1[i]);
        }
        for (int i = 0; i < ppids.length; i++) {
            ppids[i] = Integer.parseInt(line2[i]);
        }

        Main main = new Main();
        int result = main.getResult(pids, ppids, killId);
        System.out.println(result);
    }

    private int getResult(int[] pid, int[] ppid, int killId) {
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < ppid.length; i++) {
            if (ppid[i] == 0) {
                continue;
            } else if (map.containsKey(ppid[i])) {
                map.get(ppid[i]).add(pid[i]);
            } else {
                Set<Integer> tmp = new HashSet<>();
                tmp.add(pid[i]);
                map.put(ppid[i], tmp);
            }
        }
        return dfs(killId, map, new HashSet<>());
    }

    private int dfs(int pid, HashMap<Integer, Set<Integer>> map, Set<Integer> hasKillSet) {
        int result = 1;
        hasKillSet.add(pid);
        if (map.containsKey(pid)) {
            Set<Integer> killLists = map.get(pid);
            for (int id : killLists) {
                if (!hasKillSet.contains(id)) {
                    result += dfs(id, map, hasKillSet);
                }
            }
        }
        return result;
    }
}

import java.util.Scanner;

/**
 * 两个人找他们的共同祖先
 * 100%
 * 不要想的太复杂了，用什么构成二叉树之类的，直接用数组，即使是普通的二叉树都能直接做
 * 首先知道题目的输入是以层次遍历的方式构造二叉树，空节点用-1表示
 * 有个特性一个节点i(i为数组下标+1)的父节点下标为2 * i
 * 两个节点的共同祖先，那么先找到这个两个节点的i(数组下标+1),
 * 不断取最小的那个*2，最后两者相等的那个下标就是父节点小标
 * 同时注意处理一下，边界条件就可以了
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int count = (int) Math.pow(2, n) - 1;
        int[] node = new int[count];

        for (int i = 0; i < count; i++) {
            node[i] = in.nextInt();
        }

        int objOne = in.nextInt();
        int objTwo = in.nextInt();

        Main main = new Main();
        int result = main.getResult(node, objOne, objTwo);
        System.out.println(result);
    }

    private int getResult(int[] node, int objOne, int objTwo) {
        int indexOne = findIndex(node, objOne);
        int indexTwo = findIndex(node, objTwo);
        int indexUseOne = indexOne + 1;
        int indexUseTwo = indexTwo + 1;

        if (indexOne == -1 || indexTwo == -1) {
            return -1;
        } else if (node[indexOne] == -1 || node[indexTwo] == -1) {
            return -1;
        } else {
            while (indexUseOne != indexUseTwo) {
                if (indexUseOne < indexUseTwo) {
                    indexUseTwo = indexUseTwo / 2;
                } else {
                    indexUseOne = indexUseOne / 2;
                }
            }
            return node[indexUseOne - 1];
        }
    }

    private int findIndex(int[] node, int op) {
        for (int i = 0; i < node.length; i++) {
            if (node[i] == op) {
                return i;
            }
        }
        return -1;
    }
}