LeetCode周賽309,米哈遊贊助的比賽居然不收簡歷……
大家好,我是梁唐。
LeetCode系列原本是週一更新的,但由於昨天恰了個飯,因此推遲一天。
LeetCode周賽309由大名鼎鼎的米哈遊贊助,米哈遊也是近期唯一一個不提供簡歷直通內推機會的贊助商……
這一場的難度比之前略大一些,很多同學在評論區反應心態崩了……
很遺憾這一場比賽我沒有參加(剛好收到密接簡訊聯絡社群去了……),我是賽後補的。但即便是在賽後比較輕鬆的狀態下,依然做得不是很順利,也側面體現這一場的難度。
好了,我們閒言少敘,來看題吧。
檢查相同字母間的距離
給你一個下標從 0 開始的字串 s
,該字串僅由小寫英文字母組成,s
中的每個字母都 恰好 出現 兩次 。另給你一個下標從 0 開始、長度為 26
的的整數陣列 distance
。
字母表中的每個字母按從 0
到 25
依次編號(即,'a' -> 0
, 'b' -> 1
, 'c' -> 2
, ... , 'z' -> 25
)。
在一個 勻整 字串中,第 i
個字母的兩次出現之間的字母數量是 distance[i]
。如果第 i
個字母沒有在 s
中出現,那麼 distance[i]
可以 忽略 。
如果 s
是一個 勻整 字串,返回 true
;否則,返回 false
。
題解
主要的坑點在讀題,需要注意如果某個字串沒有出現過,那麼它的距離統統視為合法。
```cpp
class Solution {
public:
bool checkDistances(string s, vector
for (int i = 0; i < 26; i++) {
if (distance[i] != 0 && mp.count('a'+i)) return false;
}
return true;
}
}; ```
恰好移動 k 步到達某一位置的方法數目
給你兩個 正 整數 startPos
和 endPos
。最初,你站在 無限 數軸上位置 startPos
處。在一步移動中,你可以向左或者向右移動一個位置。
給你一個正整數 k
,返回從 startPos
出發、恰好 移動 k
步併到達 endPos
的 不同 方法數目。由於答案可能會很大,返回對 109 + 7
取餘 的結果。
如果所執行移動的順序不完全相同,則認為兩種方法不同。
注意:數軸包含負整數。
題解
表面上看很容易想到搜尋或者是動態規劃,但實際上這是一道數學題。
由於我們只需要考慮可行解的數量,我們可以強行規定左邊的點是起點,右邊的點是終點。加上我們 知道了一共需要的步數k
,所以我們可以算出向左、向右移動的步數。到這裡會發現這其實是一個組合問題,我們假設向左移動lef
,向右移動rig
。
那麼應該滿足lef + rig = k,start + rig - lef = end
。這是一個很簡單的二元一次方程,求解即可。另外還需要注意,rig和lef
都是非負整數。如果算出來是負數或者不為整數,說明無解。
求出了lef
和rig
之後,剩下的就是一個組合問題,我們要求的答案就是$C_k^{rig}$。
這裡有一個問題,由於答案可能很大,所以我們需要在計算的過程當中取模。但是組合數的運算會用到除法,但對於取模運算,除法不滿足結合律,即$a \bmod p * b \bmod p = ab \bmod p$,但是沒有$a \mod p \div b \bmod p \neq \frac a b \bmod p$。
要解決這個問題有兩種辦法,第一種辦法是通過$C_i^j = C_{i-1}^j + C_{i-1}^{j-1}$來推算,第二種辦法是求逆元。我們要求$\frac a b \bmod p$的結果,可以轉化成乘上$b$關於$a$和$p$的逆元。
這兩種方法都可以,我個人用的是逆元法。關於逆元的原理以及計算方法,這裡不做過多介紹了,大家感興趣可以查閱相關資料。
附上程式碼:
```cpp class Solution { public: typedef long long lint; void Exgcd(lint a,lint b,lint &x,lint &y){ if(!b) x=1,y=0; else Exgcd(b,a%b,y,x), y-=a/b*x; }
int inverse(lint a, lint p){
lint x, y;
Exgcd (a,p,x,y);
x = (x%p+p)%p;
return x;
}
int numberOfWays(int st, int ed, int k) {
int Mod = 1e9 + 7;
int start = min(st, ed);
int end = max(st, ed);
int rig = end - start;
int lef = k - rig;
if (lef < 0 || lef % 2) return 0;
rig += lef / 2;
lint ret = 1;
for (int i = 0; i < rig; i++) {
ret = ret * (k - i) % Mod;
ret = ret * inverse(i+1, Mod) % Mod;
}
return ret;
}
}; ```
最長優雅子陣列
給你一個由 正 整陣列成的陣列 nums
。
如果 nums
的子陣列中位於 不同 位置的每對元素按位 與(AND)運算的結果等於 0
,則稱該子陣列為 優雅 子陣列。
返回 最長 的優雅子陣列的長度。
子陣列 是陣列中的一個 連續 部分。
注意:長度為 1
的子陣列始終視作優雅子陣列。
題解
這題題意裡藏著坑,主要是子陣列而非子序列,這兩者的意思完全不同。子序列可以不連續,但子陣列必須連續。
我們很容易發現,假設我們找到了一個完美子陣列,那麼這個子陣列內的任意兩個數的與值為0。轉化成二進位制,即這若干個數的每一個二進位制位最多隻有一個1。
有了這個限制條件之後很容易想到two pointers演算法,我們維護一段區間內所有二進位制位1的個數。如果新增一個數之後會導致某一位的個數大於1,那麼從左邊進行彈出操作,直到每一個二進位制位最多隻有一個1為止。
```cpp
class Solution {
public:
// 將整數轉化成二進位制表示
vector
int longestNiceSubarray(vector<int>& nums) {
int ret = 1;
int l = 0, st = nums[0];
int n = nums.size();
// 存放當前區間內二進位制1的數量
vector<int> bits = to_bit(nums[0]);
for (int r = 1; r < n; r++) {
vector<int> cur = to_bit(nums[r]);
// 標記是否存在某一位的1的數量大於1
bool flag = false;
for (int i = 0; i < 32; i++) {
bits[i] += cur[i];
if (bits[i] > 1) flag = true;
}
while (flag) {
cur = to_bit(nums[l]);
flag = false;
for (int i = 0; i < 32; i++) {
bits[i] -= cur[i];
if (bits[i] > 1) flag = true;
}
l++;
}
ret = max(ret, r - l + 1);
}
return ret;
}
}; ```
會議室 III
給你一個整數 n
,共有編號從 0
到 n - 1
的 n
個會議室。
給你一個二維整數陣列 meetings
,其中 meetings[i] = [starti, endi]
表示一場會議將會在 半閉 時間區間 [starti, endi)
舉辦。所有 starti
的值 互不相同 。
會議將會按以下方式分配給會議室:
- 每場會議都會在未佔用且編號 最小 的會議室舉辦。
- 如果沒有可用的會議室,會議將會延期,直到存在空閒的會議室。延期會議的持續時間和原會議持續時間 相同 。
- 當會議室處於未佔用狀態時,將會優先提供給原 開始 時間更早的會議。
返回舉辦最多次會議的房間 編號 。如果存在多個房間滿足此條件,則返回編號 最小 的房間。
半閉區間 [a, b)
是 a
和 b
之間的區間,包括 a
但 不包括 b
。
題解
模擬題,由於會議開始的時間各不相同,我們可以對會議進行排序,從最先開始的會議開始安排。
對於每一個會議,我們要找到最先空出來的會議室,如果有多個空的,我們選擇序號最小的。觀察一下資料範圍,會議最多是1e5個,會議室最多有100個。對於每個會議我們需要遍歷一次所有的會議室。那麼總的複雜度就是1e7,在可接受的範圍內。
當然如果想要優化也可以使用線段樹這樣的資料結構,可以把會議室的查詢降低到logN。但我個人感覺意義不大,大家如果感興趣可以看看大佬的部落格。
要注意會議延續的時間可能會很長,超過int的範圍,所以要用int64
。
```cpp
class Solution {
public:
int mostBooked(int n, vector
const lint MAXI = 0x3f3f3f3f3f3f3f3f;
sort(meetings.begin(), meetings.end());
for (auto &vt: meetings) {
lint sta = vt[0], end = vt[1];
int choose = -1;
lint mini = MAXI;
bool not_exceed = false;
for (int i = 0; i < n; i++) {
if (mst[i] <= sta) {
choose = i;
not_exceed = true;
break;
}
if (mst[i] < mini) {
mini = mst[i];
choose = i;
}
}
if (not_exceed) {
mst[choose] = end;
}else {
mst[choose] += end - sta;
}
cnt[choose] ++;
}
int mxi = -1, ret = -1;
for (int i = 0; i < n; i++) {
if (cnt[i] > mxi) {
mxi = cnt[i];
ret = i;
}
}
return ret;
}
}; ```
- LeetCode周賽309,米哈遊贊助的比賽居然不收簡歷……
- LeetCode周賽311,中規中矩的裸題大賽……
- 日拱一卒,麻省理工教你資訊保安和密碼學
- LeetCode周賽301,離大譜,手速場掉分,質量場掉大分……
- 日拱一卒,超程式設計不是元宇宙,麻省理工教你makefile、依賴管理和CI
- LeetCode周賽300,差點AK,剛拿到的勳章要丟了……
- 日拱一卒,麻省理工教你效能分析,火焰圖、系統呼叫棧,黑科技滿滿
- 日拱一卒,麻省理工教你Debug,從此debug不再脫髮
- 日拱一卒,麻省理工教你學Git,工程師必備技能
- 日拱一卒,配置開發環境不再愁,麻省理工手把手教你
- 日拱一卒,麻省理工CS入門課,命令列這樣用也太帥了
- 日拱一卒,麻省理工YYDS,一節課讓我學會用vim
- 日拱一卒,麻省理工教你CS基礎,那些酷炫無比的命令列工具
- LeetCode周賽297,一小時AK你也可以
- 聽說你入行好幾年還只會cd和ls,麻省理工開了這門課……
- 日拱一卒,伯克利CS61A完結撒花
- 日拱一卒,伯克利教你用SQL處理資料
- LeetCode周賽296,難度較低的新手練習場
- 日拱一卒,伯克利教你Python核心技術,迭代器和生成器
- 日拱一卒,伯克利CS61A,教你用Python寫一個Python直譯器