LeetCode第 70 场双周赛

5971. 打折购买糖果的最小开销

题目描述：给你\(n\)个糖果的价格，每买两种价格的糖果，可以获得一种不超过买的两种价格的糖果，问最少需要花费多少钱才能获得所有种类的糖果。

思路：贪心，将糖果价格从小到大排序，即所有糖果的价格和为\(sum\)，然后倒着每三个就从\(sum\)中减去当前糖果的价格。

时间复杂度：\(O(nlogn)\)

参考代码：

class Solution {
public:
    int minimumCost(vector& cost) {
        sort(cost.begin() , cost.end());
        int n = cost.size() , res = 0;
        for(int c : cost) res += c;
        for(int i = n - 3 ; i >= 0 ; i -= 3){
            res -= cost[i];   
        }
        return res;
    }
};

5972. 统计隐藏数组数目

题目描述：有一个数组\(arr\)，其长度为\(n + 1\),现在告诉你其每相邻元素的差值组成的数组differences，其中\(differences_i = arr_i - arr_{i - 1} \;2 \leq i \leq n + 1\)。并告诉你数组\(arr\)的元素的范围，即\(lower \leq arr_i \leq upper , 1 \leq i \leq n + 1\)。让你计算符合要求的数组arr的数量。

思路：显然对于第一个元素，其范围为\([lower , upper]\)，令lr = lower , rs = upper我们遍历differences数组，每次根据差值更新当前元素的值的范围，若当前范围超过了给定范围就返回0，否则一直模拟下去，最终答案为rs - lr + 1。

时间复杂度：\(O(n)\)

参考代码：

class Solution {
public:
    int numberOfArrays(vector& differences, int lower, int upper) {
        int lr = lower , rs = upper;
        for(auto diff : differences){
            int newlr = lr + diff, newrs = rs + diff;
            if(newlr > upper || newrs < lower) return 0;
            lr = max(newlr , lower);
            rs = min(newrs , upper);
        }
        return rs - lr + 1;
    }
};

5973. 价格范围内最高排名的 K 样物品

题目描述：自己看题目吧。

思路：根据题意BFS即可，然后将存储的答案按照题目给定的优先级排序，最终得到前k个的答案并返回即可。

时间复杂度：\(O(n\times m + (n \times m) log(n\times m))\) 前者是BFS的复杂度，后者是排序的最坏复杂度。

参考代码：

class Solution {
private:
    struct Node{
        int x , y , step;
        Node(int _x = 0, int _y = 0, int _step = 0):x(_x) , y(_y) , step(_step){}
    };    
public:
    vector> highestRankedKItems(vector>& grid, vector& pricing, vector& start, int k) {
        vector>res;
        int n = grid.size() , m = grid[0].size();
        const int xd[4] = {0 , 0 , 1 , -1};
        const int yd[4] = {1 , -1 , 0 , 0}; 
        int low = pricing[0] , up = pricing[1];
        queue q;
        q.push({start[0] , start[1] , 0});
        vector>vis(n , vector(m , false));
        vis[start[0]][start[1]] = true;
        while(!q.empty()){
            auto [x , y , step] = q.front();
            q.pop();
            if(grid[x][y] != 1 && grid[x][y] >= low && grid[x][y] <= up) res.push_back({step , grid[x][y] , x , y});
            for(int i = 0 ; i < 4 ; ++i){
                int dx = x + xd[i] , dy = y + yd[i];
                if(dx < 0 || dx >= n || dy < 0 || dy >= m || grid[dx][dy] == 0 || vis[dx][dy]) continue;
                vis[dx][dy] = true;
                q.push({dx , dy , step + 1});
            }
        }
        sort(res.begin(),res.end() , [&](const vector& a , const vector& b){
            if(a[0] != b[0]) return a[0] < b[0];
            if(a[1] != b[1]) return a[1] < b[1];
            if(a[2] != b[2]) return a[2] < b[2];
            return a[3] < b[3];
        });
        vector>ans;
        int len = res.size();
        for(int i = 0 ; i < min(k , len) ; ++i) ans.push_back({res[i][2] , res[i][3]});
        return ans;
    }
};

5974. 分隔长廊的方案数

题目描述：有一个字符串\(s\)，只含有s , p两种字符，让你将字符串分割成非空子串，使得每一个子串都含有恰好两个s字符，问分割方案数。

思路：我们只需要统计每两组s字符中间的p字符个数，然后根据乘法原理将其加一再全部乘起来即可。例如sspppssppss，对于前面两组s中间有3个p字符，对于后面两组s之间有2个p字符，故最终的分割方案数为(3 + 1) * (2 + 1) = 12种。

注意特判s为奇数和不足两个的情况。

时间复杂度：\(O(n)\),\(n\)为字符串长度

参考代码：

class Solution {
public:
    int numberOfWays(string s) {
        int cnt = 0;
        for(auto c : s) cnt += c == 'S';
        if((cnt & 1) || cnt < 2) return 0;
        int res = 1, ct = 1;
        cnt = 0;
        const int mod = 1e9 + 7;
        for(auto c : s){
            if(c == 'S'){
                if(cnt < 2) ++cnt;
                else{
                    res = 1ll * res * ct % mod;
                    ct = 1;
                    cnt = 1;
                }
            }
            else{
                if(cnt < 2) continue;
                else ++ct;
            }
        }
        return res;
    }
};