剑指offer三

jiezi

5 年前

前面我们已经刷过《剑指 offer》的一些题目了
剑指 offer(一)
剑指 offer(二)
今天的题目主要使用一些高级的算法，比如动态规划、回溯法来解决主要有以下知识点：

矩阵中的路径（回溯法）
剪绳子（动态规划和贪心算法）
连续子数组的最大和）

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中间向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
例如：在下面的 3 * 4 的矩阵中包含一条字符串”bcced”的路径。但矩阵中不包含字符串“abcb”的路径，因为字符串的第一个字符 b 占据了矩阵中的第一行第二格子之后，路径不能再次进入这个格子。
a b c e
s f c s
a d e e

`解题思路`

首先，在矩阵中任选一个格子作为路径的起点。假设矩阵中某个格子的字符为 c，并且这个格子将对应路径上的第 i 个字符。如果路径上的第 i 个字符正好是 c，那么往相邻的格子寻找路径上的第 i + 1 个字符 。除在矩阵边界上的格子之外，其他格子都有 4 个相邻的格子。
由于路径不能重复进入矩阵的格子，还需要 定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。
当矩阵中坐标为（row,col）的格子和路径字符串中下标为 pathLength 的字符一样时，从 4 个相邻的格子 (row,col-1),(row-1,col),(row,col+1) 以及 (row+1,col) 中去定位路径字符串中下标为 pathLength+ 1 的字符。
如果 4 个相邻的格子都没有匹配字符串中下标为 pathLength+ 1 的字符，表明当前路径字符串中下标为 pathLength 的字符在矩阵中的定位不正确，我们需要 回到前一个字符 (pathLength-1)，然后重新定位。
一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置。

public class Test {

    /**
     * @param matrix 输入矩阵
     * @param rows   矩阵行数
     * @param cols   矩阵列数
     * @param str    要搜索的字符串
     * @return 是否找到 true 是，false 否
     */ 

    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {

        // 输入判断
        if (matrix == null || rows < 1 || cols < 1 || str == null)
            return false;

        //visited: 访问标记数组——用来标识路径是否已经进入过格子 false 表示没有
        boolean[] visited = new boolean[rows * cols];
        for (int i = 0; i < visited.length; i++) {visited[i] = false;
        }

        //pathLength：记录字符串下标
        int pathLength = 0;

        // 开始检索
        for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {if (hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited)) {return true;}

            }
        }
        return false;
    }
    
    /**
     * 回溯搜索算法
     * @param matrix     输入矩阵
     * @param rows       矩阵行数
     * @param cols       矩阵列数
     * @param str        要搜索的字符串
     * @param visited    访问标记数组
     * @param row        当前处理的行号
     * @param col        当前处理的列号
     * @param pathLength 已经处理的 str 中字符个数
     * @return 是否找到 true 是，false 否
     */ 
    public static boolean hasPathCore(char[] matrix, int rows, int cols, int row, int col,
                                      char[] str, int pathLength, boolean[] visited) {

        // 匹配成功
        if (pathLength == str.length)
            return true;

        boolean hasPath = false;

        // 判断位置是否合法
        if (row >= 0 && row < rows && col >= 0 && col < cols
                && matrix[row * cols + col] == str[pathLength] && !visited[row * cols + col]) {

            pathLength++;
            visited[row * cols + col] = true;

            // 按左上右下回溯
            hasPath = hasPathCore(matrix, rows, cols, row, col - 1, str, pathLength, visited)
                    || hasPathCore(matrix, rows, cols, row - 1, col, str, pathLength, visited)
                    || hasPathCore(matrix, rows, cols, row, col + 1, str, pathLength, visited)
                    || hasPathCore(matrix, rows, cols, row + 1, col, str, pathLength, visited);

            // 上下左右都无法匹配到字符则重新回到前一个字符
            if (!hasPath) {
                pathLength--;
                visited[row * cols + col] = false;
            }
        }
        return hasPath;
    }

    public static void main(String[] args) {
        System.out.println(hasPath("ABCESFCSADEE".toCharArray(), 3, 4,"ABCCED".toCharArray())
        );
    }
}
输出：true

矩阵中的路径（回溯法）

解题思路

代码实现

`解题思路`