站长工具网站备案,深圳小程序开发与制作,沧州网络推广管理公司,wordpress媒体缩略图本系列为笔者的 Leetcode 刷题记录#xff0c;顺序为 Hot 100 题官方顺序#xff0c;根据标签命名#xff0c;记录笔者总结的做题思路#xff0c;附部分代码解释和疑问解答。
目录
01 矩阵置零
方法一#xff1a;标记数组
方法二#xff1a;两个标记变量
02 螺旋矩阵…本系列为笔者的 Leetcode 刷题记录顺序为 Hot 100 题官方顺序根据标签命名记录笔者总结的做题思路附部分代码解释和疑问解答。
目录
01 矩阵置零
方法一标记数组
方法二两个标记变量
02 螺旋矩阵
方法一模拟
方法二按层模拟
03 旋转图像
方法一辅助数组
方法二原地旋转
方法三用翻转代替旋转
04 搜索二维矩阵 Ⅱ
方法一直接查找
方法二二分法
方法三Z字形查找 01 矩阵置零 class Solution {
public:void setZeroes(vectorvectorint matrix) {}
};
方法一标记数组
时间复杂度 O(mn)空间复杂度 O(m n) 建立两个数组 row(m) 和 col(n)存储 matrix 中行和列的含零情况 遍历数组判断行或列含零执行 matrix[i][j] 0
class Solution {
public:void setZeroes(vectorvectorint matrix) {int m matrix.size();int n matrix[0].size();vectorint row(m), col(n);for(int i0; im; i){for(int j0; jn; j){if(!matrix[i][j]){row[i] true;col[j] true;}}}for(int i0; im; i){for(int j0; jn; j){if(row[i] || col[j]){matrix[i][j] 0;}}}}
};
① vectorint row(m), col(n);这俩数组没有初始化啥的吗它们声明时的默认元素值是多少
使用 vectorint row(m) 这样的语句声明一个 vector并指定大小时 vector会自动初始化为指定大小的元素且每个元素默认初始化为零。
方法二两个标记变量
时间复杂度 O(mn)空间复杂度 O(1) 建立两个标记 flag_col0 和 flag_row0存储 matrix 中除第零行和第零列的含零情况 遍历数组判断 !matrix[i][0] || !matrix[0][j]执行 matrix[i][j] 0 第零行和第零列单独更新
class Solution {
public:void setZeroes(vectorvectorint matrix) {int m matrix.size(); //一共m行int n matrix[0].size(); //一共n列int flag_col0 false, flag_row0 false;for(int i0; im; i){if(!matrix[i][0]) flag_col0 true;}for(int j0; jn; j){if(!matrix[0][j]) flag_row0 true;}//处理大部分元素for(int i1; im; i){for(int j1; jn; j){if(!matrix[i][j]){matrix[i][0] 0;matrix[0][j] 0;}}}for(int i1; im; i){for(int j1; jn; j){if(!matrix[i][0] || !matrix[0][j]) {matrix[i][j] 0;}}}//处理第零行、第零列元素if(flag_col0){for(int i0; im; i){matrix[i][0] 0;}}if(flag_row0){for(int j0; jn; j){matrix[0][j] 0;}}}
};
02 螺旋矩阵 class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {}
};
方法一模拟
时间复杂度 O(mn)空间复杂度 O(mn) 建立二维数组 visited(rows, vectorbool(columns)存储矩阵元素的访问情况 遍历矩阵判断 nextRow 和 nextColumn 是否越过边界
class Solution {
public:static constexpr int dirs[4][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //向右、下、左、上vectorint spiralOrder(vectorvectorint matrix) {if (matrix.size() 0 || matrix[0].size() 0) return {};int rows matrix.size(), columns matrix[0].size(), total rows * columns;vectorvectorbool visited(rows, vectorbool(columns)); //标记vectorint order(total); //答案int row 0, column 0, dirIndex 0;for(int i0; itotal; i){order[i] matrix[row][column]; //更新答案visited[row][column] true; //更新标记int nextRow row dirs[dirIndex][0];int nextColumn column dirs[dirIndex][1];if(nextRow rows || nextRow 0 || nextColumn columns || nextColumn 0 || visited[nextRow][nextColumn]){dirIndex (dirIndex 1) % 4;}row dirs[dirIndex][0];column dirs[dirIndex][1];}return order;}
};
① static 意味着变量在程序的生命周期内只会被分配一次并且在所有对该数组的函数调用中共享同一存储空间。
② constexpr 用于指定变量值在编译时就确定下来它提示编译器尽量进行优化。
③ {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}每一对元素代表在二维平面上一个方向的坐标变换 {0, 1}代表向右移动 —— 行不变列加一 {1, 0}代表向下移动 —— 行加一列不变 {0, -1}代表向左移动 —— 行不变列减一 {-1, 0}代表向上移动 —— 行减一列不变
④ vectorbool(columns) 创建一个布尔向量大小为 columns其中每个元素默认初始化为 false。
⑤ vectorvectorbool(rows, ...) 表示创建一个这样的布尔向量的向量其长度为 rows即每一行都是一个布尔向量且每列都是初始化为 false。
⑥ spiral 螺旋形的 constexpr 常量表达式
⑦ 在什么样的情况下 if (nextRow 0 || nextRow rows || nextColumn 0 || nextColumn columns || visited[nextRow][nextColumn]) 中的 nextRow 0 成立
由于初始位置是 (0, 0) 且遍历顺序是顺时针螺旋因此 nextRow 0 通常在当前方向反转尝试向上之前使用过的路径上被访问时发生。
⑧ 将代码中涉及 nextRow 和 nextColumn 部分的片段改为如下片段如何
if((column (columns - 1)) || (row (rows - 1)) || (column 0) || matrix[row dirs[dirIndex][0]][column dirs[dirIndex][1]]){dirIndex (dirIndex 1) % 4;
} matrix[row dirs[dirIndex][0]][column dirs[dirIndex][1]]这种方式不仅增加了代码复杂度并且可能由于超出 matrix 的边界而导致访问无效内存出现内存错误。
if (column columns || row rows || column -1 || row -1 ||
row dirs[dirIndex][0] 0 || row dirs[dirIndex][0] rows ||
column dirs[dirIndex][1] 0 || column dirs[dirIndex][1] columns ||
visited[row dirs[dirIndex][0]][column dirs[dirIndex][1]]) {
dirIndex (dirIndex 1) % 4;
}
row dirs[dirIndex][0] 0检查向当前方向移动后新的行索引是否小于0。这会保持我们不越过上边界。
row dirs[dirIndex][0] rows检查向当前方向移动后新的行索引是否大于或等于总行数。这会确保我们不越过下边界。
column dirs[dirIndex][1] 0检查向当前方向移动后新的列索引是否小于0。这会确保我们不越过左边界。
column dirs[dirIndex][1] columns检查向当前方向移动后新的列索引是否大于或等于总列数。这会确保我们不越过右边界。
方法二按层模拟
时间复杂度 O(mn)空间复杂度 O(1) class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {if(matrix.size() 0 || matrix[0].size() 0) return {};vectorint order;int rows matrix.size(), columns matrix[0].size();int left 0, right columns-1, top 0, bottom rows-1;//主打一个遍历while(leftright topbottom){for(int columnleft; columnright; column) {order.push_back(matrix[top][column]);}for(int rowtop1; rowbottom; row) {order.push_back(matrix[row][right]);}if(leftright topbottom){for(int columnright-1; columnleft1; --column) {order.push_back(matrix[bottom][column]);}for(int rowbottom; rowtop1; --row) {order.push_back(matrix[row][left]);}}top;left;right--;bottom--;}return order;}
};
① 为什么还要第二次判断 if(leftright topbottom) 呢
在只有一行或者一列剩下时第二次顺时针迭代会导致重复元素被添加到结果中。例如当只剩下一行时上面的第二次和第三次迭代从右向左会和已经处理的行产生重复。比如 单行例如[[1, 2, 3]] 单列例如[[1], [2], [3]]
03 旋转图像 class Solution {
public:void rotate(vectorvectorint matrix) {}
};
方法一辅助数组
时间复杂度 O(n^2)空间复杂度 O(n^2)
class Solution {
public:void rotate(vectorvectorint matrix) {auto matrix_new matrix;int n matrix.size();for(int i0; in; i){for(int j0, jn; j){matrix_new[j][n-1-i] matrix[i][j];}}return matrix_new;}
};
auto matrix_new matrix;这行代码的作用是复制matrix变量的值到一个新的变量matrix_new中matrix_new的类型与matrix一致。
对于大多数与标准库相关的容器如 std::vector这会创建 matrix 的一个浅拷贝整体上是深拷贝其内容而不是仅仅复制指针如果它是一个复杂数据结构。
方法二原地旋转
时间复杂度 O(n^2)空间复杂度 O(1) class Solution {
public:void rotate(vectorvectorint matrix) {int n matrix.size();for(int x0; xn/2; x){for(int y0; y(n1)/2; y){int flag matrix[x][y];matrix[x][y] matrix[n-1-y][x];matrix[n-1-y][x] matrix[n-1-x][n-1-y];matrix[n-1-x][n-1-y] matrix[y][n-1-x];matrix[y][n-1-x] flag;}}}
};
方法三用翻转代替旋转
时间复杂度 O(n^2)空间复杂度 O(1) class Solution {
public:void rotate(vectorvectorint matrix) {int n matrix.size();for(int x0; xn/2; x){for(int y0; yn; y){swap(matrix[x][y], matrix[n-1-x][y]);}}for(int x0; xn; x){for(int y0; yx; y){swap(matrix[x][y], matrix[y][x]);}}}
};
04 搜索二维矩阵 Ⅱ class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {}
};
方法一直接查找
时间复杂度 O(mn)空间复杂度 O(1)
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {for(const auto row: matrix){for(int element: row){if(element target) return true;}}return false;}
};
方法二二分法
时间复杂度 O(mlogn)空间复杂度 O(1)
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {for(const auto row: matrix){auto it lower_bound(row.begin(), row.end(), target);if(it ! row.end() *it target) return true;}return false;}
};
lower_bound 是一个标准库函数位于 algorithm 头文件中用于在一个已排序的范围内查找目标值的位置。lower_bound 返回一个迭代器指向范围内第一个不小于目标值的元素的位置如果所有的元素都小于目标值它将返回指向末尾的迭代器。
注意使用 lower_bound 的前提是 row 必须是排序好的否则结果是不确定的。
方法三Z字形查找
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int m matrix.size(), n matrix[0].size();int x 0, y n-1;while(x m y 0){if(matrix[x][y] target) return true;else if(matrix[x][y] target) y--;else x;}return false;}
}; 文章部分代码来源于力扣LeetCode
