跳转至

带你快速刷完67道剑指offer

这是六则或许对你有些许帮助的信息:

⭐️1、阿秀与朋友合作开发了一个编程资源网站，目前已经收录了很多不错的学习资源和黑科技（附带下载地址），如过你想要寻求合适的编程资源，欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份阿秀从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解 如果可以的话求个B站三连，感谢！

3、😊 分享一个阿秀自己私藏的黑科技网站，点此直达，主要是各类小众实用APP、网站等，除此外也包括高清影视、音乐、电视剧、AI、纪录片、英语四六级考试、考研考公、副业等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23/24/25届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。

No65、矩阵中的路径

牛客网原题链接

题目描述

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

示例1

输入

Text Only
1
"ABCESFCSADEE",3,4,"ABCCED"

返回值

Text Only
1
true

示例2

输入

Text Only
1
"ABCESFCSADEE",3,4,"ABCB"

返回值

Text Only
1
false

1、DFS

这道题是典型的深度优先遍历DFS的应用，原二维数组就像是一个迷宫，可以 //上下左右四个方向行走 我们的二维数组board中每个数都作为起点和给定的字符串做匹配，我们需要 一个和原二维数组board等大小的visited数组，是bool型的，用来记录当前位置 是否被访问过。因为题目要求一个cell只能被访问一次。 如果二维数组的当前字符和目标字符串str对应的字符相等，则对其上下左右四个邻字 符串分别调用dfs的递归函数，只要有一个返回true，那么就表示找到对应的字符串

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool dfs(vector<vector<char>> &board, char* str, int index, int x, int y,
    vector<vector<bool>>& visited) 

{
    if (index == strlen(str)) return true;//搜寻超过路径长度，符合条件，返回true，//此时已经超过最大程度了 strlen返回不带 ‘\0’的长度，此时str[k]已经越界了，所以这个判断一定要放在函数开头，如果放在if之后，str[k]会越界
    if ((x < 0) || (y < 0) || (x >= board.size()) || (y >= board[0].size()))
        return false;//访问越界，终止，返回false
    if (visited[x][y]) return false;//之前访问过，剪枝
    if (board[x][y] != str[index]) return false;//不相等，剪枝
    visited[x][y] = true;
    if (dfs(board, str, index + 1, x, y - 1, visited) || //上
        dfs(board, str, index + 1, x, y + 1, visited) ||     //下
        dfs(board, str, index + 1, x - 1, y, visited) ||     //左
        dfs(board, str, index + 1, x + 1, y, visited))      //右
        return true; //有符合要求的

    visited[x][y] = false;//记得此处改回false，以方便下一次遍历搜索。
    return false;
}

bool hasPath(char* matrix, int rows, int cols, char* str)
{
    if (str == NULL || rows <= 0 || cols <= 0)
        return false;
    vector<vector<char>> board(rows, vector<char>(cols));
    for (int i = 0; i < rows; ++i) {//将matrix装入二维数组board中
        for (int j = 0; j < cols; ++j) {
            board[i][j] = matrix[i * cols + j];
        }
    }
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (dfs(board, str, 0, i, j, visited) == true)
                return true;//以矩阵board中的每个字符为起点进行广度优先搜索
            //找到一个符合条件的即返回true.
        }
    }
    return false;//遍历完都没找到匹配的路径，返回false
}

2、回溯法 写法非常的好啊

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*参数说明  k 字符串索引初始为0即先判断字符串的第一位*/
bool judge(char* matrix, int rows, int cols, int i, int j, char* str, int k, bool* flag)
{
    //因为是一维数组存放二维的值，index值就是相当于二维数组的（i，j）在一维数组的下标
    int index = i * cols + j;
    //flag[index]==true,说明被访问过了，那么也返回true;
    if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == true)
        return false;
    //字符串已经查找结束，说明找到该路径了
    if (str[k + 1] == '\0') return true;
    //向四个方向进行递归查找,向左，向右，向上，向下查找
    flag[index] = true;//标记访问过 //要走的第一个位置置为true，表示已经走过了0

      //回溯，递归寻找，每次找到了就给k加一，找不到，还原
    if (judge(matrix, rows, cols, i - 1, j, str, k + 1, flag)
        || judge(matrix, rows, cols, i + 1, j, str, k + 1, flag)
        || judge(matrix, rows, cols, i, j - 1, str, k + 1, flag)
        || judge(matrix, rows, cols, i, j + 1, str, k + 1, flag))
    {
        return true;
    }

    //走到这，说明这一条路不通，还原，再试其他的路径
    flag[index] = false;
    return false;
}

bool hasPath(char* matrix, int rows, int cols, char* str)
{
    if (matrix == NULL || rows < 1 || cols < 1 || str == NULL) return false;
    bool* flag = new bool[rows * cols];
    memset(flag, false, rows * cols);
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (judge(matrix, rows, cols, i, j, str, 0, flag))
            {
                return true;
            }
        }
    }
    delete[] flag;
    return false;
}

二刷：

1、很经典的题目

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool hasPathCore(vector<vector<char>>& matrix, char* str, int row, int col,int index , vector<vector<bool>> &visit) {

    if (str[index] == '\0') return true;
    if (row<0 || row >= matrix.size() || col<0 || col >= matrix[0].size() || visit[row][col] == true || str[index] != matrix[row][col]) return false;
    visit[row][col] = true;

    if (hasPathCore(matrix, str, row + 1, col, index + 1,visit) ||
        hasPathCore(matrix, str, row - 1, col, index + 1, visit) ||
        hasPathCore(matrix, str, row, col + 1, index + 1, visit) ||
        hasPathCore(matrix, str, row, col - 1, index + 1, visit))
        return true;

    visit[row][col] = false;
    return false;
}

bool hasPath(char* matrix, int rows, int cols, char* str)
{
    vector<vector<char>> matri(rows, vector<char>(cols, ' '));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            matri[i][j] = matrix[i * cols + j];
        }
    }

    vector<vector<bool>> visit(rows, vector<bool>(cols, false));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; ++j) {
            if (hasPathCore(matri, str, i, j, 0,visit)) return true;
        }
    }
    return false;
}