5535. 括号的最大嵌套深度——easy
如果字符串满足一下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
- 字符串是一个空字符串
""，或者是一个不为"("或")"的单字符。 - 字符串可以写为
AB（A与B字符串连接），其中A和B都是 有效括号字符串 。 - 字符串可以写为
(A)，其中A是一个 有效括号字符串 。
类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
depth("") = 0depth(A + B) = max(depth(A), depth(B))，其中A和B都是 有效括号字符串depth("(" + A + ")") = 1 + depth(A)，其中A是一个 有效括号字符串
例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。
给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
示例 1：
输入：s = “(1+(2*3)+((8)/4))+1”
输出：3
解释：数字 8 在嵌套的 3 层括号中。
示例 2：
输入：s = “(1)+((2))+(((3)))”
输出：3
示例 3：
输入：s = “1+(2*3)/(2-1)”
输出：1
示例 4：
输入：s = “1”
输出：0
提示：
1 <= s.length <= 100
s 由数字 0-9 和字符 ‘+’、’-‘、’*’、’/‘、’(‘、’)’ 组成
题目数据保证括号表达式 s 是 有效的括号表达式
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses
思路：
实际上就是求最多有多少个 ( 还未匹配 )
/*** @param {string} s* @return {number}*/var maxDepth = function(s) {let left = 0;let cnt = 0;for(let i = 0;i<s.length;i++){if(s[i]==='('){left++;cnt =Math.max(cnt,left)}else if(s[i]===')'){left--;}}return cnt;};
5536. 最大网络秩——medium
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。
示例 1：
输入：n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
输出：4
解释：城市 0 和 1 的网络秩是 4，因为共有 4 条道路与城市 0 或 1 相连。位于 0 和 1 之间的道路只计算一次。
示例 2：
输入：n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
输出：5
解释：共有 5 条道路与城市 1 或 2 相连。
示例 3：
输入：n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
输出：5
解释：2 和 5 的网络秩为 5，注意并非所有的城市都需要连接起来。
提示：
- 2 <= n <= 100
- 0 <= roads.length <= n * (n - 1) / 2
- roads[i].length == 2
- 0 <= ai, bi <= n-1
- ai != bi
- 每对城市之间 最多只有一条 道路相连
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-network-rank
思路：
其实就是问，图中任意找出两个点，以其中至少一个为端点的不重复的边的数目的最大值是多少？
对于每个城市统计连接的道路数，以及记录双向边，枚举起点和终点，如果两点有直接连通，两者道路数相加去掉一个重复的，如果未连通，则两者道路数相加。
var maximalNetworkRank = function(n, roads) {let cnt = 0;let city = new Array(n+1).fill(0);let edge = new Array(n+1).fill(undefined).map(()=>{return new Array(n+1).fill(0)})for(let i = 0;i<roads.length;i++){let [u,v]= roads[i];city[u]++;city[v]++;edge[u][v] =1;edge[v][u] = 1;}for(let i = 0;i<n;i++){for(let j=i+1;j<n;j++){let tmp;if(edge[i][j]){tmp = city[i]+city[j] -1;}else{tmp = city[i]+city[j] ;}cnt = Math.max(tmp,cnt)}}return cnt;};
1616. 分割两个字符串得到回文串——medium
给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： a 和 a ，满足 a = aprefix + asuffix ，同理，由 b 可以得到两个字符串 b 和 b ，满足 b = bprefix + bsuffix 。请你判断 a + b 或者 b + a 能否构成回文串。
当你将一个字符串 s 分割成 s 和 s 时， s 或者 s 可以为空。比方说， s = “abc” 那么 “” + “abc” ， “a” + “bc” ， “ab” + “c” 和 “abc” + “” 都是合法分割。
如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
请注意， x + y 表示连接字符串 x 和 y 。
示例 1：
输入：a = “x”, b = “y”
输出：true
解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割：
aprefix = “”, asuffix = “x”
bprefix = “”, bsuffix = “y”
那么 aprefix + bsuffix = “” + “y” = “y” 是回文串。
示例 2：
输入：a = “ulacfd”, b = “jizalu”
输出：true
解释：在下标为 3 处分割：
aprefix = “ula”, asuffix = “cfd”
bprefix = “jiz”, bsuffix = “alu”
那么 aprefix + bsuffix = “ula” + “alu” = “ulaalu” 是回文串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-two-strings-to-make-palindrome
思路：
定义 i=0 从正序遍历a，j=n-1 逆序遍历b，如果 a[i] ===b[j]，此时是回文：i++;j-- 。如果 a[i] !==b[j] 此时得到a[0~i-1]和b[j+1,n-1]可形成回文串，但是要求在相同的下标割开，所以需要a或b的i~j之间字符串满足回文，则可拼接成一个回文 ： [a[0~i-1], 回文子串,b[j+1,n-1]] 。
var checkPalindromeFormation = function (a, b) {const checkPalindrome = (s)=>{let n = s.length;for(let i = 0;i<n/2;i++){if(s[i]!==s[n-1-i]){return false}}return true}const check = (s1,s2)=>{let i =0,j=s1.length-1;while(i<j&& s1[i] === s2[j]){i++;j--;}return checkPalindrome(s1.slice(i,j+1))||checkPalindrome(s2.slice(i,j+1))}return check(a,b) || check(b,a)};
5538. 统计子树中城市之间最大距离——hard
给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。
一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。
对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。
请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。
请注意，两个城市间距离定义为它们之间需要经过的边的数目。
示例 1：
**
输入：n = 4, edges = [[1,2],[2,3],[2,4]]
输出：[3,4,0]
解释：
子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。
子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。
不存在城市间最大距离为 3 的子树。
示例 2：
输入：n = 2, edges = [[1,2]]
输出：[1]
示例 3：
输入：n = 3, edges = [[1,2],[2,3]]
输出：[2,1]
提示：
- 2 <= n <= 15
- edges.length == n-1
- edges[i].length == 2
- 1 <= ui, vi <= n
- 题目保证 (ui, vi) 所表示的边互不相同。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-subtrees-with-max-distance-between-cities
思路:
floyd跑一个最短路，枚举组合，通过dfs判断是否可连通，如果可连通，找到这个子树两点间的最大距离，更新答案数组。
var countSubgraphsForEachDiameter = function (n, edges) {let vis, visAll;let d = new Array(n).fill(undefined).map(() => {return new Array(n).fill(Infinity);});let g = new Array(n).fill(undefined).map(() => {return [];});const dfs = (u, fa) => {vis |= 1 << u;for (let v of g[u]) {if ((vis >> v & 1) === 0 && (visAll >> v & 1) === 1 && v !== fa) {dfs(v, u);}}};for (let i = 0; i < n; i++) {d[i][i] = 0;}for (let edge of edges) {let [u, v] = edge;u = u - 1;v = v - 1;d[u][v] = 1;d[v][u] = 1;g[u].push(v);g[v].push(u);}let ans = new Array(n - 1).fill(0);for (let k = 0; k < n; k++) {for (let i = 0; i < n; i++) {for (let j = 0; j < n; j++) {d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);}}}for (let s = 2; s < (1 << n); s++) {let t = [];for (let i = 0; i < n; i++) {if ((s >> i) & 1) t.push(i);}visAll = s;vis = 0;dfs(t[0], -1);if (vis === visAll) {let max = 0;for (let u of t) {for (let v of t) {max = Math.max(max, d[u][v]);}}if (max > 0 && max <= n - 1) ans[max - 1]++;}}return ans;};
若有收获，就点个赞吧
0 人点赞
