2

我已经完成了一项 Google Foobar 任务，并且很好奇为什么 2 个似乎等效的实现以不同的方式工作。当第二个解决方案通过所有测试用例时，第一个给我带来“测试 2 失败”。我知道他们两个都没有遵循最佳 OOP 实践，但我很感兴趣第一个实现的确切问题是什么。

1.

public class Answer {
    static Map<Character, LinkedList<Character>> g = new HashMap<Character, LinkedList<Character>>();
    static Set<Character> visited = new HashSet<Character>();
    static ArrayList<Character> ans = new ArrayList<Character>();

    public static void dfs(char v) {
        visited.add(v);
        //some standard code for DFS
        ans.add(v);
    }

    public static String topologicalSort() {

        for (Character element : g.keySet()) {
            if (!visited.contains(element))
                dfs(element);
        }

        //some code to prepare the output
    }

    public static void builGraph(String[] words) {

        //some code to build adjacency list and then use it through g reference 
    }

    public static String answer(String[] words) {

        if (words.length == 1) {
            //some code
        }

        builGraph(words);

        return topologicalSort();
    }

    public static void main(String[] args) {
        //some code
        System.out.println(answer(words));
    } 
}

2.

public class Answer {
    static Map<Character, LinkedList<Character>> g;
    static Set<Character> visited;
    static ArrayList<Character> ans;

    public static void dfs(char v) {
        visited.add(v);
        //some standard code for DFS
        ans.add(v);
    }

    public static String topologicalSort() {
        visited = new HashSet<Character>();
        ans = new ArrayList<Character>();

        for (Character element : g.keySet()) {
            if (!visited.contains(element))
                dfs(element);
        }

        //some code to prepare the output
    }

    public static void builGraph(String[] words) {

        g = new HashMap<Character, LinkedList<Character>>();

        //some code to build adjacency list and then use it through g reference 
    }

    public static String answer(String[] words) {

        if (words.length == 1) {
            //some code
        }

        builGraph(words);

        return topologicalSort();
    }

    public static void main(String[] args) {
        //some code
        System.out.println(answer(words));
    } 
}
4

2 回答 2

1

在第一个实现中，您在哪里清除容器（Map、Set、ArrayList）？一个测试用例可能会多次调用 answer() ，所以我会将 answer() 方法从第一个实现更改为：

public static String answer(String[] words) {
    this.g.clear();
    this.visited.clear();
    this.ans.clear();

    // ...
}
于 2015-11-09T08:41:44.700 回答
0

我不知道测试在检查什么，所以我不知道为什么它失败了。但是，很容易区分这两种实现之间的差异。

在 Java 中（引用4.12.5. Initial Values of Variables）：

对于所有引用类型（第4.3 节），默认值为null.

第二种情况下的对象在null您初始化它们之前被分配，并且您在每次调用topologicalSort. 所以每次调用该方法时，都会创建一个新对象。

在第一个实现中，您只需将它们初始化一次 - 在创建类时。这应该足以让您更深入地研究问题并更好地理解测试在第一次实现中失败的原因。

于 2015-11-09T07:50:16.170 回答