优化算法java

Question

嗨，我有以下方法。它所做的是找到从上到左到右下角的N矩阵的所有可能的路径。我想知道什么是最好的方式来优化它的速度，因为它现在有点慢。生成的路径然后存储在一个集合中。

编辑我忘了澄清您只能向下或右移到相邻的位置，没有从当前位置的对角线。

For example
ABC
DEF
GHI

从左上角到右下角的路径是ADEFI。

static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) {
    String newString = tempString + arr[i][j];
    if (i == m -1 && j == n-1) {
        palindrome.add(newString);
        return;
    }
    //right
    if (j+1 < n) {
        printPaths (newString, i, j+1, m, n, arr, palindrome);
    }
    //down
    if (i+1 < m) {
        printPaths (newString, i+1, j, m, n, arr, palindrome);          
    }
}

这里的编辑是代码的全部

public class palpath {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("palpath.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("palpath.out")));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int d = Integer.parseInt(st.nextToken());


        char[][] grid = new char [d][d];

        String index = null;

        for(int i = 0; i < d; i++)
        {
            String temp = br.readLine();
            index = index + temp;
            for(int j = 0; j < d; j++)
            {
                grid[i][j] = temp.charAt(j);
            }
        }

        br.close();

        int counter = 0;

        HashSet<String> set = new HashSet<String>();
        printPaths ("", 0, 0, grid.length, grid[0].length, grid, set);

        Iterator<String> it = set.iterator();
        while(it.hasNext()){
            String temp =  it.next();
            StringBuilder sb = new StringBuilder(temp).reverse();
            if(temp.equals(sb.toString()))  {
                counter++;
            }

        }




        pw.println(counter);
        pw.close();

    }


        static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) {
            String newString = tempString + arr[i][j];
            if (i == m -1 && j == n-1) {
                palindrome.add(newString);
                return;
            }
            //right
            if (j+1 < n) {
                printPaths (newString, i, j+1, m, n, arr, palindrome);
            }
            //down
            if (i+1 < m) {
                printPaths (newString, i+1, j, m, n, arr, palindrome);          
            }
        }

Answer 1

给定一个长度为M的图，从(0,0)到(M1，N1)的所有仅涉及向右和向下移动的路径都保证包含完全M-1向右移动和N-1向下移动。

这给我们带来了一个有趣的性质:我们可以将从(0,0)到(M-1，N1)的路径表示为二进制字符串(0表示向右移动，1表示向下移动)。

因此，问题是:我们能以多快的速度打印出该位字符串的排列列表？

相当快。

public static void printPaths(char[][] arr) {
    /* Get Smallest Bitstring (e.g. 0000...111) */
    long current = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        current <<= 1;
        current |= 1;
    }

    /* Get Largest Bitstring (e.g. 111...0000) */
    long last = current;
    for (int i = 0; i < arr[0].length - 1; i++) {
        last <<= 1;
    }

    while (current <= last) {
        /* Print Path */
        int x = 0, y = 0;
        long tmp = current;
        StringBuilder sb = new StringBuilder(arr.length + arr[0].length);
        while (x < arr.length && y < arr[0].length) {
            sb.append(arr[x][y]);
            if ((tmp & 1) == 1) {
                x++;
            } else {
                y++;
            }
            tmp >>= 1;
        }
        System.out.println(sb.toString());

        /* Get Next Permutation */
        tmp = (current | (current - 1)) + 1;
        current = tmp | ((((tmp & -tmp) / (current & -current)) >> 1) - 1);
    }
}

Answer 2

您在字符串内存管理上花费了大量时间。

Java中的字符串是可变的吗？如果可以在字符串中更改字符，那么将字符串的长度设置为n+m，并在每次迭代时使用这是惟一的string，set (i+j)th char。如果它们不是可变的，请使用char数组或类似的数组，并在末尾将其转换为字符串。

Answer 3

对于给定大小的数组，所有路径都有N+M+1项(N+M步骤)，因此优化的第一步是消除递归，分配数组并在显式堆栈上运行while递归。

每个部分路径可以用一个或两个步骤扩展:右或向下。因此，您可以轻松地创建一个显式堆栈，其中包含访问的位置以及在每个位置上所采取的步骤。将位置(0,0)放置到堆栈中，并执行阶段(步骤)为“none”，然后：

while stack not empty {
    if stack is full /* reached lower-right corner, path complete */ {
        print the path;
        pop;
    }
    else if stack.top.phase == none {
        stack.top.phase = right;
        try push right-neighbor with phase none;
    }
    else if stack.top.phase == right {
        stack.top.phase = down;
        try push down-neighbor with phase none;
    }
    else /* stack.top.phase == down */ {
        pop;
    }
}