上周的双周赛~

还是 3 题选手，这次周赛的题好像也简单了一点...

2299. Strong Password Checker II

Analysis

思路很直接，判断字符串是否符合要求即可。

Code

这是当时提交通过的代码：

class Solution {
public:
    bool strongPasswordCheckerII(string password) {
        string ht = "!@#$%^&*()-+";
        int n = password.size();
        if(n < 8) return false;
        bool lower = false, upper = false, num = false, spec = false, consective = false;
        for(int i = 0; i < n; i++) {
            if(isupper(password[i])) upper = true;
            if(islower(password[i])) lower = true;
            if(isdigit(password[i])) num = true;
            if(ht.find(password[i]) != string::npos) spec = true;
            if(i != 0 && password[i] == password[i - 1]) consective = true;
        }
        return lower && upper && num && spec && !consective;
    }
};

可惜的是，一开始用的是if-else if导致 WA 了一次。其实只要将是否出现连续字符单独拿出来判断就可以了。
实际上也可以用二进制位来取代bool变量：

class Solution {
public:
    bool strongPasswordCheckerII(string password) {
        int n = password.size();
        if(n < 8) return false;
        int flag = 0;
        for(int i = 0; i < n; i++) {
            if(i > 0 && password[i] == password[i - 1]) return false;
            if(isupper(password[i])) flag |= 1;
            else if(islower(password[i])) flag |= 2;
            else if(isdigit(password[i])) flag |= 4;
            else flag |= 8;
        }
        return flag == 15;
    }
};

这种技巧会被用在状态压缩等其他高级解法中。

2300. Successful Pairs of Spells and Potions

Analysis

简单来讲，这个题就是在算笛卡尔积，然后统计对应的符合条件的结果即可。如果直接暴力，复杂度是 $O(n^2)$，数量级在 $10^{10}$，肯定会超时。为了避免超时，就不能直接算笛卡尔积，可以先对 pairs 进行排序，然后遍历 spells 时，二分查找 pairs 中第一个满足条件的解，这样就可以直接得到符合条件的组合数目了。

Code

这是当时提交通过的代码：

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = spells.size();
        vector<int> ans(n);
        sort(potions.begin(), potions.end());
        for(int i = 0; i < n; i++) {
            long long tmp = (success % spells[i] == 0 ? success / spells[i] : success / spells[i] + 1);
            ans[i] = potions.end() - lower_bound(potions.begin(), potions.end(), tmp);
        }
        return ans;
    }
};

这个题一开始也 WA 了一次，原因是 tmp 用的int，没有考虑到 spells 中的数为 1，而 success 为超出int范围的情况。实际上，当时比赛的时候，其实一看到 WA 就反应过来是 tmp 没用long long的问题。而且，出错的那个用例正好是很长的那个，一看就知道是最后专门用来卡边界的。但是，自己还是死死的盯着输出和预期结果很久，浪费了不少时间😐。
实际上，上面的这段代码是向上取整的思路。对于正整数而言，$xy \geqslant success$ 等价于 $y \geqslant \lceil \frac {success} x \rceil$，也等价于 $ y > \lfloor \frac {success - 1} x \rfloor$。
那么，上面的代码可以改成：

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = spells.size();
        vector<int> ans(n);
        sort(potions.begin(), potions.end());
        for(int i = 0; i < n; i++) {
            ans[i] = potions.end() - upper_bound(potions.begin(), potions.end(), (success - 1) / spells[i]);
        }
        return ans;
    }
};

2302. Count Subarrays With Score Less Than K

Analysis

这是第四个题，但是第三个提交的题。为什么第三个提交呢？因为差不多是原题...😂
类似的题是：713. Subarray Product Less Than K。
所以这个题的解法也很多，当时的思路是滑动窗口 + 前缀和的思路。

Code

这是当时提交通过的代码：

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long ans = 0, sum = 0;
        int n = nums.size();
        int left = 0, right = 0;
        while(right < n) {
            sum += nums[right];
            long long product = sum * (right - left + 1);
            while(left <= right && product >= k) {
                sum -= nums[left];
                left++;
                product = sum * (right - left + 1);
            }
            ans += right - left + 1;
            right++;
        }
        return ans;
    }
};

与其说是前缀和的思路，倒不如说是在模拟，不过也相差无几。