剩下10分钟还有一题hard开摆了
第一题
分别用用红球当头和蓝球当头模拟取高度比较高的那个。
class Solution {
public int maxHeightOfTriangle(int red, int blue) {
return Math.max(helper(red, blue), helper(blue, red));
}
private int helper(int red, int blue) {
int h = 1;
int round = 0;
while (true) {
if (round == 0) {
red -= h;
} else {
blue -= h;
}
if (red < 0 || blue < 0) {
break;
}
h++;
round = 1 ^ round;
}
return h - 1;
}
}
第二题
dp问题 序列要马是
1.全偶数
2.全奇数
3.奇偶交错
上面三个情况取最大的就好
class Solution {
public int maximumLength(int[] nums) {
int odd = 0;
int even = 0;
int oddEven = 0;
int evenOdd = 0;
for (int num : nums) {
if (num % 2 == 1) {
odd++;
oddEven = evenOdd + 1;
} else {
even++;
evenOdd = oddEven + 1;
}
}
int res = Math.max(even, odd);
res = Math.max(res, oddEven);
res = Math.max(res, evenOdd);
return res;
}
}
第三题
第二题的延伸 要想出一个通用方法 因为测资变小了所以可以用很暴力的方式
class Solution {
public int maximumLength(int[] nums, int k) {
int n = nums.length;
int res = 0;
int[][] dp = new int[n][k];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], 1);
for (int j = 0; j < i; j++) {
int key = (nums[i] + nums[j]) % k;
dp[i][key] = Math.max(dp[i][key], dp[j][key] + 1);
res = Math.max(res, dp[i][key]);
}
}
return res;
}
}