代码之家 › 专栏 › 技术社区 › daniel

java—如何避免将全局外部变量作为递归函数的输出

lcs dynamic-programming recursion algorithm java

daniel · 技术社区 · 7 年前

我有这个代码来查找“所有最长的公共序列”及其长度。

public class LCS {
    static Set<String> lcsList = new HashSet<>();

    public static int[][] twoStringMatrix(String a, String b) {
        int arr[][] = new int[a.length() + 1][b.length() + 1];

        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    arr[i][j] = Math.max(arr[i][j - 1], arr[i - 1][j]);
                }
            }
        }
        return arr;
    }

    public static int lengthLcs(int[][] twoStringMatrix) {
        return twoStringMatrix[twoStringMatrix.length - 1][twoStringMatrix[0].length - 1];
    }

    public static void allPaths(String a, String b, int i, int j, String s, int arr[][]) {
        if (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                allPaths(a, b, i - 1, j - 1, a.charAt(i - 1) + s, arr);
            } else if (arr[i][j - 1] == arr[i - 1][j]) {
                allPaths(a, b, i, j - 1, s, arr);
                allPaths(a, b, i - 1, j, s, arr);
            } else if (arr[i][j - 1] > arr[i - 1][j]) {
                allPaths(a, b, i, j - 1, s, arr);
            } else if (arr[i][j - 1] < arr[i - 1][j]) {
                allPaths(a, b, i - 1, j, s, arr);
            }
        } else {
            lcsList.add(s);
        }
    }

    public static void main(String[] args) {
        String b = "abbaecde";
        String a = "abacbae";

        System.out.println("length = " + twoStringMatrix(a, b).length);
        System.out.println("length = " + twoStringMatrix(a, b)[0].length);
        allPaths(a, b, a.length(), b.length(), "", twoStringMatrix(a, b));
        System.out.println((lcsList));
    }
}

这个代码的问题是我必须使用 lcsList 作为“全局”变量。

如何避免访问中的外部变量 allPaths ?

我可能可以这样做,但看起来不对:

public static void getAll(String a, String b, int i, int j, String s, int arr[][]){
    allPaths(a, b, a.length(), b.length(), "", twoStringMatrix(a, b));
    System.out.println(lcsList);
    lcsList.clear();
}

如果这个类中有100个函数,它们都有这个外部变量呢?这似乎是一种不好的做法。

1 回复 | 直到 7 年前

Devstr 7 年前

您可以将可变容器作为累加器参数传递,如下所示: 注意新的 paths 参数

public static void allPaths(String a, String b, int i, int j, String s, int[][] arr, List<String> paths) {
    if (i > 0 && j > 0) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            allPaths(a, b, i - 1, j - 1, a.charAt(i - 1) + s, arr, paths);
        } else if (arr[i][j - 1] == arr[i - 1][j]) {
            allPaths(a, b, i, j - 1, s, arr, paths);
            allPaths(a, b, i - 1, j, s, arr, paths);
        } else if (arr[i][j - 1] > arr[i - 1][j]) {
            allPaths(a, b, i, j - 1, s, arr, paths);
        } else if (arr[i][j - 1] < arr[i - 1][j]) {
            allPaths(a, b, i - 1, j, s, arr, paths);
        }
    } else {
        paths.add(s);
    }
}

public static void main(String[] args) {
    String b = "abbaecde";
    String a = "abacbae";

    final List<String> paths = new ArrayList<>();
    allPaths(a, b, a.length(), b.length(), "", twoStringMatrix(a, b), paths);
    System.out.println((paths));
}

我得到的结果包含重复项( [abbae, abace, abace, abace] )所以你可能想使用 Set 而是:

 final Set<String> paths = new HashSet<>();

P、我还注意到,使用字符串串联来构造路径并不是很有效,因为 String 每次创建对象时(作为 一串 s是不可变的)。你应该使用 StringBuilder 及其 insert 活动