一面

2021-10-18

想做个介绍吧，

balabala10分钟。。。

咱们先做到题吧

？？？那你先让我介绍干嘛

BFS聚类的题，面试官说可以做到O(n)时间复杂度，我没想明白怎么O(N)。。。

#include "../common.h"


int nums = 0;
vector<vector<int>> global_res;

vector<vector<int>> GroupNodes(const vector<vector<int>>& nodes){
    nums = nodes.size();
    vector<bool> visited(nums, false);

    queue<int> q_index;

    q_index.push(0);
    vector<int> tmp_cluster;
    int used_num = 0;
    while(used_num<nums){
        while(!q_index.empty()){
            auto cur = q_index.front();
            q_index.pop();
            if(visited[cur]){
                continue;
            }
            visited[cur] = true;
            tmp_cluster.push_back(cur);
            used_num++;
            auto neighbors =  nodes[cur];
            for(const auto& ele:neighbors){
                q_index.push(ele);
            }
        }
        global_res.push_back(tmp_cluster);
        tmp_cluster.clear();

        // random
        for(int i = 0; i<nums; i++){
            if(visited[i]){
                continue;
            }
            else{
                q_index.push(i);
                break;
            }
        }

    }
}

int main(){

    return 0;
}

项目

基础

从深度学习，到基本算法

反问

无感，面了1个小时，累了。。