力扣第 116 场双周赛
大约 3 分钟
力扣第 116 场双周赛
比赛时间 2023-10-28。本场周赛国服共 72 人 AK。
本场 T4 解法太优美，忍不住记录一下。
T1. 子数组不同元素数目的平方和 I（3 分）
解题思路
两层 for 循环 + 哈希表。
时间复杂度：O(n^2)。
参考代码
class Solution {
private static final int MOD = (int) (1e9 + 7);
public int sumCounts(List<Integer> nums) {
int n = nums.size();
long ans = 0;
for (int i = 0; i < n; i++) {
Set<Integer> set = new HashSet<>();
for (int j = i; j < n; j++) {
set.add(nums.get(j));
long d = set.size();
ans += d * d;
ans %= MOD;
}
}
return (int) ans;
}
}
T2. 使二进制字符串变美丽的最少修改次数（4 分）
解题思路
脑筋急转弯。由于 s 的长度为偶数，所以一定有解，贪心的做法的按长度 2 分割子字符串。
时间复杂度：O(n)。
参考代码
class Solution {
public int minChanges(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; i += 2) {
if (s.charAt(i) != s.charAt(i + 1)) {
ans++;
}
}
return ans;
}
}
T3. 和为目标值的最长子序列的长度（5 分）
解题思路
0-1 背包问题，刚好装满背包场景，需要初始化 -inf。
时间复杂度：O(n^2)。
参考代码
class Solution {
private static final int INF = (int) 1e9;
public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
int[] f = new int[target + 1];
Arrays.fill(f, -INF);
f[0] = 0;
for (Integer num : nums) {
for (int j = target; j >= num; j--) {
f[j] = Math.max(f[j], f[j - num] + 1);
if (f[j] < 0) {
f[j] = -INF;
}
}
}
return f[target] == -INF ? -1 : f[target];
}
}
T4. 子数组不同元素数目的平方和 II（7 分）
解题思路
数学 & 线段树。
old = a^2 + b^2 + c^2
new = (a+1)^2 + (b+1)^2 + (c+1)^2
= (a^2 + 2a + 1) + (b^2 + 2b + 1) + (c^2 + 2c + 1)
= (a^2 + b^2 + c^2) + 2(a+b+c) + 3
new = old + 2sum + n
时间复杂度：O(nlogn)。
参考:
- https://leetcode.cn/circle/discuss/SwnhNk/
- https://www.luogu.com.cn/problem/P1972
- https://codeforces.com/gym/104459/problem/F
- https://atcoder.jp/contests/abc256/tasks/abc256_f
相似题目:
100094. 子数组不同元素数目的平方和 Ihttps://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-i/2262. 字符串的总引力https://leetcode.cn/problems/total-appeal-of-a-string/828. 统计子串中的唯一字符https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/
参考代码
class Solution {
private static final int MOD = (int) (1e9 + 7);
private static final int MAX_N = (int) (1e5 + 5);
public int sumCounts(int[] nums) {
int n = nums.length;
long ans = 0;
int[] last = new int[MAX_N];
SegmentTree seg = new SegmentTree(n);
for (int i = 1; i <= n; i++) {
int old = last[nums[i - 1]];
seg.add1(old + 1, i);
last[nums[i - 1]] = i;
// 答案就是 [1, i] 这段区间的 sum2 之和
ans = (ans + seg.getSum2(1, i)) % MOD;
}
return (int) ans;
}
private static class SegmentTree {
int n;
// sum1:区间和, sum2:区间平方和
long[] sum1, sum2, lazy;
public SegmentTree(int n) {
this.n = n;
this.sum1 = new long[n * 4];
this.sum2 = new long[n * 4];
this.lazy = new long[n * 4];
}
public void add1(int ql, int qr) {
add1(1, 1, n, ql, qr);
}
public long getSum2(int ql, int qr) {
return getSum2(1, 1, n, ql, qr);
}
// 根据公式维护区间加 K
// sum2 = sum2 + 2 * k * sum1 + len * k * k; // len 是区间长度
// sum1 = sum1 + len * k;
void formula(int p, int l, int r, long k) {
int len = r - l + 1;
sum2[p] = (sum2[p] + 2 * k * sum1[p] + k * k % MOD * len) % MOD;
sum1[p] = (sum1[p] + k * len) % MOD;
}
void pushDown(int p, int l, int r) {
if (lazy[p] > 0) {
int mid = l + (r - l) / 2;
lazy[p << 1] += lazy[p];
formula(p << 1, l, mid, lazy[p]);
lazy[p << 1 | 1] += lazy[p];
formula(p << 1 | 1, mid + 1, r, lazy[p]);
lazy[p] = 0;
}
}
// 区间加 1
void add1(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
formula(p, l, r, 1);
lazy[p]++;
return;
}
pushDown(p, l, r);
int mid = l + (r - l) / 2;
if (ql <= mid) add1(p << 1, l, mid, ql, qr);
if (qr > mid) add1(p << 1 | 1, mid + 1, r, ql, qr);
pushUp(p);
}
void pushUp(int p) {
sum1[p] = (sum1[p << 1] + sum1[p << 1 | 1]) % MOD;
sum2[p] = (sum2[p << 1] + sum2[p << 1 | 1]) % MOD;
}
long getSum2(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return sum2[p];
}
pushDown(p, l, r);
int mid = l + (r - l) / 2;
long sum = 0;
if (ql <= mid) sum = getSum2(p << 1, l, mid, ql, qr) % MOD;
if (qr > mid) sum = (sum + getSum2(p << 1 | 1, mid + 1, r, ql, qr)) % MOD;
return sum;
}
}
}
（全文完）