欢迎大家加QQ群：623375442，可以方便群里面交流。
这周题目需要细心。。。疯狂WA，心累。
100301. Count Pairs That Form a Complete Day II
给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。
测试样例：
输入：hours = [12,12,30,24,24]
输出：2
解释：构成整天的下标对分别是 (0, 1) 和 (3, 4)。
解答：这题可以取模之后，利用HashMap来计算可以成为整天的统计情况。取模之后，最多24个数，直接用int[]当HashMap用了。
class Solution {
public long countCompleteDayPairs(int[] hours) {
int[] count = new int[24];
long res = 0;
for (int n : hours) {
int remain = n % 24;
if (remain == 0) {
res += count[remain];
} else {
res += count[24 - remain];
}
count[remain] += 1;
}
return res;
}
}100316. Maximum Total Damage With Spell Casting
一个魔法师有许多不同的咒语。
给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。
已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。
每个咒语最多只能被使用 一次 。
请你返回这个魔法师可以达到的伤害值之和的 最大值 。
测试样例：
输入：power = [1,1,3,4]
输出：6
解释：可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。
解答：需要注意，使用power[i]之后，power[i]这个伤害的咒语还是可以继续使用的。这题需要用动态规划来完成计算，遍历，这俩条件其实可以不考虑power[i] + 1 或者 power[i] + 2。我用了TreeMap寻找需要的位置，但是这里最好用双指针来优化。 更新一下，用了Stream API取了distinct后sort，这样就不用这么麻烦了。
注意返回需要long，我悲剧WA一次。
class Solution {
public long maximumTotalDamage(int[] power) {
HashMap<Integer, Long> sum = new HashMap<>();
for (int n : power) {
sum.put(n, sum.getOrDefault(n, 0L) + n);
}
int[] org = Arrays.stream(power).distinct().sorted().toArray();
long[] max = new long[org.length];
for (int i = 0; i < max.length; ++i) {
long add = sum.get(org[i]);
long last = i == 0 ? 0 : max[i - 1];
max[i] = add;
for (int j = 1; j <= 3; ++j) {
if (i - j >= 0 && org[i] - org[i - j] > 2) {
max[i] = add + max[i - j];
break;
}
}
max[i] = Math.max(max[i], last);
}
return max[max.length - 1];
}
}100317. Peaks in Array
数组 arr 中 大于 前面和后面相邻元素的元素被称为 峰值 元素。
给你一个整数数组 nums 和一个二维整数数组 queries 。
你需要处理以下两种类型的操作：
- queries[i] = [1, li, ri] ，求出子数组 nums[li..ri] 中 峰值 元素的数目。
- queries[i] = [2, indexi, vali] ，将 nums[indexi] 变为 vali 。
请你返回一个数组 answer ，它依次包含每一个第一种操作的答案。
注意：
- 子数组中 第一个 和 最后一个 元素都 不是 峰值元素。
测试样例：
输入：nums = [3,1,4,2,5], queries = [[2,3,4],[1,0,4]]
输出：[0]
解释：第一个操作：我们将 nums[3] 变为 4 ，nums 变为 [3,1,4,4,5] 。第二个操作：[3,1,4,4,5] 中峰值元素的数目为 0 。
解答：利用线段树计算动态区间的情况。需要注意nums[li..ri]子数组，头尾必然不是峰值元素，需要去掉。然后li == ri这种情况还需要特殊处理。两种情况，WA 2次。这周太难了。
class Solution {
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int[] nums) {
if (nums.length > 0) {
n = nums.length;
tree = new int[n * 2];
buildTree(nums);
}
}
private void buildTree(int[] nums) {
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = nums[j];
for (int i = n - 1; i > 0; --i)
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
void update(int pos, int val) {
pos += n;
tree[pos] = val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
tree[pos / 2] = tree[left] + tree[right];
pos /= 2;
}
}
public int sumRange(int l, int r) {
l += n;
r += n;
int sum = 0;
while (l <= r) {
if ((l % 2) == 1) {
sum += tree[l];
l++;
}
if ((r % 2) == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
int len = nums.length;
int[] ori = new int[len];
for (int i = 0; i < len; ++i) {
ori[i] = isPeak(nums, i);
}
SegmentTree tree = new SegmentTree(ori);
List<Integer> res = new ArrayList<>();
for (int[] q : queries) {
if (q[0] == 2) {
nums[q[1]] = q[2];
tree.update(q[1], isPeak(nums,q[1]));
if (q[1] - 1 >= 0) {
tree.update(q[1] - 1, isPeak(nums,q[1] - 1));
}
if (q[1] + 1 < nums.length) {
tree.update(q[1] + 1, isPeak(nums,q[1] + 1));
}
} else {
int tmp = tree.sumRange(q[1], q[2]) - isPeak(nums, q[1]);
if (q[1] != q[2]) {
tmp -= isPeak(nums, q[2]);
}
res.add(tmp);
}
}
return res;
}
private int isPeak(int[] nums, int pos) {
if (pos - 1 >= 0 && pos + 1 < nums.length && nums[pos] > nums[pos - 1] && nums[pos] > nums[pos + 1]) {
return 1;
}
return 0;
}
}