Re: [閒聊] 每日leetcode
73. Set Matrix Zeroes
https://leetcode.com/problems/set-matrix-zeroes/
題意：
類似炸彈超人，
一個 m × n 矩陣，有 0 就十字方向成員都炸成 0 炸整條十字，
額外要求：不准另外宣告矩陣，要使用 in-place 空間複雜度 O(1) 的方法。
思路：
用 row[0], col[0] 來儲存資訊，但這樣會汙染第零行列的資訊，
所以先用兩個變數判斷是否清除 row[0], col[0] 的成員，
並在非零行列的成員處理完之後才進行第零行列的清除。
Code:
impl Solution {
pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
let rows = matrix.len();
let cols = matrix[0].len();
let mut first_row_zero = false;
let mut first_col_zero = false;
for i in 0..rows {
if matrix[i][0] == 0 {
first_col_zero = true;
}
}
for j in 0..cols {
if matrix[0][j] == 0 {
first_row_zero = true;
}
}
for i in 1..rows {
for j in 1..cols {
if matrix[i][j] == 0 {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for i in 1..rows {
for j in 1..cols {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0;
}
}
}
if first_col_zero {
for i in 0..rows {
matrix[i][0] = 0;
}
}
if first_row_zero {
for j in 0..cols {
matrix[0][j] = 0;
}
}
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.97 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1747818107.A.DB3.html
討論串 (同標題文章)
完整討論串 (本文為第 1433 之 1548 篇)：