leetcode contest 325

难得见到质量稍微高一些的第四题，前几次的周赛的第四题基本上都是送分题，这次的周赛第四题还算有些难度。

6269. 到目标字符串的最短距离

给你一个下标从 0 开始的环形字符串数组 words 和一个字符串 target 。环形数组 意味着数组首尾相连。

形式上， words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 n 是 words 的长度。

从 startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。

返回到达目标字符串 target 所需的最短距离。如果 words 中不存在字符串 target ，返回 -1 。

示例 1：

输入：words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
输出：1
解释：从下标 1 开始，可以经由以下步骤到达 "hello" ：
- 向右移动 3 个单位，到达下标 4 。
- 向左移动 2 个单位，到达下标 4 。
- 向右移动 4 个单位，到达下标 0 。
- 向左移动 1 个单位，到达下标 0 。
到达 "hello" 的最短距离是 1 。

示例 2：

输入：words = ["a","b","leetcode"], target = "leetcode", startIndex = 0
输出：1
解释：从下标 0 开始，可以经由以下步骤到达 "leetcode" ：
- 向右移动 2 个单位，到达下标 3 。
- 向左移动 1 个单位，到达下标 3 。
到达 "leetcode" 的最短距离是 1 。

示例 3：

输入：words = ["i","eat","leetcode"], target = "ate", startIndex = 0
输出：-1
解释：因为 words 中不存在字符串 "ate" ，所以返回 -1 。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 和 target 仅由小写英文字母组成
0 <= startIndex < words.length

地址

https://leetcode.cn/contest/weekly-contest-325/problems/shortest-distance-to-target-string-in-a-circular-array/

题意

直接遍历

思路

找到所有索引位置 $j$ 满足 $words[j] = target$，此时我们需要检测两个方向，要么为左到右，要么为从右向左,检测过程如下:

如果满足 $j \le startIndex$，此时我们从左向右需要移动的距离为 $startIndex - j$，从右向左移动的距离为 $(j - startIndex + n) \mod n $。
如果满足 $j > startIndex$，此时我们从左向右需要移动的距离为 $j - startIndex$，从右向左移动的距离为 $(startIndex - j + n) \mod n $。

复杂度分析：

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

代码

class Solution {
public:
    int closetTarget(vector<string>& words, string target, int startIndex) {
        int n = words.size();
        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (words[i] == target) {
                if (i <= startIndex) {
                    res = min(res, startIndex - i);
                    res = min(res, (i - startIndex + n) % n);
                } else {
                    res = min(res, i - startIndex);
                    res = min(res, (startIndex - i + n) % n);
                }
            }
        }
        return res == INT_MAX ? -1 : res;
    }
};

6270. 每种字符至少取 K 个

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1 。

示例 1：

输入：s = "aabaaaacaabc", k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。

示例 2：

输入：s = "a", k = 1
输出：-1
解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。

提示：

1 <= s.length <= 105
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

地址

https://leetcode.cn/contest/weekly-contest-325/problems/take-k-of-each-character-from-left-and-right/

题意

二分查找或者滑动窗口

思路

题目说的很长，其实很简单我们只需要找到字符串的前 $i$ 个元素与后 $j$ 个元素，且满足 $i + j$ 个元素中每个字符都至少出现了 $k$ 次，且满足 $i + j$ 最小即可。因此我们可以利用典型的二分查找或者滑动窗口即可，我们可以依次尝试字符串的左边依次取了 $i= 0,1,2,\cdots,n$ 个元素，然后此时求出且满足条件的 $j$ 即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为给定的数。最优的情况的下变换一次 $n$ 变为 $\dfrac{n}{2} + 2$，所以最多需要给定的元素变换即可
空间复杂度：$O(n)$，需要

代码

二分查找

class Solution {
public:
    int takeCharacters(string s, int k) {
        int n = s.size();
        vector<vector<int>> cnt(n + 1, vector<int>(3));
        for (int i = 0; i < n; i++) {
            cnt[i + 1] = cnt[i];
            cnt[i + 1][s[i] - 'a']++;
        }
        int res = INT_MAX;
        for (int i = 0; i <= n; i++) {
            int ca = cnt[i][0];
            int cb = cnt[i][1];
            int cc = cnt[i][2];
            int l = 0, r = n - i;
            while (l <= r) {
                int mid = (l + r) / 2;
                int ta = ca + cnt[n][0] - cnt[n - mid][0];
                int tb = cb + cnt[n][1] - cnt[n - mid][1];
                int tc = cc + cnt[n][2] - cnt[n - mid][2];
                if (ta >= k && tb >= k && tc >= k) {
                    res = min(res, mid + i);
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return res == INT_MAX ? -1 : res;
    }
};

滑动窗口

class Solution {
    public int takeCharacters(String s, int k) {
        int[] c = new int[3];
        int n = s.length(),j = n;
        while(c[0] < k || c[1] < k || c[2] < k){
            if(j == 0) return -1;
            j--;
            c[s.charAt(j) - 'a']++;
        }
        int ans = n - j;
        for(int i = 0;i<n;i++){
            c[s.charAt(i) - 'a']++;
            while(j < n && c[s.charAt(j)-'a'] > k){
                c[s.charAt(j)-'a']--;
                j++;
            }
            ans = Math.min(ans,n - (j - i) + 1);
            if(j == n) break;
        }
        return ans;
    }
}

6271. 礼盒的最大甜蜜度

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类不同糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果价格绝对差的最小值。

返回礼盒的最大甜蜜度。

示例 1：

输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。

示例 2：

输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。 
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。

示例 3：

输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

提示：

1 <= price.length <= 105
1 <= price[i] <= 109
2 <= k <= price.length

地址

https://leetcode.cn/contest/weekly-contest-325/problems/maximum-tastiness-of-candy-basket/

题意

二分查找 + 贪心

思路

题目看起来貌似很难的题目，实际仔细分析一下发现很简单，题目要求取出的 $k$ 个元素中的绝对值的最小值要尽可能的大，我们若要使的绝对值的最小值尽可能的大，则应该要求数组中的任意两个数的绝对值的最小值都应尽可能的大，因此按照贪心原则，我们假设相邻元素的最小间隔为 $x$，则我们在这个最小间隔下应该可以取足 $k$ 个元素即可。

此时我们想到了二分查找 + 贪心的解法，我们将数组按照从小达到大进行排序，因为要保证相邻元素的差值尽可能的大，因此我们应该最优选择从最小值或者最大值开始选择，按照每次相邻至少为 $maxVal$ 的取法，检测数组中是否可以取到 $k$ 个元素即可。

复杂度分析

时间复杂度：时间复杂度为 $O(n \log n)$，$n$ 表示数组中元素的数目。
空间复杂度：时间复杂度为 $O(\log n)$。

代码

class Solution {
public:
    bool check(vector<int>& price, int k, int maxVal) {
        int n = price.size();
        int prev = price[0];
        int tot = 1;
        for (int i = 1; i < price.size(); i++) {
            if (price[i] - prev >= maxVal) {
                tot++;
                prev = price[i];
            }
        }
        if (tot >= k) {
            return true;
        }
        return false;
    }
    
    int maximumTastiness(vector<int>& price, int k) {
        int n = price.size();
        sort(price.begin(), price.end());
        int l = 0, r = price[n - 1] - price[0];
        int res = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(price, k, mid)) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }
};

6272. 好分区的数目

给你一个正整数数组 nums 和一个整数 k 。

分区的定义是：将数组划分成两个有序的组，并满足每个元素恰好存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。

返回不同的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余后的结果。

如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。

示例 1：

输入：nums = [1,2,3,4], k = 4
输出：6
解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。

示例 2：

输入：nums = [3,3,3], k = 4
输出：0
解释：数组中不存在好分区。

示例 3：

输入：nums = [6,6], k = 2
输出：2
解释：可以将 nums[0] 放入第一个分区或第二个分区中。
好分区的情况是 ([6], [6]) 和 ([6], [6]) 。

提示：

1 <= nums.length, k <= 1000
1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-325/problems/number-of-great-partitions/

题意

动态规划

思路

看来时自己想复杂了，逆向求出数组的和小于 $k$ 的数目，此时题目就变的容易多了，我们利用 $0-1$ 背包问题就很容易求解了，可以参考题解题解。
复杂度分析：

时间复杂度：$O(nk)$，其中 $n$ 表示数组的长度，$k$ 表示给定的元素。
空间复杂度：$O(nk)$，其中 $n$ 表示数组的长度，$k$ 表示给定的元素。

代码

class Solution {
public:
    int countPartitions(vector<int>& nums, int k) {
        int n = nums.size();
        long long mod = 1e9 + 7;
        long long res = 1LL;
        long long sum = accumulate(nums.begin(), nums.end(), 0LL);
        if (sum < k * 2) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            res = res * 2L % mod;
        }
        vector<vector<long long>> dp(n + 1, vector<long long>(k));
        dp[0][0] = 1LL;
        for (int i = 0; i < n; i++) {
            for (int j = k - 1; j >= 0; j--) {
                if (j >= nums[i]) {
                    dp[i + 1][j] = (dp[i][j] + dp[i][j - nums[i]]) % mod;
                } else {
                    dp[i + 1][j] = dp[i][j];
                }
            }
        }
        long long tot = 0;
        for (int i = 0; i < k; i++) {
            tot = (tot + dp[n][i]) % mod;
        }
        return (res - tot * 2L + mod) % mod;
    }
};

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

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

Tags: 力扣周赛题解

← leetcode biweekly contest 94 leetcode contest 326 →

扫描二维码，分享此文章