且听疯吟

leetcode biweekly contest 94

2022-12-25

leetcode biweekly contest 94

第四题就是模板题目，太没什么新意了，第三题时个贪心的数论的题目还算比较有新意的题目。

image-20221225135945227

6273. 最多可以摧毁的敌人城堡数目

给你一个长度为 n ，下标从 0 开始的整数数组 forts ，表示一些城堡。forts[i] 可以是 -1 ，0 或者 1 ，其中：

  • -1 表示第 i 个位置 没有 城堡。
  • 0 表示第 i 个位置有一个 敌人 的城堡。
  • 1 表示第 i 个位置有一个你控制的城堡。

现在，你需要决定，将你的军队从某个你控制的城堡位置 i 移动到一个空的位置 j ，满足：

  • 0 <= i, j <= n - 1
  • 军队经过的位置 只有 敌人的城堡。正式的，对于所有 min(i,j) < k < max(i,j) 的 k ，都满足 forts[k] == 0 。

当军队移动时，所有途中经过的敌人城堡都会被 摧毁 。

请你返回 最多 可以摧毁的敌人城堡数目。如果 无法 移动你的军队，或者没有你控制的城堡，请返回 0 。

示例 1：

输入：forts = [1,0,0,-1,0,0,0,0,1]
输出：4
解释：
- 将军队从位置 0 移动到位置 3 ，摧毁 2 个敌人城堡，位置分别在 1 和 2 。
- 将军队从位置 8 移动到位置 3 ，摧毁 4 个敌人城堡。
4 是最多可以摧毁的敌人城堡数目，所以我们返回 4 。

示例 2：

输入：forts = [0,0,1,-1]
输出：0
解释：由于无法摧毁敌人的城堡，所以返回 0 。

提示：

  • 1 <= forts.length <= 1000
  • -1 <= forts[i] <= 1

地址

https://leetcode.cn/contest/biweekly-contest-94/problems/maximum-enemy-forts-that-can-be-captured/

题意

直接遍历

思路

  1. 由于移动方向可以有两种，那么从左到右移动，要么从右向左移动，我们需要找到一段连续的区间，起点为 $1$，终点为 $-1$，且中间的位置全部为 $0$，找到这样的最长的连续区间即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。其中 $n$ 表示数组的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int captureForts(vector<int>& forts) {
        int n = forts.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (forts[i] == 1) {
                int cnt = 0;
                for (int j = i + 1; j < n; j++) {
                    if (forts[j] == 0) {
                        cnt++;
                    } else {
                        if (forts[j] == -1) {
                            ans = max(ans, j - i - 1);
                        }
                        break;
                    }
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (forts[i] == 1) {
                int cnt = 0;
                for (int j = i - 1; j >= 0; j--) {
                    if (forts[j] == 0) {
                        cnt++;
                    } else {
                        if (forts[j] == -1) {
                            ans = max(ans, i - j - 1);
                        }
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

6274. 奖励最顶尖的 K 名学生

给你两个字符串数组 positive_feedback 和 negative_feedback ，分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。

一开始，每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分，每个负面的词会给学生的分数 减 1 分。

给你 n 个学生的评语，用一个下标从 0 开始的字符串数组 report 和一个下标从 0 开始的整数数组 student_id 表示，其中 student_id[i] 表示这名学生的 ID ，这名学生的评语是 report[i] 。每名学生的 ID 互不相同。

给你一个整数 k ，请你返回按照得分 从高到低 最顶尖的 k 名学生。如果有多名学生分数相同，ID 越小排名越前。

示例 1：

输入：positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is studious","the student is smart"], student_id = [1,2], k = 2
输出：[1,2]
解释：
两名学生都有 1 个正面词汇，都得到 3 分，学生 1 的 ID 更小所以排名更前。

示例 2：

输入：positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is not studious","the student is smart"], student_id = [1,2], k = 2
输出：[2,1]
解释：
- ID 为 1 的学生有 1 个正面词汇和 1 个负面词汇，所以得分为 3-1=2 分。
- ID 为 2 的学生有 1 个正面词汇，得分为 3 分。
学生 2 分数更高，所以返回 [2,1] 。

提示：

  • 1 <= positive_feedback.length, negative_feedback.length <= 104
  • 1 <= positive_feedback[i].length, negative_feedback[j].length <= 100
  • positive_feedback[i] 和 negative_feedback[j] 都只包含小写英文字母。
  • positive_feedback 和 negative_feedback 中不会有相同单词。
  • n == report.length == student_id.length
  • 1 <= n <= 104
  • report[i] 只包含小写英文字母和空格 ' ' 。
  • report[i] 中连续单词之间有单个空格隔开。
  • 1 <= report[i].length <= 100
  • 1 <= student_id[i] <= 109
  • student_id[i] 的值 互不相同 。
  • 1 <= k <= n

地址

https://leetcode.cn/contest/biweekly-contest-94/problems/reward-top-k-students/

题意

哈希表

思路

  1. 题目比较简单的哈希映射即可。首先我们对每个单词求出其对应的分数。接着我们遍历每个人对应的报告，并将其报告中的每个单词切割出来，对每个单词求其分数。如果该单词为正面单词，则其得分加上 $3$，如果该单词为负面单词，则其得分减去 $3$，最后求出每个人的总得分，按照题目要求取最大的 $k$ 个得分的 $ID$ 即可。
  2. 复杂度分析：
  • 时间复杂度：$O(nm + n\log n)$，其中 $n$ 为给定的学生的人数，$m$ 表示每个同学的句子的长度。先遍历求出每个学生的得分，然后利用排序求出 $topk$ 即可。
  • 空间复杂度：$O(n)$。

代码

class Solution {
public:
    vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) {
        int n = student_id.size();
        unordered_set<string> pos, neg;
        for (auto w : positive_feedback) {
            pos.emplace(w);
        }
        for (auto w : negative_feedback) {
            neg.emplace(w);
        }
        vector<pair<int,int>> arr;
        for (int i = 0; i < n; i++) {
            string s = report[i];
            int j = 0;
            int score = 0;
            while (j < s.size()) {
                string word;
                while (j < s.size() && s[j] != ' ') {
                    word.push_back(s[j]);
                    j++;
                }
                if (pos.count(word)) {
                    score += 3;
                }
                if (neg.count(word)) {
                    score -= 1;
                }
                while (j < s.size() && s[j] == ' ') {
                    j++;
                }
            }
            arr.emplace_back(student_id[i], score);
        }
        sort(arr.begin(), arr.end(), [](const pair<int,int> &a, const pair<int,int> & b) {
            if (a.second == b.second) {
                return a.first < b.first;
            } 
            return a.second > b.second;
        });
        vector<int> res;
        for (int i = 0; i < k; i++) {
            res.emplace_back(arr[i].first);
        }
        return res;
    }
};

6295. 最小化两个数组中的最大值

给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：

  • arr1 包含 uniqueCnt1 个 互不相同 的正整数，每个整数都 不能 被 divisor1 整除 。
  • arr2 包含 uniqueCnt2 个 互不相同 的正整数，每个整数都 不能 被 divisor2 整除 。
  • arr1 和 arr2 中的元素 互不相同 。

给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。

示例 1：

输入：divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
输出：4
解释：
我们可以把前 4 个自然数划分到 arr1 和 arr2 中。
arr1 = [1] 和 arr2 = [2,3,4] 。
可以看出两个数组都满足条件。
最大值是 4 ，所以返回 4 。

示例 2：

输入：divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
输出：3
解释：
arr1 = [1,2] 和 arr2 = [3] 满足所有条件。
最大值是 3 ，所以返回 3 。

示例 3：

输入：divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
输出：15
解释：
最终数组为 arr1 = [1,3,5,7,9,11,13,15] 和 arr2 = [2,6] 。
上述方案是满足所有条件的最优解。

提示：

  • 2 <= divisor1, divisor2 <= 105
  • 1 <= uniqueCnt1, uniqueCnt2 < 109
  • 2 <= uniqueCnt1 + uniqueCnt2 <= 109

地址

https://leetcode.cn/contest/biweekly-contest-94/problems/minimize-the-maximum-of-two-arrays/

题意

贪心

思路

  1. 这个题目稍微有点意思，假如我们直接求最小数的话似乎不太好求，但是我们自然而然的会想到用二分法，假设当前的最大数为 $x$，我们只需要求出所有小于等于 $x$ 的元素中符合题要求的元素数目大于等于 $uniqueCnt1 + uniqueCnt2$ 即可，采用逼近法即可求出最小的 $x$。首先我们需要分析一下数的关系:
  • 所有不能被 $divisor1$ 整除的元素都可以作为 $arr1$ 的元素；
  • 所有不能被 $divisor2$ 整除的元素都可以作为 $arr2$ 的元素；
  • $arr1$ 与 $arr2$ 都不能包含既能被 $divisor1$ 整除又能被 $divisor2$ 整除的元素；
  • 我们知道给定的上限为 $x$，则可以知道:
    • 所有小于等于 $x$ 且能被 $divisor1$ 整除的元素数目为 $c_1 =\dfrac{x}{divisor1}$；
    • 所有小于等于 $x$ 且能被 $divisor2$ 整除的元素数目为 $c_2 = \dfrac{x}{divisor2}$；
    • 所有小于等于 $x$ 且能被 $divisor1$ 又能被 $divisor2$ 整除的元素数目为 $c_3 = \dfrac{x}{lcm(divisor1,divisor2)}$, 其中 $lcm(divisor1,divisor2) = \dfrac{divisor1 \times divisor2}{\gcd(divisor1,divisor2)}$，表示二者的最小公倍数。
  • 根据贪心原则，首先我们应该剔除所有能被二者整除的元素，即剔除掉 $c_3$，此时还剩下 $x-c_3$ 个元素；
  • 所有能被 $divisor1$ 整除但不能被 $divisor2$ 整除的元素都可以放到 $arr2$ 中，其数目为 $c_1 - c_3$；所有能被 $divisor2$ 整除但不能被 $divisor1$ 整除的元素都可以放到 $arr1$ 中，其数目为 $c_2-c_3$，此时 $arr1$ 还需要从小于等于 $x$ 的元素中取出 $uniqueCnt1 - (c_2-c_3)$ 个元素，$arr2$ 还需要从小于等于 $x$ 的元素中取出 $uniqueCnt2 - (c_1-c_3)$ 个元素，此时只需要满足剩下的元素能够被二者全部取到即可。此时需要满足的条件为:
    $$
    x - c_1 - c_2 + c_3 \ge \textit{uniqueCnt1} - (c_2-c_3) + uniqueCnt2 - (c_1-c_3)\
    $$
  • 我们只需要利用上述的规则找到最小的 $x$ 即可，即为满足题目要求的最大元素的最小值。
  1. 复杂度分析
  • 时间复杂度：时间复杂度为 $O(\log n)$，$n$ 表示给定元素的最大数目。
  • 空间复杂度：时间复杂度为 $O(1)$。

代码

class Solution {
public:
    int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        long long l = 1;
        long long r = 1e10 + 10;
        long long lcm = (long long)divisor1 * divisor2 / __gcd(divisor1, divisor2);
        long long res = 0;
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long c3 = mid / lcm;
            long long c1 = mid / divisor1 - c3;
            long long c2 = mid / divisor2 - c3;
            long long tot = mid - c1 - c2 - c3;
            int need1 = max(0LL, uniqueCnt1 - c2);
            int need2 = max(0LL, uniqueCnt2 - c1);
            if (need1 + need2 <= tot) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
};

6276. 统计同位异构字符串数目

给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。

如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。

  • 比方说，"acb dfe" 是 "abc def" 的同位异构字符串，但是 "def cab" 和 "adc bef" 不是。

请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 109 + 7 取余 后返回。

示例 1：

输入：s = "too hot"
输出：18
解释：输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。

示例 2：

输入：s = "aa"
输出：1
解释：输入字符串只有一个同位异构字符串。

提示：

  • 1 <= s.length <= 105
  • s 只包含小写英文字母和空格 ' ' 。
  • 相邻单词之间由单个空格隔开。

地址

https://leetcode.cn/contest/biweekly-contest-94/problems/count-anagrams/

题意

模板题目 + 排列组合

思路

  1. 题目一看非常简单，无法比较麻烦的是求阶乘的逆元。首先求出每个单词异构的单词的数目，这个很容易求出，我们可以利用排列组合公式，$cnt_i = \dfrac{(a+b+c+\cdots)!}{a!\times b!\times c!\cdots}$，求出每个单词的异构单词数目，然后相乘即可求出整个句子的异构数目，此时需要复杂的操作时需要用到求阶乘的逆元，常规做法利用逆元的求解公式加上快速幂 $a^{-1} \equiv a^{m-2} \pmod m$，当然我们也可以用利用公式在线性时间复杂度内求出阶乘的逆元，这个直接抄模板即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示字符串的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示字符串的长度。

代码

const int MOD = 1e9 + 7;
class Comb {
    vector<int> Facs, Invs;
    void expand(size_t n) {
        while(Facs.size() < n + 1) Facs.push_back(1ll * Facs.back() * Facs.size() % MOD);
        if(Invs.size() < n + 1) { // 线性求阶乘的逆元
            Invs.resize(n + 1, 0);
            Invs.back() = 1;
            for(int a = Facs[n], p = MOD - 2; p; p >>= 1, a = 1ll * a * a % MOD)
                if(p & 1) Invs.back() = 1ll * Invs.back() * a % MOD; // 快速乘求 n! 的逆元
            for(int j = n-1; !Invs[j]; --j) Invs[j] = 1ll * Invs[j+1] * (j + 1) % MOD;
        }
    }
public:
    Comb() : Facs({1}), Invs({1}) {}
    Comb(int n) : Facs({1}), Invs({1}) { expand(n); }
    int operator() (int n, int k) {
        if(k > n) return 0;
        expand(n);
        return (1ll * Facs[n] * Invs[n-k] % MOD) * Invs[k] % MOD; 
    }
    int inv(int x) {
        return Invs[x];
    }
    int fac(int x) {
        return Facs[x];
    }
};

class Solution {
public:
    int countAnagrams(string s) {
        int n = s.size();
        long long mod = 1e9 + 7;
        long long ans = 1;
        int i = 0;
        Comb comb(n + 1);
        while (i < s.size()) {
            vector<int> cnt(26);
            int tot = 0;
            while (i < s.size() && s[i] != ' ') {
                cnt[s[i] - 'a']++;
                tot++;
                i++;
            }
            if (tot > 0) {
                ans = (ans * comb.fac(tot)) % mod;
                for (int j = 0; j < 26; j++) {
                    if (cnt[j] > 0) {
                        ans = ans * comb.inv(cnt[j]) % mod;
                    }
                }
            }
            while (i < s.size() && s[i] == ' ') {
                i++;
            }
        }
        return ans;
    }
};

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

Tags: 力扣周赛 题解
← 【MIT6.S081】lab11 network leetcode contest 325 →

扫描二维码，分享此文章