5

力扣每日一题——蜡烛之间的盘子

 2 years ago
source link: https://unique-pure.github.io/2022/03/08/suan-fa-xue-xi-ji-hua/mei-ri-yi-ti/20220308/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

1 题目描述

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti]$表示 子字符串 s[lefti...righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。比方说，s = "||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||***\**\***|" 。子字符串中在两支蜡烛之间的盘子数目为 2

子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

  • 3 <= s.length <= 105
  • s 只包含字符 '*' 和 '|' 。
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= lefti <= righti < s.length

2 预处理+前缀和O(n + q)

对于每个询问[l,r][l,r]，我们只需要找到给定区间内最左侧和最右侧的两个蜡烛，这样两个蜡烛之间的所有盘子是一定符合条件的。对于蜡烛的寻找，我们可以预处理得到每个点左侧的第一个蜡烛和右侧的第一个蜡烛，这样区间左端点的右侧第一个蜡烛即为区间最左侧的蜡烛，同理，区间右端点的左侧第一个蜡烛即为区间最右侧的蜡烛。

对于区间盘子数量的计算，我们很容易想到前缀和，如果求出了盘子数量的前缀和prefixSum，那么对于找到的两个蜡烛的位置分别为x和y，则两位置之间的盘子数量为prefixSum[y] - prefixSum[x-1]。至此可解决此题，在一些细节处理方面，我们注意某个位置的左侧或右侧是可能不存在蜡烛的，此时我们将对应数组的值为-1，故当x==-1||y==-1||x>=y的时候，都是不存在满足条件的盘子。 同时由于x位置是蜡烛，所以盘子数量可以表示为prefixSum[y] - prefixSum[x]，这样可以防止x=0时数组越界

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int len = s.size();
        vector<int> prefixSum(len), left(len), right(len), res;
        for (int i = 0, sum = 0; i < len; ++ i ) {
            if (s[i] == '*') {
                ++ sum;
            }
            prefixSum[i] = sum;
        }
        for (int i = 0, l = -1; i < len; ++ i ) {
            if (s[i] == '|') {
                l = i;
            }
            left[i] = l;
        }
        for (int i = len - 1, r = -1; i >= 0; -- i ) {
            if (s[i] == '|') {
                r = i;
            } 
            right[i] = r;
        }
        for (auto &query : queries) {
            int x = right[query[0]], y = left[query[1]];
            res.push_back((x == -1 || y == -1 || x >= y) ? 0 : prefixSum[y] - prefixSum[x]);
        }
        return res;
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK