2021.02.07 矩阵中的路径

今日题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
image.png
image.png
提示：

  • 1 <= board.length <= 200

  • 1 <= board[i].length <= 200

  • 思路：

本质上就是深度有限搜索。设置两个全局变量word（String）、tag（boolean[][] 记录是否已经访问过），然后遍历二维矩阵中的每个元素，以目前元素为起点，查看是否存在路径，若是存在则直接返回true，遍历结束后若是不存在则直接返回false。

  • 算法过程：

hasPath(row, col, length, board)：用于判断是否含有路径，row、col表示要比较字符所处的行、列，length表示要比较字符在字符串中的索引值。
若length == word.length()，表示已比对完毕，存在路径。
否则在row、col的值合法、board[row][col] == word.charAt(length)、board[row][col]未被访问的情况下，length+1，继续判断该位置的上下左右四个方向是否存在剩下的路径，用has记录判断结果，若不存在剩下的路径，则回退，最后返回has。
大佬改进版本则直接省去了tag标记数组。

  • 自己的菜鸡代码： ```java class Solution { private boolean[][] tag; private String word; public boolean exist(char[][] board, String word) {

    1.   if(board.length == 0 || word.length() == 0) return false;
    2.   //自动初始化为false
    3.   this.tag = new boolean[board.length][board[0].length];
    4.   this.word = word;
    5.   for(int i = 0; i < board.length; i++){
    6.       for(int j = 0; j < board[0].length; j++){
    7.           if(hasPath(i, j, 0, board)){
    8.               return true;
    9.           }
    10.       }
    11.   }
    12.   return false;

    }

    boolean hasPath(int row, int col, int length, char[][] board){

    1.   // 判断是否存在路径
    2.   if(length == word.length()) return true;
    3.   boolean has = false;
    4.   if(row >= 0 && row < board.length && col >= 0 && col < board[0].length && word.charAt(length) == board[row][col]
    5.   && !tag[row][col]){
    6.       ++length;
    7.       tag[row][col] = true;
    8.       has = hasPath(row, col-1, length, board) || hasPath(row, col+1, length, board) 
    9.                   || hasPath(row-1, col, length, board) || hasPath(row+1, col, length, board);
    10.       if(!has){
    11.           // 回退
    12.           --length;
    13.           tag[row][col] = false;
    14.       }
    15.   }
    16.   return has;

    } }

// 大佬改进版本的

  2. - 运行结果：
  4. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/1584832/1612669336367-12bc67be-b571-44e3-8dd6-548229da04f9.png#align=left&display=inline&height=289&margin=%5Bobject%20Object%5D&name=image.png&originHeight=459&originWidth=628&size=28649&status=done&style=none&width=395)
  6. <a name="clwS3"></a>
  7. ### 2021.02.07 机器人的运动范围
  8. 今日题目：地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/1584832/1612686996194-9e75bcf8-9ef9-4eb6-9c4b-0e1de93adeb7.png#align=left&display=inline&height=105&margin=%5Bobject%20Object%5D&name=image.png&originHeight=113&originWidth=253&size=2779&status=done&style=none&width=235)![image.png](https://cdn.nlark.com/yuque/0/2021/png/1584832/1612687008927-a2531495-487a-44a8-82f2-03f6d5c87076.png#align=left&display=inline&height=100&margin=%5Bobject%20Object%5D&name=image.png&originHeight=113&originWidth=260&size=2896&status=done&style=none&width=231)<br />提示：
  10. - 1 <= n,m <= 100
  11. - 0 <= k <= 20
  13. - 思路：这题也是用深度优先搜索的方法。
  15. 算法过程：
  17.    - countPath(int row, int col) ：用于递归计算路径长度
  19. 检查row、col值是否符合要求，若是不符合则返回0；否则返回 1+ 上下左右的可达路径长度。
  21.    - check(int row, int col)：用于检查row、col的值是否符合要求。
  23. 用value来记录每次的数位之和。<br />不符合的情况：row < 0 || row >= rows || col < 0 || col >= cols、value  > k。返回false。<br />符合的话则返回true。
  25. - 自己的菜鸡代码：
  26. ```java
  27. class Solution {
  28.     private boolean[][] tag;
  29.     private int k;
  30.     private int rows;
  31.     private int cols;
  32.     public int movingCount(int m, int n, int k) {
  33.         this.tag = new boolean[m][n];
  34.         this.k = k;
  35.         this.rows = m;
  36.         this.cols = n;
  37.         return countPath(0, 0);
  38.     }
  39.     int countPath(int row, int col){
  40.         // 用于计算路径长度
  41.         int count = 0;
  42.         if(check(row,col)){
  43.             tag[row][col] = true;
  44.             count = 1 + countPath(row, col+1) + countPath(row, col-1) + countPath(row+1, col) + countPath(row-1, col);
  45.         }
  46.         return count;
  47.     }
  49.     boolean check(int row, int col){
  50.         if(row < 0 || row >= rows || col < 0 || col >= cols) return false;
  51.         int value = row / 10 + row % 10 + col / 10 + col % 10;
  52.         if(value <= k && !tag[row][col]) return true;
  53.         return false;
  54.     }
  55. }
  • 运行结果：

image.png

2021.01.22 二叉树中和为某一值的路径（思路还没写）

今日题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
image.pngimage.png
提示：节点总数 <= 10000

  • 思路：这题也好烦555。

  • 自己的菜鸡代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * public class TreeNode {
    4. *     int val;
    5. *     TreeNode left;
    6. *     TreeNode right;
    7. *     TreeNode(int x) { val = x; }
    8. * }
    9. */
    10. class Solution {
    11.   private LinkedList<List<Integer>> lists = new LinkedList<>();
    12.   private LinkedList<Integer> list = new LinkedList<>();
    14.   public List<List<Integer>> pathSum(TreeNode root, int sum) {
    15.       // 本质上是先序遍历
    16.       dfs(root, sum);
    17.       return lists;
    18.   }
    20.   void dfs(TreeNode root, int sum){
    21.       // 怎么回溯
    22.       if(root == null) return;
    23.       list.add(root.val);
    24.       sum -= root.val;
    26.       if(root.left == null && root.right == null && sum == 0){
    27.           lists.add(new LinkedList<>(list));
    28.       }
    29.       dfs(root.left, sum);
    30.       dfs(root.right, sum);
    31.       list.removeLast();
    32.   }
    33. }

  • 运行结果：

image.pngimage.pngimage.png

2021.02.18 字符串的排列

今日题目：输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
image.png
限制：1 <= s 的长度 <= 8

  • 思路：（回溯法）分为两步，第一步是将字符串的第一个字符与后边的字符逐个交换；第二步是固定第一个字符，将后边的部分作为一个字符串整体继续进行相同的操作，很明显就是递归。第三步就是将现第一个字符与原第一个字符交换，即恢复到原来（回溯）。

需要注意的地方：
因为字符串中可能会出现的字符，所以要进行去重操作，设立一个HashSet用于该字符串中已经当过第一个字符的字符，当在每一层的字符串第一个结点与后边相交换时，检查HashSet中是否已经包含后边待交换的字符，若已包含，则直接跳过。

  • 自己的菜鸡代码：

    1. class Solution {
    2.   private List<String> res = new ArrayList<>();;
    3.   private char[] s;
    4.   public String[] permutation(String s) {
    5.       this.s = s.toCharArray();
    6.       dfs(0);
    7.       return res.toArray(new String[res.size()]);
    8.   }
    10.   void dfs(int cur){
    11.       if(cur == s.length - 1){
    12.           res.add(String.valueOf(s));
    13.       }else{
    14.           HashSet<Character> set = new HashSet<>();
    15.           for(int i = cur; i < s.length; i++){
    16.               if(set.contains(s[i])) continue;
    17.               set.add(s[i]);
    18.               char temp = s[cur];
    19.               s[cur] = s[i];
    20.               s[i] = temp;
    22.               dfs(cur + 1);
    23.               // 再交换回来
    24.               temp = s[cur];
    25.               s[cur] = s[i];
    26.               s[i] = temp;
    27.           }
    28.       }
    29.   }
    30. }

  • 运行结果：

image.png