LeetCode 第 194 場周賽

• 數(shù)組異或操作
• • 思路和代碼
• 保證文件名唯一
• • 思路及代碼
• 避免洪水泛濫
• • 思路及代碼
• 找到最小生成樹里的關(guān)鍵邊和偽關(guān)鍵邊
• • 思路及代碼

這次周賽比以往難很多.

數(shù)組異或操作

給你兩個整數(shù)，n 和 start 。

數(shù)組 nums 定義為：nums[i] = start + 2*i（下標(biāo)從 0 開始）且 n == nums.length 。

請返回 nums 中所有元素按位異或（XOR）后得到的結(jié)果。

思路和代碼

直接暴力

class Solution:def xorOperation(self, n: int, start: int) -> int:nums = [start + 2 * i for i in range(n)];ret = 0;for val in nums:ret ^= valreturn ret

保證文件名唯一

給你一個長度為 n 的字符串?dāng)?shù)組 names 。你將會在文件系統(tǒng)中創(chuàng)建 n 個文件夾：在第 i 分鐘，新建名為 names[i] 的文件夾。

由于兩個文件 不能 共享相同的文件名，因此如果新建文件夾使用的文件名已經(jīng)被占用，系統(tǒng)會以 (k) 的形式為新文件夾的文件名添加后綴，其中 k 是能保證文件名唯一的 最小正整數(shù) 。

返回長度為 n 的字符串?dāng)?shù)組，其中 ans[i] 是創(chuàng)建第 i 個文件夾時系統(tǒng)分配給該文件夾的實際名稱。

示例:

輸入：names = ["kaido","kaido(1)","kaido","kaido(1)"] 輸出：["kaido","kaido(1)","kaido(2)","kaido(1)(1)"] 解釋：注意，如果含后綴文件名被占用，那么系統(tǒng)也會按規(guī)則在名稱后添加新的后綴 (k) 。

思路及代碼

用一個字典保存文件下一次生成的索引, 舉個例子

['a', 'a', 'a', 'a']

那么生成的字典為

d = {'a': 4, 'a(1)':1, 'a(2)': 1, 'a(3)': 1}

例如, 如果后續(xù)加入文件a, 先從字典里面查, d['a'] = 4, 那么我們嘗試使用a(4), 發(fā)現(xiàn)成立, 這時候字典更新為

d = {'a': 5, 'a(1)':1, 'a(2)': 1, 'a(3)': 1, 'a(4)': 1}

如果下一次加入文件a(1) 那么我們知道a(1)下一次對應(yīng)生成的索引為1,那么嘗試生成a(1)(1), 也是成立的.

考慮另外一種情況, 例如現(xiàn)在字典為

d = {'a':5, 'a(1)':1, 'a(1)(1)':1}

下一次加入a(1), 首先下一次生成的索引應(yīng)該為a(1)(1), 此時發(fā)現(xiàn)被占用, 所以對索引增加操作a(1)(2) 此時成立, 此時字典需要更新a(1) 和 a(1)(2), 更新為, 通過一個循環(huán)可以處理

d = {'a':5, 'a(1)': 1 + 2, 'a(1)(1)': 1, 'a(1)(2)': 1}

代碼如下: python

class Solution:def getFolderNames(self, names: List[str]) -> List[str]:visited = collections.defaultdict(int)ret = []for name in names: if name not in visited:ret.append(name)visited[name] += 1else:n = visited[name]cnt = 0while name + '(' + str(n + cnt)+ ')' in visited:cnt += 1;visited[name] += cnt + 1;name += '(' + str(n + cnt)+ ')'ret.append(name)visited[name] += 1return ret

CPP:

class Solution { public:vector<string> getFolderNames(vector<string>& names) {unordered_map<string, int> counter;vector<string> ret;for(auto name: names){if (counter.count(name)){int &n = counter[name];int cnt = 0;while (counter.count(name + "(" + to_string(n + cnt) + ")")) ++cnt;ret.push_back(name + "(" + to_string(n + cnt) + ")");++counter[name + "(" + to_string(n + cnt) + ")"];n += cnt + 1;}else{ret.push_back(name);++counter[name];}}return ret;} };

避免洪水泛濫

你的國家有無數(shù)個湖泊，所有湖泊一開始都是空的。當(dāng)?shù)?n 個湖泊下雨的時候，如果第 n 個湖泊是空的，那么它就會裝滿水，否則這個湖泊會發(fā)生洪水。你的目標(biāo)是避免任意一個湖泊發(fā)生洪水。

給你一個整數(shù)數(shù)組 rains ，其中：

• rains[i] > 0 表示第 i 天時，第 rains[i] 個湖泊會下雨。

• rains[i] == 0 表示第 i 天沒有湖泊會下雨，你可以選擇 一個 湖泊并 抽干 這個湖泊的水。
  請返回一個數(shù)組 ans ，滿足：

• ans.length == rains.length

• 如果 rains[i] > 0 ，那么ans[i] == -1。

• 如果 rains[i] == 0 ，ans[i] 是你第 i 天選擇抽干的湖泊。

如果有多種可行解，請返回它們中的任意一個 。如果沒辦法阻止洪水，請返回一個 空的數(shù)組 。

請注意，如果你選擇抽干一個裝滿水的湖泊，它會變成一個空的湖泊。但如果你選擇抽干一個空的湖泊，那么將無事發(fā)生（詳情請看示例 4）。
示例:

輸入：rains = [69,0,0,0,69] 輸出：[-1,69,1,1,-1] 解釋：任何形如 [-1,69,x,y,-1], [-1,x,69,y,-1] 或者 [-1,x,y,69,-1] 都是可行的解，其中 1 <= x,y <= 10^9

思路及代碼

一個最樸素的思路是回溯, 即當(dāng)面某天下雨時, 隨機抽一個滿誰的湖泊, 看最后能否成立 ,超時.

如果同一個湖泊在第i天和第j被填滿, 我們應(yīng)該在i和j 之間選擇不下雨的一天, 來抽干該湖泊的水, 選擇的策略是如果其中很多天不下雨, 那么選擇在第i天之后且最接近第i天的不下雨的那天

那么思路可以是, 遍歷rains, 維護(hù)一個不下雨天的索引, 顯然這個索引是遞增的, 同時記錄被填滿的湖泊和對應(yīng)天數(shù), 當(dāng)遍歷到某一天出現(xiàn)下雨到同一個湖泊這種情況, 則找出上一次這個湖泊被填滿那天i 用二分搜索$O(\log n)$, 搜索i的 upper_bound(大于 i 的最小索引), 將次索引的結(jié)果填入對應(yīng)胡泊序號, 同時在維護(hù)的索引數(shù)據(jù)刪除這個位置的元素$O(n)$(對于 python). (Cpp可以用 set 保證查找和刪除都是$\log n$)

代碼如下:

class Solution:def avoidFlood(self, rains: List[int]) -> List[int]:import bisectids = []v = {}ret = [0] * len(rains)for idx, val in enumerate(rains):if val:ret[idx] = -1if val in v:i = bisect.bisect_right(ids, v[val])if i == len(ids):return []else:ret[ids[i]] = valids.pop(i)v[val] = idxelse:ids.append(idx)for idx, val in enumerate(ret):if val == 0:ret[idx] = 1return ret

進(jìn)一步優(yōu)化: 使用優(yōu)先隊列, 首先逆序遍歷rains, 使用數(shù)組記錄當(dāng)前下雨湖泊下一次下雨的天數(shù).

順序遍歷rains, 使用優(yōu)先隊列記錄[下一個下雨天數(shù), 對應(yīng)胡泊], 當(dāng)某天不下雨的時候, 開始出隊. Cpp 代碼如下:

class Solution { public:vector<int> avoidFlood(vector<int>& rains) {unordered_map<int, int> pos;int n = rains.size();vector<int> nxt(n, n);for(int i = n - 1; i >=0; --i){if(rains[i] == 0 || pos.count(rains[i]) == 0){pos[rains[i]] = i;}else{nxt[i] = pos[rains[i]];pos[rains[i]] = i;} }vector<int> ret;priority_queue<pair<int, int> > que;unordered_set<int> visited;for (int i = 0; i < n; ++i){if (rains[i] == 0){if(que.empty()) ret.push_back(1);else{auto p = que.top();que.pop();ret.push_back(p.second);visited.erase(p.second);}}else{if (visited.count(rains[i])) return {};if(nxt[i] != n){que.push(make_pair(-nxt[i], rains[i]));visited.insert(rains[i]);}ret.push_back(-1);}}return ret;} };

找到最小生成樹里的關(guān)鍵邊和偽關(guān)鍵邊

給你一個 n 個點的帶權(quán)無向連通圖，節(jié)點編號為 0 到 n-1 ，同時還有一個數(shù)組 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi和 toi 節(jié)點之間有一條帶權(quán)無向邊。最小生成樹 (MST) 是給定圖中邊的一個子集，它連接了所有節(jié)點且沒有環(huán)，而且這些邊的權(quán)值和最小。

請你找到給定圖中最小生成樹的所有關(guān)鍵邊和偽關(guān)鍵邊。如果從圖中刪去某條邊，會導(dǎo)致最小生成樹的權(quán)值和增加，那么我們就說它是一條關(guān)鍵邊。偽關(guān)鍵邊則是可能會出現(xiàn)在某些最小生成樹中但不會出現(xiàn)在所有最小生成樹中的邊。

請注意，你可以分別以任意順序返回關(guān)鍵邊的下標(biāo)和偽關(guān)鍵邊的下標(biāo)。

思路及代碼

參考零神題解, 由于數(shù)據(jù)量不大, 反復(fù)使用 Kruskal 算法, 關(guān)于 MST 和 Kruskal 算法, 參考我的這篇博客

其中, 注意關(guān)鍵邊和偽關(guān)鍵邊的含義:
關(guān)鍵邊: 所有 MST 共享的邊
偽關(guān)鍵邊: 任意 MST 的有一條邊, 且這條邊不是關(guān)鍵邊.

流程如下:

按照權(quán)值對邊進(jìn)行排序

調(diào)用 Kruskal 計算 MST 的值, 即為v

任意去掉一條邊, 調(diào)用 Kruskal 計算 MST 的 value, 如果v != value, 說明這條邊為關(guān)鍵邊, 記錄下所有關(guān)鍵邊

將關(guān)鍵邊先連接起來, 選定一條剩余邊, 將其強制加入 MST 中, 然后使用 Kruskal 生成 MST , 如果value == v 則這條剩余邊為偽關(guān)鍵邊.

代碼如下

class DSU{public:vector<int> parent;DSU(DSU &dsu){int n = dsu.parent.size();parent.resize(n);for(int i = 0; i < n; ++i) parent[i] = dsu.parent[i];}DSU(int n){parent.resize(n);for(int i = 0; i < n; ++i) parent[i] = i;}int find(int x){if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];}void union_(int x, int y){int rx = find(x), ry = find(y);if (rx != ry){parent[rx] = ry;}}bool isCircle(int x, int y){return find(x) == find(y);}void clear(){for(int i = 0; i < parent.size(); ++i) parent[i] = i;} };bool cmp(vector<int> &a, vector<int> &b){return a[2] < b[2];}class Solution { public:vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {int v = 0;for(int i = 0; i < edges.size(); ++i){edges[i].push_back(i);}DSU dsu(n);sort(edges.begin(), edges.end(), cmp);int cnt = 0;for(auto &edge: edges){if(!dsu.isCircle(edge[0], edge[1])){++cnt;v += edge[2];dsu.union_(edge[0], edge[1]);}if(cnt == n - 1) break;}vector<int > ret1;unordered_set<int> st;for (int cur = 0; cur < edges.size(); ++ cur){dsu.clear();int value = 0;int ccnt = 0;for(int i = 0; i < edges.size(); ++i){auto &edge = edges[i];if(i == cur) continue;if(!dsu.isCircle(edge[0], edge[1])){++ccnt;value += edge[2];dsu.union_(edge[0], edge[1]);}if(ccnt == n - 1) break;}if (value != v) {ret1.push_back(edges[cur][3]); st.insert(cur);}}vector<int> ret2;int rest = n - 1 - st.size();dsu.clear();int st_v = 0;for(auto &i: st) {dsu.union_(edges[i][0], edges[i][1]);st_v += edges[i][2];}for(int cur = 0; cur < edges.size(); ++cur){if(st.count(cur)) continue;DSU tmp(dsu);int value = st_v;int _rest = rest;if(tmp.isCircle(edges[cur][0], edges[cur][1])) continue;else{value += edges[cur][2];--_rest;tmp.union_(edges[cur][0], edges[cur][1]);}for(int i = 0; i < edges.size(); ++i){if(i == cur || st.count(i)) continue;if(!tmp.isCircle(edges[i][0], edges[i][1])){--_rest;value += edges[i][2];tmp.union_(edges[i][0], edges[i][1]);}if(_rest == 0) break;}if (_rest == 0 && value == v) ret2.push_back(edges[cur][3]);}return {ret1, ret2};} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 第 194 场周赛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。