Leetcode 851. Loud and Rich 以及一些面试的想法

水深无声 2023-02-25 12:27 55阅读 0赞

# Leetcode 851. Loud and Rich 以及一些面试的想法 #

Leetcode 851. Loud and Rich 这道题本身没有什么很特殊的地方，但是它引发了我对面试写算法题的一些想法和思考。

题意：  
给你一个拓扑序列richer，给你一个安静值quiet。  
对于每一个节点，找到拓扑序列严格在这个节点之后的最小的quiet值的节点。（无法排列拓扑关系的，则不是严格在节点之后的）。

## 思路 ##

看到题目第一眼，首先想到排一个拓扑序列，再对于每个节点，取拓扑序列后一段的最小值（和最小值代表的节点）。时间复杂度大概是 O ( N l o g N ) O(NlogN) O(NlogN)。但是稍微想一下就觉得好像有点难处理拓扑序的严格之后，因为如果本身这个拓扑图就是一颗树一样的形状，每一个末梢都会被单独处理。

然后就开始想怎么解决这个最坏的拓扑图，树结构。

一想到树，就很简单了，如果题目把拓扑图变成树机构，这题就变成了，找到这棵子树quiet值最小的节点编号。

拓扑图是有向图，这题就变成了，找到这个节点之后的子图的quiet最小的节点编号。

然后就可以逆向建图，倒着推断，有一种记忆化搜索的感觉。

## 代码 ##

第一种写法是这样的，维护了两个值，子图中最小的quiet值，一个是子图中最小的quiet值的节点编号。

class Solution {
    public:
        vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
            const int n = quiet.size();
            vector<vector<int>> g(n);
            vector<int> ans(n, -1);
            
            for(const auto& e : richer) {
                g[e[1]].push_back(e[0]);
            }
            
            for(int i = 0; i < n; i++) {
                dfs(i, g, quiet, ans);
            }
            return ans;
        }
        
        pair<int, int> dfs(int node, const vector<vector<int>>& g, const vector<int>& quiet, vector<int>& ans) {
            if (ans[node] > 0)
                return make_pair(quiet[ans[node]], ans[node]);
            ans[node] = node;
            int minNode = quiet[node];
            for(auto& next : g[node]) {
                auto [minNext, ansNext] = dfs(next, g, quiet, ans);
                if (minNode > minNext) {
                    minNode = minNext;
                    ans[node] = ans[next];
                }
            }
            return make_pair(minNode, quiet[ans[node]]);
        }
    };

后来琢磨了一下代码，发现可以不用维护最小值，因为最小值就是最小值节点编号的quiet值。

class Solution {
    public:
        vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
            const int n = quiet.size();
            vector<vector<int>> g(n);
            vector<int> ans(n, -1);
            
            for(const auto& e : richer) {
                g[e[1]].push_back(e[0]);
            }
            
            for(int i = 0; i < n; i++) {
                dfs(i, g, quiet, ans);
            }
            return ans;
        }
        
        int dfs(int node, const vector<vector<int>>& g, const vector<int>& quiet, vector<int>& ans) {
            if (ans[node] > 0)
                return quiet[ans[node]];
            ans[node] = node;
            for(auto& next : g[node]) {
                if (quiet[ans[node]] > dfs(next, g, quiet, ans)) {
                    ans[node] = ans[next];
                }
            }
            return quiet[ans[node]];
        }
    };

## 思考 ##

1.  对于任何题目，都应该多考虑考虑极端情况。大部分题目的极端情况，可能是corner case，需要多加关注；也可能就是一种解题的方向。比如，有向图的极限情况，可能是一棵树。
2.  在写代码的时候，多牺牲一些空间复杂度，让代码的可读性更高，在面试过程中是非常有必要的。
    
    1.  面试的时候，不应该太考虑在工程代码中的情况，我觉得可读性应该是最重要的一件事。
    2.  然后面试官能够清晰可见地读懂你的代码，可以在讲解代码的时候，提一嘴可以进行一些空间上的优化，但是会牺牲代码可读性，可能会让面试官觉得你有思考，会trade off。