leetcode contest biweekly 80

官方难道是手速场，第三题想了半天也没想到什么好办法，直接暴力竟然过了，不知道是什么出题逻辑。

6095. 强密码检验器 II

题目

如果一个密码满足以下所有条件，我们称它是一个强密码：

它有至少 8 个字符。
至少包含一个小写英文字母。
至少包含一个大写英文字母。
至少包含一个数字。
至少包含一个特殊字符。特殊字符为："!@#$%^&*()-+" 中的一个。
它不包含 2 个连续相同的字符（比方说 "aab" 不符合该条件，但是 "aba" 符合该条件）。
给你一个字符串 password ，如果它是一个强密码，返回 true，否则返回 false 。

示例 1：

输入：password = "IloveLe3tcode!"
输出：true
解释：密码满足所有的要求，所以我们返回 true 。

示例 2：

输入：password = "Me+You--IsMyDream"
输出：false
解释：密码不包含数字，且包含 2 个连续相同的字符。所以我们返回 false 。

示例 3：

输入：password = "1aB!"
输出：false
解释：密码不符合长度要求。所以我们返回 false 。

提示：

1 <= password.length <= 100
password 包含字母，数字和 "!@#$%^&*()-+" 这些特殊字符。

地址

https://leetcode.cn/contest/biweekly-contest-80/problems/strong-password-checker-ii/

题意

直接模拟

思路

按照题目逻辑模拟即可。
复杂度分析：

时间复杂度：$O(n)$, 其中 $n$ 为字符串的长度。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    bool strongPasswordCheckerII(string password) {
        if (password.size() < 8) {
            return false;
        }
        
        bool hasBig = false;
        bool hasSmall = false;
        bool hasDigit = false;
        bool hasSpecial = false;
        bool hasSame = false;
        set<char> cnt;
        string special = "!@#$%^&*()-+";
        for (auto c : special) {
            cnt.emplace(c);
        }
        for (int i = 0; i < password.size(); i++) {
            if(password[i] >= 'A' && password[i] <= 'Z') {
                hasBig = true;
            }
            if(password[i] >= 'a' && password[i] <= 'z') {
                hasSmall = true;
            }
            if(password[i] >= '0' && password[i] <= '9') {
                hasDigit = true;
            }
            if(cnt.count(password[i])) {
                hasSpecial = true;
            }
            if(i > 0 && password[i] == password[i-1]){
                hasSame = true;
            }
        }
        if (hasBig && hasSmall && hasDigit && hasSpecial && (!hasSame)) {
            return true;
        } else {
            return false;
        }
    }
};

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

题目

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度相乘如果大于等于 success ，那么它们视为一对成功的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的药水数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

提示：

n == spells.length
m == potions.length
1 <= n, m <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010

地址

https://leetcode.cn/contest/biweekly-contest-80/problems/successful-pairs-of-spells-and-potions/

题意

二分查找

思路

直接对potions进行排序，每次遍历 $\textit{spells}[i]$, 找到 $\textit{potions}$ 中所有大于等于 $\lceil \dfrac{success}{spells} \rceil$ 的数目即可，我们可以用二分查找完成即可。
复杂度分析：

时间复杂度：$O((m + n) \times \log n)$，其中 $m$ 为数组 $\textit{spells}$ 的长度，其中 $n$ 为数组 $\textit{potions}$ 的长度。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> ans;
        sort(potions.begin(), potions.end());
        for (auto x : spells) {
            long long curr =  (success + x - 1) / x;
            long long y = potions.end() - lower_bound(potions.begin(), potions.end(), curr);
            ans.emplace_back(y);
        }
        return ans;
    }
};

6097. 替换字符后匹配

题目

给你两个字符串 s 和 sub 。同时给你一个二维字符数组 mappings ，其中 mappings[i] = [oldi, newi] 表示你可以替换 sub 中任意数目的 oldi 个字符，替换成 newi 。sub 中每个字符不能被替换超过一次。

如果使用 mappings 替换 0 个或者若干个字符，可以将 sub 变成 s 的一个子字符串，请你返回 true，否则返回 false 。
一个子字符串是字符串中连续非空的字符序列。

示例 1：

输入：s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
输出：true
解释：将 sub 中第一个 'e' 用 '3' 替换，将 't' 用 '7' 替换。
现在 sub = "l3e7" ，它是 s 的子字符串，所以我们返回 true 。

示例 2：

输入：s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
输出：false
解释：字符串 "f00l" 不是 s 的子串且没有可以进行的修改。
注意我们不能用 'o' 替换 '0' 。

示例 3：

输入：s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
输出：true
解释：将 sub 里第一个和第二个 'e' 用 '3' 替换，用 'b' 替换 sub 里的 'd' 。
得到 sub = "l33tb" ，它是 s 的子字符串，所以我们返回 true 。

提示：

1 <= sub.length <= s.length <= 5000
0 <= mappings.length <= 1000
mappings[i].length == 2
oldi != newi
s 和 sub 只包含大写和小写英文字母和数字。
oldi 和 newi 是大写、小写字母或者是个数字。

地址

https://leetcode.cn/contest/biweekly-contest-80/problems/match-substring-after-replacement/

题意

暴力循环

思路

想了半天没有想到这个题目有什么好的解法，只能每次遍历所有可能的组合，遍历两个字符串中所有的组合，找到组合中的不同的字符变换，查找该字符映射是否能够完成即可，反正莫名其妙就过了，感觉解法应该不对，时间复杂度应该不需要这么高。
复杂度分析：

时间复杂度：$O(m \times n)$, 其中 $m,n$ 为字符串 $s, \textit{sub}$ 的长度。
空间复杂度：$O(k)$，其中 $k$ 为 $\textit{mappings}$ 的长度。

代码

class Solution {
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        int m = s.size();
        int n = sub.size();
        unordered_set<int> cnt;
        for (auto & v : mappings) {
            cnt.emplace(v[0] * 256 + v[1]);
        }
        for (int i = n - 1; i < m; i++) {
            bool valid = true;
            for (int j = n - 1; j >= 0; j--) {
                int x = n - 1 - j;
                if (s[i-x] != sub[j]) {
                    int y = sub[j] * 256 + s[i-x];
                    if (!cnt.count(y)){
                        valid = false;
                        break;
                    }
                }
            }
            if(valid){
                return true;
            }
        }
        return false;
    }
};

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

题目

一个数字的分数定义为数组之和乘以数组的长度。

比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。
给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数严格小于 k 的非空整数子数组数目。

子数组是数组中的一个连续元素序列。

示例 1：

输入：nums = [2,1,4,3,5], k = 10
输出：6
解释：
有 6 个子数组的分数小于 10 ：
- [2] 分数为 2 * 1 = 2 。
- [1] 分数为 1 * 1 = 1 。
- [4] 分数为 4 * 1 = 4 。
- [3] 分数为 3 * 1 = 3 。 
- [5] 分数为 5 * 1 = 5 。
- [2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。

示例 2：

输入：nums = [1,1,1], k = 5
输出：5
解释：
除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 1015

地址

https://leetcode.cn/contest/biweekly-contest-80/problems/count-subarrays-with-score-less-than-k/

题意

二分查找

思路

这个题目感觉只能算是中等难度题目，不晓得为啥是hard级别。我们可以每次枚举以 $nums[i]$ 为结尾的子数组所有构成的最长符合要求的子数组。我们用二分查找枚举子数组的起点 $j$，我们可以知道如果当 $(i - j + 1) * (sum[i] - sum[j - 1]) \ge k$ 时，此时则我们应当增加 $j$, 否则减少 $j$。知道我们找到最大的 $j$ 即可，此时满足要求的子数组一共有 $i - j + 1$ 个，我们依次求出符合满足每个元素构成的子数组的数目，然后累加即可。
复杂度分析：

时间复杂度：$n \log n$，其中 $n$ 表示数组的长度。每次枚举时需要进行二分查找。
空间复杂度：$O(n)$, 其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        int n = nums.size();
        vector<long long> sum(n + 1);
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
        for (int i = 1; i <= n; i++) {
            int l = 0;
            int r = i;
            int last = i;
            while (l <= r) {
                int mid = (l + r) / 2;
                long long curr = (sum[i] - sum[mid]) * (i - mid);
                if (curr >= k) {
                    l = mid + 1; 
                } else {
                    last = mid;
                    r = mid - 1;
                }
            }
            ans += i - last;
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode contest biweekly 297 leetcode contest 295 →

扫描二维码，分享此文章