Leetcode 2055. Plates Between Candles [Python]

本文主要是介绍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 = 0res = []for idx, char in enumerate(s):if char == '*':cummulate += 1the_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 = startif end not in dicofcandle:realend = bisect.bisect_left(dicofcandle, end) - 1else:realend = bisect.bisect_left(dicofcandle, end)if the_sum[dicofcandle[realend]] - the_sum[dicofcandle[realstart]] < 0:numofplate = 0else: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 = 0res = []for idx, char in enumerate(s):if char == '*':cummulate += 1the_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 -= 1while theindex>= 0 and s[theindex] == '*':the_sum[theindex] = numbertheindex -= 1total = cummulatesum_reverse = []cummulate = 0dicofcandle2 = []s = s[::-1]for idx, char in enumerate(s):if char == '*':cummulate += 1sum_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 -= 1while theindex>= 0 and s[theindex] == '*':sum_reverse[theindex] = numbertheindex -= 1sum_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]