intellij idea汉化 分布式机器 树莓派USB algorithm reflection ansible nginx视频 jquery的each遍历方法 jquery清除子元素 oracle修改字段默认值 idea大小写转换快捷键 matlab图像识别 mser算法 mysql分区表优劣分析 java创建字符串数组 网页设计公司 python入门教程 java文件 java中正则表达式 java获取月份 java方法的重载 java匿名对象 linuxshell编程 redis入门指南 英雄联盟体验服转换器 cfqq网吧任务 robotstudio 位置不可用 0x000008e jsp源码下载 painter下载 kz文件 苹果手机怎么微信双开 图片文字提取软件 adb安装 手机上怎么剪辑音乐 易语言tv 唯品会客服在哪 cdr群组快捷键 qupzilla
当前位置: 首页 > 学习教程  > 编程语言

剑指Offer 矩阵中的路径

2021/1/13 19:28:51 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

/*** 矩阵中的路径** 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,* 每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了…


/**
 * 矩阵中的路径
 *
 * 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,
 * 每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。
 * 例如 [abce sfcs adee]\begin{bmatrix} a & b & c &e \\ s & f & c & s \\ a & d & e& e\\ \end{bmatrix}
 * 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,
 * 路径不能再次进入该格子。
 *
 * 示例1:
 *  输入:"ABCESFCSADEE",3,4,"ABCCED"
 *  输出:true
 *
 * 示例2:
 *  输入:"ABCESFCSADEE",3,4,"ABCB"
 *  输出:false
 */
public class JZ065PathInMatrix {

    /**
     * 1 根据给定数组,初始化一个标志位数组,初始化为false,表示从未走过,true表示已经走过,不能走第二遍
     * 2 根据行数和列数,遍历数组,先找到一个与str字符串的第一个元素相匹配的矩阵元素,进入递归hasPath
     * 3 根据i和j先确定一维数组的位置,因为给定的matrix是一个一维数组
     * 4 确定递归终止条件:越界、当前找到的矩阵值不等于数组对应位置的值、已经走过的,这3种情况,都直接false,说明这条路不通
     * 5 若k,就是待判定的字符串str的索引已经判断到了最后一位,此时就说明是匹配成功的
     * 6 递归不断的寻找周围四个格子是否符合条件,只要有一个格子符合条件,就继续再找这个符合条件的格子的四周是否存在符合条件的格子,直到k到达末尾或者不满足递归条件就终止
     * 7 走到上一步,说明上一步是不成功的,我们需要还原一下标志位数组index处的标志位,进入到下一轮的判断
     * @param matrix
     * @param rows
     * @param cols
     * @param str
     * @return
     */
    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str)  {

        if (matrix == null || matrix.length <= 0 || str == null || str.length <= 0 || matrix.length != rows * cols || rows <= 0 || cols <= 0 || rows * cols < str.length) {
            return false;
        }

        boolean[] visited = new boolean[rows * cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hasPath(matrix, i, j, rows, cols, visited, str, 0)) {
                    return true;
                }
            }
        }

        return false;

    }

    private static boolean hasPath(char[] matrix, int i, int j, int rows, int cols, boolean[] visited, char[] str, int k) {

        int index = i * cols + j;

        if (i < 0 || j < 0 || i >= rows || j >= cols || matrix[index] != str[k] || visited[index]) {
            return false;
        }

        if (k == str.length - 1) {
            return true;
        }

        visited[index] = true;

        if (hasPath(matrix, i - 1, j, rows, cols, visited, str, k + 1) ||
        hasPath(matrix, i, j - 1, rows, cols, visited, str, k + 1) ||
        hasPath(matrix, i + 1, j, rows, cols, visited, str, k + 1) ||
        hasPath(matrix, i, j + 1, rows, cols, visited, str, k + 1)) {
            return true;
        }

        visited[index] = false;

        return false;
    }

    public static void main(String[] args) {

        String m = "ABCESFCSADEE";
        String s = "ABCB";
        char[] matrix = m.toCharArray();
        char[] str = s.toCharArray();
        int rows = 3;
        int cols = 4;

        System.out.println(hasPath(matrix, rows, cols, str));
    }

}

 


本文链接: http://www.dtmao.cc/news_show_600079.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?