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

前端力扣刷题 | 6:hot100之 矩阵

73. 矩阵置零

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
在这里插入图片描述

法一:
var setZeroes = function(matrix) {let setX = new Set(); // 用于存储需要置零的行索引let setY = new Set(); // 用于存储需要置零的列索引let row = matrix.length;let col = matrix[0].length;for(let i=0;i<row;i++){for(let j=0;j<col;j++){if(matrix[i][j]===0){setX.add(i);setY.add(j);}}}// 将需要置零的行全置为 0for(let i of setX){for(let j=0;j<col;j++){matrix[i][j]=0;}}// 将需要置零的列全置为 0for(let i of setY){for(let j=0;j<row;j++){matrix[j][i]=0;}}
};
  • 时间复杂度:O(m*n)
  • 空间复杂度:O(m+n),额外使用了两个set来存储行和列索引
法二:
解题思路:
  1. 使用矩阵的第一行和第一列作为标记区域:
    • 用第一行标记需要置零的列。
    • 用第一列标记需要置零的行。
  2. 步骤概述:
    • 第一步:先遍历整个矩阵,记录哪些行和列需要置零(但不要急着修改矩阵)。
      • 使用第一行的元素记录某一列是否需要置零。
      • 使用第一列的元素记录某一行是否需要置零。
      • 此外,需要一个变量标记第一行和第一列本身是否需要置零。
    • 第二步:根据第一行和第一列的标记,修改矩阵对应的行和列为零。
    • 第三步:单独处理第一行和第一列(因为它们被用作标记,最后再更新)。
var setZeroes = function(matrix) {let row = matrix.length;let col = matrix[0].length;// 标记第一列和第一行是否需要置零let firstRowZero = false;let firstColZero = false;for (let i = 0; i < row; i++) {    // 检查第一列是否需要置零if (matrix[i][0] === 0) {firstColZero = true;break;}}for (let j = 0; j < col; j++) {    // 检查第一行是否需要置零if (matrix[0][j] === 0) {firstRowZero = true;break;}}for (let i = 1; i < row; i++) {    // 使用第一行和第一列标记需要置零的行和列for (let j = 1; j < col; j++) {if (matrix[i][j] === 0) {matrix[i][0] = 0; // 标记该行需要置零matrix[0][j] = 0; // 标记该列需要置零}}}for (let i = 1; i < row; i++) {    // 遍历矩阵,根据标记置零(跳过第一行和第一列)for (let j = 1; j < col; j++) {if (matrix[i][0] === 0 || matrix[0][j] === 0) {matrix[i][j] = 0;}}}if (firstColZero) {    // 根据标记处理第一列for (let i = 0; i < row; i++) {matrix[i][0] = 0;}}if (firstRowZero) {    // 根据标记处理第一行for (let j = 0; j < col; j++) {matrix[0][j] = 0;}}
};
  • 时间复杂度:O(m*n)
  • 空间复杂度:O(1),

54 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
在这里插入图片描述

思路:
  1. 定义边界:使用四个变量 top、bottom、left、right 分别表示矩阵的上、下、左、右边界。
  2. 遍历顺序:按照顺时针方向,依次遍历上边界、右边界、下边界和左边界。
  3. 调整边界:每遍历完一个边界后,调整相应的边界。
  4. 重复遍历:直到所有元素都被遍历。
代码实现:
var spiralOrder = function(matrix) {let res = [];// 维护四个边界let left = 0;let right = matrix[0].length-1;let top = 0;let bottom = matrix.length-1;// 遍历while(left<=right&&top<=bottom){for(let i=left;i<=right;i++){  // 遍历上边界res.push(matrix[top][i]);}top++;for(let i=top;i<=bottom;i++){  // 遍历右边界res.push(matrix[i][right]);}right--;if(top<=bottom){for(let i=right;i>=left;i--){  // 遍历下边界res.push(matrix[bottom][i]);}bottom--;}if(left<=right){for(let i=bottom;i>=top;i--){  // 遍历左边界res.push(matrix[i][left]);}left++;}}return res;
};

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
在这里插入图片描述

思路:
  1. 转置矩阵:将矩阵的行和列互换(即 matrix[i][j] 和 matrix[j][i] 交换)。
  2. 翻转每一行:将转置后的矩阵的每一行反转。
代码实现:
var rotate = function(matrix) {for(let i=0;i<matrix.length;i++){for(let j=i;j<matrix.length;j++){[matrix[i][j],matrix[j][i]] = [matrix[j][i],matrix[i][j]];}}for(let i=0;i<matrix.length;i++){matrix[i].reverse();}
};

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
    在这里插入图片描述
思路:从右上角或左下角开始搜索
  1. 从右上角开始:

    • 初始化指针在矩阵的右上角(即 row = 0,col = n - 1)。
    • 如果当前元素等于 target,返回 true。
    • 如果当前元素大于 target,说明目标值不可能在当前列,因此向左移动一列(col–)。
    • 如果当前元素小于 target,说明目标值不可能在当前行,因此向下移动一行(row++)。
    • 重复上述步骤,直到找到目标值或指针越界。
  2. 从左下角开始:

    • 初始化指针在矩阵的左下角(即 row = m - 1,col = 0)。
    • 如果当前元素等于 target,返回 true。
    • 如果当前元素大于 target,说明目标值不可能在当前行,因此向上移动一行(row–)。
    • 如果当前元素小于 target,说明目标值不可能在当前列,因此向右移动一列(col++)。
    • 重复上述步骤,直到找到目标值或指针越界。
代码实现(从右上角开始)
var searchMatrix = function(matrix, target) {if (matrix.length === 0 || matrix[0].length === 0) return false;let row = 0;let col = matrix[0].length-1;while(row<matrix.length && col>=0){if(matrix[row][col]===target){return true;}else if(matrix[row][col]>target){col--;}else{row++;}}return false;
};
http://www.lryc.cn/news/530883.html

相关文章:

  • docker gitlab arm64 版本安装部署
  • 路径规划之启发式算法之二十九:鸽群算法(Pigeon-inspired Optimization, PIO)
  • 【AudioClassificationModelZoo-Pytorch】基于Pytorch的声音事件检测分类系统
  • 一文讲解Java中的ArrayList和LinkedList
  • CNN的各种知识点(五):平均精度均值(mean Average Precision, mAP)
  • 【优先算法】专题——前缀和
  • gitea - fatal: Authentication failed
  • 基于Spring Security 6的OAuth2 系列之八 - 授权服务器--Spring Authrization Server的基本原理
  • 蓝桥与力扣刷题(234 回文链表)
  • Google C++ Style / 谷歌C++开源风格
  • Windows图形界面(GUI)-QT-C/C++ - QT Tab Widget
  • 【大数据技术】教程05:本机DataGrip远程连接虚拟机MySQL/Hive
  • C++:结构体和类
  • MATLAB的数据类型和各类数据类型转化示例
  • UE求职Demo开发日志#19 给物品找图标,实现装备增加属性,背包栏UI显示装备
  • C++泛型编程指南09 类模板实现和使用友元
  • 使用MATLAB进行雷达数据采集可视化
  • 【Elasticsearch】allow_no_indices
  • 54【ip+端口+根目录通信】
  • python算法和数据结构刷题[3]:哈希表、滑动窗口、双指针、回溯算法、贪心算法
  • DeepSeek横空出世,AI格局或将改写?
  • 聚簇索引、哈希索引、覆盖索引、索引分类、最左前缀原则、判断索引使用情况、索引失效条件、优化查询性能
  • OpenAI 实战进阶教程 - 第四节: 结合 Web 服务:构建 Flask API 网关
  • python的pre-commit库的使用
  • 架构技能(四):需求分析
  • Linux环境下的Java项目部署技巧:安装 Nginx
  • 前端 Vue 性能提升策略
  • 深入理解linux中的文件(上)
  • Unity特效插件GodFX
  • 从 C 到 C++:理解结构体中字符串的存储与操作