欢迎大家加QQ群：623375442，可以方便群里面交流。
100340. Maximum Height of a Triangle
给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。
每一行的球必须是 相同 颜色，且相邻行的颜色必须 不同。
返回可以实现的三角形的 最大 高度。
测试样例：
输入：red = 2, blue = 4
输出：3
解释：唯一可能的排列方式。
解答：暴力计算一下，先红后蓝，以及先蓝后红。
class Solution {
public int maxHeightOfTriangle(int red, int blue) {
return Math.max(findHeight(new int[]{red, blue}), findHeight(new int[]{blue, red}));
}
private int findHeight(int[] arr) {
int height = 0, need = 1;
int res = 0;
while (arr[height] >= need) {
arr[height] -= need;
height ^= 1;
need += 1;
++res;
}
return res;
}
}100357. Find the Maximum Length of Valid Subsequence I
给你一个整数数组 nums。
nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列：
- (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2
返回 nums 的 最长的有效子序列 的长度。
一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。
测试样例：
输入： nums = [1,2,3,4]
输出：4
解释：最长的有效子序列是 [1, 2, 3, 4]。
解答：因为是%2，我们建立一个DP数组，数组中有4个元素，分别是00,01,10,11。代表最后两位数%2的情况。这样有这样的转移方式：00 -> 00, 01 -> 10, 10 -> 01, 11 -> 11。然后遍历数组，根据当前数字的%2情况，更新一下数组。
class Solution {
public int maximumLength(int[] nums) {
int[] dp = new int[4];
for (int n : nums) {
int[] next = new int[4];
for (int i = 0; i < 4; ++i) {
int k = (i * 2) % 4 + n % 2;
next[i] = Math.max(next[i], dp[i]);
if ((i == 0 && k == 0) || (i == 1 && k == 2) || (i == 2 && k == 1) || (i == 3 && k == 3)) {
next[k] = Math.max(next[k], dp[i] + 1);
}
}
dp = next;
}
int res = 0;
for (int n : dp) {
res = Math.max(res, n);
}
return res;
}
}100358. Find the Maximum Length of Valid Subsequence II
给你一个整数数组 nums 和一个 正 整数 k 。
nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：
- (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k
返回 nums 的 最长有效子序列 的长度。
测试样例：
输入：nums = [1,4,2,3,1,4], k = 3
输出：4
解释：最长有效子序列是 [1, 4, 1, 4] 。
解答：这题范围小了很多，果断就是双循环暴力计算了。双循环暴力确定i和j的位置之后（i > j），我们就确定了%k的结果状态，然后寻找j位置对应的上一个结果更新即可。
class Solution {
public int maximumLength(int[] nums, int k) {
int len = nums.length;
int[][] mem = new int[len][k];
int res = 2;
for (int i = 0; i < len; ++i) {
Arrays.fill(mem[i], 1);
int c = nums[i] % k;
for (int j = i - 1; j >= 0; --j) {
int t = nums[j] % k;
mem[i][t] = Math.max(mem[i][t], mem[j][c] + 1);
res = Math.max(res, mem[i][t]);
}
}
return res;
}
}100318. Find Minimum Diameter After Merging Two Trees
给你两棵 无向 树，分别有 n 和 m 个节点，节点编号分别为 0 到 n - 1 和 0 到 m - 1 。给你两个二维整数数组 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [ai, bi] 表示在第一棵树中节点 ai 和 bi 之间有一条边，edges2[i] = [ui, vi] 表示在第二棵树中节点 ui 和 vi 之间有一条边。
你必须在第一棵树和第二棵树中分别选一个节点，并用一条边连接它们。
请你返回添加边后得到的树中，最小直径 为多少。
一棵树的 直径 指的是树中任意两个节点之间的最长路径长度。
测试样例：
输入：edges1 = [[0,1],[0,2],[0,3]], edges2 = [[0,1]]
输出：3
解释：将第一棵树中的节点 0 与第二棵树中的任意节点连接，得到一棵直径为 3 得树。
解答：这题可以参考树中距离之和。我们通过类似的思路需要寻找到两个值：当前节点为root时，通过当前节点的最大直径和最长root到叶节点距离。算法一样，两次DFS就能获得。然后记录一下两颗树树内最大直径，和连接两点之后，带来的最长直径。
class Solution {
public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
InternalData d1 = new InternalData(edges1.length + 1, edges1);
InternalData d2 = new InternalData(edges2.length + 1, edges2);
int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE;
int dm1 = Integer.MIN_VALUE, dm2 = Integer.MIN_VALUE;
for (int n : d1.res) {
m1 = Math.min(n, m1);
}
for (int n : d1.diameter) {
dm1 = Math.max(n, dm1);
}
for (int n : d2.res) {
m2 = Math.min(n, m2);
}
for (int n : d2.diameter) {
dm2 = Math.max(n, dm2);
}
return Math.max(m1 + m2 + 1, Math.max(dm1, dm2));
}
private class InternalData {
private int[][] zeroRemain;
private int n;
private List<Integer>[] edges;
private int[] res, diameter;
public InternalData(int n, int[][] _edges) {
this.n = n;
zeroRemain = new int[n][4];
edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
buildZero();
findAnswer();
}
private void buildZero() {
dfsWithZeroSeed(0, -1);
}
private void dfsWithZeroSeed(int cur, int last) {
for (int n : edges[cur]) {
if (n != last) {
dfsWithZeroSeed(n, cur);
if (zeroRemain[n][0] + 1 > zeroRemain[cur][0]) {
zeroRemain[cur][2] = zeroRemain[cur][0];
zeroRemain[cur][3] = zeroRemain[cur][1];
zeroRemain[cur][0] = zeroRemain[n][0] + 1;
zeroRemain[cur][1] = n;
} else if (zeroRemain[n][0] + 1 > zeroRemain[cur][2]) {
zeroRemain[cur][2] = zeroRemain[n][0] + 1;
zeroRemain[cur][3] = n;
}
}
}
}
private void findAnswer() {
res = new int[n];
diameter = new int[n];
dfsResult(0, -1, -1);
}
private void dfsResult(int cur, int last, int lastDistance) {
if (cur == 0) {
res[0] = zeroRemain[0][0];
diameter[0] = zeroRemain[0][0] + zeroRemain[0][2];
} else {
res[cur] = Math.max(lastDistance, zeroRemain[cur][0]);
if (lastDistance >= zeroRemain[cur][2]) {
diameter[cur] = lastDistance + zeroRemain[cur][0];
} else {
diameter[cur] = zeroRemain[cur][0] + zeroRemain[cur][2];
}
}
for (int n : edges[cur]) {
if (n != last) {
if (lastDistance >= zeroRemain[cur][0]) {
dfsResult(n, cur, lastDistance + 1);
} else if (n == zeroRemain[cur][1]) {
dfsResult(n, cur, Math.max(lastDistance + 1, zeroRemain[cur][2] + 1));
} else {
dfsResult(n, cur, zeroRemain[cur][0] + 1);
}
}
}
}
}
}