前言
我曾经认为自己喜欢这个人
t1 按身高排序
排序的一个trick技巧
Java
class Solution {
public String[] sortPeople(String[] names, int[] heights) {
Integer[] arr = IntStream.range(0, names.length).boxed().toArray(Integer[]::new);
Arrays.sort(arr, Comparator.comparingInt(a -> -heights[a]));
return Arrays.stream(arr).map(x -> names[x]).toArray(String[]::new);
}
}t2 按位与最大的最长子数组
如果K是任取的，那这题挺难的。
但这边的K，按照题意就是最大值。
Java
class Solution {
public int longestSubarray(int[] nums) {
// 求最大值
int target = Arrays.stream(nums).max().getAsInt();
int ans = 0;
int inc = 0;
for (int v: nums) {
if (v == target) {
inc++;
ans = Math.max(ans, inc);
} else {
inc = 0;
}
}
return ans;
}
}t3 找到所有好下标
哈哈，给个固定长度K的滑窗单调队列解吧，左边维护一个单调队列，右边维护一个单调队列，当他们大小刚好为k时，说明该下标为可行解。
Java
class Solution {
// *)
public List<Integer> goodIndices(int[] nums, int k) {
Deque<Integer> before = new LinkedList<>();
Deque<Integer> after = new LinkedList<>();
// *) 固定长度的滑窗单调队列
for (int i = 0; i < k; i++) {
while (!before.isEmpty() && nums[before.peekLast()] < nums[i]) {
before.pollLast();
}
before.addLast(i);
}
for (int i = k + 1; i < nums.length && i <= 2 * k; i++) {
while (!after.isEmpty() && nums[after.peekLast()] > nums[i]) {
after.pollLast();
}
after.addLast(i);
}
List<Integer> result = new ArrayList<>();
for (int i = k; i < nums.length; i++) {
if (before.size() == k && after.size() == k) {
result.add(i);
}
// 处理前置的滑窗单调队列
while (!before.isEmpty() && before.peekFirst() <= i - k) {
before.pollFirst();
}
while (!before.isEmpty() && nums[before.peekLast()] < nums[i]) {
before.pollLast();
}
before.addLast(i);
// 处理后置的滑窗单调队列
while (!after.isEmpty() && after.peekFirst() <= i + 1) {
after.pollFirst();
}
if (i + k + 1 < nums.length) {
while (!after.isEmpty() && nums[after.peekLast()] > nums[i + k + 1]) {
after.pollLast();
}
after.addLast(i + k + 1);
}
}
return result;
}
}t4 好路径的数目
确实是好题, 真的没想到可以用并查集来解决，算是学到了。
通过从小到大，逐步合并，完美解决判定是否连通的问题。
不过在用并查集的时候，好像有两大类
- 批处理同等的值，等完成后，统一计算, 不破坏并查集模板
- 每次合并中，进行计算，需要对并查集进行扩展
这题思路，参考了多个大神的思路和写法，权当做复盘和笔记了。
并查集 (思路一)
Java
class Solution {
// 并查集
static class DSU {
int n;
int[] arr;
public DSU(int n) {
this.n = n;
this.arr = new int[n];
Arrays.fill(this.arr, -1);
}
int find(int u) {
if (arr[u] == -1) {
return u;
}
// 路径压缩
return arr[u] = find(arr[u]);
}
void union(int u, int v) {
int p1 = find(u);
int p2 = find(v);
if (p1 != p2) {
this.arr[p2] = p1;
}
}
}
// *)
public int numberOfGoodPaths(int[] vals, int[][] edges) {
// 构建图
int n = vals.length;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] e: edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
DSU dsu = new DSU(n);
Integer[] arr = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(arr, Comparator.comparingInt(a -> vals[a]));
int gAns = 0;
int i = 0;
while (i < arr.length) {
int j = i + 1;
while (j < arr.length && vals[arr[j]] == vals[arr[i]]) {
j++;
}
// 同大小的进行 同一批合并
for (int k = i; k < j; k++) {
int idx = arr[k];
List<Integer> es = adj.get(idx);
for (int e: es) {
if (vals[idx] >= vals[e]) {
// 进行合并
dsu.union(idx, e);
}
}
}
// 计算同大小的每个组的个数
Map<Integer, Integer> gp = new TreeMap<>();
for (int k = i; k < j; k++) {
int g = dsu.find(arr[k]);
gp.put(g, gp.getOrDefault(g, 0) + 1);
}
for (Map.Entry<Integer, Integer> e: gp.entrySet()) {
gAns += e.getValue() * (e.getValue() + 1) / 2;
}
i = j;
}
return gAns;
}
}
启发式合并
Java
class Solution {
// Java的闭包 不太友好
// 这边外置，丑陋但是没辙
List<List<Integer>> gAdj = new ArrayList<>();
int[] gVals;
int gAns = 0;
TreeMap<Integer, Integer> dfs(int p, int fa) {
TreeMap<Integer, Integer> res = new TreeMap<>();
res.put(gVals[p], 1);
gAns++;
List<Integer> es = gAdj.get(p);
for (int v: es) {
if (v == fa) continue;
TreeMap<Integer, Integer> tm = dfs(v, p);
while (!tm.isEmpty() && tm.firstKey() < gVals[p]) {
tm.remove(tm.firstKey());
}
// swap (这个优化很重要)
if (res.size() < tm.size()) {
TreeMap<Integer, Integer> t = tm;
tm = res;
res = t;
}
// 计算结果 & 合并
for (Map.Entry<Integer, Integer> e : tm.entrySet()) {
gAns += e.getValue() * res.getOrDefault(e.getKey(), 0);
res.put(e.getKey(), res.getOrDefault(e.getKey(), 0) + e.getValue());
}
}
return res;
}
public int numberOfGoodPaths(int[] vals, int[][] edges) {
for (int i = 0; i < vals.length; i++) {
gAdj.add(new ArrayList<>());
}
for (int[] e: edges) {
gAdj.get(e[0]).add(e[1]);
gAdj.get(e[1]).add(e[0]);
}
gVals = vals;
dfs(0, -1);
return gAns;
}
}备注： 其实我一直认为这是树形DP， 实际在比赛中也是这种写法，但一直 TLE，真的是无尽的绝望。两者的差异在有无swap，对比之下，这个swap真的是太关键了.
启发式合并的精髓：小集合合并于大集合。
评论 (0)
