526互联

2055. 蜡烛之间的盘子

发布时间 2023-04-07 17:23:13作者: zhangk1988

题目描述

给了一个字符串，只有* 和 | ，分别表示盘子和蜡烛
再给了很多查询，对某个查询[x, y]，问在区间内的且在蜡烛之间的盘子的个数？

f1-预处理+前缀和

基本分析

  1. 1个字符多个查询可以考虑什么？预处理
  2. 对每个查询x，y需要知道什么？索引>=x的最近的盘子位置；索引<=y的最近的盘子的位置
  3. 根据2的需求，需要预处理出什么？对每个数字x，找到索引<=x的蜡烛的索引l，left[x] = l; 对每个数字x，找到索引>=x的蜡烛的索引r，right[y] = r。
  4. 找到蜡烛以后，还需要知道啥？每个蜡烛左边的盘子的个数，可以在遍历left数组时候计算出来
  5. 怎么找到区间内的和？presum[y] - presum[x-1]

代码

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)

        left, l = [0] * n, -1
        presum = [0] * n
        cnt = 0

        for i in range(n):
            if s[i] == "|":
                l = i
            else:
                cnt += 1
            left[i] = l
            presum[i] = cnt
        
        right, r = [0] * n, -1
        for i in range(n-1, -1, -1):
            if s[i] == '|':
                r = i
            right[i] = r
        
        m = len(queries)
        ans = [0] * m

        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

总结

  1. 统计left和right数组时候，如果左边和右边没有蜡烛怎么办？初值给成-1
  2. 当x=0时候，presum[-1]越界怎么办？如果x=0，表示x处是蜡烛，可以用presum[x]代替