第 195 场周赛

Posted on | In , | |
Words count in article: 443 | Reading time ≈ 2

5448. 判断路径是否相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPathCrossing(string path) {
        int x = 0, y = 0;
        map<pair<int, int>, int> mp;
        mp[{0,0}] = 1;
        for(auto& c: path) {
            if(c == 'N') y++;
            else if(c == 'S') y--;
            else if(c == 'E') x++;
            else if(c == 'W') x--;
            if(mp[{x, y}]) return true;
            else mp[{x,y}] = 1;
        }
        return false;
    }
};

5449. 检查数组对是否可以被 k 整除

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
class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        map<int, int> mp;
        for(auto i: arr) {
            int m = i % k;
            if(m < 0) m += k;
            mp[m] ++;
        }
        if(mp[0] % 2 != 0) return false;
        if(k % 2 == 0) {
            for(int i=1; i<k/2; i++) {
                int j = k-i;
                if(mp[i] != mp[j]) return false;
            }
            if(mp[k/2] % 2 != 0) return false;
        } else {
            for(int i=1; i<=k/2; i++) {
                int j = k-i;
                if(mp[i] != mp[j]) return false;
            }
        }
        return true;
    }
};

5450. 满足条件的子序列数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        int maxn = 1e9+7;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int res = 0, pw[n];
        pw[0] = 1;
        for(int i=1; i<n; i++) pw[i] = (pw[i-1]*2) % maxn;
        for(int i=0, j=n-1; i<n; i++) {
            while(i<=j && nums[i]+nums[j] > target) j--;
            if(i > j) break;
            res = (res + pw[j-i]) % maxn;
        }
        return res;
    }
};

5451. 满足不等式的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef pair<int, int> PII;
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<PII> dq;
        dq.push_back({points[0][0], points[0][1] - points[0][0]});
        int ans = -2e9;
        for(int i = 1; i < points.size(); i ++) {
            
            while (dq.size() && points[i][0] - dq.front().first > k) dq.pop_front();
            if (dq.size()) ans = max(ans, dq.front().second + points[i][0] + points[i][1]);
            while (dq.size() && dq.back().second <= points[i][1] - points[i][0]) dq.pop_back();
            dq.push_back({points[i][0], points[i][1] - points[i][0]});
        }
        return ans;
    }
};
Donate? comment?