第 186 场周赛

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

1422. 分割字符串的最大得分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxScore(string s) {
        int sum = 0;
        for(int i=0; i<s.size(); i++) {
            if(s[i] == '1') sum ++;
        }
        int res = 0;
        int count0 = 0;
        int count1 = 0;
        for(int i=0; i<s.size()-1; i++) {
            if(s[i] == '1') count1++;
            else count0++;
            res = max(res, count0 + (sum-count1));
        }
        return res;
    }
};

1423. 可获得的最大点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int sum = 0;
        for(auto c: cardPoints) sum += c;
        int mina = INT_MAX, temp = 0;
        int len = cardPoints.size()-k;
        for(int i=0; i<cardPoints.size(); i++) {
            temp += cardPoints[i];
            if(i >= len) temp -= cardPoints[i-len];
            if(i >= len-1) mina = min(mina, temp);
        }
        return sum - mina;
    }
};

1424. 对角线遍历 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        map<int, vector<int>> mp;
        for(int i=nums.size()-1; i>=0; i--) {
            for(int j=0; j<nums[i].size(); j++) {
                mp[i+j].push_back(nums[i][j]);
            }
        }
        vector<int> ans;
        for(auto m: mp) {
            for(auto a: m.second) {
                ans.push_back(a);
            }
        }
        return ans;
    }
};

1425. 带限制的子序列和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int ans = INT_MIN, n = nums.size();
        deque<int> q;
        vector<int> dp(n);
        for(int i=0; i<n; i++) {
            if(q.size() && i-q.front() > k) q.pop_front();
            dp[i] = max(0, (q.empty() ? 0: dp[q.front()])) + nums[i];
            while(q.size() && dp[q.back()] < dp[i]) {
                q.pop_back();
            }
            q.push_back(i);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
Donate? comment?