Leetcode - 周赛404

目录

一，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;
    }
}