weekly contest 210

写在前面

• Maximum Nesting Depth of the Parentheses 字符串
• Maximal Network Rank 图 brute force
• Split Two Strings to Make Palindrome 回文字符 hash
• Count Subtrees With Max Distance Between Cities

Maximum Nesting Depth of the Parentheses

原题链接

class Solution {
public:
    int maxDepth(string s) {
        if(s.size() == 0) return 0;
        int depth = 0,res = 0;
        for(char n : s){
            if(n == '('&&depth >= 0){depth++; res=max(depth,res);}
            else if(n == ')')depth--;
        }
        return res;
    }
};

Maximal Network Rank

原题链接

const int MAX=100 + 50;
bool lnk [MAX][MAX];//ai和bi之间是否有边
int cnt[MAX];//每个节点边的个数
class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        int m = roads.size();
        for(int i = 0; i < n; i++){
            cnt[i] = 0;
            for(int j = 0; j < n; j++)lnk[i][j] = false;
        }
        for(int i = 0; i < m; i++){
            int a = roads[i][0], b = roads[i][1];
            cnt[a] += 1; cnt[b] += 1;
            lnk[a][b] = lnk[b][a] = true;
        }
        int ans = 0;
        for(int i=0;  i < n; i++){
            for(int j = i+1; j < n; j++){
                int cur =cnt[i] + cnt[j] - (lnk[i][j] ? 1 : 0);
                ans= max(ans, cur);
            }
        }
        return ans;
    }
};

Split Two Strings to Make Palindrome

原题链接

class Solution {
public:
	bool isPalindrome(string s,int l,int r){
        while(l<r)
            if(s[l++]!=s[r--]) return false;
        return true;
    }
    bool check(string &a, string &b) {
    int i = 0, j = a.size() - 1;
    while (i < j && a[i] == b[j])
        ++i, --j;
    return isPalindrome(a, i, j) || isPalindrome(b, i, j);
	}
	bool checkPalindromeFormation(string a, string b) {
    return check(a, b) || check(b, a);
	}
};

Count Subtrees With Max Distance Between Cities

原题链接