leetcode biweekly contes 111

最近周赛一直不稳定，感觉还是智商着急啊，简单的题目想复杂了，其实很多题目只是需要想明白其中的 tricky 的部分，绝大部分都是卡在某个非常 tricky 的点上，把这个 tricky 的点想明白以后，其实题目就非常简单了。其实绝大部分题目都是提示信息的，特别是非常关键的题目给定的数量级上，基本上给定题目的数量级以后差不多即可确定题目解法的时间复杂度，再从时间复杂度中选择合适的解题技巧即可。

6954. 统计和小于目标的下标对数目

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。

示例 1：

输入：nums = [-1,1,2,3,1], target = 2
输出：3
解释：总共有 3 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target 
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。

示例 2：

输入：nums = [-6,2,5,-2,-7,-1,3], target = -2
输出：10
解释：总共有 10 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
- (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
- (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
- (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
- (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
- (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
- (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
- (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
- (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target

提示：

1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50

地址

https://leetcode.cn/contest/biweekly-contest-111/problems/count-pairs-whose-sum-is-less-than-target/

题意

直接模拟

思路

直接模拟即可，当然如何题目给定的数量级较大时，采用二分查找和双指针即可。
复杂度分析：

时间复杂度：$O(n \log n)$, 其中 $n$ 表示数组的长度。
空间复杂度：$O(1)$。

代码

[sol1-C++]

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] < target) {
                    res++;
                }
            }
        }
        return res;
    }
};

8014. 循环增长使字符串子序列等于另一个字符串

给你一个下标从 0 开始的字符串 str1 和 str2 。

一次操作中，你选择 str1 中的若干下标。对于选中的每一个下标 i ，你将 str1[i] 循环递增，变成下一个字符。也就是说 'a' 变成 'b' ，'b' 变成 'c' ，以此类推，'z' 变成 'a' 。

如果执行以上操作 至多一次 ，可以让 str2 成为 str1 的子序列，请你返回 true ，否则返回 false 。

注意：一个字符串的子序列指的是从原字符串中删除一些（可以一个字符也不删）字符后，剩下字符按照原本先后顺序组成的新字符串。

示例 1：

输入：str1 = "abc", str2 = "ad"
输出：true
解释：选择 str1 中的下标 2 。
将 str1[2] 循环递增，得到 'd' 。
因此，str1 变成 "abd" 且 str2 现在是一个子序列。所以返回 true 。

示例 2：

输入：str1 = "zc", str2 = "ad"
输出：true
解释：选择 str1 中的下标 0 和 1 。
将 str1[0] 循环递增得到 'a' 。
将 str1[1] 循环递增得到 'd' 。
因此，str1 变成 "ad" 且 str2 现在是一个子序列。所以返回 true 。

示例 3：

输入：str1 = "ab", str2 = "d"
输出：false
解释：这个例子中，没法在执行一次操作的前提下，将 str2 变为 str1 的子序列。
所以返回 false 。

提示：

1 <= str1.length <= 105
1 <= str2.length <= 105
str1 和 str2 只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-111/problems/make-string-a-subsequence-using-cyclic-increments/

题意

直接模拟

思路

由于题目可以更换所有的一批索引而不是一个索引，所以就变的非常简单了，如果是只能更换一个索引，则题目难度会变高很多。
- $str1[j] = str2[i]$;
- $str1[j] = str2[i] - 1$;
满足以上条件中的任何一个，则可以认为 $str1[j] 与 str2[i]$ 相等匹配，我们按照上述规则进行 $LCP$ 匹配即可。
复杂度分析：

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

代码

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int m = str1.size(), n = str2.size();
        for (int i = 0, j = 0; i < m && j < n; i++) {
            if (str1[i] == str2[j] || ((str2[j] - str1[i] + 26) % 26) == 1) {
                j++;
                if (j == n) {
                    return true;
                }
            }
        }
        return false;
    }
};

6941. 将三个组排序

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

从 0 到 n - 1 的数字被分为编号从 1 到 3 的三个组，数字 i 属于组 nums[i] 。注意，有的组可能是空的。

你可以执行以下操作任意次：

选择数字 x 并改变它的组。更正式的，你可以将 nums[x] 改为数字 1 到 3 中的任意一个。

你将按照以下过程构建一个新的数组 res ：

将每个组中的数字分别排序。
将组 1 ，2 和 3 中的元素依次连接以得到 res 。

如果得到的 res 是 非递减顺序的，那么我们称数组 nums 是 美丽数组 。

请你返回将 nums 变为 美丽数组 需要的最少步数。

示例 1：

输入：nums = [2,1,3,2,1]
输出：3
解释：以下三步操作是最优方案：
1. 将 nums[0] 变为 1 。
2. 将 nums[2] 变为 1 。
3. 将 nums[3] 变为 1 。
执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3,4] ，组 2 和组 3 都为空。所以 res 等于 [0,1,2,3,4] ，它是非递减顺序的。
三步操作是最少需要的步数。

示例 2：

输入：nums = [1,3,2,1,3,3]
输出：2
解释：以下两步操作是最优方案：
1. 将 nums[1] 变为 1 。
2. 将 nums[2] 变为 1 。
执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3] ，组 2 为空，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。
两步操作是最少需要的步数。

示例 3：

输入：nums = [2,2,2,2,3,3]
输出：0
解释：不需要执行任何操作。
组 1 为空，组 2 为 [0,1,2,3] ，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 3

地址

https://leetcode.cn/contest/biweekly-contest-111/problems/sorting-three-groups/

题意

枚举

思路

题目本身是个好题目，但是给定的数量级太低了，所以变成了暴力模拟，就很简单了，实际数量可以到 $1000$ 以上，此时需要二分查找即可。根据题意可以知道，若要使得三个数组合并后递增则需要满足如下：
- $arr1[0\cdots l_1] < arr2[0\cdots l_2] < arr3[0\cdots l_3]$, 即第一个分组中的元素严格小于第二个分组中的元素，第二个分组中的元素严格小于第三个分组中的元素；
- 最直接的做法我们枚举 $arr1$ 中的最大元素 $x$，枚举 $arr3$ 中的最小元素 $y$，即此时需要满足 $arr1$ 中的所有元素都要大于 $x$, $arr3$ 中的所有元素都要大于 $y$, 此时 $x,y$ 需要满足 $x \in (0, n), y \in (0, n), x \le y$；
- 我们按照上述策略枚举所有的可能性即可：
  - $arr1$ 中所有大于等于 $x$ 的元素需要被替换；
  - $arr2$ 中所有小于 $x$ 或者大于 $y$ 的元素需要被替换；
  - $arr3$ 中所有小于 $y$ 的元素需要被替换；
- 我们直接遍历数组进行替换即可，当然可以用二分查找，可以将时间复杂度进一步降低；
也可以转换为最长递增子序列问题，即题目中依次找到 $arr[i] \ge arr[i-1]$ 的最长非递减子序列的长度；
复杂度分析：

时间复杂度：$O(n^3)$，其中 $n$ 表示数组的长度。
空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<vector<int>> cnt(3);
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            cnt[nums[i] - 1].emplace_back(i);
        }
        int res = INT_MAX;
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int tot = 0;
                for (auto v : cnt[0]) {
                    if (v >= i) tot++;
                }
                for (auto v : cnt[1]) {
                    if (!(v >= i && v < j)) tot++;
                }
                for (auto v : cnt[2]) {
                    if (v < j) tot++;
                }
                res = min(res, tot);
            }
        }
        return res;
    }
};

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<vector<int>> cnt(3);
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            cnt[nums[i] - 1].emplace_back(i);
        }
        for (int i = 0; i < 3; i++) {
            sort(cnt[i].begin(), cnt[i].end());
        }
        int res = INT_MAX;
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int tot = 0;
                /* 第一个分组中大于等于 i 的元素 */
                tot += cnt[0].end() - lower_bound(cnt[0].begin(), cnt[0].end(), i);
                /* 第二个分组中小于 i 或者大于等于 j 的元素 */
                tot += cnt[1].end() - lower_bound(cnt[1].begin(), cnt[1].end(), j);
                tot += lower_bound(cnt[1].begin(), cnt[1].end(), i) - cnt[1].begin();
                /* 第三个分组中小于 j 的元素 */
                tot += lower_bound(cnt[2].begin(), cnt[2].end(), j) - cnt[2].begin();
                res = min(res, tot);
            }
        }
        return res;
    }
};

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<int> arr;
        for (int i = 0; i < nums.size(); i++) {
            int x = upper_bound(arr.begin(), arr.end(), nums[i]) - arr.begin();
            if (x == arr.size()) {
                arr.emplace_back(nums[i]);
            } else {
                arr[x] = nums[i];
            }
        }
        return nums.size() - arr.size();
    }
};

8013. 范围中美丽整数的数目

给你正整数 low ，high 和 k 。

如果一个数满足以下两个条件，那么它是 美丽的 ：

偶数数位的数目与奇数数位的数目相同。
这个整数可以被 k 整除。

请你返回范围 [low, high] 中美丽整数的数目。

示例 1：

输入：low = 10, high = 20, k = 3
输出：2
解释：给定范围中有 2 个美丽数字：[12,18]
- 12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
- 18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
以下是一些不是美丽整数的例子：
- 16 不是美丽整数，因为它不能被 k = 3 整除。
- 15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
给定范围内总共有 2 个美丽整数。

示例 2：

输入：low = 1, high = 10, k = 1
输出：1
解释：给定范围中有 1 个美丽数字：[10]
- 10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。
给定范围内总共有 1 个美丽整数。

示例 3：

输入：low = 5, high = 5, k = 2
输出：0
解释：给定范围中有 0 个美丽数字。
- 5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。

提示：

0 < low <= high <= 109
0 < k <= 20

地址

https://leetcode.cn/contest/biweekly-contest-111/problems/number-of-beautiful-integers-in-the-range/

题意

数位dp

思路

典型的数位 dp 了，题目关键在于给定的 $k$ 的值为 $[0,20]$ 这个是一个关键提示信息，如果知道该关键信息此时即可用数位 dp 来表示状态，数位 dp 的题目确实不太容易写对，但是关键还是在于模板。知道几个常见的状态转移，昨天比赛的关键没有想好能被 $k$ 整除该如何处理，实际本质上还是数位 $dp$ 的一个子状态而已。当然数位 dp 也可以从自底向上的写法，不用递归，但是写法太复杂，直接自顶向下的递归写法比较好写。
复杂度分析：

时间复杂度：$O(k \times n^3)$，其中 $n$ 表示数位的长度。
空间复杂度：$O(k \times n^2)$，其中 $n$ 表示数位的长度。

代码

class Solution {
public:
    constexpr static int INF = 0x3f3f3f3f;

    int calc(int high, int k) {
        string s = to_string(high);
        int n = s.size();
        int memo[n][2 * n + 1][k + 1];
        memset(memo, -1, sizeof(memo));

        function<int(int, int, int, bool, bool)> dfs = [&](int pos, int val, int diff, bool isNum, bool isLimit) -> int {
            if (pos == n) {
                return isNum && val == 0 && diff == n;
            }
            if (!isLimit && isNum && memo[pos][diff][val] != -1) {
                return memo[pos][diff][val];
            }
            int res = 0;
            if (!isNum) {
                res = dfs(pos + 1, val, diff, false, false);
            }
            int up = isLimit ? s[pos] - '0' : 9;
            if (isNum) {
                for (int i = 0; i <= up; i++) {
                    int odd = i % 2 == 0 ? -1 : 1;
                    res += dfs(pos + 1, (val * 10 + i) % k, diff + odd, true, isLimit && i == up);
                }
            } else {
                for (int i = 1; i <= up; i++) {
                    int odd = i % 2 == 0 ? -1 : 1;
                    res += dfs(pos + 1, (val * 10 + i) % k, diff + odd, true, isLimit && i == up);
                }
            }
            if (!isLimit && isNum) {
                memo[pos][diff][val] = res;
            }
            return res;
        };
        return dfs(0, 0, n, false, true);
    }

    int numberOfBeautifulIntegers(int low, int high, int k) {
        return calc(high, k) - calc(low - 1, k);
    }
};

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

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

Tags: 题解力扣周赛赛

← leetcode biweekly contes 357 leetcode weekly contes 359 →

扫描二维码，分享此文章