当前位置：首页 > news >正文

盐城微信公众平台网站制作湖南网站建设seo

news 2025/8/18 16:56:02

盐城微信公众平台网站制作,湖南网站建设seo,网站建设完整版,宁夏银川网站建设本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。目录 01 矩阵置零方法一：标记数组方法二：两个标记变量 02 螺旋矩阵…

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。

01 矩阵置零

方法一：标记数组

方法二：两个标记变量

02 螺旋矩阵

方法一：模拟

方法二：按层模拟

03 旋转图像

方法一：辅助数组

方法二：原地旋转

方法三：用翻转代替旋转

04 搜索二维矩阵 Ⅱ

方法一：直接查找

方法二：二分法

方法三：Z字形查找

01 矩阵置零

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {}
};

方法一：标记数组

时间复杂度 O(mn)，空间复杂度 O(m + n)

建立两个数组 row(m) 和 col(n)，存储 matrix 中行和列的含零情况
遍历数组，判断行或列含零，执行 matrix[i][j] = 0

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<int> row(m), col(n);for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){if(!matrix[i][j]){row[i] = true;col[j] = true;}}}for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){if(row[i] || col[j]){matrix[i][j] = 0;}}}}
};

① vector<int> row(m), col(n);这俩数组没有初始化啥的吗，它们声明时的默认元素值是多少？

使用 vector<int> 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(vector<vector<int>>& matrix) {int m = matrix.size(); //一共m行int n = matrix[0].size(); //一共n列int flag_col0 = false, flag_row0 = false;for(int i=0; i<m; ++i){if(!matrix[i][0]) flag_col0 = true;}for(int j=0; j<n; ++j){if(!matrix[0][j]) flag_row0 = true;}//处理大部分元素for(int i=1; i<m; ++i){for(int j=1; j<n; ++j){if(!matrix[i][j]){matrix[i][0] = 0;matrix[0][j] = 0;}}}for(int i=1; i<m; ++i){for(int j=1; j<n; ++j){if(!matrix[i][0] || !matrix[0][j]) {matrix[i][j] = 0;}}}//处理第零行、第零列元素if(flag_col0){for(int i=0; i<m; ++i){matrix[i][0] = 0;}}if(flag_row0){for(int j=0; j<n; ++j){matrix[0][j] = 0;}}}
};

02 螺旋矩阵

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {}
};

方法一：模拟

时间复杂度 O(mn)，空间复杂度 O(mn)

建立二维数组 visited(rows, vector<bool>(columns)，存储矩阵元素的访问情况
遍历矩阵，判断 nextRow 和 nextColumn 是否越过边界

class Solution {
public:static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //向右、下、左、上vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.size() == 0 || matrix[0].size() == 0) return {};int rows = matrix.size(), columns = matrix[0].size(), total = rows * columns;vector<vector<bool>> visited(rows, vector<bool>(columns)); //标记vector<int> order(total); //答案int row = 0, column = 0, dirIndex = 0;for(int i=0; i<total; 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}：代表向上移动 —— 行减一，列不变

④ vector<bool>(columns) 创建一个布尔向量，大小为 columns，其中每个元素默认初始化为 false。

⑤ vector<vector<bool>>(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:vector<int> spiralOrder(vector<vector<int>>& matrix) {if(matrix.size() == 0 || matrix[0].size() == 0) return {};vector<int> order;int rows = matrix.size(), columns = matrix[0].size();int left = 0, right = columns-1, top = 0, bottom = rows-1;//主打一个遍历while(left<=right && top<=bottom){for(int column=left; column<=right; ++column) {order.push_back(matrix[top][column]);}for(int row=top+1; row<=bottom; ++row) {order.push_back(matrix[row][right]);}if(left<right && top<bottom){for(int column=right-1; column>=left+1; --column) {order.push_back(matrix[bottom][column]);}for(int row=bottom; row>=top+1; --row) {order.push_back(matrix[row][left]);}}top++;left++;right--;bottom--;}return order;}
};

① 为什么还要第二次判断 if(left<right && top<bottom) 呢？

在只有一行或者一列剩下时，第二次顺时针迭代会导致重复元素被添加到结果中。例如，当只剩下一行时，上面的第二次和第三次迭代（从右向左）会和已经处理的行产生重复。比如：

单行（例如，[[1, 2, 3]]）
单列（例如，[[1], [2], [3]]）

03 旋转图像

class Solution {
public:void rotate(vector<vector<int>>& matrix) {}
};

方法一：辅助数组

时间复杂度 O(n^2)，空间复杂度 O(n^2)

class Solution {
public:void rotate(vector<vector<int>>& matrix) {auto matrix_new = matrix;int n = matrix.size();for(int i=0; i<n; ++i){for(int j=0, j<n; ++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(vector<vector<int>>& matrix) {int n = matrix.size();for(int x=0; x<n/2; ++x){for(int y=0; y<(n+1)/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(vector<vector<int>>& matrix) {int n = matrix.size();for(int x=0; x<n/2; ++x){for(int y=0; y<n; ++y){swap(matrix[x][y], matrix[n-1-x][y]);}}for(int x=0; x<n; ++x){for(int y=0; y<x; ++y){swap(matrix[x][y], matrix[y][x]);}}}
};

04 搜索二维矩阵 Ⅱ

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {}
};

方法一：直接查找

时间复杂度 O(mn)，空间复杂度 O(1)

class Solution {
public:bool searchMatrix(vector<vector<int>>& 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(vector<vector<int>>& 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(vector<vector<int>>& 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;}
};