Leetcode第 309 场周赛 补打

Leetcode 第309场周赛

没统计时间，不过看做题情况。1，4对我来说比较好写。2，3不怎么会处理

1. 开一个数组记录字符的位置
2. 动归/记忆化搜索。确实有点像斐波那契。状态是dp[i][j] = (dp[i-1][j-1],dp[i-1][j+1])%mod。 i表示0-k的第i步, j表示坐标。
3. 位运算。还好是连续的能暴力。暴力的话最多也只是31*1e5。因为要&为0，一定是每一位不同。int最大只是2^31. 31个不同位（可以想想不连续怎么求）
4. 堆排序。使用会议室的优先条件：空闲的编号小的优先；都不空闲先空闲的优先（结束早==时间小 的优先）。对于第1个条件，需要预先将 会议开始时间> 会议室中会议结束时间 的会议室全都置为 会议开始时间。

priority_queue排序的模板：参考链接

2399. 检查相同字母间的距离

class Solution {
public:
    bool checkDistances(string s, vector<int>& distance) {
        int val = 0;
        vector<int> vist(26,-1);
        for(int i=0;i<s.size();i++) {
            if(vist[s[i]-'a']==-1) vist[s[i]-'a'] = i;
            else {
                int dis = i-vist[s[i]-'a']-1;
                if(distance[s[i]-'a']!=dis) return false;
            } 
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2400. 恰好移动 k 步到达某一位置的方法数目

class Solution {
public:
    const int mod = 1e9+7;
    int numberOfWays(int startPos, int endPos, int k) {
        vector<vector<int>> dp(k+1,vector<int>(4000));
        startPos += 1010;
        endPos += 1010; 
        dp[0][startPos] = 1;
        for(int i=1;i<=k;i++) {
            for(int j=startPos-k; j<=startPos+k; j++) {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%mod;
            } 
        }
        return dp[k][endPos];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2401. 最长优雅子数组

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int ans = 1;
        for(int i=0; i<nums.size(); i++) {
            int j = i, sum = 0;
            while(j>=0 && (sum & nums[j]) == 0) 
                sum |= nums[j--]; 
            ans = max(i-j, ans);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

2402. 会议室 III

class Solution {
public:
    struct cmp_min{
        template <typename T, typename U>
        bool operator()(T const &left, U const &right) {
            if(left.second==right.second) return left.first > right.first;
            return left.second > right.second; //小顶
        }
    };
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(),meetings.end(),[](vector<int> &x,vector<int> &y){return x[0]<y[0];}) ;
        priority_queue<pair<int,long long>,vector<pair<int,long long>>,cmp_min> pq;
        vector<int> used(n,0);
        for(int i=0;i<n;i++) pq.emplace(i,0);
        for(auto &meet: meetings) {
            while(pq.top().second < meet[0]) { //为了空闲的可以编号排序
                auto x = pq.top(); pq.pop();
                pq.emplace(x.first,meet[0]);
            }
            auto x = pq.top(); pq.pop();
            // cout<
            used[x.first] += 1;
            pq.emplace(x.first,x.second+meet[1]-meet[0]);
        }
        int ans = 0;
        for(int i=0;i<n;i++) if(used[ans]<used[i]) ans = i;
        return ans; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29