A.括号的最大嵌套深度

解题思路：
模拟。
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxDepth(string s) {
        int n = s.size(),ans = 0,t = 0;
        for(int i = 0;i < n;i++){
            if(s[i] == '('){
                t++;
                ans = max(ans,t);
            }else if(s[i] == ')'){
                t--;
            }
        }
        return ans;
    }
};

B.最大网络秩

解题思路：
用邻接矩阵记录两个城市是否有道路，并记录每个城市相连的道路条数。暴力枚举城市对，算出这个城市对的答案为两个城市相连道路条数和并减去两个城市互连的道路。最大网络秩为各个城市对答案的最大值。
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> isr;
    vector<int> nums;
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        isr.resize(n,vector<int>(n,0));
        nums.resize(n,0);
        int ans = 0;
        for(int i = 0;i < roads.size();i++){
            int x = roads[i][0], y = roads[i][1];
            isr[x][y] = isr[y][x] = 1;
            nums[x]++;  nums[y]++;
        }
        for(int i = 0;i < n;i++){
            for(int j = i + 1;j < n;j++){
                ans = max(ans,nums[i] + nums[j] - isr[i][j]);
            }
        }
        return ans;
    }
};

C.分割两个字符串得到回文串

解题思路：
从字符串A中心找最大回文串，以此划分A字符串为Ale AmidAri，以相同位置划分B为Ble BmidBri。如果Ale + Bri 或者 Ble+Ari 为回文串，则分割这两个字符串可以得到回文串。同理寻找B的中心回文串，以此来划分A和B字符串，判断Ale + Bri 或者 Ble+Ari 是否为回文串。如果都不是，则分割这两个字符串不可以得到回文串。
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int n = a.size(),midl,midr;
        if(n == 1 || n == 0) return true;
        midl = (n - 2) / 2;midr = midl + 1 + n % 2;
        while(midl >= 0){
            if(a[midl] != a[midr])  break;
            midl--;midr++;
        }
        if(midl < 0)    return true;
        string s1 = a.substr(0,midl + 1), s2 = a.substr(midr,n - midr);
        string s3 = b.substr(0,midl + 1), s4 = b.substr(midr,n - midr);
        reverse(s2.begin(),s2.end());
        reverse(s4.begin(),s4.end());
        if(s1 == s4 || s2 == s3)    return true;
        midl = (n - 2) / 2;midr = midl + 1 + n % 2;
        while(midl >= 0){
            if(b[midl] != b[midr])  break;
            midl--;midr++;
        }
        if(midl < 0)    return true;
        s1 = a.substr(0,midl + 1), s2 = a.substr(midr,n - midr);
        s3 = b.substr(0,midl + 1), s4 = b.substr(midr,n - midr);
        reverse(s2.begin(),s2.end());
        reverse(s4.begin(),s4.end());
        if(s1 == s4 || s2 == s3)    return true;
        return false;
    }
};

D.统计子树中城市之间最大距离

解题思路：
二进制枚举，最短路。一共只有十五个城市，二进制枚举所有可能情况。先判断枚举的城市组合是否是连通的。如果是连通的，则以每个城市为起点，用广度优先搜索算法计算一次最短路。

代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    int n;
    vector<int> ans;
    vector<int> vis;
    vector<vector<int>> edges;
    int max_dis(){
        int res = 0,eds=0;
        vector<int> v;
        vector<vector<int>> e(n);
        for(int i = 0;i < edges.size();i++){
            int x = edges[i][0], y = edges[i][1];
            if(vis[x] && vis[y]){
                eds++;
                e[x].push_back(y); e[y].push_back(x);
            }
        }
        int t = 0;
        for(int i = 0;i < vis.size();i++){
            if(vis[i])  t++;
            if(vis[i] && e[i].size() == 0)  return 0;
        }
        if(t != eds+1) return 0;
        for(int i = 0;i < vis.size();i++){
            if(vis[i]){
                v = vis;
                queue<pair<int,int>> q;
                q.push({i,0});
                v[i] = false;
                while(!q.empty()){
                    auto t = q.front();
                    q.pop();
                    int x = t.first, d = t.second;
                    res = max(res,d);
                    for(int j = 0;j < e[x].size();j++){
                        int to = e[x][j];
                        if(v[to]){
                            v[to] = false;
                            q.push({to,d+1});
                        }
                    }
                }
            }
        }
        return res;
    }
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
        this->n = n;
        ans.resize(n-1,0);
        vis.resize(n);
        int e = edges.size();
        for(int i = 0;i < e;i++){
            edges[i][0]--;
            edges[i][1]--;
        }
        this->edges = edges;
        for(int i = 0;i < (1<<n);i++){
            for(int j = 0;j < n;j++) vis[j] = false;
            for(int j = 0;j < n;j++){
                if(i & (1 << j)){
                    vis[j] = true;
                }
            }
            int res = max_dis();
            if(res>=1) ans[res-1]++;
        }
        return ans;
    }
};

做题情况：
AC 三题
排名：291 / 4006
总结反思：
前三题写的还行，第四题一开始没想到二进制枚举，写起来也比较生疏，导致最后也没写完。