LeetCode 题解工作台
蜡烛之间的盘子
给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ， '|' 表示一支 蜡烛 。 同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [left i , rig…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
class Solution: def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 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 <= 105s只包含字符'*'和'|'。1 <= queries.length <= 105queries[i].length == 20 <= lefti <= righti < s.length
解题思路
方法一
class Solution:
def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
presum = [0] * (n + 1)
for i, c in enumerate(s):
presum[i + 1] = presum[i] + (c == '*')
left, right = [0] * n, [0] * n
l = r = -1
for i, c in enumerate(s):
if c == '|':
l = i
left[i] = l
for i in range(n - 1, -1, -1):
if s[i] == '|':
r = i
right[i] = r
ans = [0] * len(queries)
for k, (l, r) in enumerate(queries):
i, j = right[l], left[r]
if i >= 0 and j >= 0 and i < j:
ans[k] = presum[j] - presum[i + 1]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for understanding of binary search over answer space and efficient query handling.
- question_mark
Test the candidate's ability to optimize the problem using prefix sums.
- question_mark
Check for the candidate's familiarity with handling large inputs efficiently.
常见陷阱
外企场景- error
Incorrectly handling queries where no valid plate is between candles.
- error
Failing to optimize the solution for large input sizes, leading to timeouts.
- error
Misunderstanding how to handle cases where candles are adjacent or missing in the query range.
进阶变体
外企场景- arrow_right_alt
Handling cases where no candles are present in the substring.
- arrow_right_alt
Optimizing for multiple queries with overlapping ranges.
- arrow_right_alt
Modifying the problem to count plates without requiring both left and right candles.