请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。-笔试面试资料

这是qklbishe.com第8723 篇笔试面试资料
提供答案分析,通过本文《请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如   矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如   矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。 KolHuang
//深搜模版 import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param matrix char字符型二维数组       * @param word string字符串       * @return bool布尔型      */     public boolean hasPath (char[][] matrix, String word) {         if(matrix == null || matrix.length == 0 || matrix[0].length == 0)    return false;         visited = new boolean[matrix.length][matrix[0].length];         // write code here         for(int i = 0; i < matrix.length; ++i){             for(int j = 0; j < matrix[0].length; ++j){                 if(dfs(matrix, word, 0, i, j)){                     return true;                 }             }         }         return false;     }     int[][] direction = {{1,0}, {0,1}, {-1,0}, {0,-1}};     boolean[][] visited;     boolean dfs(char[][] matrix, String word, int cur, int x, int y){         if(cur == word.length())    return true;         if(x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length)    return false;         if(visited[x][y])    return false;                  if(word.charAt(cur) != matrix[x][y])    return false;         visited[x][y] = true;         boolean res = false;         for(int i = 0; i < 4; ++i){             int newX = x + direction[i][0];             int newY = y + direction[i][1];             res = res || dfs(matrix, word, cur + 1, newX, newY);         }         visited[x][y] = false;         return res;     } }

今天 15:02:40 回复(0)
C/C++

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如   矩阵中包含一条字符串&quot;bcced&quot;的路径,但是矩阵中不包含&quot;abcb&quot;路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。 Clannad丶Fan

这题是改了吗,我怎么记得以前做过这题,不过用的不是matrix,而是string
class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param matrix char字符型vector<vector<>>       * @param word string字符串       * @return bool布尔型      */     bool hasPath(vector<vector<char> >& matrix, string word) {         if(matrix.empty() || word.empty())             return false;         int row = matrix.size(), col = matrix[0].size();         vector<vector<int>> visit(row, vector<int>(col, 0));         for(int i = 0;i < row;++i)             for(int j = 0;j < col;++j)                 if(helper(visit, matrix, 0, i, j, word))                     return true;         return false;     } private:     bool helper(vector<vector<int>> &v, vector<vector<char>> &m, int index, int i, int j, string &word)     {         if(index == word.size())             return true;         if(i < 0 || i >= m.size() || j < 0 || j >= m[0].size() || v[i][j] == 1 || m[i][j] != word[index])             return false;         v[i][j] = 1;         if(helper(v, m, index + 1, i - 1, j, word) || helper(v, m, index + 1, i + 1, j, word) ||            helper(v, m, index + 1, i, j - 1, word) || helper(v, m, index + 1, i, j + 1, word))             return true;         v[i][j] = 0;         return false;     } };

今天 14:11:44 回复(0)
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如   矩阵中包含一条字符串&quot;bcced&quot;的路径,但是矩阵中不包含&quot;abcb&quot;路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。 Uncle_Yang
dfs解法,标记数组深拷贝。
public class Solution {

    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    private char word[];
    private char matrix[][];
    
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
           this.word=word.toCharArray();
           this.matrix = matrix;
           for(int i=0; i<matrix.length; i++){
               for(int j=0; j<matrix[0].length; j++){
                   if(matrix[i][j]==this.word[0]
                      &&this._hasPath(i,j,0,new boolean[matrix.length][matrix[0].length]))
                       return true;
               }
           }
            return false;
    }
    
    private boolean _hasPath(int i, int j, int index, boolean flag[][]){
        if(index==this.word.length) return true;
        else{
            boolean isSane = (i>=0 && i<matrix.length && j>=0 && j<matrix[0].length
                              && flag[i][j]==false);
            if(isSane&&this.word[index]==this.matrix[i][j]) {
                flag[i][j]=true;
                boolean flag1[][] = new boolean[flag.length][flag[0].length];
                boolean flag2[][] = new boolean [flag.length][flag[0].length];
                boolean flag3[][] = new boolean[flag.length][flag[0].length];
                boolean flag4[][] = new boolean [flag.length][flag[0].length];
                for(int k=0; k<flag.length; k++) flag1[k]=flag[k].clone();
                for(int k=0; k<flag.length; k++) flag2[k]=flag[k].clone();
                for(int k=0; k<flag.length; k++) flag3[k]=flag[k].clone();
                for(int k=0; k<flag.length; k++) flag4[k]=flag[k].clone();
                return this._hasPath(i,j+1,index+1,flag1)||this._hasPath(i+1,j,index+1,flag3)
                    ||this._hasPath(i,j-1,index+1,flag2)||this._hasPath(i-1,j,index+1,flag4);
            }
            else return false;
        }
    }
}

今天 13:20:17 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情