leetcode之回溯

1.矩阵中的路径

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 \begin{bmatrix} a & b & c &e \\ s & f & c & s \\ a & d & e& e\\ \end{bmatrix}\quad???asa?bfd?cce?ese???? 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。 数据范围：, 进阶：时间复杂度，空间复杂度 方法：采用递归的方式，以当前点为起点，分别向上下左右做移动，查看字符是否相同；

  1 import java.util.*;
  2 
  3 class Position{
  4     int x;
  5     int y;
  6     public Position(int x, int y){
  7         this.x = x;
  8         this.y = y;
  9     }
 10     
 11         //重写equals方法, 最佳实践就是如下这种判断顺序:
 12     public boolean equals(Object obj) {
 13         if (!(obj instanceof Position))
 14             return false;   
 15         if (obj == this)
 16             return true;
 17         //this.name.equals(((Person)obj).name);
 18         return (this.x == ((Position)obj).x && this.y == ((Position)obj).y);
 19     }
 20 
 21     public int hashCode(){
 22         return 1;
 23     }
 24 }
 25 
 26 public class Solution {
 27     /**
 28      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 29      *
 30      * 
 31      * @param matrix char字符型二维数组 
 32      * @param word string字符串 
 33      * @return bool布尔型
 34      */
 35     public static boolean hasPath (char[][] matrix, String word) {
 36         // write code here
 37         int rows = matrix.length;
 38         int cols = matrix[0].length;
 39         if(word.length() == 0){
 40             return true;
 41         }
 42         HashSet sets = new HashSet<>();
 43         for(int i = 0; i < rows; i++){
 44             for(int j = 0; j < cols; j++){
 45                 if(matrix[i][j] != word.charAt(0)){
 46                     continue;
 47                 }
 48                 Position curPosition = new Position(i, j);
 49                 boolean flag = hasPath2(matrix, curPosition, sets, word);
 50                 if(flag){
 51                     return flag;
 52                 }
 53             }
 54         }
 55         return false;
 56     }
 57 
 58     public static boolean hasPath2(char[][] matrix,Position cur, HashSet sets,String word){
 59         if(word.length() == 0){
 60             return true;
 61         }
 62         // 第一次处理
 63         int rows = matrix.length;
 64         int cols = matrix[0].length;
 65         //向着4个方向处理
 66         int x = cur.x;
 67         int y = cur.y;
 68         if(word.charAt(0) != matrix[x][y]){
 69             return false;
 70         }else{
 71             if(word.length() == 1){
 72                 return true;
 73             }
 74         }
 75         sets.add(cur);
 76         boolean flag = false;
 77 
 78         //向上处理
 79         if(x - 1>= 0){
 80             Position nextPosition = new Position(x-1, y);
 81             //当前字符串不在
 82             if(!sets.contains(nextPosition)){
 83                 flag = hasPath2(matrix, nextPosition, sets, word.substring(1));
 84             }
 85             sets.remove(nextPosition);
 86         }
 87         if(flag){
 88             sets.remove(cur);
 89             return flag;
 90         }
 91         //向左处理
 92         if(y - 1 >= 0){
 93             Position nextPosition = new Position(x, y - 1);
 94             if(!sets.contains(nextPosition)){
 95                 flag = hasPath2(matrix, nextPosition, sets, word.substring(1));
 96             }
 97             sets.remove(nextPosition);
 98         }
 99         if(flag){
100             sets.remove(cur);
101             return flag;
102         }
103         //向右处理
104         if(y + 1 < cols){
105             Position nextPosition = new Position(x, y + 1);
106             if(!sets.contains(nextPosition)){
107                 flag = hasPath2(matrix, nextPosition, sets, word.substring(1));
108             }
109             sets.remove(nextPosition);
110         }
111         if(flag){
112             sets.remove(cur);
113             return flag;
114         }
115 
116         //向下处理
117         if(x + 1 < rows){
118             Position nextPosition = new Position(x + 1, y);
119             if(!sets.contains(nextPosition)){
120                 flag = hasPath2(matrix, nextPosition, sets, word.substring(1));
121             }
122             sets.remove(nextPosition);
123         }
124         sets.remove(cur);
125         return flag;
126     }
127 }

2. 机器人的运动范围

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格   [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？   数据范围：  ，   进阶：空间复杂度  ，时间复杂度  方法一：采用深度优先的递归调用方式，找出所有可以访问的格子，要求不访问已经访问过的格子；

 1 import java.util.HashSet;
 2 
 3 class Position{
 4     int x;
 5     int y;
 6     public Position(int x, int y){
 7         this.x = x;
 8         this.y= y;
 9     }
10     public int hashCode(){
11         return 1;
12     }
13     public boolean equals(Object obj){
14         if(!(obj instanceof Position)){
15             return false;
16         }
17         if(obj == this){
18             return true;
19         }
20         return (this.x == ((Position)obj).x && this.y == ((Position)obj).y);
21     }
22 }
23 
24 public class Solution {
25     public int movingCount(int threshold, int rows, int cols) {
26         if(threshold == 0){
27             return 1;
28         }
29         HashSet sets = new HashSet<>();
30         Position p = new Position(0, 0);
31         moving2(threshold, rows,  cols, p, sets);
32         return sets.size();
33     }
34     public void moving2(int threshold, int rows, int cols, Position pos, HashSet sets){
35         if(sets.contains(pos)){
36             return;
37         }
38         int x = pos.x;
39         int y = pos.y;
40         int sum = 0;
41         sum = x / 100 + x % 100 / 10 + x % 10 + y / 100 + y % 100 / 10 + y % 10;
42         if(sum > threshold){
43             return;
44         }
45         sets.add(pos);
46         // 向左处理
47         if(x - 1 >= 0){
48             Position pos2 = new Position(x - 1, y);
49             if(!sets.contains(pos2))
50                 moving2(threshold, rows, cols, pos2, sets);
51         }
52         // 向右处理
53         if(x + 1 < cols){
54             Position pos2 = new Position(x + 1, y);
55             if(!sets.contains(pos2))
56                 moving2(threshold, rows, cols, pos2, sets);
57         }
58         // 向上处理
59         if(y - 1 >= 0){
60             Position pos2 = new Position(x, y - 1);
61             if(!sets.contains(pos2))
62                 moving2(threshold, rows, cols, pos2, sets);
63         }
64         // 向下处理
65         if(y + 1 < rows){
66             Position pos2 = new Position(x, y + 1);
67             if(!sets.contains(pos2))
68                 moving2(threshold, rows, cols, pos2, sets);
69         }
70     }
71 }