LeetCode 第 210 场周赛 解题报告

class Solution {
public:
    int maxDepth(string s) {
        int depth = 0; // 并不需要一个 std::stack，只维护一下元素数量就可以了。
        int anw = 0; // 记录一下 depth 的最大值。
        for(auto c : s) {
            if(c == '(') {
                depth ++;
            } else if(c == ')') {
                depth --;
            }
            anw = max(anw, depth);
        }
        return anw;
    }
};

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        int anw = 0;
        vector<vector<int>> cnt(n, vector<int>(n, 0));
        vector<int> cl(n, 0), cr(n, 0);
        for(const auto &r : roads) {
            cnt[r[0]][r[1]]++; // 标记是否存在边(u，v)
            cnt[r[1]][r[0]]++;
            cl[r[0]]++;   // 预处理与 p 直接相连边的数量
            cl[r[1]]++;
            cr[r[0]]++;
            cr[r[1]]++;
        }
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                anw = max(anw, cl[i] + cr[j] - cnt[i][j]);
            }
        }
        return anw;
    }
};

class Solution {
public:
    bool isPalindrome(const std::string &a, int l, int r) {
        // 判断中间部分是否为回文串
        while(l < r) {
            if(a[l] != a[r]) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
    
    bool check(const string &a, const string &b) {
        // 从 a 中选取前缀， 从 b 中选取后缀
        for(int i = 0, j = a.size()-1; i < j; i++, j--) {
            if(a[i] != b[j]) {
                if(isPalindrome(a, i, j) || isPalindrome(b, i, j)) {
                    return true;
                } else {
                    break;
                }
            }
            if(j-i <= 2) { // 中间部分为空字符串或者为单字符的情况
                return true;
            }
        }
        
        // 从 b 中选取前缀， 从 a 中选取后缀
        for(int i = 0, j = a.size()-1; i < j; i++, j--) {
            if(b[i] != a[j]) {
                return isPalindrome(a, i, j) || isPalindrome(b, i, j);
            }
            if(j-i <= 2) {  // 中间部分为空字符串或者为单字符的情况
                return true;
            }
        }
        return true;
    }
    bool checkPalindromeFormation(string a, string b) {
        return check(a, b);
    }
};

class Solution {
public:
    vector<int> vec[20];
    vector<int> anw;
    bool getPath(int s, int pre, int t, vector<int> &path) {
        if(s == t) {
            return true;
        }
        for(auto c : vec[s]) {
            if(c == pre) {
                continue;
            }
            if(getPath(c, s, t, path)) {
                path.push_back(s);
                return true;
            }
        }
        return false;
    }
    int getDis(int s, int t, int status) {
        vector<int> path;
        // dfs 获取 (s, t) 之间的路径
        getPath(s, -1, t, path);
        
        // 判断路径上的点是否都在点集内
        for(auto c : path) {
            if((status&(1<<(c-1))) == 0) {
                return -1;
            }
        }
        return path.size();
    }
    int get(int n, int status) {
        int maxDis = 0;
        for(int i = 1, bi = 1; i <= n; i++, bi <<= 1) {
            if((bi&status) == 0) {
                continue;
            }
            for(int j = i+1, bj = bi<<1; j <= n; j++, bj <<= 1) {
                // 两层 for 循环，枚举点对 (i,j)
                if((bj&status) == 0) {
                    continue;
                }
                // 获取 (i,j)之间的路径长度，并判断路径上的点是否都在该点集内。
                int tmpDis = getDis(i, j, status);
                
                // tmpDis 不超过 0，说明status不能构成一棵子树
                if(tmpDis <= 0) {
                    return 0;
                }
                maxDis = max(maxDis, tmpDis);
            }
        }
        return maxDis;
    }
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
        // 先搞个邻接表
        for(const auto &pair : edges) {
            vec[pair[0]].push_back(pair[1]);
            vec[pair[1]].push_back(pair[0]);
        }
        // 初始化答案
        anw.resize(n-1);
        //因为至少应该包含两个点，所以从 3 开始枚举
        
        for(int i = 3, mask = 1<< n; i < mask; i++) {
            int dis = get(n, i);
            //利用 dis <= 0 表示点集不能构成子树
            if(dis <= 0) {
                continue;
            }
            anw[dis-1] ++;
        }
        return anw;
    }
};