题目详情

首先给出两个节点的地址和数值N，两个地址分别是两个单词的首字母，N是全部节点的数量。随后，以 地址 数值 下一节点的地址 的方式逐行输入N个节点。要求输出两个字母相同后缀的起始地址，如果两个字母没有相同的后缀，则输出-1。

我的版本

在做这道题的时候，发现在Idea能够正常编译的代码到Pat中运行结果为空，未查明原因。

需要注意一个问题：相同value的index不一定相同，例如a在不同word里面的index可能就不同，此时认为具有两个index的a不等同。在我的代码中，使用index+value的方式记录具有不同index的同一value。

import java.util.*;
import java.io.*;
public class Main {
    static class Node {
        String val;
        Node next;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        String i1 = line[0];
        String i2 = line[1];
        int n = Integer.parseInt(line[2]);
        HashMap<String, Node> hm = new HashMap<>();
        HashMap<String, String> rs = new HashMap<>();
        Node n1, n2;
        for (int i = 0; i < n; i ++) {
            line = br.readLine().split(" ");
            n1 = hm.computeIfAbsent(line[0], y -> new Node());
            n1.val = line[0] + line[1];
            n2 = hm.computeIfAbsent(line[2], y -> new Node());
            n1.next = n2;
            rs.put(n1.val, line[0]);
        }
        n1 = hm.get(i1);
        n2 = hm.get(i2);
        String w2 = "";
        while (n2 != null) {
            w2 += n2.val;
            n2 = n2.next;
        }
        n = w2.length();
        while (n1.next != null) {
            int ti = w2.indexOf(n1.val);
            if (ti != -1 && n > ti) {
                n = ti;
                n2 = n1;
            }
            n1 = n1.next;
        }
        if (n != w2.length()) {
            System.out.println(rs.get(n2.val));
        } else {
            System.out.println(-1);
        }
    }
}

参考版本

import java.util.Scanner;
public class Main {
    /**
     * 到牛客网提交，不然会有一组数据超时
     *
     * */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int startA = scanner.nextInt(), startB = scanner.nextInt(), n = scanner.nextInt();
        scanner.nextLine();
        Node1032[] linked = new Node1032[100000 + 11];
        for (int i = 0; i < n; ++i) {
            String[] inputStrings = scanner.nextLine().split("\\s+");
            int address = Integer.parseInt(inputStrings[0]);
            int next = Integer.parseInt(inputStrings[2]);
            Node1032 tempNode = new Node1032();
            tempNode.address = address;
            tempNode.data = inputStrings[1];
            tempNode.next = next;
            linked[address] = tempNode;
        }
        scanner.close();
        boolean tag = false;
        int resultAddress = -1;
        while(startA!=-1) {
            linked[startA].flag = true;
            startA = linked[startA].next;
        }
        while(startB!=-1) {
            if (linked[startB].flag==true) {
                resultAddress = startB;
                tag = true;
                break;
            }
            startB = linked[startB].next;
        }
        if (tag) {
            System.out.printf("%05d\n", resultAddress);
        } else {
            System.out.println(resultAddress);
        }
    }
}
class Node1032 {
    Integer address;
    String data;
    Integer next;
    boolean flag;
}

总结

• 我使用hashmap寻址，并借助字符串的方法进行检索。参考版本通过新建一个超大的list直接寻址
• 参考版本给Node节点设置Flag判断是否为重复点。我的方法有点绕，先将word以string方式存储之后使用indexOf方法进行查询。对比之下，参考方法更简洁。
• 参考版本初始化超大的list，直接占用了至少100011*4byte的内存，真的可取吗？