leetcode weekly contes 349

周赛的题目质量非常高的题目，还是喜欢挑战质量高的题目，太简单的题目没啥意思。

2733. 既不是最小值也不是最大值

给你一个整数数组 nums ，数组由 不同正整数 组成，请你找出并返回数组中任一既不是 最小值 也不是 最大值 的数字，如果不存在这样的数字，返回 -1 。

返回所选整数。

示例 1：

输入：nums = [3,2,1,4]
输出：2
解释：在这个示例中，最小值是 1 ，最大值是 4 。因此，2 或 3 都是有效答案。

示例 2：

输入：nums = [1,2]
输出：-1
解释：由于不存在既不是最大值也不是最小值的数字，我们无法选出满足题目给定条件的数字。因此，不存在答案，返回 -1 。

示例 3：

输入：nums = [2,1,3]
输出：2
解释：2 既不是最小值，也不是最大值，这个示例只有这一个有效答案。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100
nums 中的所有数字互不相同

地址

https://leetcode.cn/contest/weekly-contest-349/problems/neither-minimum-nor-maximum/

题意

模拟

思路

排序后选择既不是最大的数字又不是最小的数字返回即可。
复杂度分析：

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

代码

class Solution {
public:
    int findNonMinOrMax(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (auto v : nums) {
            if (v != nums[0] && v != nums.back()) {
                return v;
            }
        }
        return -1;
    }
};

2734. 执行子串操作后的字典序最小字符串

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：

选则 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，’b’ 用 ‘a’ 替换，’a’ 用 ‘z’ 替换。

返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。

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

现有长度相同的两个字符串 x 和字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。

示例 1：

输入：s = "cbabc"
输出："baabc"
解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。 
可以证明最终得到的字符串是字典序最小的。

示例 2：

输入：s = "acbbc"
输出："abaab"
解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

示例 3：

输入：s = "leetcode"
输出："kddsbncd"
解释：我们选择整个字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

提示：

1 <= s.length <= 3 * 105
s 仅由小写英文字母组成

地址

https://leetcode.cn/contest/weekly-contest-349/problems/lexicographically-smallest-string-after-substring-operation/

题意

模拟

思路

 1. 根据题意找到一次变换后字典序最小字符串，分为如下步骤：
 + 从 $0$  开始找到第一个不等 $a$ 的字符 $s[l]$;
 + 从 $l$ 开始找到第一个等于 $a$ 的字符 $s[r]$;
 + 如果 $l = n$  ， 此时字符串中所有字符均为 $a$, 此时我们只需要将最后一个 $a$ 改为 $z$ 即可；
 + 如果 $l \neq n$, 此时我们将 $s[l\cdots r-1]$ 之间的字符均进行一次操作，即循环前移一次，这样保证最前面 $a$ 可以进行往前移动从而使得字典序最小，由于 $s[r] = a$ 此时该字符已经是最小，因此无需移动；

复杂度分析：

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

代码

class Solution {
public:
    string smallestString(string s) {
        int l = 0;
        int r = 0;
        while (l < s.size() && s[l] == 'a') {
            l++;
        }
        r = l;
        while (r < s.size() && s[r] != 'a') {
            r++;
        }
        if (l == s.size()) {
            s[s.size() - 1] = 'z';
            return s;
        }
        for (int i = l; i < r; i++) {
            s[i] = (s[i] - 'a' + 25) % 26 + 'a';
        }
        return s;
    }
};

2735. 收集巧克力

给你一个长度为 n 、下标从 0 开始的整数数组 nums ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。

在一步操作中，你可以用成本 x 执行下述行为：

同时修改所有巧克力的类型，将巧克力的类型 ith 修改为类型 ((i + 1) mod n)th。

假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。

示例 1：

输入：nums = [20,1,15], x = 5
输出：13
解释：最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。
接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。
然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。
因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。

示例 2：

输入：nums = [1,2,3], x = 4
输出：6
解释：我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 109
1 <= x <= 109

地址

https://leetcode.cn/contest/weekly-contest-349/problems/collecting-chocolates/

题意

构造题目

思路

首先题目说的比较模糊，没有看懂题目到底什么意思，每移动一次操作会将所有的巧克力都进行旋转，而此时巧克力的购买价格可以选择最低的，因此我们可以得到如下公司：
$$
cost_k = k * x + \sum_{i=0}^{n-1}\min(nums[i], nums[(i + 1) \mod n],nums[(i + 2) \mod n], \cdots, nums[(i + k) \mod n])
$$
可以知道移动 $k$ 次的最小成本为上述等式。
知道上述等式后，我们此时即可枚举 $k$ 的次数即可，有数组为循环数组，每次移动则垓心第 $i$ 个位置巧克力可能的最小购置成本即可，以上枚举本身就比较简单了，主要是这个题目描述与举例没有让人看懂是啥意思。
还有更加线性的解法，不过没看懂题目的解法的本质；
复杂度分析：

时间复杂度：$O(n^2)$，其中 $n$ 为数组的长度；
空间复杂度：$O(n)$，其中 $n$ 为数组的长度；

代码

class Solution {
public:
    long long minCost(vector<int>& nums, int x) {
        int n = nums.size();
        vector<int> minCost = nums;
        long long res = LONG_MAX;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                minCost[j] = min(minCost[j], nums[(j + i) % n]);
            }
            res = min(res, accumulate(minCost.begin(), minCost.end(), 0LL) + (long long) i * x);
        }
        return res;
    }
};

2736. 最大和查询

显示英文描述

我的提交返回竞赛

通过的用户数214
尝试过的用户数701
用户总通过次数253
用户总提交次数1642
题目难度****Hard

给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。

对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。

返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。

示例 1：

输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
输出：[6,10,7]
解释：
对于第 1 个查询：xi = 4 且 yi = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。
对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。
对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。nums1[j] + nums2[j] 等于 7 ，可以证明 7 是可以获得的最大值。
因此，我们返回 [6,10,7] 。

示例 2：

输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
输出：[9,9,9]
解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。

示例 3：

输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
输出：[-1]
解释：示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ，都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此，不存在答案。

提示：

nums1.length == nums2.length
n == nums1.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 109
1 <= queries.length <= 105
queries[i].length == 2
xi == queries[i][1]
yi == queries[i][2]
1 <= xi, yi <= 109

地址

https://leetcode.cn/contest/weekly-contest-349/problems/maximum-sum-queries/

题意

二分查找 + 线段树

思路

题目比较超纲的题目，要处理的细节比较多，但是如果会线段树的模板题目，这个倒也不是很难，需要处理的细节如下：
- 首先需要进行降维处理，直接处理二维实际上不太好处理，我们需要处理一维的数据，处理的方式就是排序，将查询全部按照 $x$ 的大小进行排序，将所有的 $nums$ 按照 $nums1$ 从小到大进行排序；
- 其次在排序的过程中我们需要进行预处理，即对 $nums2$ 进行离散化，我们先将 $nums2$ 按照从小到大进行排序，这样处理为了方便二分查找，并对排序后的每个元素进行编号，将每个元素编号后再将其按照 $nums1$ 进行从小到大排序，这样处理的目的是假设我们当前从小到大遍历了 $nums1$ 中的前 $x$ 个元素，则这 $x$ 个元素在 $nums2$ 中的编号即可一一对应；
- 再次题目要求时 $x_i \ge x, y_i \ge y$，即同时严格大于两个查询的横坐标与纵坐标；
- 为了方便处理我们按照 $x$ 的从大到小的顺序进行遍历，然后将所有大于 $x$ 的 $nums1$ 对应的 $nums2$ 的编号加入到树中，此时即可利用之前的编号，这样编号的目的是保证严格按照递增顺序。
- 加入完成后，我们利用二分查找在排序后的 $nums2$ 中进行查找，找到第一个大于等于 $y$ 的起始索引 $start$, 此时我们直接在线段中进行范围查找，即查找 $[start, n-1]$ 中最大值返回即可，此时的查找结果即为符合题目要求的最大值。
- 不过整体感觉这个做法还是太复杂了，应该有更简洁的解法。
复杂度分析：

时间复杂度：$O((m + n)\times \log n$，其中 $n$ 表示数组 $nums1$ 的长度，$m$ 表示给定查询的次数;
空间复杂度：$O(m + n)$，其中 $n$ 表示数组 $nums1$ 的长度，$m$ 表示给定查询的次数;

代码

const int N = 1e5;
struct node{
    int l, r, maxVal;
};
vector<node> tree(N * 4);

void build(int id, int l, int r) {
    tree[id].l = l;
    tree[id].r = r;
    if(l == r){
        tree[id].maxVal = -1;
        return;
    }
    int mid = (l + r) >> 1;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    tree[id].maxVal = max(tree[2 * id].maxVal, tree[2 * id + 1].maxVal);
    return;
}

int search(int id, int l, int r) {
    if(tree[id].l >= l && tree[id].r <= r)
        return tree[id].maxVal;
    if(tree[id].r < l || tree[id].l > r)
        return -1;
    int s = -1;
    if(tree[2 * id].r >= l)
        s = max(s, search(2 * id, l, r));
    if(tree[2 * id + 1].l <= r)
        s = max(s, search(2 * id + 1, l, r));
    return s;
}

void change(int id, int i, int k) {
    if(tree[id].l == i && tree[id].r == i){
        tree[id].maxVal = k;
        return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if(i <= mid)
        change(2 * id, i, k);
    else
        change(2 * id + 1, i, k);
    tree[id].maxVal = max(tree[2 * id].maxVal, tree[2 * id + 1].maxVal);
    return;
}

void update(int index, int val) {
    change(1, index, val);
}

class Solution {
public:
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        int m = nums1.size(), n = queries.size();
        for (int i = 0; i < queries.size(); i++) {
          queries[i].emplace_back(i);
        }
        sort(queries.begin(), queries.end());
        vector<array<int, 2>> arr(m);
        vector<array<int, 2>> brr(m);
        for (int i = 0; i < nums1.size(); i++) {
            arr[i] = {nums2[i], nums1[i]};
        }
        sort(arr.begin(), arr.end());
        for (int i = 0; i < m; i++) {
            brr[i] = {arr[i][1], i};
        }
        sort(brr.begin(), brr.end());
        vector<int> res(n);
        build(1, 0, m - 1);
        for (int i = n - 1, j = m - 1; i >= 0; i--) {
            int x = queries[i][0];
            int y = queries[i][1];
            int idx = queries[i][2];
            for (; j >= 0 && brr[j][0] >= x; j--) {
                int k = brr[j][1];
                update(k, arr[k][0] + arr[k][1]);
            }
            array<int, 2> key = {y, 0};
            int start = lower_bound(arr.begin(), arr.end(), key) - arr.begin();
            res[idx] = search(1, start, m - 1);
        }
        return res;
    }
};

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

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

Tags: 题解力扣周赛赛

← leetcode weekly contes 348 【CMU 15-445/645】lec5 →

扫描二维码，分享此文章