RANK297
A：✅ B：✅ C：✅ T4：❌
思路：数据范围小，按照题意直接模拟。
时间复杂度：O(n^2 * logK)
public int[] findXSum(int[] nums, int k, int x) {
int n = nums.length;
int[] res = new int[n-k+1];
for (int i = 0; i < n; i++) {
var cnt = new HashMap<Integer, Integer>();
int sum = 0;
for (int j = i; j < n; j++) {
cnt.merge(nums[j], 1, Integer::sum);
sum += nums[j];
if (j - i + 1 == k) {
int v = 0;
List<int[]> list = new ArrayList<>();
for (var e : cnt.entrySet()) {
list.add(new int[]{e.getValue(), e.getKey()});
}
list.sort((a, b) -> b[0] == a[0] ? b[1] - a[1] : b[0] - a[0]);
if (list.size() < x) {
res[i] = sum;
} else {
for (int l = 0; l < x; l++) {
v += list.get(l)[0] * list.get(l)[1];
}
res[i] = v;
}
break;
}
}
}
return res;
}思路：DFS后序遍历树，返回left和right的信息来更新root的信息，并记录到一个list里面，最后排序返回k-1即可。
算法标签：DFS、排序。
时间复杂度：O(NLogN)
List<int[]> tset = new ArrayList<>();
public int kthLargestPerfectSubtree(TreeNode root, int k) {
dfs(root);
if (tset.size() < k) {
return -1;
}
List<int[]> list = new ArrayList<>();
list.addAll(tset);
list.sort((a, b) -> b[0] - a[0]);
return list.get(k - 1)[0];
}
boolean dfs(TreeNode root) {
if (root == null) return true;
boolean ok1 = dfs(root.left);
boolean ok2 = dfs(root.right);
int v1 = root.left != null ? root.left.val : 0;
int v2 = root.right != null ? root.right.val : 0;
if (ok1 && ok2 && v1 == v2) {
tset.add(new int[]{v1 + v2 + 1, root.val});
root.val = v1 + v2 + 1;
return true;
} else {
root.val = 0;
return false;
}
}C. 统计能获胜的出招序列数
思路：动态规划，定义dp[i][v][pre]表示前i个比赛，Bob获得分数差为v，并且Bob i-1场出牌为pre的出招序列数。然后就按照题意if-else模拟，注意这个分差可能为负数（Alice一直赢的情况），我们需要将v加一个OFFSET来防止越界，最后判断下分差v如果大于0，则说明是一种合法的出牌序列。
算法标签：动态规划。
时间复杂度：O(N*2)
int[][][] dp;
static final int MOD = (int) (1e9 + 7);
int OFFSET = 0;
char[] a;
public int countWinningSequences(String s) {
int n = s.length();
a = s.toCharArray();
OFFSET = n + 1;
int m = 'W'-'A';
dp = new int[n][n+OFFSET][m+1];
for (int[][] arr : dp) {
for (int[] row : arr) {
Arrays.fill(row, -1);
}
}
return dfs(0, 0, 'A');
}
public int dfs(int i, int v, char prev) {
if (i >= a.length) return v > 0 ? 1 : 0;
if (dp[i][v+OFFSET][prev-'A'] != -1) return dp[i][v+OFFSET][prev-'A'];
int ret = 0;
if (a[i] == 'F') {
if (prev != 'E') ret += dfs(i + 1, v - 1, 'E'); ret %= MOD;
if (prev != 'F') ret += dfs(i + 1, v, 'F'); ret %= MOD;
if (prev != 'W') ret += dfs(i + 1, v + 1, 'W'); ret %= MOD;
} else if (a[i] == 'W') {
if (prev != 'F') ret += dfs(i + 1, v - 1, 'F'); ret %= MOD;
if (prev != 'W') ret += dfs(i + 1, v, 'W'); ret %= MOD;
if (prev != 'E') ret += dfs(i + 1, v + 1, 'E'); ret %= MOD;
} else {
if (prev != 'W') ret += dfs(i + 1, v - 1, 'W'); ret %= MOD;
if (prev != 'E') ret += dfs(i + 1, v, 'E'); ret %= MOD;
if (prev != 'F') ret += dfs(i + 1, v + 1, 'F'); ret %= MOD;
}
dp[i][v+OFFSET][prev-'A'] = ret;
return ret;
}思路：两个有序集合维护前k大元素。具体看b站灵神视频讲解。
算法标签：滑动窗口、有序集合。
时间复杂度：O(NLogN)
TreeSet<int[]> L = new TreeSet<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); // 维护出现次数前x大
TreeSet<int[]> R = new TreeSet<>(L.comparator());
Map<Integer, Integer> cnt = new HashMap<>();
long sumL = 0;
public long[] findXSum(int[] nums, int k, int x) {
int n = nums.length;
long[] ans = new long[n - k + 1];
for (int r = 0; r < nums.length; r++) {
// 入
int in = nums[r];
del(in);
cnt.merge(in, 1, Integer::sum);
add(in);
int l = r + 1 - k;
if (l < 0) continue;
while (!R.isEmpty() && L.size() < x) r2l();
while (L.size() > x) l2r();
ans[l] = sumL;
// 出
int out = nums[l];
del(out);
cnt.merge(out, -1, Integer::sum);
add(out);
}
return ans;
}
void add(int val) {
int c = cnt.getOrDefault(val, 0);
if (c == 0) return;
int[] p = new int[]{c, val};
if (!L.isEmpty() && L.comparator().compare(p, L.first()) > 0) {
sumL += (long) p[0] * p[1];
L.add(p);
} else {
R.add(p);
}
}
void del(int val) {
int c = cnt.getOrDefault(val, 0);
if (c == 0) return;
int[] p = new int[]{c, val};
if (L.contains(p)) {
sumL -= (long) p[0] * p[1];
L.remove(p);
} else {
R.remove(p);
}
}
void l2r() {
int[] p = L.pollFirst();
sumL -= (long) p[0] * p[1];
R.add(p);
}
void r2l() {
int[] p = R.pollLast();
sumL += (long) p[0] * p[1];
L.add(p);
}