1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public int[] platesBetweenCandles(String s, int[][] queries) {
char[] sArray = s.toCharArray();
int[] prevCandlePos = new int[s.length()];
int[] nextCandlePos = new int[s.length()];
int[] candleCount = new int[sArray.length];
int lastLeftCandle = -1, lastRightCandle = sArray.length, count = 0;
for (int left = 0, right = sArray.length - 1; left < sArray.length; left++, right--) {
if (sArray[left] == '*') {
prevCandlePos[left] = lastLeftCandle;
} else {
lastLeftCandle = left;
prevCandlePos[left] = left;
count += 1;
candleCount[left] = count;
}
if (sArray[right] == '*') {
nextCandlePos[right] = lastRightCandle;
} else {
lastRightCandle = right;
nextCandlePos[right] = right;
}
}
int[] ans = new int[queries.length];
for (int i = 0; i < ans.length; i++) {
int leftBound = queries[i][0];
int rightBound = queries[i][1];
int firstCandle = nextCandlePos[leftBound];
int lastCandle = prevCandlePos[rightBound];
if (firstCandle == -1 || lastCandle == -1) {
ans[i] = 0;
} else {
int eleNum = lastCandle - firstCandle - 1;
if (eleNum > 0) {
ans[i] = eleNum - (candleCount[lastCandle] - candleCount[firstCandle] - 1);
} else {
ans[i] = 0;
}
}
}
return ans;
}
}
|
一开始想到了先计算每个plate的prev和next candle的位置. 但是没有想到在一个range中如何计算valid plates的个数. 想到了prefix sum但是没想到prefix记录的是candles的个数而非plates的个数, 因为如果记录plates的个数, 每个plate是否valid要看给的范围, 如何确定范围就是问题. 因此我们可以记录candles的个数的prefix sum. 在某个范围内candles的个数就能知道.
时间复杂度: O(N + Q)
空间复杂度: O(N + Q) N是存prev, next以及candleCount, Q是ans的长度.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
public int[] platesBetweenCandles(String s, int[][] queries) {
List<Integer> candleIdx = new ArrayList<>();
char[] sArray = s.toCharArray();
for (int i = 0; i < sArray.length; i++) {
if (sArray[i] == '|') {
candleIdx.add(i);
}
}
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int leftBound = queries[i][0];
int rightBound = queries[i][1];
int firstCandle = binarySearchCeil(candleIdx, leftBound);
int lastCandle = binarySearchFloor(candleIdx, rightBound);
if (firstCandle < lastCandle) {
ans[i] = candleIdx.get(lastCandle) - candleIdx.get(firstCandle) + 1 - (lastCandle - firstCandle + 1);
} else {
ans[i] = 0;
}
}
return ans;
}
private int binarySearchCeil(List<Integer> candleIdx, int target) {
int left = 0, right = candleIdx.size() - 1, ans = candleIdx.size();
while (left <= right) {
int mid = left + (right - left) / 2;
if (candleIdx.get(mid) > target) {
ans = mid;
right = mid - 1;
} else if (candleIdx.get(mid) < target) {
left = mid + 1;
} else {
ans = mid;
break;
}
}
return ans;
}
private int binarySearchFloor(List<Integer> candleIdx, int target) {
int left = 0, right = candleIdx.size() - 1, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (candleIdx.get(mid) < target) {
ans = mid;
left = mid + 1;
} else if (candleIdx.get(mid) > target) {
right = mid - 1;
} else {
ans = mid;
break;
}
}
return ans;
}
}
|
这个是binary search的做法. 这个做法是真没想到. 我们记录每一个candle的index是什么. 当给我们一个range后, 我们计算这个range中第一个candle和最后一个candle的位置是什么. 找candle的位置就是binary search了, 我们需要找candle index比leftBound大的中最小的, candle index比rightBound小的中最大的. 找到后返回给我们的是这两个candle index在list中的index, 实际在s中的index需要list.get()一下, 毕竟我们在list中记录的就是candle在s中的index. 之后我们计算这两个candle框起来的区域长度是多少, 然后这个区域内candle的数量是多少.
时间复杂度: O(N + 2QlogN) 我们准备candle的list是O(N), list中candle的个数最多是N个, 我们需要进行2Q次binary search(一个floor, 一个ceil). 因此是O(N + QlogN)
空间复杂度: O(N) 我们需要存candle的index都是什么.
