没有各种指针看花眼的 LeetCode 310:. Minimum Height Trees


这题我做完后看了下博客,C++代码指针指的我醉醉的(不是指针小白),所以写了个时间复杂度稍高的不带指针写法==!
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        if (n == 0){
            return ans;
        }
        if (edges.size() == 0){
            vector<int> t;
            for (int i = 0; i < n; ++i){
                t.push_back(i);
            }
            return t;
        }
        
        memset(inDegree, 0, sizeof(inDegree));
        
        for (int i = 0; i < edges.size(); ++i){
            adj[edges[i].first].push_back(edges[i].second);
            adj[edges[i].second].push_back(edges[i].first);
            inDegree[edges[i].first]++;
            inDegree[edges[i].second]++;
        }
        
        int nCount = n;
        int flag[100000];
        memset(flag, 0, sizeof(flag));
        while (nCount > 2){
            vector<int> curDel;
            for (int i = 0; i < n; ++i){
                if(inDegree[i] == 1){
                    curDel.push_back(i);
                    flag[i] = 1;
                    nCount--;
                }
            }  
            for (int i = 0; i < curDel.size(); ++i){
                int neighbor = *adj[curDel[i]].begin();
                adj[curDel[i]].erase(adj[curDel[i]].begin());
                
                list<int>::iterator it;
                for (it = adj[neighbor].begin(); it != adj[neighbor].end(); ++it){
                    if (*it == curDel[i]){
                        break;
                    }
                }
                adj[neighbor].erase(it);
                
                inDegree[curDel[i]]--;
                inDegree[neighbor]--;
            }
            curDel.clear();
        }

        
        for (int i = 0; i < n; ++i){
            if(flag[i] == 0){
                ans.push_back(i);
            }
        }
        return ans;
    }
    
private:
    queue<int> que;
    list<int> adj[100000];
    int inDegree[100000];
    vector<int> ans;
};
已邀请:

July - 抠细节抠体验,不妥协不将就。

赞同来自:


运行时间多长

要回复问题请先登录注册