2022-09-29-小红书-一面-30min

redstar C++开发

交流了十来分钟研究方向，然后说做个题，然后走了
做完后没来，后来来了一次，在和别人说话，然后又走了
最后终于来了，现场环境特别吵，他耳机不行，时断时续，最后直接开麦结束了

面试题是30号的每日一题...https://leetcode.cn/problems/zero-matrix-lcci/

题目就是设置为0的那些位所在的列和行为0
面试官说复杂度有点高，我说只会进入一次if，如果同一行或者同一列已经处理过一次了就不会再遍历一遍了，最后面试官勉强同意了
但感觉说服力还是不足，只是种感觉，到底是不是Omn

最后写题解的时候才发现做错了！
前面位置置为0后影响了后面的位置是否为0的判断
可以把mark过程和遍历过程隔离开来，先只标记两个数组
最后遍历完后再处理 rowMark，把相应的行置为0，
再处理columnMark，把相应的列置为0，
这样就是三个O（mn）了，清晰了，任务量没变，显然复杂度还是一次遍历的。

#include <iostream>
#include <vector>
using namespace std;

// O(mn)
void setMatrixZero(vector<vector<int>>& matrix){
    if(matrix.size()==0) return;
    int n=matrix.size(),m=matrix[0].size();
    vector<bool> rowMark(n,false),columnMark(m,false);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(matrix[i][j]==0){
                if(rowMark[i]==false){
                    for(int k=0;k<m;k++)
                        matrix[i][k]=0;
                    rowMark[i]=true;
                }
                if(columnMark[j]==false){
                    for(int k=0;k<n;k++)
                        matrix[k][j]=0;
                    columnMark[j]=true;
                }
            } // zero position
        } // each column
    } // each row
}

int main() {
    string words = "Hello, World!";
    cout << words << endl;
    int a, b;
    while(cin>> a >> b)
    cout << "Your result is : "<< a + b << endl;
      return 0;
}