您好,我有以下方法。它所做的是找到从 N x M 矩阵的左上角到右下角的所有可能路径。我想知道优化速度的最佳方法是什么,因为它现在有点慢。然后将生成的路径存储在一个集合中。
编辑 我忘了澄清你只能向下或向右移动到相邻的位置,不能从你当前位置的对角线
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);
}
}
最佳答案
给定一个长度为 M x N 的图,从 (0,0) 到 (M-1, N-1) 的所有只涉及向右和向下移动的路径都保证恰好包含 M-1 向右移动和 N- 1 向下移动。
这为我们提供了一个有趣的属性:我们可以将从 (0,0) 到 (M-1, N-1) 的路径表示为二进制字符串(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);
}
}
关于java - 优化算法java,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29486548/