概述
leetcode
[hot] 48. 旋转图像
题目
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
题解
先水平翻转,然后再对角线翻转,示例代码如下所示:
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int length = matrix.size();
for (int i = 0; i < length / 2; ++i) {
for (int j = 0; j < length; ++j) {
swap(matrix[i][j], matrix[length - 1 - i][j]);
}
}
for (int i = 0; i < length; ++i) {
for (int j = 0; j < i; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
};
复杂度
时间复杂度:
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度:
O
(
1
)
O(1)
O(1)
73. 矩阵置零
题目
给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
进阶:
一个直观的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗?
题解1
空间复杂度 O ( m + n ) O(m+n) O(m+n)的解法,示例代码如下所示:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<int> row(m, 1);
vector<int> col(n, 1);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (!matrix[i][j]) {
row[i] = col[j] = 0;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (!row[i] || !col[j]) {
matrix[i][j] = 0;
}
}
}
}
};
题解2
常量空间复杂度的解法,示例代码如下所示:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool flag = false;
for (int i = 0; i < m; ++i) {
// 只改变标志位,不改变矩阵的第一列元素,保证第一列不影响矩阵其他位置的置零
if (!matrix[i][0]) {
flag = true;
}
for (int j = 1; j < n; ++j) {
// 如果matrix[i][j] == 0,则其所在和行首和列首的元素都置为0
if (!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
// 从下到上遍历,第0行最后被遍历,保证第一行不影响矩阵其他位置的置零
for (int i = m - 1; i >= 0; --i) {
for (int j = 1; j < n; ++j) {
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
if (flag) {
matrix[i][0] = 0;
}
}
}
};
[hot] 79. 单词搜索
题目
给定一个二维网格和一个单词,找出该单词是否存在于网格中。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
题解
回溯法解决问题。示例代码如下所示:
class Solution {
public:
bool valid(int row, int col, int k) {
return row >= 0 && row < rows && col >= 0 && col < cols && k >= 0 && k < _word.size();
}
bool dfs(int row, int col, int k) {
if (!valid(row, col, k)) {
return false;
}
if (_word[k] != _board[row][col]) {
return false;
}
// 一定要把return true放到最后面判断,如果不这样有时会误判
if (k == _word.size() - 1) {
return true;
}
bool res = false;
visisted[row][col] = true;
for (int i = 0; i < 4; ++i) {
int n_row = dirs[i][0] + row;
int n_col = dirs[i][1] + col;
if (!valid(n_row, n_col, k + 1) || visisted[n_row][n_col]) {
continue;
}
if (dfs(n_row, n_col, k + 1)) {
res = true;
break;
}
}
visisted[row][col] = false;
return res;
}
bool exist(vector<vector<char>>& board, string word) {
rows = board.size();
cols = board[0].size();
_word = word;
visisted = vector<vector<bool>>(rows, vector<bool>(cols));
_board = board;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (dfs(row, col, 0)) {
return true;
}
}
}
return false;
}
private:
int rows;
int cols;
vector<vector<char>> _board;
vector<vector<bool>> visisted;
string _word;
vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
};
复杂度
时间复杂度:一个非常宽松的上界为
O
(
m
n
⋅
3
L
)
O(mn cdot 3^L)
O(mn⋅3L),其中 m, n 为网格的长度与宽度,L 为字符串word 的长度。在每次调用函数 check 时,除了第一次可以进入 4 个分支以外,其余时间我们最多会进入 3 个分支(因为每个位置只能使用一次,所以走过来的分支没法走回去)。
空间复杂度:
O
(
m
n
)
O(mn)
O(mn)
[hot] 200. 岛屿数量
题目
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1
示例 2:
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3
题解
深度优先遍历,遍历过程中遇0变1,示例代码如下所示:
class Solution {
public:
bool is_in_grid(int row, int col) {
return row < rows && row >= 0 && col < cols && col >= 0;
}
void dfs(int row, int col) {
if (!is_in_grid(row, col)) {
return;
}
_grid[row][col] = '0';
for (int i = 0; i < 4; ++i) {
int new_row = row + dirs[i][0];
int new_col = col + dirs[i][1];
if (is_in_grid(new_row, new_col) && _grid[new_row][new_col] == '1') {
dfs(new_row, new_col);
}
}
}
int numIslands(vector<vector<char>>& grid) {
rows = grid.size();
cols = grid[0].size();
_grid = grid;
int res = 0;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (_grid[row][col] == '1') {
++res;
dfs(row, col);
}
}
}
return res;
}
private:
vector<vector<int>> dirs = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
vector<vector<char>> _grid;
int rows;
int cols;
};
复杂度
时间复杂度:
O
(
m
n
)
O(mn)
O(mn),m代表矩阵的宽度,n代表矩阵的长度
空间复杂度:
O
(
m
n
)
O(mn)
O(mn)
329. 矩阵中的最长递增路径
题目
给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。
输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出:4
解释:最长递增路径为 [1, 2, 6, 9]。
题解
深度优先遍历解决问题。在遍历过程中记录中间结果以避免重复计算。示例代码如下所示:
class Solution {
public:
bool is_in_matrix(int row, int col) {
return row < rows && row >= 0 && col < cols && col >= 0;
}
void resize_mem(int rows, int cols) {
mem.resize(rows);
for (int i = 0; i < rows; ++i) {
mem[i].resize(cols);
}
}
int max_path(int row, int col) {
if (!is_in_matrix(row, col)) {
return 0;
}
if (mem[row][col] > 0) {
return mem[row][col];
}
mem[row][col] = 1;
for (int i = 0; i < 4; ++i) {
int new_row = row + dirs[i][0];
int new_col = col + dirs[i][1];
if (is_in_matrix(new_row, new_col) && _matrix[row][col] < _matrix[new_row][new_col]) {
mem[row][col] = max(mem[row][col], max_path(new_row, new_col) + 1);
}
}
return mem[row][col];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
rows = matrix.size();
cols = matrix[0].size();
resize_mem(rows, cols);
_matrix = matrix;
int res = 0;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
res = max(res, max_path(row, col));
}
}
return res;
}
private:
int rows;
int cols;
vector<vector<int>> mem;
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<int>> _matrix;
};
复杂度
时间复杂度:
O
(
m
n
)
O(mn)
O(mn),m代表矩阵的宽度,n代表矩阵的长度
空间复杂度:
O
(
m
n
)
O(mn)
O(mn),递归的缓存不会超过m*n,memo申请的内存为mn,因而空间复杂度为O(mn)
695. 岛屿的最大面积
题目
给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
题解
思路类似【200. 岛屿数量],只不过本题求解目标不同,示例代码如下所示:
class Solution {
public:
void dfs(int row, int col) {
if (row < 0 || row >= rows || col < 0 || col >= cols || _grid[row][col] == 0) {
return;
}
++res;
_grid[row][col] = 0;
for (int i = 0; i < 4; ++i) {
int new_row = row + dirs[i][0];
int new_col = col + dirs[i][1];
dfs(new_row, new_col);
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
rows = grid.size();
cols = grid[0].size();
_grid = grid;
int max_res = 0;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (_grid[row][col] == 0) {
continue;
}
res = 0;
dfs(row, col);
max_res = max(max_res, res);
}
}
return max_res;
}
private:
int rows;
int cols;
vector<vector<int>> _grid;
int res;
vector<vector<int>> dirs = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
};
复杂度
时间复杂度:
O
(
m
n
)
O(mn)
O(mn)
空间复杂度:
O
(
m
n
)
O(mn)
O(mn)
剑指offer
4. 二维数组中的查找
题目
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。
给定 target = 20,返回 false。
题解
由于数组从左到右、从上到下都是递增的,因而可以考虑从右上角开始遍历,如果发现右上角元素小于target,则证明所在行元素都小于target,可以从下面一行开始继续寻找目标;如果右上角元素大于target,则证明所在列元素都大于target,可以从左边一列开始继续寻找目标,示例代码如下所示:
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) {
return false;
}
int rows = matrix.size();
int cols = matrix[0].size();
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0) {
if (matrix[row][col] > target) {
--col;
} else if (matrix[row][col] < target) {
// ++row的原因在于当前位置所在行右边的元素已经都比target大了
// 但不能保证row+1行col左侧的数据比target大,因而这里需要++row
++row;
} else {
return true;
}
}
return false;
}
};
复杂度
时间复杂度:
O
(
m
n
)
O(mn)
O(mn)
空间复杂度:
O
(
1
)
O(1)
O(1)
13. 机器人的运动范围
题目
地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?
示例 1:
输入:m = 2, n = 3, k = 1
输出:3
示例 2:
输入:m = 3, n = 1, k = 0
输出:1
提示:
1 <= n,m <= 100
0 <= k <= 20
题解
本题为【329. 矩阵中的最长递增路径】的简化版,回溯法解决问题,值得注意的是这里定义二维数组visited,记录某个节点是否已经被走过,这样能够加速计算,示例代码如下:
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> vis(m, vector<bool>(n, false));
_m = m;
_n = n;
return dfs(vis, 0, 0, k);
}
int count(int row, int col) {
int res = 0;
while (row) {
res += row % 10;
row /= 10;
}
while (col) {
res += col % 10;
col /= 10;
}
return res;
}
int dfs(vector<vector<bool>>& vis, int row, int col, int k) {
if (row >= _m || col >= _n || count(row, col) > k || vis[row][col]) {
return 0;
}
vis[row][col] = true;
return 1 + dfs(vis, row + 1, col, k) + dfs(vis, row, col + 1, k);
}
private:
int _m;
int _n;
};
复杂度
时间复杂度:
O
(
m
n
)
O(mn)
O(mn)
空间复杂度:
O
(
m
n
)
O(mn)
O(mn)
最后
以上就是笨笨世界为你收集整理的算法(十三)数组之二维数组leetcode剑指offer的全部内容,希望文章能够帮你解决算法(十三)数组之二维数组leetcode剑指offer所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复