5971. Minimum cost of buying candy at a discount

Title Description: give you \ (n \) the price of candy. For every candy at two prices, you can get a candy at no more than two prices. Ask how much it will cost at least to get all kinds of candy.

Idea: greedy, sort the candy prices from small to large, that is, the sum of all candy prices is \ (sum \), and then subtract the current candy price from \ (sum \) every three backwards.

Time complexity: \ (O(nlogn) \)

Reference code:

class Solution {
public:
    int minimumCost(vector<int>& 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. Count the number of hidden arrays

Title Description: there is an array \ (arr \) with a length of \ (n + 1 \), and now tell you the array differences composed of the difference of each adjacent element, where \ (differences_i = arr_i - arr_{i - 1} \;2 \leq i \leq n + 1 \). And tell you the range of elements of the array \ (arr \), that is \ (lower \ Leq arr_i \ Leq upper, 1 \ Leq I \ Leq n + 1 \). Let you calculate the number of arrays arr that meet the requirements.

Idea: obviously, for the first element, its range is \ ([lower, upper] \), let LR = lower and rs = upper. We traverse the differences array and update the range of the current element's value every time according to the difference. If the current range exceeds the given range, it will return 0, otherwise we will continue to simulate, and the final answer is rs - lr + 1.

Time complexity: \ (O(n) \)

Reference code:

class Solution {
public:
    int numberOfArrays(vector<int>& 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. The highest ranked K-sample items in the price range

Title Description: read the title yourself.

Idea: according to the meaning of the question, BFS can be used, and then the stored answers can be sorted according to the priority given by the question. Finally, the first k answers can be obtained and returned.

Time complexity: \ (O(n\times m + (n \times m) log(n\times m)) \) the former is the complexity of BFS and the latter is the worst complexity of sorting.

Reference code:

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<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
        vector<vector<int>>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<Node> q;
        q.push({start[0] , start[1] , 0});
        vector<vector<bool>>vis(n , vector<bool>(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<int>& a , const vector<int>& 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<vector<int>>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. Number of options for separated corridors

Title Description: there is a string \ (s \), which only contains s and P characters. You can divide the string into non empty substrings so that each substring contains exactly two s characters. Ask the number of segmentation schemes.

Idea: we only need to count the number of p characters in the middle of each two groups of s characters, and then multiply them all again and again according to the multiplication principle. For example, for ssppppss, there are 3 p characters in the middle of the first two groups of S and 2 p characters between the last two groups of S, so the final number of segmentation schemes is (3 + 1) * (2 + 1) = 12.

Note that the special judgment s is odd and less than two.

Time complexity: \ (O(n)\),\(n \) is the length of the string

Reference code:

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;
    }
};