2055.蜡烛之间的盘子

链接：2055.蜡烛之间的盘子
难度：Medium
标签：数组、字符串、二分查找、前缀和
简介：请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

题解 1 - cpp

• 编辑时间：2022-03-08
• 执行用时：364ms
• 内存消耗：138.9MB
• 编程语言：cpp
• 解法介绍：前缀和，遍历存储每个点的前后蜡烛。

class Solution {
   public:
    typedef pair<int, int> node;
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.size(), prev = 0;
        vector<node> list;
        for (int i = 0; i < n; i++) {
            if (s[i] == '|') list.push_back(make_pair(i, prev));
            if (s[i] == '*') prev++;
        }
        vector<int> find_l(n), find_r(n);
        for (int i = 0, start = 0; i < n; i++) {
            find_l[i] = start;
            if (start < list.size() && i == list[start].first) start++;
        }
        for (int i = n - 1, start = list.size() - 1; i >= 0; i--) {
            find_r[i] = start;
            if (start > -1 && i == list[start].first) start--;
        }
        vector<int> ans;
        ans.reserve(queries.size());
        for (auto& query : queries) {
            int l = find_l[query[0]], r = find_r[query[1]], res;
            if (l == list.size() || r == -1 || list[l].first > query[1] ||
                l == r)
                res = 0;
            else
                res = list[r].second - list[l].second;
            ans.push_back(res);
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-03-08
• 执行用时：380ms
• 内存消耗：135.3MB
• 编程语言：cpp
• 解法介绍：前缀和，二分。

class Solution {
   public:
    typedef pair<int, int> node;
    vector<node> list;
    int n;
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        n = s.size();
        int prev = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '|') list.push_back(make_pair(i, prev));
            if (s[i] == '*') prev++;
        }
        vector<int> ans;
        ans.reserve(queries.size());
        for (auto& query : queries) {
            int l = bs_l(query[0]), r = bs_r(query[1]), res;
            if (l == list.size() || r == -1 || list[l].first > query[1] ||
                l == r)
                res = 0;
            else
                res = list[r].second - list[l].second;
            ans.push_back(res);
        }
        return ans;
    }
    int bs_l(int idx) {
        int l = 0, r = list.size(), m;
        while (l < r) {
            m = (l + r) >> 1;
            if (list[m].first >= idx)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
    int bs_r(int idx) {
        int l = -1, r = list.size() - 1, m;
        while (l < r) {
            m = (l + r + 1) >> 1;
            if (list[m].first <= idx)
                l = m;
            else
                r = m - 1;
        }
        return l;
    }
};