LeetCode第210场周赛(栈、图的存储、回文串、二进制枚举子集+树的直径)

5535. 括号的最大嵌套深度

class Solution {
public:int maxDepth(string s) {int cnt &＃61; 0, ans &＃61; 0;for(char c:s){if(c&＃61;&＃61;&＃39;(&＃39;){cnt&＃43;&＃43;;ans &＃61; max(ans,cnt);}if(c&＃61;&＃61;&＃39;)&＃39;){cnt--;}}return ans;}
};


5536. 最大网络秩
时间复杂度O(n2&＃43;m)O(n^2&＃43;m)O(n2&＃43;m)

class Solution {
public:int maximalNetworkRank(int n, vector<vector<int>>& roads) {int ans &＃61; 0,id &＃61; 1;vector<int> g[110];for(auto& e:roads){id&＃43;&＃43;;g[e[0]].push_back(id);g[e[1]].push_back(id);}for(int x&＃61;0;x<n;x&＃43;&＃43;){for(int y&＃61;x&＃43;1;y<n;y&＃43;&＃43;){bool vis[10010] &＃61; {0};int res &＃61; 0;for(int i:g[x]){if(!vis[i]){vis[i] &＃61; 1;res&＃43;&＃43;;}}for(int i:g[y]){if(!vis[i]){vis[i] &＃61; 1;res&＃43;&＃43;;}}ans &＃61; max(ans,res);}}return ans;}
};


零神的基本思路是选择度数最大和次大的&＃xff0c;具体做的时候要注意分类讨论&＃xff0c;
时间复杂度&＃xff1a;$O(m\&＃43;n)$

1616. 分割两个字符串得到回文串
比赛的时候用字符串hash做的&＃xff0c;醉了

• a.prefix &＃43; b.suffix 或者 b.prefix &＃43; a.suffix 可以处理成一种情况
• 双指针比较 a 和 b 前后相等的地方&＃xff0c;剩余的串必须是回文串。
  

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


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

• 二进制枚举子集
• 判断点集的连通性
• 树形DP求树的直径

注&＃xff1a;在用书上的DP求直径的时候&＃xff0c;可以直接用vis数组判断连通性。

const int N &＃61; 250;
class Solution {int head[N] &＃61; {0},next[N] &＃61; {0}, v[N] &＃61; {0}, cnt &＃61; 0;
int dis &＃61; 0,d[N],vis[N],n;
bool dots[N];void add(int x,int y){v[&＃43;&＃43;cnt] &＃61; y;next[cnt] &＃61; head[x];head[x] &＃61; cnt;
}void dp(int x){vis[x] &＃61; 1;for(int i &＃61; head[x];i;i&＃61;next[i]){int y &＃61; v[i];if(vis[y] || !dots[y]) continue;dp(y);dis &＃61; max(dis,d[x]&＃43;d[y]&＃43;1);d[x] &＃61; max(d[x],d[y]&＃43;1);}
}void solve(){memset(d,0,sizeof d);memset(vis,0,sizeof vis);dis &＃61; 0;int x;for(x&＃61;1;x<&＃61;n;x&＃43;&＃43;){if(dots[x]) break;}if(x&＃61;&＃61;n&＃43;1) return;dp(x);// 判断是否连通for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(dots[i] && !vis[i]){dis &＃61; 0;return;}}
} public:vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {this->n &＃61; n;vector<int> ans(n-1,0);// 1~nfor(auto&e:edges) {add(e[0],e[1]);add(e[1],e[0]);}int lim &＃61; 1<<n;for(int ss&＃61;0;ss<lim;ss&＃43;&＃43;){memset(dots,0,sizeof dots);int pos &＃61; 1;int s &＃61; ss;while(s){if(s&1) dots[pos] &＃61; 1;s >>&＃61; 1;pos&＃43;&＃43;;}solve();if(dis) ans[dis - 1]&＃43;&＃43;;}return ans;}
};