Leetcode 2055. Plates Between Candles [Python]

第一种前缀和加二分搜索，会TLE。这里着重看第二种方法的思路，前缀和从左到右做一次，然后以“|”蜡烛位置为标杆，将一颗蜡烛位置之前的盘子数量统一，也就是例如，到地3颗蜡烛，共有5个盘子，而到第二颗蜡烛之前，有2颗盘子，则把第3颗蜡烛到第三颗蜡烛之间的盘子数和都记做5.因为题目要求只看start右侧最近的蜡烛之后的盘子。同理，只看end左侧最近的蜡烛之前的盘子。这里，把“s”颠倒，重复上述前缀和以及区间的结果统一的操作，然后将结果颠倒就可以。此时给定start，其无论是不是蜡烛位置，其位置的盘子数前缀和都是start右侧最近的蜡烛之前全部的盘子和的数量；给定end，end对应位置的（从右往左）的前缀和都代表到end左侧最近的蜡烛之前的盘子数之和。两者相加，用总盘子数减去就是结果。
这里有一个点，为何不统一最后一个蜡烛之后的盘子数量呢？在实际操作操作中，如果start位置超过了最后一个蜡烛的位置，从正向前缀和和反向前缀和的相加结果来看，其都等于总的盘子数量。其结果等于“0”。所以不用特殊操作了。

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        dicofcandle = []
        the_sum = []
        cummulate = 0
        res = []
        for idx, char in enumerate(s):
            if char == '*':
                cummulate += 1
                the_sum.append(cummulate)
            else:
                dicofcandle.append(idx)
                the_sum.append(cummulate)
        
        
        for start, end in queries:
            if start in dicofcandle and end in dicofcandle:
                res.append(the_sum[end] - the_sum[start])
                continue
            #if start not in dicofcandle:
            realstart = bisect.bisect_left(dicofcandle, start)
            #else:
            #    realstart = start
            if end not in dicofcandle:
                realend = bisect.bisect_left(dicofcandle, end) - 1
            else:
                realend = bisect.bisect_left(dicofcandle, end)
            
            if the_sum[dicofcandle[realend]] - the_sum[dicofcandle[realstart]] < 0:
                numofplate = 0
            else:
                numofplate = the_sum[dicofcandle[realend]] - the_sum[dicofcandle[realstart]]
            
            res.append(numofplate)
        return res

接下来还是第二种办法吧。

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        dicofcandle = []
        the_sum = []
        cummulate = 0
        res = []
        for idx, char in enumerate(s):
            if char == '*':
                cummulate += 1
                the_sum.append(cummulate)
            else:
                dicofcandle.append(idx)
                the_sum.append(cummulate)
        
        for idx in range(len(dicofcandle) - 1, -1, -1):
            theindex = dicofcandle[idx]
            number = the_sum[theindex]
            theindex -= 1
            while theindex>= 0 and s[theindex] == '*':
                the_sum[theindex] = number
                theindex -= 1
        
        total = cummulate
        
        sum_reverse = []
        cummulate = 0
        dicofcandle2 = []
        s = s[::-1]
        for idx, char in enumerate(s):
            if char == '*':
                cummulate += 1
                sum_reverse.append(cummulate)
            else:
                dicofcandle2.append(idx)
                sum_reverse.append(cummulate)
        for idx in range(len(dicofcandle2) - 1, -1, -1):
            theindex = dicofcandle2[idx]
            number = sum_reverse[theindex]
            theindex -= 1
            while theindex>= 0 and s[theindex] == '*':
                sum_reverse[theindex] = number
                theindex -= 1
        sum_reverse = sum_reverse[::-1]
        print(sum_reverse)
        for start, end in queries:
            res.append(max(total - the_sum[start] - sum_reverse[end],0))
        return res   
#tc："***|**|*****|**||**|*"
#[[1,17],[4,5],[14,17],[5,11],[15,16]]

#左向右前缀和：[3, 3, 3, 3, 5, 5, 5, 10, 10, 10, 10, 10, 10, 12, 12, 12, 12, 14, 14, 14, 15]
#右向左前缀和[15, 14, 13, 12, 12, 12, 10, 10, 10, 10, 10, 10, 5, 5, 5, 3, 3, 3, 3, 1, 1]