You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
class Solution {
public int[] minReverseOperations(int n, int p, int[] banned, int k) {
int[] res = new int[n];
boolean[] visited = new boolean[n];
for (int j : banned) {
res[j] = -1;
visited[j] = true;
}
visited[p] = true;
TreeSet<Integer> even = new TreeSet<>(), odd = new TreeSet<>();
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
if (i % 2 == 0) even.add(i);
else odd.add(i);
}
Queue<Integer> q = new ArrayDeque<>();
q.add(p);
int steps = 1;
TreeSet<Integer> set = new TreeSet<>();
int min, max, mCurrent;
while (!q.isEmpty()) {
int sz = q.size();
while (sz-- > 0) {
int cur = q.poll();
if (k % 2 == 0) {
if (cur + 1 < n) {
set = (cur + 1) % 2 == 0 ? even : odd;
} else if (cur - 1 >= 0) {
set = (cur - 1) % 2 == 0 ? even : odd;
}
} else {
set = cur % 2 == 0 ? even : odd;
}
// calculate min index
if (cur < k - 1) {
min = (k - 1) - cur;
}else {
min = cur - k + 1;
}
// calculate max index
if (cur + k - 1 >= n) {
max = (n - k) + (n - cur - 1);
}else {
max = cur + k - 1;
}
Integer mid = set.ceiling(min);
while (mid != null && mid <= max) {
if (visited[mid]) {
set.remove(mid);
min += 2;
mid = set.ceiling(min);
continue;
}
visited[mid] = true;
q.add(mid);
res[mid] = steps;
set.remove(mid);
min += 2;
mid = set.ceiling(min);
}
}
++steps;
}
for (int i = 0; i < n; ++i) {
if (res[i] == 0 && i != p) res[i] = -1;
}
return res;
}
}
看完题目,首先想到的是在数组中使用BFS。
观察规律,结合k,可以发现扩散范围跟奇偶有关。接着就很容易写出BFS题解。但发现TLE了,说明最坏情况下时间复杂度是O(nk)。然后我就不知道如何优化。
赛后,这个卡点的解决方法是利用平衡树来取数,可以使时间复杂度缩减为O(n+nlgn)。提前存好奇偶索引,两个TreeSet,然后利用**ceilling(E e)**方法(该方法取大于等于e参数的最小值),如此可以优化取数算法。TreeSet内置就是个优化的链表+红黑树的结构。这种写法算是取数的一种黑科技了。
同时要注意界定取数时的最小值和最大值。如果没超出时间范围还好说,如果超出了,就需要从0或n-1开始计算k大小的范围内的索引变化了。这也算是个小卡点。
还有个并查集的写法,这里我不写了XD,可以看参考资料。
类似题目:
The text was updated successfully, but these errors were encountered: