文章目錄
- 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;
}
}