5.LC 零矩陣(中等)

面試題 01.08. 零矩陣 - 力扣（LeetCode）

思想:

法一:
利用兩個集合分別儲存要清0的行和列索引
另外兩種原地優化空間的做法暫時不是目前刷題目標，故不考慮

代碼

c++:

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {set<int> hang;set<int> lie;int n = matrix.size(), m = matrix[0].size();for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (matrix[i][j] == 0) {hang.insert(i);lie.insert(j);}}}for (const auto& x : hang) {for (int j = 0; j < m; ++j) {matrix[x][j] = 0;}}for (const auto& x : lie) {for (int i = 0; i < n; ++i) {matrix[i][x] = 0;}}}
};

python:

class Solution:def setZeroes(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""hang = set()lie = set()n, m = len(matrix), len(matrix[0])for i in range(n):for j in range(m):if matrix[i][j] == 0:hang.add(i)lie.add(j)for x in hang:for j in range(m):matrix[x][j] = 0for x in lie:for i in range(n):matrix[i][x] = 0

相似題

73. 矩陣置零 - 力扣（LeetCode）

6.LC 對角線遍歷(中等，學習)

498. 對角線遍歷 - 力扣（LeetCode）

思想:

1.n行m列矩陣,因為是按照對角線遍歷，但是分析可得有兩種對角線遍歷方式，從左下到右上和從右上到左下，是由第i條對角線的奇偶決定的，所以按照對角線遍歷，$i\in [0,n+m?1)$
2.對于偶數對角線，是從左下到右上的遍歷順序，但又會出現遍歷初始位置不同的情況，故再分類

• i<n,說明在左邊界，初始位置(i,0)
• i>=n,說明在下邊界，初始位置(n-1,i-(n-1))即(n-1,i-n+1)
  3.奇數對角線，是從右上到左下的遍歷順序,對偶式即可
• i<m,說明在上邊界，初始位置(0,i)
• i>=m,說明在右邊界，初始位置(i-m+1,m-1)

代碼

c++:

class Solution {
public:vector<int> findDiagonalOrder(vector<vector<int>>& mat) {vector<int> res;int n = mat.size(), m = mat[0].size();for (int i = 0; i < n + m - 1; ++i) {// 右上到左下if (i % 2) {int x = i < m ? 0 : i - m + 1;int y = i < m ? i : m - 1;while (x < n && y >= 0) {res.emplace_back(mat[x][y]);x++;y--;}}// 左下到右上else {int x = i < n ? i : n - 1;int y = i < n ? 0 : i - n + 1;while (y < m && x >= 0) {res.emplace_back(mat[x][y]);x--;y++;}}}return res;}
};

python:

class Solution:def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:n, m = len(mat), len(mat[0])res = []for i in range(n + m - 1):if i % 2 == 1:x = 0 if i < m else i - m + 1y = i if i < m else m - 1while x < n and y >= 0:res.append(mat[x][y])x += 1y -= 1else:y = 0 if i < n else i - n + 1x = i if i < n else n - 1while y < m and x >= 0:res.append(mat[x][y])y += 1x -= 1return resclass Solution:def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:n,m=len(mat),len(mat[0])res=[]for i in range(n+m-1):if i%2==1:x=0 if i<m else i-m+1y=i if i<m else m-1while x<n and y>=0:res.append(mat[x][y])x+=1y-=1else:y=0 if i<n else i-n+1x=i if i<n else n-1while y<m and x>=0:res.append(mat[x][y])y+=1x-=1return res

1.沒有三目運算符，要寫成x=0 if i<m else i-m+1
2.沒有++運算符，要寫成x+=1