记录 LeetCode 第 80 场双周赛

本次周赛是参加 Leetcode 周赛以来第一次AK！心情非常激动！

战局详情

排名	用户名	得分	完成时间	题目1（3）	题目2（4）	题目3（6）	题目4（6）
734 / 3949	Juruoer	19	1:25:10	0:08:34 1	0:21:50	1:20:10	0:57:41

题目及解答

• 题目1
• 题目2
• 题目3
• 题目4

强密码检验器 II

6095. 强密码检验器 II

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

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

提示：

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

示例一：

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

示例二：

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

示例三：

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

解决方案：

模拟：

按题意模拟即可。

代码：

class Solution
{
public:
    bool strongPasswordCheckerII(string password)
    {
        if (password.size() < 8) // 密码太短
            return false;
        bool haveNum, haveTes, haveBig, haveLow;
        char c = ' ';
        haveBig = haveLow = haveNum = haveTes = false;
        for (int i = 0; i < password.size(); ++i)
        {
            if(c == password[i]) // 连续两个字符相同
                return false;
            c = password[i];
            if(isdigit(c)) // 存在数字
                haveNum = true;
            else if(islower(c)) // 存在小写字母
                haveLow = true;
            else if(isupper(c)) // 存在大写字母
                haveBig = true;
            else // 存在特殊字符
                haveTes = true;
        }
        return haveBig && haveLow && haveNum && haveTes;
    }
};

时间复杂度为：$O(n)$ ；空间复杂度为：$O(1)$ 。其中 n 为 password 的长度。

咒语和药水的成功对数

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

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

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

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

提示：

• n == spells.length
• m == potions.length
• 1 <= n, m <= 1e5
• 1 <= spells[i], potions[i] <= 1e5
• 1 <= success <= 1e10

示例一：

输入：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] 。

示例二：

输入：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] 。

解决方案：

二分查找：

对于 spells 中的每个咒语，在 potions 中找到能与其组合成功的药水的数量。

我们可以将药水按照能量强度从小到大排序，然后使用二分查找找到能与当前咒语组合成功的能量强度最小的药水，设其排序后的下标为 idx，idx 的值也即不能与当前咒语组合的药水数量，则能与当前咒语组合成功的药水数量为 n - idx 。

代码：

class Solution
{
public:
    vector<int> successfulPairs(vector<int> &spells, vector<int> &potions, long long success)
    {
        sort(potions.begin(), potions.end());

        int l, r, mid, n = potions.size();
        long long t;
        vector<int> rst;

        for (int spell : spells)
        {
            l = 0;
            r = n - 1;
            // t 即能与 spell 组合成功的最小能量强度
            t = success / spell + (success % spell != 0);
            // 找到 potions 中大于等于 t 的值的个数
            while(l <= r)
            {
                mid = (l + r) >> 1;
                if (potions[mid] >= t)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            // 此时 l 即能与当前咒语组合成功的能量强度最小的药水的下标 idx
            rst.push_back(n - l);
        }
        return rst;
    }
};

时间复杂度为：$O(n \log m)$ ；空间复杂度为：$O(n)$ 。其中 n 表示 spells 的长度，m 表示 potions 的长度。

替换字符后匹配

6097. 替换字符后匹配

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

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

一个 子字符串 是字符串中连续非空的字符序列。

提示：

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

示例一：

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

示例二：

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

示例三：

输入：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 。

解决方案：

暴力穷举：

遍历 s 中的所有与 sub 长度相等的子字符串，并判断是否可以由 sub 变换而来。

代码：

class Solution
{
public:
    bool matchReplacement(string s, string sub, vector<vector<char>> &mappings)
    {
        int n = s.length();
        int m = sub.length();
        int i, j;
        // canTo[i][j] 表示 (char)i 能否转变为 (char)j
        bool canTo[128][128];

        memset(canTo, false, sizeof(canTo));
		
        // 记录下 mappings 中所有的转变
        for(auto map : mappings)
            canTo[map[0]][map[1]] = true;

        // 每个字符都可以转变为它自己
        for (i = 0; i < 128; ++i)
            canTo[i][i] = true;
        
        string temp;

        // 遍历 s 的所有长度为 m 的子字符串
        for (i = 0; i <= n - m; ++i)
        {
            temp = s.substr(i, m);
            // 判断子字符串 temp 能否由 sub 转变而来
            for (j = 0; j < m; ++j)
            {
                if (!canTo[sub[j]][temp[j]])
                    break;
            }
            if(j == m) // sub 成功转变为 temp
                return true;
        }

        return false;
    }
};

时间复杂度为：$O(c + (n - m) * m)$；额外空间为 128 * 128 的 bool 型数组，空间复杂度为：$O(1)$。其中 n 表示 s 的长度，m 表示 sub 的长度，c 表示 mapping 的长度。

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

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

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

• 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。

给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目 。

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

提示：

• 1 <= nums.length <= 1e5
• 1 <= nums[i] <= 1e5
• 1 <= k <= 1e15

示例一：

输入：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 。

示例二：

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

解决方案：

前缀和 + 二分查找：

对于以 nums[i] 开始的子数组，由于 nums 中的元素均大于0，故可以找出一个长度 maxlen，对于 nums[i] 开始的，长度不超过 maxlen 的子数组的分数小于 k 。

可以使用二分查找找到这个长度 k ，并使用前缀和计算以 nums[i] 开始，长度为 len 的子数组的和。

代码：

class Solution
{
public:
    long long countSubarrays(vector<int> &nums, long long k)
    {
        int i, n = nums.size();
        // 前缀和，preSum[i] 表示 nums[0] ~ nums[i - 1] 的和。
        vector<long long> preSum(n + 1);
        
        preSum[0] = 0;
        for (int i = 0; i < n; ++i)
            preSum[i + 1] = preSum[i] + nums[i];

        int l, r, mid;
        long long t, sum, rst = 0;
        for (int i = 0; i < n; ++i)
        {
            // 计算以nums[i]开始的子数组满足要求的最长长度 maxlen
            l = 1;
            r = n - i;
            while(l <= r)
            {
                mid = (l + r) >> 1;
                sum = preSum[i + mid] - preSum[i];
                t = sum * mid;
                if(t >= k)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            // 此时maxLen = l
            rst += r;
        }
        return rst;
    }
};

时间复杂度为：$O(n \log n)$ ；空间复杂度为：$O(n)$ 。其中 n 表示 nums 的长度。