每日算法刷题 Day3 5.11:leetcode数组2道题，用时1h(有点慢)

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] = 0
        for 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 + 1
                y = i if i < m else m - 1
                while x < n and y >= 0:
                    res.append(mat[x][y])
                    x += 1
                    y -= 1
            else:
                y = 0 if i < n else i - n + 1
                x = i if i < n else n - 1
                while y < m and x >= 0:
                    res.append(mat[x][y])
                    y += 1
                    x -= 1
        return res
        
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+1
                y=i if i<m else m-1
                while x<n and y>=0:
                    res.append(mat[x][y])
                    x+=1
                    y-=1
            else:
                y=0 if i<n else i-n+1
                x=i if i<n else n-1
                while y<m and x>=0:
                    res.append(mat[x][y])
                    y+=1
                    x-=1
        return res

1.没有三目运算符，要写成x=0 if i<m else i-m+1
2.没有++运算符，要写成x+=1