微软第二道题目0通过率,自己实在想不出错误在哪里,求大神们棒看一眼

0
0
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class Main {

private static int N;
private static int M;
private static int K;
private static int[] layerNumArr;
private static List<List<Integer>> layer;
private static List<Integer> totalList;
private static Set<Integer> leafSet;
private static int[] leafArr;
private static int[][] arr;
private static int p;
private static int[] res;

public static void main(String[] args) {
    read();

    res = new int[N + 1];
    res[1] = 0;
    p = N;

    for (int i = M - 1; i > 0; i--) {
        computeOneLayer(i);
    }

    int[] tranArr = transform(res);
    for (int i = 1; i < tranArr.length - 1; i++) {
        System.out.print(tranArr[i] + " ");
    }
    System.out.print(tranArr[tranArr.length - 1]);
}

public static int[] transform(int[] res){
    int[] tranArr=new int[res.length];
    for(int i=1;i<res.length;i++){
        tranArr[totalList.get(i)]=res[i];
    }
    return tranArr;
}
public static void read() {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    M = sc.nextInt();
    K = sc.nextInt();

    layerNumArr = new int[M];
    for (int i = 0; i < M; i++) {
        layerNumArr[i] = sc.nextInt();
    }
    //layer
    layer = new ArrayList<>();
    totalList = new ArrayList<>();
    totalList.add(0);//index+=1
    for (int i = 0; i < M; i++) {
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < layerNumArr[i]; j++) {
            int num = sc.nextInt();
            list.add(num);
            totalList.add(num);
        }
        layer.add(list);
    }

    //leaf
    leafSet = new HashSet<>();
    leafArr = new int[K];
    for (int i = 0; i < K; i++) {
        int num = sc.nextInt();
        leafArr[i] = num;
        leafSet.add(num);
    }

    arr = new int[N + 1][N + 1];
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            arr[leafArr[i]][leafArr[j]] = sc.nextInt();
        }
    }
}

public static void updateParent(int child) {
    int parent = res[child];
    for (int node = 0; node < child; node++) {
        if (node == child);
        if (arr[node][child] > 1) {
            arr[parent][node] = arr[node][child] - 1;
            arr[node][parent] = arr[node][child] - 1;
        }
    }
}

public static void computeOneLayer(int i) {
    List<Integer> preList = layer.get(i - 1);
    List<Integer> curList = layer.get(i);
    int preSize = preList.size();
    int curSize = curList.size();
    int parentP = preSize - 1;
    int childP = curSize - 1;

    while (leafSet.contains(preList.get(parentP))) {
        parentP--;
    }

    res[p] = preList.get(parentP);
    updateParent(p);//用孩子更新它父亲到所有点的距离
    p--;

    while (childP > 0) {
        childP--;
        int child = curList.get(childP);
        int parent = preList.get(parentP);
        if (arr[child][parent] > 1) {
            parentP--;
            while (leafSet.contains(preList.get(parentP))) {
                parentP--;
            }
            updateParent(p);//用孩子更新它父亲到所有点的距离
        }

        res[p] = preList.get(parentP);
        p--;
    }
}
}

2 answer(s)

0

错误不多,都是些小错误,对你程序做了轻微修改后Accepted,下面贴上修改后的代码,修改处有Modified标识,具体错误请问主自己分析和总结。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class Main {

private static int N;
private static int M;
private static int K;
private static int[] layerNumArr;
private static List<List<Integer>> layer;
private static List<Integer> totalList;
private static Set<Integer> leafSet;
private static int[] leafArr;
private static int[][] arr;
private static int p;
private static int[] res;

public static void main(String[] args) {
    read();

    res = new int[N + 1];
    res[1] = 0;
    p = N;

    for (int i = M - 1; i > 0; i--) {
        computeOneLayer(i);
    }

    int[] tranArr = transform(res);
    for (int i = 1; i < tranArr.length - 1; i++) {
        System.out.print(tranArr[i] + " ");
    }
    System.out.print(tranArr[tranArr.length - 1]);
}

public static int[] transform(int[] res){
    int[] tranArr=new int[res.length];
    for(int i=1;i<res.length;i++){
        tranArr[totalList.get(i)]=res[i];
    }
    return tranArr;
}
public static void read() {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    M = sc.nextInt();
    K = sc.nextInt();

    layerNumArr = new int[M];
    for (int i = 0; i < M; i++) {
        layerNumArr[i] = sc.nextInt();
    }
    //layer
    layer = new ArrayList<>();
    totalList = new ArrayList<>();
    totalList.add(0);//index+=1
    for (int i = 0; i < M; i++) {
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < layerNumArr[i]; j++) {
            int num = sc.nextInt();
            list.add(num);
            totalList.add(num);
        }
        layer.add(list);
    }

    //leaf
    leafSet = new HashSet<>();
    leafArr = new int[K];
    for (int i = 0; i < K; i++) {
        int num = sc.nextInt();
        leafArr[i] = num;
        leafSet.add(num);
    }

    arr = new int[N + 1][N + 1];
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            arr[leafArr[i]][leafArr[j]] = sc.nextInt();
        }
    }
}

public static void updateParent(int child) {
    int parent = res[child];
    child = totalList.get(child);//Modified
    for (int node = 1; node < N+1; node++) {//Modified
        if (node == child);
        if (arr[node][child] > 1) {
            arr[parent][node] = arr[node][child] - 1;
            arr[node][parent] = arr[node][child] - 1;
        }
    }
}

public static void computeOneLayer(int i) {
    List<Integer> preList = layer.get(i - 1);
    List<Integer> curList = layer.get(i);
    int preSize = preList.size();
    int curSize = curList.size();
    int parentP = preSize - 1;
    int childP = curSize - 1;

    while (leafSet.contains(preList.get(parentP))) {
        parentP--;
    }

    res[p] = preList.get(parentP);
    updateParent(p);//用孩子更新它父亲到所有点的距离
    p--;

    while (childP > 0) {
        childP--;
        int child = curList.get(childP);
        int parent = preList.get(parentP);
        if (arr[child][parent] > 1) {
            parentP--;
            while (leafSet.contains(preList.get(parentP))) {
                parentP--;
            }
            res[p] = preList.get(parentP); //Modified
            updateParent(p);//用孩子更新它父亲到所有点的距离
        }

        res[p] = preList.get(parentP);
        p--;
    }
}
}

*小恩不言谢,有空请我吃饭就好*

0
  • 我的想法是
  • read函数——将所有变量保存到全局。
  • updateParent函数——将当前节点的父亲到所有节点的距离更新,根据当前节点的信息。
  • computeOneLayer函数——从后往前遍历当前层节点,与上层节点距离如果为1,该上层节点就是它父亲,如不为1,上层节点的前一个非叶子节点才是它的父亲。
  • transform函数——转换res向量,res向量没有考虑输入点是乱序的情况。

write answer 切换为英文 切换为中文


转发分享