leetcode70双周赛

竞赛链接

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

---

思路

模拟，用大根堆不断取，一次取三个，第三个不付钱

Code

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        priority_queue<int>ha;
        int sum=0;
        for(auto& i:cost)
            ha.push(i);
        while(ha.size()>=3){
            sum+=ha.top();
            ha.pop();
            sum+=ha.top();
            ha.pop();
            ha.pop();
        }
        while(ha.size()>0){
            int l=ha.top();
            sum+=l;
            ha.pop();
        }
        return sum;
    }
};

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

T2: 5972. 统计隐藏数组数目

---

思路

根据differences数组还原出原数组的最大基准增量和最小基准增量，就是把数组开头那个元素规定为0，利用differences是差值，加上前继可以还原出以0作为原数组开头时此位置数组的值，然后最大值最小值差值就是原数组会表达的范围状态，如果这个值大于upper - lower，说明给定的最大最小值范围没法覆盖原数组的表达范围，返回0即可；否则返回upper - (lower + max - min) + 1，可以等价的转化为(upper - lower) - (max - min) + 1就可以了。

Code

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) 
    {
        long long curmin = 0, curmax = 0, sum = 0;
        for (auto e : differences){
            sum += e;
            curmax = max(curmax, sum);
            curmin = min(curmin, sum);
        }
        if (curmax - curmin > upper - lower)
            return 0;

        return (upper - lower) - (curmax - curmin) + 1;
    }
};

复杂度分析

• 时间复杂度O(N)。
• 空间复杂度O(1)。

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

---

思路

BFS找出所有符合条件的物品，再按照题目要求排序取前 K 个即可。

Code

typedef struct node {
    int x;
    int y;
    int price;
    int dist;
}no;

class Solution {
public:
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& p, vector<int>& start, int k) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> ans;
        vector<vector<int>> isVisited(m, vector<int>(n));  // int isvist[100000][100000]  会爆栈
        vector<no> v;  //这里先用v统一存储，再弹出，如果这里直接用优先队列的话，每次插入新的数都要排序，所以会超时
        queue<pair<int, int>> q;
        isVisited[start[0]][start[1]] = true;
        q.push({start[0], start[1]});
        int dist = 0;
        while (q.size()) {
            int len = q.size();
            for (int i = 0; i < len; ++i) {
                auto cur = q.front();
                q.pop();
                int x = cur.first;
                int y = cur.second;
                if (grid[x][y] >= p[0] && grid[x][y] <= p[1]) {
                    v.push_back({x, y, grid[x][y], dist});
                }
                for (int i = 0; i < 4; ++i) {
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && isVisited[nx][ny] == 0 && grid[nx][ny] > 0) {
                        isVisited[nx][ny] = 1;
                        q.push({nx, ny});
                    }
                }
            }
            ++dist;
        }
        sort(v.begin(), v.end(), [&](auto &a, auto &b){
            if (a.dist == b.dist) {
                if (a.price == b.price) {
                    if (a.x == b.x) {
                        return a.y < b.y;
                    }
                    return a.x < b.x;
                }
                return a.price < b.price;
            }
            return a.dist < b.dist;
        });

        if (v.size() < k) {
            for (auto &node : v) {
                ans.push_back(vector<int>{node.x, node.y});
            }
            return ans;
        }
        for (int i = 0; i < k; ++i) {
            ans.push_back(vector<int>{v[i].x, v[i].y});
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(NMlog(NM))
• 空间复杂度：O(NM)

T4: 5974. 分隔长廊的方案数

---

思路

每两个座位放置一个屏风，对分隔点处的植物计数，然后累乘每个分隔点的植物即可。

Code

const int mod=1e9+7;

class Solution {
public:
    int numberOfWays(string cor) {
        long long cnt=0,sum=1;
        for(auto& i:cor){
            if(i=='S')
                cnt++;
        }
        if(cnt==0||cnt%2!=0)
            return 0;

        int n=cor.size();
        long long now=0,nowc=0;

        for(int i=0;i<n;++i){
            if(cor[i]=='S'){
                now++;
                if(now>2){
                   now=1;
                   sum%=mod;
                   sum*=nowc;
                   sum%=mod; 
                   nowc=0;
                }
            }
            if(now==2)
                nowc++;
        } 
        return sum%mod;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

个人总结

---

本次双周赛，t1正常模拟，t2解法想复杂了 直接裂开，t3码了半天因为二维数组爆栈问题卡死，t4的话到还挺简单的，不过前面浪费时间有点多，赛后2分钟才做出来😭