LeetCode 力扣官方题解 | 2055. 蜡烛之间的盘子
2055. 蜡烛之间的盘子（点击文末阅读原文查看题目）
题目描述
难易度：中等
给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 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
解决方案
方法一：预处理 + 前缀和
思路
对于每一个询问，我们只需要找到给定区间内最左侧和最右侧的两个蜡烛，这样两个蜡烛之间的所有盘子都是符合条件的。
对于寻找蜡烛，我们可以预处理区间内每个位置左侧的第一个蜡烛和右侧的第一个蜡烛。这样区间左端点 lefti 右侧的第一个蜡烛即为区间最左侧的蜡烛，区间右端点 righti 左侧的第一个蜡烛即为区间最右侧的蜡烛。
对于计算盘子数量，我们可以计算盘子数量的前缀和 preSum。假设找到的两蜡烛的位置分别为 x 和 y，那么两位置之间的盘子数量即为 preSumy − preSumx − 1。
这样我们就通过预处理，将寻找蜡烛和计算盘子数量两个操作的时间复杂度降至 O(1)，因此对于每个询问，时间复杂度为 O(1)。
在实际代码中，可能某个位置的左侧或右侧是不存在蜡烛的，此时我们将对应数组的值记为 -1。当 x 为 −1 或者 y 为 −1 或者 x ≥ y 时，不存在满足条件的盘子。同时注意到因为 x 位置是蜡烛，所以盘子数量也可以表示为 preSumy − preSumx，这个写法可以防止 x 为 0 时数组越界。
代码
C++
class Solution {public:vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {int n = s.length();vector<int> preSum(n);for (int i = 0, sum = 0; i < n; i++) {if (s[i] == '*') {sum++;}preSum[i] = sum;}vector<int> left(n);for (int i = 0, l = -1; i < n; i++) {if (s[i] == '|') {l = i;}left[i] = l;}vector<int> right(n);for (int i = n - 1, r = -1; i >= 0; i--) {if (s[i] == '|') {r = i;}right[i] = r;}vector<int> ans;for (auto& query : queries) {int x = right[query[0]], y = left[query[1]];ans.push_back(x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x]);}return ans;}};
Java
class Solution {public int[] platesBetweenCandles(String s, int[][] queries) {int n = s.length();int[] preSum = new int[n];for (int i = 0, sum = 0; i < n; i++) {if (s.charAt(i) == '*') {sum++;}preSum[i] = sum;}int[] left = new int[n];for (int i = 0, l = -1; i < n; i++) {if (s.charAt(i) == '|') {l = i;}left[i] = l;}int[] right = new int[n];for (int i = n - 1, r = -1; i >= 0; i--) {if (s.charAt(i) == '|') {r = i;}right[i] = r;}int[] ans = new int[queries.length];for (int i = 0; i < queries.length; i++) {int[] query = queries[i];int x = right[query[0]], y = left[query[1]];ans[i] = x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x];}return ans;}}
C#
public class Solution {public int[] PlatesBetweenCandles(string s, int[][] queries) {int n = s.Length;int[] preSum = new int[n];for (int i = 0, sum = 0; i < n; i++) {if (s[i] == '*') {sum++;}preSum[i] = sum;}int[] left = new int[n];for (int i = 0, l = -1; i < n; i++) {if (s[i] == '|') {l = i;}left[i] = l;}int[] right = new int[n];for (int i = n - 1, r = -1; i >= 0; i--) {if (s[i] == '|') {r = i;}right[i] = r;}int[] ans = new int[queries.Length];for (int i = 0; i < queries.Length; i++) {int[] query = queries[i];int x = right[query[0]], y = left[query[1]];ans[i] = x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x];}return ans;}}
C
int* platesBetweenCandles(char * s, int** queries, int queriesSize, int* queriesColSize, int* returnSize){int n = strlen(s);int * preSum = (int *)malloc(sizeof(int) * n);memset(preSum, 0, sizeof(int) * n);for (int i = 0, sum = 0; i < n; i++) {if (s[i] == '*') {sum++;}preSum[i] = sum;}int * left = (int *)malloc(sizeof(int) * n);memset(left, 0, sizeof(int) * n);for (int i = 0, l = -1; i < n; i++) {if (s[i] == '|') {l = i;}left[i] = l;}int * right = (int *)malloc(sizeof(int) * n);memset(right, 0, sizeof(int) * n);for (int i = n - 1, r = -1; i >= 0; i--) {if (s[i] == '|') {r = i;}right[i] = r;}int * ans = (int *)malloc(sizeof(int) * queriesSize);for (int i = 0; i < queriesSize; i++) {int x = right[queries[i][0]], y = left[queries[i][1]];ans[i] = x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x];}free(preSum);free(left);free(right);*returnSize = queriesSize;return ans;}
Python3
class Solution:def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:n = len(s)preSum, sum = [0] * n, 0left, l = [0] * n, -1for i, ch in enumerate(s):if ch == '*':sum += 1else:l = ipreSum[i] = sumleft[i] = lright, r = [0] * n, -1for i in range(n - 1, -1, -1):if s[i] == '|':r = iright[i] = rans = [0] * len(queries)for i, (x, y) in enumerate(queries):x, y = right[x], left[y]if x >= 0 and y >= 0 and x < y:ans[i] = preSum[y] - preSum[x]return ans
Golang
func platesBetweenCandles(s string, queries [][]int) []int {n := len(s)preSum := make([]int, n)left := make([]int, n)sum, l := 0, -1for i, ch := range s {if ch == '*' {sum++} else {l = i}preSum[i] = sumleft[i] = l}right := make([]int, n)for i, r := n-1, -1; i >= 0; i-- {if s[i] == '|' {r = i}right[i] = r}ans := make([]int, len(queries))for i, q := range queries {x, y := right[q[0]], left[q[1]]if x >= 0 && y >= 0 && x < y {ans[i] = preSum[y] - preSum[x]}}return ans}
JavaScript
var platesBetweenCandles = function(s, queries) {const n = s.length;const preSum = new Array(n).fill(0);for (let i = 0, sum = 0; i < n; i++) {if (s[i] === '*') {sum++;}preSum[i] = sum;}const left = new Array(n).fill(0);;for (let i = 0, l = -1; i < n; i++) {if (s[i] === '|') {l = i;}left[i] = l;}const right = new Array(n).fill(0);;for (let i = n - 1, r = -1; i >= 0; i--) {if (s[i] === '|') {r = i;}right[i] = r;}const ans = new Array(queries.length).fill(0);for (let i = 0; i < queries.length; i++) {const query = queries[i];const x = right[query[0]], y = left[query[1]];ans[i] = x === -1 || y === -1 || x >= y ? 0 : preSum[y] - preSum[x];}return ans;};
复杂度分析
时间复杂度：O(n+q)，其中 n 为数组长度，q 为询问数量。我们需要 O(n) 的时间预处理。对于每一个询问，我们需要 O(1) 的时间计算答案。
空间复杂度：O(n)，其中 n 为数组长度。我们需要 O(n) 的空间保存预处理的结果。注意返回值不计入空间复杂度。
BY /
本文作者：力扣
编辑&版式：Irene
声明：本文归“力扣”版权所有，如需转载请联系。
点个在看，少个 bug
微信扫码关注该文公众号作者
戳这里提交新闻线索和高质量文章给我们。
来源: qq
点击查看作者最近其他文章