为什么更改代码中的一行会导致堆栈溢出？

Question

这是一个[联合查找问题]：https://leetcode.com/problems/similar-string-groups/

如果我将行 parents[find(j)] = i; 更改为 parents[find(i)] = j;，代码将导致堆栈溢出。显然路径对于递归 find() 方法来说太深了。但我不知道这种变化有什么不同。有人可以帮忙吗？

class Solution {
    int[] parents;
    public int numSimilarGroups(String[] A) {
        parents = new int[A.length];
        for(int i = 0;i < parents.length;i++) {
            parents[i] = i;
        }
        for(int i = 0;i < A.length;i++) {
            for(int j = 0;j < i;j++) {
                if(similar(A[i],A[j])) {
                    parents[find(j)] = i;
                }
            }
        }
        int ans = 0;
        for(int i = 0;i < parents.length;i++) {
            if(parents[i] == i)
                ans++;
        }
        return ans;
    }

    private int find(int curr) {
        int p = parents[curr];
        if(p != curr) {
            int pp = find(p);
            parents[curr] = pp;
        }
        return parents[curr];
    }

    private boolean similar(String a, String b) {
        int diff = 0;
        int i = 0;
        boolean consecutive = false;
        while(diff <= 2 && i < a.length()) {
            if(a.charAt(i) != b.charAt(i))
                diff++;
            if(i > 0 && a.charAt(i) == a.charAt(i-1))
                consecutive = true;
            i++;
        }
        return diff == 2 || diff == 0 && consecutive;
    }
}

Answer 1

使用parents[find(i)] = j允许一个值通过重复索引可以变成的值变得小于它的索引。这可能会导致 2 个元素彼此反转 indexes/values 的情况。例如：

给定 A.length == 5，您的起始数组如下所示：

parents[0] = 0; parents[1] = 1; parents[2] = 2; parents[3] = 3; parents[4] = 4;

我们使用的值将用于 similar 返回 true。从 i = 2, j = 1 开始，这将调用：

find(2);    //Array doesn't change in recursive function

//Resulting array after applying j to parents[2]:
//          parents[0] = 0; parents[1] = 1; parents[2] = 1; parents[3] = 3; parents[4] = 4;

接下来，i = 3, j = 1：

find(3);    //Array doesn't change in recursive function

//Resulting array after applying j to parents[3]:
//          parents[0] = 0; parents[1] = 1; parents[2] = 1; parents[3] = 1; parents[4] = 4;

然后 i = 3, j = 2:

find(3); find(1);    //Array doesn't change in recursive function

//Resulting array after applying j to parents[1]:
//          parents[0] = 0; parents[1] = 2; parents[2] = 1; parents[3] = 1; parents[4] = 4;

您现在可以看到我们已经设置了无限循环 (parents[1] = 2; parents[2] = 1)。如果使用 1 或 2 调用 find，这将卡在这两个值之间。我们还需要两步才能到达那里。 i = 4, j = 1:

find(4);    //Array doesn't change in recursive function

//Resulting array after applying j to parents[1]:
//          parents[0] = 0; parents[1] = 2; parents[2] = 1; parents[3] = 1; parents[4] = 1;

最后，i = 4, j = 2：

find(4); find(1); find(2); find(1); find(2); find(1); find(2); ...

使用 parents[find(j)] = i 意味着分配的值不能变小，因为 i 总是递增，而 j 在 i 的每次迭代中重复。 j 可以是 0 to i -1.

的任意值

为什么更改代码中的一行会导致堆栈溢出？

Why changing a line in my code will result in a stack overflow?

java

stack-overflow

recursion

union-find