leetcode contest 327

2529. 正整数和负整数的最大计数

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。

注意：0 既不是正整数也不是负整数。

示例 1：

输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 2：

输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 3：

输入：nums = [5,20,66,1314]
输出：4
解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。

提示：

1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums 按 非递减顺序 排列。

地址

https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/

题意

直接遍历

思路

直接统计负数与整数的个数即可。
复杂度分析：

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

代码

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int pCnt = 0, nCnt = 0;
        for (auto v : nums) {
            if (v < 0) nCnt++;
            if (v > 0) pCnt++;
        }
        return max(nCnt, pCnt);
    }
};

2530. 执行 K 次操作后的最大分数

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。

在一步操作中：

选出一个满足 0 <= i < nums.length 的下标 i ，
将你的分数增加 nums[i] ，并且
将 nums[i] 替换为 ceil(nums[i] / 3) 。

返回在恰好执行 k 次操作后，你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

示例 1：

输入：nums = [10,10,10,10,10], k = 5
输出：50
解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。

示例 2：

输入：nums = [1,10,3,3,3], k = 3
输出：17
解释：可以执行下述操作：
第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。分数增加 10 。
第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。分数增加 4 。
第 3 步操作：选中 i = 2 ，nums 变为 [1,1,1,3,3] 。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。

提示：

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

地址

https://leetcode.cn/problems/maximal-score-after-applying-k-operations/

题意

直接模拟 + 堆

思路

按照题目模拟，我们每次找到数组中的最大元素 $x$，并将 $x$ 变为 $y = \lceil \frac{x}{3} \rceil$，并将 $y$ 再次加入到数组中，上述操作执行 $k$ 次即可。
复杂度分析：

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

代码

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        map<int, int> cnt;
        for (auto v : nums) {
            cnt[v]++;
        }
        long long res = 0;
        for (int i = 0; i < k; i++) {
            int x = cnt.rbegin()->first;
            res += x;
            cnt[x]--;
            if (cnt[x] == 0) {
                cnt.erase(x);
            }
            cnt[(x + 2) / 3]++;
        }
        return res;
    }
};

2531. 使字符串总不同字符的数目相等

给你两个下标从 0 开始的字符串 word1 和 word2 。

一次移动由以下两个步骤组成：

选中两个下标 i 和 j ，分别满足 0 <= i < word1.length 和 0 <= j < word2.length ，
交换 word1[i] 和 word2[j] 。

如果可以通过 恰好一次 移动，使 word1 和 word2 中不同字符的数目相等，则返回 true ；否则，返回 false 。

示例 1：

输入：word1 = "ac", word2 = "b"
输出：false
解释：交换任何一组下标都会导致第一个字符串中有 2 个不同的字符，而在第二个字符串中只有 1 个不同字符。

示例 2：

输入：word1 = "abcc", word2 = "aab"
输出：true
解释：交换第一个字符串的下标 2 和第二个字符串的下标 0 。之后得到 word1 = "abac" 和 word2 = "cab" ，各有 3 个不同字符。

示例 3：

输入：word1 = "abcde", word2 = "fghij"
输出：true
解释：无论交换哪一组下标，两个字符串中都会有 5 个不同字符。

提示：

1 <= word1.length, word2.length <= 105
word1 和 word2 仅由小写英文字母组成。

地址

https://leetcode.cn/problems/make-number-of-distinct-characters-equal/

题意

直接遍历

思路

由于题目给定的元素比较少，我们直接模拟即可，当然枚举分类讨论也可以，但是感觉没有太多必要。由于字符的种类 $|\Sigma| = 26$，所以我们直接用哈希统计并遍历所有可能的交换即可，然后比较字符的种类数目即可。
复杂度分析

时间复杂度：时间复杂度为 $O(|\Sigma|^3)$，$|\Sigma|$ 表示字符集的大小。
空间复杂度：时间复杂度为 $O(|\Sigma|)$。

代码

class Solution {
public:
    bool isItPossible(string word1, string word2) {
        unordered_map<char, int> cnt1, cnt2;
        for (auto c : word1) {
            cnt1[c]++;
        }
        for (auto c : word2) {
            cnt2[c]++;
        }
        for (auto [c1, x1] : cnt1) {
            for (auto [c2, x2] : cnt2) {
                unordered_map<char, int> t1 = cnt1;
                unordered_map<char, int> t2 = cnt2;
                t1[c2]++;
                t1[c1]--;
                t2[c1]++;
                t2[c2]--;
                if (t1[c1] == 0) t1.erase(c1);
                if (t2[c2] == 0) t2.erase(c2);
                if (t1.size() == t2.size()) {
                    return true;
                }
            }
        }
        return false;
    }
};

2532. 过桥的时间

共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，数组的大小为 k x 4 ，其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。

一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。开始时，所有 k 位工人都在桥的左侧等待。为了移动这些箱子，第 i 位工人（下标从 0 开始）可以：

从左岸（新仓库）跨过桥到右岸（旧仓库），用时 leftToRighti 分钟。
从旧仓库选择一个箱子，并返回到桥边，用时 pickOldi 分钟。不同工人可以同时搬起所选的箱子。
从右岸（旧仓库）跨过桥到左岸（新仓库），用时 rightToLefti 分钟。
将箱子放入新仓库，并返回到桥边，用时 putNewi 分钟。不同工人可以同时放下所选的箱子。

如果满足下面任一条件，则认为工人 i 的 效率低于 工人 j ：

leftToRighti + rightToLefti > leftToRightj + rightToLeftj
leftToRighti + rightToLefti == leftToRightj + rightToLeftj 且 i > j

工人通过桥时需要遵循以下规则：

如果工人 x 到达桥边时，工人 y 正在过桥，那么工人 x 需要在桥边等待。
如果没有正在过桥的工人，那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待，那么 效率最低 的工人会先过桥。
如果没有正在过桥的工人，且桥右边也没有在等待的工人，同时旧仓库还剩下至少一个箱子需要搬运，此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待，那么 效率最低 的工人会先过桥。

所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。

示例 1：

输入：n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]
输出：6
解释：
从 0 到 1 ：工人 2 从左岸过桥到达右岸。
从 1 到 2 ：工人 2 从旧仓库搬起一个箱子。
从 2 到 6 ：工人 2 从右岸过桥到达左岸。
从 6 到 7 ：工人 2 将箱子放入新仓库。
整个过程在 7 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 6 。

示例 2：

输入：n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]]
输出：50
解释：
从 0 到 10 ：工人 1 从左岸过桥到达右岸。
从 10 到 20 ：工人 1 从旧仓库搬起一个箱子。
从 10 到 11 ：工人 0 从左岸过桥到达右岸。
从 11 到 20 ：工人 0 从旧仓库搬起一个箱子。
从 20 到 30 ：工人 1 从右岸过桥到达左岸。
从 30 到 40 ：工人 1 将箱子放入新仓库。
从 30 到 31 ：工人 0 从右岸过桥到达左岸。
从 31 到 39 ：工人 0 将箱子放入新仓库。
从 39 到 40 ：工人 0 从左岸过桥到达右岸。
从 40 到 49 ：工人 0 从旧仓库搬起一个箱子。
从 49 到 50 ：工人 0 从右岸过桥到达左岸。
从 50 到 58 ：工人 0 将箱子放入新仓库。
整个过程在 58 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 50 。

提示：

1 <= n, k <= 104
time.length == k
time[i].length == 4
1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000

地址

https://leetcode.cn/contest/weekly-contest-327/problems/time-to-cross-a-bridge/

题意

直接模拟 + 优先队列

思路

题目也没有特别好的思路，只能直接模拟即可，但是题目有几个关键点需要注意:

每次无论从左向右过桥还是从右向左过桥，都只能有一个人过桥，此时在遍历时，每次出现一人过桥后，则我们需要立即更新队列的状态，假设当前为第 $i$ 个从右向左过桥，当前时间为 $currTime$，它过桥花费的时间为 $rightToLeft[i]$，则他过完桥后，则当前的时间变为 $currTime + rightToLeft[i]$，此时我们需要将所有进入等待过桥时间小于等于 $currTime + rightToLeft[i]$ 的工人全部加入到队列中，此时选择等待队列中效率最低的工人过桥；
题目要求过桥时要在当前等待队列中选择效率最低的工人过桥，此时我们的优先队列的队首元素即为效率最低的工人，我们每次从队列中取出即可；
每次我们将所有完成箱子的工人按照时间的先后顺序进入到过桥的等待序列中，此时优先队列则为小根堆，队首的元素即为完成时间最早的工人；
我们每次计数时，如果当前计算有 $n$ 个工人完成了过钱操作，则表明一定存在 $n$ 个工人完成搬运工作；
我们还需要统计最后一个工人完成从右向左过桥的时间即为最终的时间；

复杂度分析：

时间复杂度：$O(k + n \log k)$，其中 $n$ 表示给定的数， $k$ 表示工人的数目。
空间复杂度：$O(k)$，$k$ 表示工人的数目。队列中最多存在 $k$ 个工人。

代码

typedef pair<int, int> pii;

class Solution {
public:
    int findCrossingTime(int n, int k, vector<vector<int>>& time) {
        vector<int> idx(k);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            if (time[a][0] + time[a][2] == time[b][0] + time[b][2]) {
                return a > b;
            }
            return time[a][0] + time[a][2] > time[b][0] + time[b][2];
        });
        priority_queue<pii, vector<pii>, greater<pii>> waitL, waitR, workL, workR;
        for (int i = 0; i < k; i++) {
            waitL.emplace(i, 0);
        }
        int currTime = 0;
        while (n > 0) {
            while (!workL.empty() && workL.top().first <= currTime) {
                auto [finishTime, i] = workL.top();
                workL.pop();
                waitL.emplace(i, finishTime); // 左侧工人放下箱子并进入左侧过桥等待队列
            }
            while (!workR.empty() && workR.top().first <= currTime) {
                auto [finishTime, i] = workR.top();
                workR.pop();
                waitR.emplace(i, finishTime); // 右侧工人放下箱子并进入右侧过桥等待队列
            }

            if (!waitR.empty() && waitR.top().second <= currTime) {
                auto [i, arriveTime] = waitR.top(); 
                waitR.pop(); // 右侧过桥等待序列中允许当前等待序列中效率最低的工人过桥
                workL.emplace(currTime + time[idx[i]][2] + time[idx[i]][3], i);
                currTime += time[idx[i]][2];
            } else if (!waitL.empty() && waitL.top().second <= currTime){
                auto [i, arriveTime] = waitL.top();
                waitL.pop(); // 左侧过桥等待序列中允许当前等待序列中效率最低的工人过桥
                workR.emplace(currTime + time[idx[i]][0] + time[idx[i]][1], i);
                currTime += time[idx[i]][0];
                n--;
            } else {
                // 如果当前没人过桥，将当前时间进行后移到下一个最近可能过桥的时间；
                currTime = max({currTime, min(workL.empty() ? INT_MAX : workL.top().first, 
                                          workR.empty() ? INT_MAX : workR.top().first)});
            }
        }
        while (!workR.empty()) {
            // 如果当前还存在右侧过的桥的工人，则此时应等等待所有的人过桥；
            auto [finishTime, i] = workR.top();
            workR.pop();
            currTime = max(currTime, finishTime) + time[idx[i]][2];
        }
        return currTime;
    }
};

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

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

Tags: 力扣周赛题解

← leetcode biweekly contest 96 leetcode weekly contest 330 →

扫描二维码，分享此文章