### 题目描述 给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。 同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [left_i, right_i] 表示 子字符串 s[left_i...right_i] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。 比方说，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 <= 10^5 - s 只包含字符 '*' 和 '|' 。 - 1 <= queries.length <= 10^5 - queries[i].length == 2 - 0 <= left_i <= right_i < s.length ### 题目解答 #### 解题思路 在解决该问题的时候，用到了**前缀和**以及数组**预处理**两个重要的想法。 **前缀和思想** 对一个数组a[i](0<=i<n), 给定一堆查询[m, n]求在该区间内的元素和，可以考虑前缀和的想法。首先建立数组b[i+1]用于记录a[0]~a[i]的总和. **预处理思想** 对于给定的[left, right]我们可以先预处理得到left右侧第一个蜡烛的位置，和right左侧第一个蜡烛的位置。通过前缀和计算这两个蜡烛之间盘子的数量得到结果。 **算法复杂度** 时间复杂度：对于前缀和、left、right三个数组，O(n)三次遍历即可得到三个数组。查询的时候只需要O(1)复杂度即可查询得到结果。 空间复杂度：需要通过3个数组记录，o(n)复杂度 ### 代码实现 ```python class Solution: def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]: preSum = list() num = 0 for i in range(len(s)): if s[i] == '*': num += 1 preSum.append(num) # 构建数组查询[left, right]区间钟[left', right']的位置 left = [len(s)] * len(s) for i in range(len(s)-1, -1, -1): if s[i] == '*': if i < len(s)-1: left[i] = left[i+1] elif s[i] == '|': left[i] = i right = [-1] * len(s) for i in range(0, len(s)): if s[i] == '*': if i > 1: right[i] = right[i-1] elif s[i] == '|': right[i] = i res = list() for query in queries: begin, end = query[0], query[1] real_begin, real_end = left[begin], right[end] if real_begin > len(s) or real_end < 0: res.append(0) elif real_begin <= real_end: res.append(preSum[real_end] - preSum[real_begin]) else: res.append(0) return res ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复