蜡烛之间的盘子-一一网

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

一、题目：

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 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 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。
复制代码

二、题解：

1.解读
对于queries数组的每一个区间，需要找到区间左边界到右边界之间对应在字符串s的区间，然后在这个区间的左右两边开始相向找到的第一个'|'字符又为一个区间，统计这个区间内的'*'字符就是该次查询的盘子数。

方法一
queries数组每个查询区间为querie=[i, j]，querie会对应s字符串内的一个子字符串，首先是需要找到在位置i处右边最近的一个'|'字符下标L和位置j处左边最近的一个'|'字符下标R，然后统计下标L到下标R直接的'*'字符数就是盘子数。如果这样遍历查询的话可能会有很多重复性查找，那么我们可以预先找出每个下标最近的'|'字符位置，这样可以快速根据下标获取最近的蜡烛位置。具体的定义left数组和right数组，left[i]就表示在字符串下标i处左边范围内离i最近的一个'|'字符的下标（即记录字符串s中的每个位置的左边最近的蜡烛位置），right[i]就表示在字符串下标i处右边范围内离|字符最近的一个下标（即记录字符串s中每个位置的右边最近的蜡烛位置），如果没有最近的'|'字符那我们就用-1来表示这里找不到最近的蜡烛了，如此在区间querie的边界查询最近蜡烛数时间复杂度就为O(1)了。同样的为了更快的计算盘子数我们也可以记录下每个下标前盘子的数量，定义preSum数组，preSum[i]表示字符串s的下标i处之前（包括i）的'*'字符总数，如果要计算某个区间[m, n]内的盘子数就只需获取preSum[n] - preSum[m]值即可。这时我们就可以再遍历querie区间去查询盘子数了，对于左区间我们到right查询最近的蜡烛位置R，对于右区间我们到left找到最近的蜡烛位置L。判断L和R不为-1即都有最近的蜡烛并且L >= R左边的蜡烛得在右边才行，然后就可以通过preSum[L] - preSum[R]获取当前querie区间内的盘子数量了。

三、代码：

方法一
Java代码

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int len = s.length();
        // 记录位置下标i前所有的盘子总数
        int[] preSum = new int[len];
        // 记录位置下标i左边最近的蜡烛位置
        int[] left = new int[len];
        // 记录位置下标i右边最近的蜡烛位置
        int[] right = new int[len];
        // 空间换时间
        char[] chars = s.toCharArray();
        for (int i = 0, p = 0; i < len; i++) {
            preSum[i] = chars[i] == '*' ? ++p : p;
        }
        for (int i = 0, p = -1; i < len; i++) {
            left[i] = chars[i] == '|' ? p = i : p;
        }
        for (int i = len - 1, p = -1; i >= 0; i--) {
            right[i] = chars[i] == '|' ? p = i : p;
        }

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = left[queries[i][1]];
            int r = right[queries[i][0]];
            if (r != -1 && l >= r) {
                answer[i] = preSum[l] - preSum[r];
            }
        }
        return answer;
    }
}
复制代码