Leetcode第80场双周赛解题报告

这周的比赛，总体而言感觉比较水，但是状态下滑的厉害

6095. 强密码检验器 II

知识点：模拟
按照题意处理字符串即可

class Solution {
public:
    bool strongPasswordCheckerII(string password) {
        if(password.size()<8) return false;
        
        bool a = false,b = false,c = false,d = false;
        
        for(int i = 0;i < password.size();i++) {
            auto now = password[i];
            if(now >='a' && now <= 'z') a = true;
            if(now >='A' && now <= 'Z') b = true;
            if(now >='0' && now <= '9') c = true;
            //!@#$%^&*()-+
            if(now == '!'||now == '@'||now == '#'||now == '$'||now == '%'||now == '^'||now == '&'||now == '*'||
              now == '('||now == ')'||now == '-'||now == '+') d = true;
            if(i > 0 && password[i]==password[i-1]) return false;
        }
        return a&&b&&c&&d;
    }
};

6096. 咒语和药水的成功对数

知识点: 二分
首先将药水进行排序。
对于每个咒语：根据题意，只需要找到满足条件的最少药水量x，二分查找到>=x的下标，该下标及其之后的元素均能满足要求，而无需每次都进行查找，复杂度为$O(nlogn)$。

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potion, long long success) {
        vector<int> ans;
        sort(potion.begin(),potion.end());
        for(auto i : spells) {
            long long x  = success/i;
            while(x * i < success) x++;
            //cout << x << " ";
            auto y = lower_bound(potion.begin(),potion.end(),x);
            //cout << y - potion.begin() << endl;
            ans.push_back(potion.end()-y);
        }
        return ans;
    }
};

6097. 替换字符后匹配

知识点：哈希表
暴力遍历所有子串，按位进行匹配，可以使用二维数组（char的哈希表）对映射关系进行存储，每次查找复杂度为1，避免卡常。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
private:
    bool search(string &s,string &need,int pos, vector<vector<char>>& mappings) {
        for(int i = 0;i < need.size();i++){
            if(i+pos >= s.size()) return false;
            if(mappings[need[i]][s[i+pos]]==0) return false;
        }
        return true;
    }
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        bool flag = false;
        vector<vector<char>> mp(256,vector<char>(256,0));
        for(int i = 0;i < 256;i++) mp[i][i] = 1;
        for(auto i : mappings) {
            mp[i[0]][i[1]] = 1;
        }

        for(int i = 0;i < s.size();i++) {
            if(search(s,sub,i,mp)) return true;
        }
        return false;
    }
};

6098. 统计得分小于 K 的子数组数目

知识点：滑动窗口
因为要求是连续数组，所以自然考虑尝试使用滑动窗口解决这个问题，滑动窗口内部只需要维护大小即可，每次更改长度时，都要增加滑动窗口大小的总量。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long ans = 0;
        long long s = nums.size();
        long long l=0,r=0;
        long long now = 0;

        while(l < s && r < s) {
            now += nums[r++];
            long long len = r - l;
            while(l<r && now * len >= k) {
                now -= nums[l++];
                len = r - l;
            }
            ans += len;
        }
        return ans;
    }
};