Leetcode 周赛题解222
难度顺序：
。
5641. 卡车上的最大单元数
请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi是类型i的箱子的数量。numberOfUnitsPerBoxi是类型i每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
返回卡车可以装载 单元 的 最大 总数*。*
示例 1：
输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：
- 1 个第一类的箱子，里面含 3 个单元。
- 2 个第二类的箱子，每个里面含 2 个单元。
- 3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8
示例 2：
输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
输出：91
提示：
1 <= boxTypes.length <= 10001 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000- ``1 <= truckSize <= 10^6`
思路：
既然选择箱子的个数有限制，我们就贪心的选择容量最大的箱子。将箱子按照容量排序之后依次取即可。
时间复杂度：
.
class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
auto cmp = [&](vector<int> &a, vector<int> &b) {
return a[1] > b[1];
};
sort(boxTypes.begin(), boxTypes.end(), cmp);
int ans = 0;
for(vector<int> &x: boxTypes) {
if(truckSize == 0) break;
int tmp = min(truckSize, x[0]);
ans += x[1] * tmp;
truckSize -= tmp;
}
return ans;
}
};
5642. 大餐计数
大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
你可以搭配 任意 两道餐品做一顿大餐。
给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 7 取余。
注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。
示例 1：
输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。
示例 2：
输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。
提示：
1 <= deliciousness.length <= 10^50 <= deliciousness[i] <= 2^20
思路：
美味度最大只有
，我们枚举每一道菜和
的幂次方即可。
时间复杂度：
.
const int mod = 1e9 + 7;
class Solution {
public:
int countPairs(vector<int>& deliciousness) {
vector<int> vis((1<<20)+1, 0);
int ans = 0;
for(int x: deliciousness) {
for(int i = 0; i < 22; ++i) {
if(x <= (1 << i) && (1 << i) - x <= (1<<20)) ans = (ans + vis[(1<<i) - x]) % mod;
}
++ vis[x];
}
return ans;
}
};
5643. 将数组分成三个子数组的方案数
我们称一个分割整数数组的方案是 好的 ，当它满足：
- 数组被分成三个 非空 连续子数组，从左至右分别命名为
left，mid，right。 left中元素和小于等于mid中元素和，mid中元素和小于等于right中元素和。
给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 109 + 7 取余后返回。
示例 1：
输入：nums = [1,1,1]
输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。
示例 2：
输入：nums = [1,2,2,2,5,0]
输出：3
解释：nums 总共有 3 种好的分割方案：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
示例 3：
输入：nums = [3,2,1]
输出：0
解释：没有好的分割方案。
提示：
3 <= nums.length <= 10^50 <= nums[i] <= 10^4
思路
要求将序列分成三段，每段数值之和不递减的合法方案数。
我们枚举第一段的位置，然后二分两次。
第一次二分中间这一段的右端点最小可以是多少。
第二次二分中间这一段的右端点最大可以是多少。
注意二分的时候要合法转移，详见代码。
时间复杂度：
.
const int mod = 1e9 + 7;
class Solution {
public:
int waysToSplit(vector<int>& nums) {
int ans = 0, n = nums.size();
vector<int64_t> pre(n, 0);
pre[0] = nums[0];
for(int i = 1; i < n; ++i) pre[i] = pre[i - 1] + nums[i];
for(int i = 0; i + 2 < n; ++i) {
int L = i + 1, R = n - 2, mid, ans1 = -1, ans2 = -1;
while(L <= R) {
mid = (L + R) >> 1;
if(pre[mid] - pre[i] >= pre[i] && pre[n - 1] - pre[mid] >= pre[mid] - pre[i]) ans1 = mid, R = mid - 1;
else if(pre[n - 1] - pre[mid] < pre[mid] - pre[i]) R = mid - 1;//最右侧的一段权值和较小，要右移
else if(pre[mid] - pre[i] < pre[i]) L = mid + 1;//中间这一段权值和较小，要左移。
else break;
}
L = i + 1, R = n - 2;
while(L <= R) {
mid = (L + R) >> 1;
if(pre[mid] - pre[i] >= pre[i] && pre[n - 1] - pre[mid] >= pre[mid] - pre[i]) ans2 = mid, L = mid + 1;
else if(pre[n - 1] - pre[mid] < pre[mid] - pre[i]) R = mid - 1;
else if(pre[mid] - pre[i] < pre[i]) L = mid + 1;
else break;
}
if(ans1 != -1 && ans2 != -1) ans = (ans + ans2 - ans1 + 1) % mod;
}
return ans;
}
};
5644. 得到子序列的最少操作次数
给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。
每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。
请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。
一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列，但 [2,4,2] 不是子序列。
示例 1：
输入：target = [5,1,3], arr = [9,4,2,3,4]
输出：2
解释：你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。
示例 2：
输入：target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出：3
提示：
1 <= target.length, arr.length <= 1051 <= target[i], arr[i] <= 109target不包含任何重复元素。
思路
最少要在arr中插入元素的个数使得target是arr的一个子序列，其实就是求两个序列的最长公共子序列长度。
注意到target中不包含重复的元素，那么其实arr中那些没在target中出现的元素都可以扔掉不管。
因为target不包含重复的元素，我们将元素重新编号。在target中第
个数字重新编号为
。然后arr数组也按照这个重新编号。
最后这个最长公共子序列的长度其实就等于arr的最长上升子序列的长度。
时间复杂度：
.
class Solution {
public:
int minOperations(vector<int>& target, vector<int>& arr) {
int n = target.size(), m = arr.size();
map<int, int> mp;
vector<int> dp(m, 0x3f3f3f3f);
for(int i = 0; i < n; ++i) mp[target[i]] = i + 1;
int Mx = 0;
for(int i = 0; i < m; ++i) {
if(mp[arr[i]] == 0) continue;
arr[i] = mp[arr[i]];
int p = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
dp[p] = arr[i];
Mx = max(Mx, p + 1);
}
return n - Mx;
}
};
腾讯云开发者
