目录
一，3200. 三角形的最大高度
二，3201. 找出有效子序列的最大长度 I
三，3202. 找出有效子序列的最大长度 II
四，3203. 合并两棵树后的最小直径
一，3200. 三角形的最大高度
本题直接模拟，分别计算一下红蓝红和蓝红蓝的最大高度。
代码如下：
class Solution {
public int maxHeightOfTriangle(int red, int blue) {
return Math.max(make(red, blue), make(blue, red));
}
int make(int a, int b){
int i = 1;
while(true){
if(i%2==1){
a -= i;
}else{
b -= i;
}
if(a < 0 || b < 0) return i-1;
i++;
}
}
}二，3201. 找出有效子序列的最大长度 I
本题讲个简单的做法，(a+b)%2 = (a%2 + b%2)%2，就是看相邻的两个数是奇奇，偶偶，还是奇偶，所以可以分别求这三种情况，即奇数的个数，偶数的个数，以及奇偶相间的个数（这里直接贪心，不用分奇偶奇还是偶奇偶，直接看第一个数是奇数还是偶数就行），代码如下：
class Solution {
public int maximumLength(int[] nums) {
int sum = 0, k = -1, cnt = 1;
for(int i=0; i<nums.length; i++){
nums[i] %= 2;
if(k == -1) k = nums[i];
else{
if((k^nums[i])==1){
k ^= 1;
cnt++;
}
}
sum += nums[i];
}
return Math.max(Math.max(sum, nums.length-sum), cnt);
}
}三，3202. 找出有效子序列的最大长度 II
本题无法使用dfs记忆化来做，会超时，那么我们如何来写这道题呢？有这样一个性质，假设(a + b)%k = (b + c)%k，可以推出 (a + b - (b + c))%k = 0，(a - c)%k = 0，即a%k = c%k。结合本题题意，如果将nums中的所有值 % k，可以得出子序列中奇数项都相同，偶数项也都相同。
定义f[x][y]：以x，y结尾的最长子序列（这里的x，y都是nums[i]%k）。由上述结论可以得出下面的递推公式 f[x][y] = f[y][x] + 1，代码如下：
class Solution {
public int maximumLength(int[] nums, int k) {
int ans = 1;
int[][] f = new int[k][k];
for(int x : nums){
x %= k;
for(int y=0; y<k; y++){
f[y][x] = f[x][y] + 1;
ans = Math.max(f[y][x], ans);
}
}
return ans;
}
}四，3203. 合并两棵树后的最小直径
写本题需要推出一个结论，就是该题的最长路径长度一定是e1的直径，e2的直径，e1的直径/2 + e2的直径/2 + 1 （即两个树直径的中点相连）这三者的最大值。
可以由反证法证明为啥是两个树直径的中点相连，存在两种情况：
- 如果存在一个点不在e1或e2的直径上，那么以它相连得到的最长直径，一定要先走到直径上，所以它一定比两个树直径的中点相连多走一段距离
- 如果存在一个点在e1或e2的直径上但是不是中点，显而易见，以它相连得到的最长直径一定要大于两个树直径的中点相连
得出结论后，我们要做的就是求出两个图的直径，代码如下：
class Solution {
public int minimumDiameterAfterMerge(int[][] e1, int[][] e2) {
int s1 = inital(e1);
int s2 = inital(e2);
return Math.max(Math.max(s1, s2), (s1+1)/2 + (s2+1)/2 + 1);
}
int res;
int inital(int[][] edge){
int n = edge.length;
List<Integer>[] g = new ArrayList[n+1];
Arrays.setAll(g, e->new ArrayList<>());
for(int[] e : edge){
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x);
}
res = 0;
dfs(0, -1, g);
return res;
}
//求直径
int dfs(int x, int fa, List<Integer>[] g){
int maxLen = 0;
for(int y : g[x]){
if(y != fa){
int t = dfs(y, x, g)+1;
res = Math.max(res, maxLen + t);
maxLen = Math.max(maxLen, t);
}
}
return maxLen;
}
}
