Skip to content

Commit d9acdb3

Browse files
committed
fix page build failed
1 parent 4d32b28 commit d9acdb3

File tree

1 file changed

+0
-49
lines changed

1 file changed

+0
-49
lines changed

docs/algorithms/剑指offer.md

Lines changed: 0 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1620,55 +1620,6 @@ public static int LastRemaining_Solution(int n, int m) {
16201620

16211621
解析:回溯法也就是特殊的dfs,需要找到所有的路径,所以每当到达边界条件或抵达目标时,递归返回,由于需要保存路径中的字母,所以递归返回时需要删除路径最后的节点,来保证路径合法。不过本题只有一个解,所以找到即可返回。
16221622

1623-
public class 矩阵中的路径 {
1624-
public static void main(String[] args) {
1625-
char[][]arr = {{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};
1626-
char []str = {'b','c','c','e','d'};
1627-
System.out.println(hasPath(arr, arr.length, arr[0].length, str));
1628-
}
1629-
static int flag = 0;
1630-
public static boolean hasPath(char[][] matrix, int rows, int cols, char[] str)
1631-
{
1632-
int [][]visit = new int[rows][cols];
1633-
StringBuilder sb = new StringBuilder();
1634-
for (int i = 0;i < rows;i ++) {
1635-
for (int j = 0;j < cols;j ++) {
1636-
if (matrix[i][j] == str[0]) {
1637-
visit[i][j] = 1;
1638-
sb.append(str[0]);
1639-
dfs(matrix, i, j, visit, str, 1, sb);
1640-
visit[i][j] = 0;
1641-
sb.deleteCharAt(sb.length() - 1);
1642-
}
1643-
}
1644-
}
1645-
return flag == 1;
1646-
}
1647-
public static void dfs(char [][]matrix, int row, int col, int [][]visit, char []str, int cur, StringBuilder sb) {
1648-
if (sb.length() == str.length) {
1649-
// System.out.println(sb.toString());
1650-
flag = 1;
1651-
return;
1652-
}
1653-
1654-
int [][]pos = {{1,0},{-1,0},{0,1},{0,-1}};
1655-
for (int i = 0;i < pos.length;i ++) {
1656-
int x = row + pos[i][0];
1657-
int y = col + pos[i][1];
1658-
if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0) {
1659-
continue;
1660-
}
1661-
if (visit[x][y] == 0 && matrix[x][y] == str[cur]) {
1662-
sb.append(matrix[x][y]);
1663-
visit[x][y] = 1;
1664-
dfs(matrix, x, y, visit, str, cur + 1, sb);
1665-
sb.deleteCharAt(sb.length() - 1);
1666-
visit[x][y] = 0;
1667-
}
1668-
}
1669-
}
1670-
1671-
16721623
16731624
## 机器人的运动范围
16741625

0 commit comments

Comments
 (0)