矩阵相关题型
题意理解:
将矩阵中0所在位置,行|列置换为全0
其中可以通过记录0元素所在的行、列号,来标记要置换的行|列
将对应位置置换为0
解题思路:
第一个思路:
可以通过两个set: row col 分别用来记录要置换的行|列号
同时set实现去重,不用重复操作
遍历row和col,将要置换的行|列,置换为全0
第二个思路:不适用额外的空间存储,使用矩阵的第一行和第一列进行存储。
1.flag_row 和flag_col标记原来的第一行|第一列是否有0,有为true
2.遍历元素(i=1,j=1),当且仅当,当前元素为0是,将对应第一行第一列的位置元素置为0
3.遍历元素(i=1,j=1),当且仅当,对应行|列头为0时,当前元素为0
4.处理第一行|第一列,当且仅当flag_row (flag_col)==true时,将第一行(第一列)置换为全0.
1.解题【额外的空间记录】
- class Solution {
- public void setZeroes(int[][] matrix) {
- Set
row=new HashSet<>(); - Set
col=new HashSet<>(); - for(int i=0;i
- for(int j=0;j
0].length;j++){ - if(matrix[i][j]==0){
- row.add(i);
- col.add(j);
- }
- }
- }
- //填充0
- for(int num:row){
- for(int j=0;j
0].length;j++){ - matrix[num][j]=0;
- }
- }
- for(int num:col){
- for(int i=0;i
- matrix[i][num]=0;
- }
- }
- }
- }
1.解题【矩阵本身记录】
- class Solution {
- public void setZeroes(int[][] matrix) {
- int row=matrix.length;
- int col=matrix[0].length;
- boolean flag_row=false,flag_col=false;
- for(int j=0;j
- if(matrix[0][j]==0){
- flag_row=true;
- break;
- }
- }
- for(int i=0;i
|
- if(matrix[i][0]==0){
- flag_col=true;
- break;
- }
- }
- //记录
- for(int i=1;i
|
- for(int j=1;j
- if(matrix[i][j]==0){
- matrix[i][0]=0;
- matrix[0][j]=0;
- }
- }
- }
- //置为0
- for(int i=1;i
|
- for(int j=1;j
- if(matrix[i][0]==0||matrix[0][j]==0){
- matrix[i][j]=0;
- }
- }
- }
- //第一行
- if(flag_row){
- for(int j=0;j
- matrix[0][j]=0;
- }
- }
- //第一列
- if(flag_col){
- for(int i=0;i
|
- matrix[i][0]=0;
- }
- }
- }
- }
2.复杂度分析
时间复杂度:O(n^2) 双for的时间损耗
空间复杂度:O(n) row和col的空间损耗
思路二的时间复杂度:O(1) 除了i,j外没有额外的空间损耗
Leetcode 54. 螺旋矩阵【中等】
题意理解:
从(0,0)位置顺时针螺旋,遍历数据
解题思路:
模拟转向:
1.模拟螺旋结构进行顺时针转向,其转向总是右下左上,依次循环
2.我们用directions={右、下、左、上}模拟转向,其中(i+1)%4表示选择的转向
3.转向的条件:i,j越界,或,下一个位置已经被访问过。
1.解题【模拟螺旋转向】
- class Solution {
- public List
spiralOrder(int[][] matrix) { - int row=matrix.length;
- int col=matrix[0].length;
- List
result=new ArrayList<>(); - if(matrix==null||matrix.length==0||matrix[0].length==0){
- return result;
- }
- int[][] diresction=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};//右下左上
- boolean[][] visited = new boolean[row][col];
- int i_index=0,j_index=0;
- int direct_index=0;
- for(int i=1;i<=row*col;i++){
- result.add(matrix[i_index][j_index]);
- visited[i_index][j_index]=true;
- int nextRow=i_index+diresction[direct_index][0],nextCol=j_index+diresction[direct_index][1];
- //越界转向
- if(nextRow<0||nextRow>=row||nextCol<0||nextCol>=col||visited[nextRow][nextCol]){
- direct_index=(direct_index+1)%4;
- }
- i_index+=diresction[direct_index][0];
- j_index+=diresction[direct_index][1];
- }
- return result;
- }
- }
1.解题【按层模拟,一次遍历转一周】
- class Solution {
- public List
spiralOrder(int[][] matrix) { - int row=matrix.length;
- int col=matrix[0].length;
- List
result=new ArrayList<>(); - if(matrix==null||matrix.length==0||matrix[0].length==0){
- return result;
- }
- //上下左右四个边界
- int top=0,bottom=row-1,left=0,right=col-1;
- while(left<=right&&top<=bottom){
- //左
- for(int j=left;j<=right;j++){
- result.add(matrix[top][j]);
- }
- //下
- for(int i=top+1;i<=bottom;i++){
- result.add(matrix[i][right]);
- }
- if(left
- //右
- for(int j=right-1;j>left;j--){
- result.add(matrix[bottom][j]);
- }
- //上
- for(int i=bottom;i>top;i--){
- result.add(matrix[i][left]);
- }
- }
- left++;
- right--;
- top++;
- bottom--;
- }
- return result;
- }
- }
2.复杂度分析
思路一:
时间复杂度:O(n) for循环时间损耗
空间复杂度:O(n^2) visited[][]数组的空间损耗
思路二:
时间复杂度:O(n^2) while+for时间损耗
空间复杂度:O(n) 结果集的空间损耗
-
相关阅读:
机器人控制器编程实践指导书旧版-实践一 LED灯(数字量)
mybatis入门
Vue使用axios进行get请求拼接参数的两种方式
IDEA的使用(一) (IntelliJ IDEA 2022.1.3版本)
非线性参数的精英学习灰狼优化算法-附代码
Linux篇:进程
001.Python3.10+Pycharm2022.2环境搭建、pip使用
文件安全外发,墨门云防范共享泄密
论文阅读---REALISE model
3D视觉系统实现自动化上下料操作
-
原文地址:https://blog.csdn.net/lt_BeiMo/article/details/138074690