LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 遍历数组元素，当出现 0 时，标记其所在行和列，最后对标记过的行和列置零即可

0$$0
$0$$
$$$$

 0  0     0  0
 0$$0     0$$0
0$0$$ => 00000
 $$$$     0$$0

• 这种做法需要添加一行和一列来存储状态。但题目要求使用原地算法，只能让数组本身存储状态，因此用第一行和第一列存储状态。但这样会覆盖掉其原有状态

$$$$$    $x$$x    $0$$0    00000
$0$$0    $0$$0    $0$$0    00$$0
$$0$$ => x$0$$ => 00000 => 00000  如果 x 原本是 0，则 x 所在的行列也要置零
$$$$$    $$$$$    $0$$0    00$$0

• 为了不丢失原有信息，先检查第一行和第一列是否有 0 即可，如果有则最后把该置零的行列置零

class Solution {
 public:
  void setZeroes(vector<vector<int>>& matrix) {
    if (empty(matrix) || empty(matrix[0])) {
      return;
    }

    bool first_row_has_zero =
        any_of(begin(matrix[0]), end(matrix[0]), [](int x) { return !x; });

    bool first_col_has_zero =
        any_of(begin(matrix), end(matrix),
               [&](const vector<int>& x) { return !x[0]; });

    int m = size(matrix);
    int n = size(matrix[0]);

    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        if (!matrix[i][j]) {  // 遍历元素，发现 0 则标记其所在行和列
          matrix[0][j] = 0;  // 该元素所在行的第一元素置 0
          matrix[i][0] = 0;  // 该元素所在列的第一个元素置 0
        }
      }
    }
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        if (!matrix[i][0] || !matrix[0][j]) {  // 元素所在行列被标记则置零
          matrix[i][j] = 0;
        }
      }
    }
    if (first_row_has_zero) {  // 如果第一行原来有 0，则将第一行全部置零
      for_each(begin(matrix[0]), end(matrix[0]), [](int& x) { x = 0; });
    }
    if (first_col_has_zero) {  // 如果第一列原来有 0，则将第一列全部置零
      for_each(begin(matrix), end(matrix), [&](vector<int>& x) { x[0] = 0; });
    }
  }
};