文章目录
- 2409. 统计共同度过的日子
- 2410. 运动员和训练师的最大匹配数
- 2411. 按位或最大的最小子数组长度
- 2412. 完成所有交易的初始最少钱数
- 总结
2409. 统计共同度过的日子
题目描述
Alice 和 Bob 计划分别去罗马开会。
给你四个字符串
arriveAlice
，
leaveAlice
，
arriveBob
和
leaveBob
。Alice 会在日期
arriveAlice
到
leaveAlice
之间在城市里（日期为闭区间），而 Bob 在日期
arriveBob
到
leaveBob
之间在城市里（日期为闭区间）。每个字符串都包含 5 个字符，格式为
"MM-DD"
，对应着一个日期的月和日。
请你返回 Alice和 Bob 同时在罗马的天数。
你可以假设所有日期都在 同一个 自然年，而且 不是 闰年。每个月份的天数分别为：
[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
。
示例
输入：arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
输出：3
解释：Alice 从 8 月 15 号到 8 月 18 号在罗马。Bob 从 8 月 16 号到 8 月 19 号在罗马，他们同时在罗马的日期为 8 月 16、17 和 18 号。所以答案为 3 。 思路
归一化
实际就是给定2个区间，求2个区间的交集。题目给出的区间的两个端点是日期，包含了月和日两个维度。我们需要做一下归一化，或者扁平化。把
月-日
这样的点，转化为一维的一个数字。具体的操作就是，把
月-日
转化为当年的第
x
天。转化为一维后，就可以将其看成简单的两个区间。
求区间的交集就非常简单了，重叠部分
d = min(R1, R2) - max(L1, L2)
，当不存在交集时，计算出的
d
会为负数，所以要将结果和
0
再取一个
max
。
class Solution {
private int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
public int countDaysTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {
// 前缀和
for (int i = 1; i <= 12; i++) days[i] += days[i - 1];
// 归一化
int L1 = normalize(arriveAlice), R1 = normalize(leaveAlice);
int L2 = normalize(arriveBob), R2 = normalize(leaveBob);
int d = Math.min(R1, R2) - Math.max(L1, L2) + 1;
return Math.max(d, 0);
}
private int normalize(String date) {
String[] ss = date.split("-");
int month = Integer.parseInt(ss[0]);
int day = Integer.parseInt(ss[1]);
return days[month - 1] + day;
}
} 2410. 运动员和训练师的最大匹配数
题目描述
给你一个下标从 0 开始的整数数组
players
，其中
players[i]
表示第
i
名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组
trainers
，其中
trainers[j]
表示第
j
名训练师的 训练能力值 。
如果第
i
名运动员的能力值 小于等于 第
j
名训练师的能力值，那么第
i
名运动员可以 匹配 第
j
名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。
请你返回满足上述要求
players
和
trainers
的 最大 匹配数。
示例
输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。 思路
贪心（实际做时采用排序+双指针）
求最大匹配，映入脑子里的是匈牙利算法。但这道题条件比较特殊，可以用更简单的贪心来做。因为运动员和训练师最多是一一匹配的关系。然后条件是运动员的能力值要小于等于训练师的能力值。那么很直观的贪心策略是，对于一个能力值为
x
的运动员，我们尝试为他匹配一个训练师时，尽可能找能力值小的。即，在能力值
>= x
的训练师中，选择能力值最小的那个。
这样做的原因是，可以将能力值更大的训练师，留给其他运动员，增加其他运动员也能被匹配上的可能性。
我们只需要将运动员和训练师两个数组，从小到大排序，然后用双指针进行挨个比较，然后统计计数即可
能够使用双指针的原因是：两个指针移动的方向具有单调性。
设
i
表示当前运动员，
j
表示当前训练师。若
j
能力值小于
i
，那么
j
不可能匹配
i
之后的运动员，所以
j
需要右移。
class Solution {
public int matchPlayersAndTrainers(int[] players, int[] trainers) {
Arrays.sort(players);
Arrays.sort(trainers);
int i = 0, j = 0, n = players.length, m = trainers.length;
int ans = 0;
while (i < n && j < m) {
if (players[i] <= trainers[j]) {
ans++;
i++;
j++;
} else {
j++;
}
}
return ans;
}
} ----更一下y总的思路，我觉得更加清晰。
这道题，假设我们的最大匹配数是
k
，那么一定是匹配了能力值最小的前
k
个y运动员。为什么呢？
现证明一下：若某个最优解下，没有选择前
k
个玩家中的某一个（假设为
i
），而是选择了
k
之后的某个玩家（假设为
j
）。（假设已经按照能力值从小到大排好了序）。
j
这个玩家一定与某一个训练师
p
匹配了，能力值我们用
c
来表示（capability），那么一定有
c[j] <= c[p]
。而由于
i
在
j
前面，有
c[i] <= c[j]
，那么一定有
c[i] <= c[p]
。也就是说，我们可以把
j
替换成
i
，同样也算作是一个最优解。所以，假设最大匹配数是
k
，那么选择能力值前
k
小个运动员的方案，一定是一个最优解。
那么只需要对运动员排个序，然后从小到大依次枚举每个运动员，看该运动员能否被匹配上。假设一个运动员能够被匹配上，那么可能有多个训练师满足条件，那么此时应该给该运动员分配哪个训练师呢？直觉告诉我们应该分配能力值最小的那个训练师。这里做一下证明。
假设运动员
i
，能够匹配两个训练师
p
和
q
，其中
p
比
q
能力值小。只需要证明一下，选择
p
不会比选择
q
更差。
当选
q
时，
- 若
p
i
q
i
p
- 若
p
p
j
c[j] <= c[p]
c[i], c[j] <= c[p] <= c[q]
i
p
j
q
所以，可以证明，最优解一定是按能力值从小到大，从运动员中进行选取，对每个运动员，选一个能力值最小的训练师与之匹配即可。
2411. 按位或最大的最小子数组长度
题目描述
给你一个长度为
n
下标从 0 开始的数组
nums
，数组中所有数字均为非负整数。对于
0
到
n - 1
之间的每一个下标
i
，你需要找出
nums
中一个 最小 非空子数组，它的起始位置为
i
（包含这个位置），同时有 最大 的 按位或运算值 。
- 换言之，令
Bij
nums[i...j]
i
max(Bik)
i <= k <= n - 1
一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。
请你返回一个大小为
n
的整数数组
answer
，其中
answer[i]
是开始位置为
i
，按位或运算结果最大，且 最短 子数组的长度。
子数组 是数组里一段连续非空元素组成的序列。
-
n == nums.length
-
1 <= n <= 10^5
-
0 <= nums[i] <= 10^9
示例
输入：nums = [1,0,2,1,3]
输出：[3,3,2,2,1]
解释：
任何位置开始，最大按位或运算的结果都是 3 。
- 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
- 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
- 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
- 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
- 下标 4 处，能得到结果 3 的最短子数组是 [3] 。
所以我们返回 [3,3,2,2,1] 。 思路
按位统计+前缀和+二分
这道题目和之前某次周赛的题目有点像，位运算相关。
由于位运算的特性，多个数做位运算，二进制位为1的那些位置的数量，是只增不减的。比如下面3个数字（二进制表示）
11001
00110
10011 这三个数字做或运算的结果是
11111
。而实际上只需要对前两个数做或运算，即可得到这个最大的结果。
每多纳入一个数进来做或运算，1的数量要么不变，要么变多。
题目的要求是：对于每个位置
i
，区间
[i, n - 1]
的所有数做或运算，能够得到一个最大的值
max
。但实际上，可能在某个位置
k
，
k < n - 1
，区间
[i, k]
上所有数做或运算，结果就是
max
。而要求解的是满足这样条件的最小的
k
。
即
[i, k]
的或运算结果为
max
，而
[i, k - 1]
的运算结果小于
max
。对于每个位置
i
，都找到这样一个
k
，即完成解答。
题目的数据范围是：数组中每个数都
<= 10^9
，那么
10^9
大概是
2^30
，实际
10^9 < 2^30
，那么对于数组中的每个数，其最多有30个二进制位。我们可以对每个位置上的1进行计数。
然后对于任意的
i
，我们通过前缀和，能够快速算出
[i, n - 1]
区间内所有数做或运算的结果中，每个二进制位上分别出现了多少个1，进而求得这个最大的结果中有多少个1，假设为
m
。
根据前面的分析，从
i
往右不断做或运算时，1的个数是只增不减的。并且我们需要找到一个
k
，满足
[i, k]
的运算结果中1的个数为
m
，而
[i, k - 1]
的运算结果中1的个数不足
m
。这个过程便可以用二分来做。因为实际上，我们要在
[i, n - 1)
上找到
k
，这个
k
是个分界点，
k
的左侧都满足或运算结果中1的个数
< m
，
k
的右侧都满足或运算结果中1的个数
=m
。这种在具有二段性的区间内，找分界点，就是经典的二分。
至于为什么要统计每一个二进制位上1的个数，这是因为或运算无法记录某个位置上出现了多少个1，无法进行类似前缀和的运算，而通过前缀和可以在 的复杂度内求出
[i, n - 1]
的或运算结果。
故我们采用对每一个位进行计数这种方式。时间复杂度为 ，数据范围是
10^5
，故不会超时。
class Solution {
public int[] smallestSubarrays(int[] nums) {
int n = nums.length;
// 求个前缀和
// 第二维可以把整个数组看成是一个状态, 是增强版的或运算, 会额外记录每一个二进制位上的1的数量
int[][] cnt = new int[n + 1][30];
for (int i = 1; i <= n; i++) {
int x = nums[i - 1]; // 求这个数每一个二进制位上的1
for (int j = 0; j < 30; j++) {
cnt[i][j] = cnt[i - 1][j];
if ((x >> j & 1) == 1) cnt[i][j]++; // 计数+1
}
}
int[] ans = new int[n];
for (int i = 1; i <= n; i++) {
int targetCnt = howMany(cnt, i, n); // 从i到n的或运算结果中, 二进制位为1的位置有多少个
// 二分终点
int l = i, r = n;
while (l < r) {
int mid = l + r >> 1;
if (howMany(cnt, i, mid) < targetCnt) l = mid + 1;
else r = mid;
}
int len = l - i + 1;
ans[i - 1] = len;
}
return ans;
}
private int howMany(int[][] cnt, int i, int j) {
// 前缀和求解
int[] bitsJ = cnt[j];
int[] bitsI = cnt[i - 1];
int ret = 0;
for (int k = 0; k < 30; k++) {
if (bitsJ[k] - bitsI[k] > 0) ret++; //这一位上还有1
}
return ret;
}
} ------记录一下y总的思路，太强了。
逆序遍历+贪心
一共30个二进制位，只需要记录一下每一个二进制位上，从左往右第一次出现1时的位置。对
[i, n - 1]
区间所有数的或运算的结果，对于所有出现过1的二进制位，取其第一次出现时的位置，再取个max。
只需要从右往左遍历一次数组，每次处理30个二进制位，时间复杂度
30n
。这是一种类似贪心的思路
class Solution {
public int[] smallestSubarrays(int[] nums) {
int n = nums.length;
// 一共30个二进制位, p数组记录某个二进制位上, 第一次出现1时的那个数对应的下标
int[] p = new int[30];
Arrays.fill(p, -1);
int[] ans = new int[n];
for (int i = n - 1; i >= 0; i--) {
int t = i; // 终点最少为i
for (int j = 0; j < 30; j++) {
// j这个位置, 更新第一次出现1时的下标
if ((nums[i] >> j & 1) == 1) p[j] = i;
// j这个位置出现过1, 则更新; 若j这个位置没有出现过1, 则不用管
else if(p[j] != -1) t = Math.max(t, p[j]);
}
ans[i] = t - i + 1;
}
return ans;
}
} 2412. 完成所有交易的初始最少钱数
题目描述
给你一个下标从 0 开始的二维整数数组
transactions
，其中
transactions[i] = [costi, cashbacki]
。
数组描述了若干笔交易。其中每笔交易必须以 某种顺序 恰好完成一次。在任意一个时刻，你有一定数目的钱
money
，为了完成交易
i
，
money >= costi
这个条件必须为真。执行交易后，你的钱数
money
变成
money - costi + cashbacki
。
请你返回 任意一种 交易顺序下，你都能完成所有交易的最少钱数
money
是多少。
示例
输入：transactions = [[2,1],[5,0],[4,2]]
输出：10
解释：
刚开始 money = 10 ，交易可以以任意顺序进行。
可以证明如果 money < 10 ，那么某些交易无法进行。 思路
周赛当天，前3题我半小时做完了。无比激动的来到第4题，读完题后更兴奋了。感觉题意非常简单，就是
n
次操作，每次会先减一个数字
A
，随后再加一个数字
B
。要求当前数字
cur
必须大于等于
A
，该次操作才能进行。
我们可以按任意的顺序执行所有操作，每种顺序可以称之为一个方案。对于每个方案，我们能得出一个初始数字。要求解调的就是所有方案中，最大的初始数字是多少。
又是求什么最大最小，那我又要开始贪了！
可是当我稍加尝试后，发现并没有那么简单。尝试了好几种贪心策略，都被一些错误样例当头一棒。于是这道题又坐牢了1个小时。
我的第一种非常天真非常naive的贪心策略是，最后一次交易过后，没有后续交易了，那么最后一次获得的利润就无法使用，那么将获得利润最大的那笔交易放在最后即可。
class Solution {
public long minimumMoney(int[][] transactions) {
int maxGain = 0;
long netProfit = 0;
for (int i = 0; i < transactions.length; i++) {
int[] t = transactions[i];
maxGain = Math.max(maxGain, t[1]);
netProfit += t[0];
netProfit -= t[1];
}
return netProfit + maxGain;
}
} 结果发现不对。随后想了各种贪心策略，都有错误的样例，都不是很正确，然后就绕进去了。这里仅简单记录下当晚都有哪些想法：
- 模拟，每次选
cost
-
cashBack
cashBack - cost > 0
cashBack - cost = 0
cost
cashBack - cost < 0
cashBack
cashBack
cost
- …
下面看下y总的思路：
Acwing上类似的题目：耍杂技的牛，国王游戏。其中耍杂技的牛，和这题比较像。这题有点迷惑性。我一开始想的就是按照某种策略，先把所有操作排个序，然后做一次模拟即可求出答案。实际好像不是这样做。
假设我们按照某种顺序执行操作，执行到第
i
笔操作时，需要满足下面这个不等式（假设第
j
笔操作的
cost
用 来表示，
cashBack
用
称每种操作顺序为一种方案，则对于全部方案的每一笔操作，都需要满足上面这个不等式。
将上面的不等式进行一下移位变形，转化为如下的不等式 ：
要求
money
的最小值，那么只要对不等式右边求一下最大值即可。
我们先来看 ，一共有
n
种取法。我们枚举 的全部情况，再来看前面的 ，这一坨式子什么时候能取最大值呢？那就是把所有
那么我们预处理出一个
sum
，然后枚举 ，更新一下答案即可。
class Solution {
public long minimumMoney(int[][] transactions) {
long sum = 0;
int n = transactions.length;
for (int[] t : transactions) {
int a = t[0], b = t[1];
if (a > b) sum += a - b;
}
long ans = 0;
for (int i = 0; i < n; i++) {
int[] t = transactions[i];
int a = t[0], b = t[1];
long k = sum + a;
if (a > b) k -= a - b;
ans = Math.max(ans, k);
}
return ans;
}
}