带你快速刷完67道剑指offer

如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习校招总结offer选择也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# No65、矩阵中的路径

牛客网原题链接 (opens new window)

# 题目描述

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

# 示例1

输入

"ABCESFCSADEE",3,4,"ABCCED"
1

返回值

true
1

示例2

输入

"ABCESFCSADEE",3,4,"ABCB"
1

返回值

false
1

# 1、DFS

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



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
}

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

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

/*参数说明  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
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

# 二刷:

# 1、很经典的题目

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;
}
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