[数据结构与算法]LeetCode-5:蜡烛之间的盘子

原题为：

具体解题思路如下：
最好的情况：
1.如果子字符串两端都是蜡烛，那么这个子字符串中的盘子数量为这个子字符串的长度减去这个子字符串蜡烛的数量
最坏的情况：
2.如果字符串两端中有一端为蜡烛，另一端为盘子；或者两端都为盘子。那么首先需要找到这个子字符串中最靠近两端的蜡烛的位置(并且left<right,left为子字符串中最靠近左端的蜡烛的位置，right为子字符串中最靠近右端的蜡烛的位置)，然后再重复第1中情况的操作即可。为了便于操作，减少时间复杂度，顺利提交代码，定义三个列表list_1,list_2,list_3
其中list_1[i]代表字符串s从下标0到i之间蜡烛数量(包括两端)
list_2[i]代表字符串s下标为i右边最靠近它的蜡烛位置
list_3[i]代表字符串s下标为i左边最靠近它的蜡烛位置
利用上述list_1,list_2,list_3中的数据，遍历列表queries中的值，即可求得最终的值

参考代码为：

class Solution(object):
    def platesBetweenCandles(self, s, queries):
        """
        :type s: str
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        n = len(s)
        list_1 = [0] * n
        list_2 = [0] * n  # 从后往前
        list_3 = [0] * n  # 从前往后
        if s[0] == '|':
            list_1[0] = 1
            list_3[0] = 0

        if s[n-1] == '|':
            list_2[n-1] = n-1

        for i in range(1, n):
            if s[i] == '|':
                list_1[i] = list_1[i - 1] + 1
            else:
                list_1[i] = list_1[i - 1]

            if s[i] == '|':
                list_3[i] = i
            else:
                list_3[i] = list_3[i-1]

        for i in range(n-2,-1,-1):
            if s[i] == '|':
                list_2[i] = i
            else:
                list_2[i] = list_2[i + 1]

        out = []
        for list_4 in queries:
            start = list_4[0]
            end = list_4[1]
            if start == end:
                out.append(0)
                continue

            index_1 = list_2[start]
            index_2 = list_3[end]
            if index_1 >=index_2:
                out.append(0)
            else:
                out.append(index_2-index_1+1-(list_1[index_2]-list_1[index_1]+1))

        return out

执行结果：