マトリックス内のパス(Java実装)
2265 ワード
本題は剣指offer面接問題66
テストアドレス:https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc出典:牛客網
[プログラミング問題]マトリクスのパス
熱指数:28891時間制限:1秒空間制限:32768 K 1つのマトリクスに文字列のすべての文字を含むパスがあるかどうかを判断する関数を設計してください.パスは、マトリクス内の任意の格子から開始できます.各ステップは、マトリクス内で左、右、上、下に1つの格子を移動できます.1つのパスがマトリクス内の格子を通過した場合、そのパスは格子に入ることができません.例えば、a b c e s f c s a d e行列には「bcced」という文字列の経路が含まれているが、行列の最初の文字bが行列の最初の行の2番目の格子を占めた後、経路が再び格子に入ることができないため、行列には「abcb」という経路が含まれていない.
Java code:
テストアドレス:https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc出典:牛客網
[プログラミング問題]マトリクスのパス
熱指数:28891時間制限:1秒空間制限:32768 K 1つのマトリクスに文字列のすべての文字を含むパスがあるかどうかを判断する関数を設計してください.パスは、マトリクス内の任意の格子から開始できます.各ステップは、マトリクス内で左、右、上、下に1つの格子を移動できます.1つのパスがマトリクス内の格子を通過した場合、そのパスは格子に入ることができません.例えば、a b c e s f c s a d e行列には「bcced」という文字列の経路が含まれているが、行列の最初の文字bが行列の最初の行の2番目の格子を占めた後、経路が再び格子に入ることができないため、行列には「abcb」という経路が含まれていない.
Java code:
package go.jacob.day616;
import org.junit.Test;
public class Demo1 {
/*
*
*/
@Test
public void test() {
String strs = "ABCESFCSADEE";
char[] matrix = strs.toCharArray();
int rows = 3;
int cols = 4;
String str = "A";
boolean flag = hasPath(matrix, rows, cols, str.toCharArray());
System.out.println(flag);
}
/*
* offer :
*/
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
//
if (matrix == null || rows <= 0 || cols <= 0 || str == null || str.length == 0)
return false;
//visited
boolean[] visited = new boolean[rows * cols];
//pathLength
int pathLength = 0;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (hasPathCode(matrix, rows, cols, row, col, str, pathLength, visited))
return true;
}
}
return false;
}
/*
* row,col str[pathLength], ,
* false
*/
private boolean hasPathCode(char[] matrix, int rows, int cols, int row, int col, char[] str, int pathLength,
boolean[] visited) {
if (pathLength == str.length)
return true;
if (row >= 0 && row < rows && col >= 0 && col < cols && matrix[row * cols + col] == str[pathLength]
&& visited[row * cols + col] == false) {
visited[row * cols + col] = true;
pathLength++;
if (hasPathCode(matrix, rows, cols, row + 1, col, str, pathLength, visited)
|| hasPathCode(matrix, rows, cols, row - 1, col, str, pathLength, visited)
|| hasPathCode(matrix, rows, cols, row, col + 1, str, pathLength, visited)
|| hasPathCode(matrix, rows, cols, row, col - 1, str, pathLength, visited))
return true;
// , true false
visited[row * cols + col] = false;
}
return false;
}
}