题目
给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，
它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。
同时给你一个下标从 0 开始的二维整数数组 queries ，
其中 queries[i]=[lefti, righti] 表示 子字符串 s[lefti...righti] （包含左右端点的字符）。
对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。
如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。
比方说，s="||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||**|" 。
子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。
请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。
示例 1:输入：s="**|**|***|", queries=[[2,5],[5,9]] 输出：[2,3]
解释：- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。
示例 2:输入：s="***|**|*****|**||**|*", queries=[[1,17],[4,5],[14,17],[5,11],[15,16]] 输出：[9,0,0,0,0]
解释：- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。
提示：3 <=s.length <=105
s 只包含字符 '*' 和 '|' 。
1 <=queries.length <=105
queries[i].length==2
0 <=lefti <=righti < s.length
1、前缀和；时间复杂度O(n),空间复杂度O(n)
func platesBetweenCandles(s string, queries [][]int) []int {
n :=len(s)
res :=make([]int, len(queries))
sum :=make([]int, n+1)
left, right :=make([]int, n), make([]int, n)
prev :=-1
for i :=0; i < n; i++ {
sum[i+1]=sum[i]
if s[i]=='|' { // 蜡烛
prev=i
} else {
sum[i+1]++
}
left[i]=prev
}
prev=n
for i :=n - 1; i >=0; i-- {
if s[i]=='|' { // 蜡烛
prev=i
}
right[i]=prev
}
for i :=0; i < len(queries); i++ {
a, b :=right[queries[i][0]], left[queries[i][1]] // 位子：右边第一个蜡烛，左边第一个蜡烛
if a < b { // 满足的条件下
res[i]=sum[b] - sum[a]
}
}
return res
}
2、二分查找；时间复杂度O(nlog(n)),空间复杂度O(n)
func platesBetweenCandles(s string, queries [][]int) []int {
n :=len(s)
res :=make([]int, len(queries))
arr :=make([]int, 0)
for i :=0; i < n; i++ {
if s[i]=='|' { // 盘子
arr=append(arr, i)
}
}
for i :=0; i < len(queries); i++ {
a, b :=queries[i][0], queries[i][1]
l :=sort.SearchInts(arr, a)
r :=sort.SearchInts(arr, b)
if r==len(arr) || arr[r] !=b { // r超出范围或者找到的下标不是目标数
r--
}
if l < r {
res[i]=arr[r] - arr[l] - (r - l) // 总个数-盘子个数
}
}
return res
}总结
Medium题目，可以使用前缀和方法，简单明了
联系客服
