每日算法刷题Day39 6.26:leetcode前缀和2道题，用时1h20min

8. 2055.蜡烛之间的盘子(中等,学习替换查询区间)

2055. 蜡烛之间的盘子 - 力扣（LeetCode）

思想

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

• 比方说，s = "||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||**_**_**|" 。子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。
  请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。
  2.这题能想到用前缀和，但是不能简单地计算[querie[0],querie[1]]的区间和，因为|*|*|例子中[0,3]为|*|*的有效*只有1个，而如果按照简单前缀和的逻辑答案为2，所以这个区间不对，要更换更小的区间。因为是考虑两个蜡烛内的盘子数，所以可以左端点querie[0]找它右边最近的蜡烛位置,右端点找它左边最近的蜡烛位置，从而替换原始查找区间,变成[rightId[querie[0]],leftId[querie[1]]],而找左边最近的蜡烛位置可以在遍历时判断赋值更新

代码

c++:

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> sum(n + 1, 0);
        vector<int> leftId(n);  // 左边最近蜡烛位置
        vector<int> rightId(n); // 右边最近蜡烛位置
        sum[0] = 0;
        int preId = -1;
        for (int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i];
            if (s[i] == '|')
                preId = i; // 边枚举边更新
            else
                ++sum[i + 1];
            leftId[i] = preId; // 边枚举边赋值
        }
        int lastId = n;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == '|')
                lastId = i;
            rightId[i] = lastId;
        }
        vector<int> res;
        for (auto& querie : queries) {
            // 用[rightId[querie[0]],leftId[querie[1]]]来替代[querie[0],querie[1]]区间
            int left = rightId[querie[0]], right = leftId[querie[1]];
            if (left < right)
                res.emplace_back(sum[right + 1] - sum[left]);
            else
                res.emplace_back(0);
        }
        return res;
    }
};

9. 1744.你能在你最喜欢的那天吃到你最喜欢的糖果吗?(中等,想法没错，范围再考虑清楚)

1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？ - 力扣（LeetCode）

思想

1.给你一个下标从 0 开始的正整数数组 candiesCount ，其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。
你按照如下规则进行一场游戏：

• 你从第 **0** 天开始吃糖果。
• 你在吃完 所有 第 i - 1 类糖果之前，不能 吃任何一颗第 i 类糖果。
• 在吃完所有糖果之前，你必须每天 至少 吃 一颗 糖果。
  请你构建一个布尔型数组 answer ，用以给出 queries 中每一项的对应答案。此数组满足：
• answer.length == queries.length 。answer[i] 是 queries[i] 的答案。
• answer[i] 为 true 的条件是：在每天吃 不超过 dailyCapi 颗糖果的前提下，你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果；否则 answer[i] 为 false 。
  注意，只要满足上面 3 条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。
  请你返回得到的数组 answer 。
  2.因为每个查询是独立的，且每个查询得到一个吃的糖果范围:[1*(favoriteDayi+1),dailyCapi*(favoriteDayi+1)](注意从0开始，且那一天也要算上，所以要加1，考虑清楚),而要吃到第favoriteTypei糖果的范围为[s[favoriteTypei-1+1]+1,s[favoriteTypei+1](因为定义的前缀和是要加上1的),这边有两个细节要考虑清楚才不会出错.两个区间有交集则说明可以

代码

c++:

class Solution {
public:
    vector<bool> canEat(vector<int>& candiesCount,
                        vector<vector<int>>& queries) {
        int n = candiesCount.size();
        vector<long long> s(n + 2, 0);
        s[0] = 0;
        s[n + 1] = LONG_MAX;
        for (int i = 0; i < n; ++i)
            s[i + 1] = s[i] + candiesCount[i];
        vector<bool> res;
        for (auto& querie : queries) {
            // day要+1，把那天吃的糖果也考虑到,所以吃的糖果范围为[1*day,cap*day]
            int type = querie[0], day = querie[1] + 1, cap = querie[2];
            // type类糖果范围为:(s[type-1]+1,s[type]),但是s还要加个1
            if ((1LL * cap * day < s[type - 1 + 1] + 1) ||
                (1LL * 1 * day > s[type + 1]))
                res.emplace_back(false);
            else
                res.emplace_back(true);
        }
        return res;
    }
};