[算法]LeetCode第194场周赛202006021
第194場(chǎng)周賽
20200621
1486. 數(shù)組異或操作
題目描述1
給你兩個(gè)整數(shù)，n 和 start 。
數(shù)組 nums 定義為：nums[i] = start + 2*i（下標(biāo)從 0 開始）且 n == nums.length 。
請(qǐng)返回 nums 中所有元素按位異或（XOR）后得到的結(jié)果。
示例 1：
輸入：n = 5, start = 0 輸出：8 解釋：數(shù)組 nums 為 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。"^" 為按位異或 XOR 運(yùn)算符。示例 2：
輸入：n = 4, start = 3 輸出：8 解釋：數(shù)組 nums 為 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.示例 3：
輸入：n = 1, start = 7 輸出：7示例 4：
輸入：n = 10, start = 5 輸出：2提示：
- 1 <= n <= 1000
- 0 <= start <= 1000
- n == nums.length
Solution1
class Solution {public int xorOperation(int n, int start) {int ans = start;for(int i = 1; i < n; i++){ans ^= (start + 2 * i);}return ans;} }1487. 保證文件名唯一
題目描述2
給你一個(gè)長(zhǎng)度為 n 的字符串?dāng)?shù)組 names 。你將會(huì)在文件系統(tǒng)中創(chuàng)建 n 個(gè)文件夾：在第 i 分鐘，新建名為 names[i] 的文件夾。
由于兩個(gè)文件 不能 共享相同的文件名，因此如果新建文件夾使用的文件名已經(jīng)被占用，系統(tǒng)會(huì)以 (k) 的形式為新文件夾的文件名添加后綴，其中 k 是能保證文件名唯一的 最小正整數(shù) 。
返回長(zhǎng)度為 n 的字符串?dāng)?shù)組，其中 ans[i] 是創(chuàng)建第 i 個(gè)文件夾時(shí)系統(tǒng)分配給該文件夾的實(shí)際名稱。
示例 1：
輸入：names = ["pes","fifa","gta","pes(2019)"] 輸出：["pes","fifa","gta","pes(2019)"] 解釋：文件系統(tǒng)將會(huì)這樣創(chuàng)建文件名： "pes" --> 之前未分配，仍為 "pes" "fifa" --> 之前未分配，仍為 "fifa" "gta" --> 之前未分配，仍為 "gta" "pes(2019)" --> 之前未分配，仍為 "pes(2019)"示例 2：
輸入：names = ["gta","gta(1)","gta","avalon"] 輸出：["gta","gta(1)","gta(2)","avalon"] 解釋：文件系統(tǒng)將會(huì)這樣創(chuàng)建文件名： "gta" --> 之前未分配，仍為 "gta" "gta(1)" --> 之前未分配，仍為 "gta(1)" "gta" --> 文件名被占用，系統(tǒng)為該名稱添加后綴 (k)，由于 "gta(1)" 也被占用，所以 k = 2 。實(shí)際創(chuàng)建的文件名為 "gta(2)" 。 "avalon" --> 之前未分配，仍為 "avalon"示例 3：
輸入：names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"] 輸出：["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"] 解釋：當(dāng)創(chuàng)建最后一個(gè)文件夾時(shí)，最小的正有效 k 為 4 ，文件名變?yōu)?"onepiece(4)"。示例 4：
輸入：names = ["wano","wano","wano","wano"] 輸出：["wano","wano(1)","wano(2)","wano(3)"] 解釋：每次創(chuàng)建文件夾 "wano" 時(shí)，只需增加后綴中 k 的值即可。示例 5：
輸入：names = ["kaido","kaido(1)","kaido","kaido(1)"] 輸出：["kaido","kaido(1)","kaido(2)","kaido(1)(1)"] 解釋：注意，如果含后綴文件名被占用，那么系統(tǒng)也會(huì)按規(guī)則在名稱后添加新的后綴 (k) 。提示：
- 1 <= names.length <= 5 * 10^4
- 1 <= names[i].length <= 20
- names[i] 由小寫英文字母、數(shù)字和/或圓括號(hào)組成。
Solution2
首先想到的是用hashset來判斷出沒出現(xiàn)過，但是會(huì)超時(shí)
要改成hashmap，用map里的value用來保存key出現(xiàn)的次數(shù)，這樣就避免了超時(shí)
//這樣寫會(huì)超時(shí) class Solution {public String[] getFolderNames(String[] names) {Set<String> set = new HashSet<>();String[] ans = new String[names.length];int i = 0;for(String name : names){if(!set.contains(name)){set.add(name);ans[i++] = name;}else{//存在 加后綴int num = 1;String name1 = name;while(set.contains(name)){String k = String.valueOf(num);name = name1 + "(" + k + ")";num++;}set.add(name);ans[i++] = name;}}return ans;} } class Solution {public String[] getFolderNames(String[] names) {// 用map里的value用來保存key出現(xiàn)的次數(shù)，這樣就避免了超時(shí)Map<String,Integer> map = new HashMap<>();String[] ans = new String[names.length];int i = 0;for(String name : names){if(!map.containsKey(name)){//map中不存在，直接寫入答案對(duì)應(yīng)位置map.put(name, 1);ans[i++] = name;}else{//map中存在//取出之前出現(xiàn)的次數(shù)int count = map.get(name);// 后面有沒有出現(xiàn)過while(map.containsKey(name + "(" + count + ")")){count++;}// 更新mapmap.put(name + "(" + count + ")", 1);map.put(name, map.get(name) + 1);ans[i++] = name + "(" + count + ")";}}return ans;} }1488. 避免洪水泛濫
題目描述3
你的國(guó)家有無數(shù)個(gè)湖泊，所有湖泊一開始都是空的。當(dāng)?shù)?n 個(gè)湖泊下雨的時(shí)候，如果第 n 個(gè)湖泊是空的，那么它就會(huì)裝滿水，否則這個(gè)湖泊會(huì)發(fā)生洪水。你的目標(biāo)是避免任意一個(gè)湖泊發(fā)生洪水。
給你一個(gè)整數(shù)數(shù)組 rains ，其中：
rains[i] > 0 表示第 i 天時(shí)，第 rains[i] 個(gè)湖泊會(huì)下雨。
rains[i] == 0 表示第 i 天沒有湖泊會(huì)下雨，你可以選擇 一個(gè) 湖泊并 抽干 這個(gè)湖泊的水。
請(qǐng)返回一個(gè)數(shù)組 ans ，滿足：
ans.length == rains.length
如果 rains[i] > 0 ，那么ans[i] == -1 。
如果 rains[i] == 0 ，ans[i] 是你第 i 天選擇抽干的湖泊。
如果有多種可行解，請(qǐng)返回它們中的 任意一個(gè) 。如果沒辦法阻止洪水，請(qǐng)返回一個(gè) 空的數(shù)組 。
請(qǐng)注意，如果你選擇抽干一個(gè)裝滿水的湖泊，它會(huì)變成一個(gè)空的湖泊。但如果你選擇抽干一個(gè)空的湖泊，那么將無事發(fā)生（詳情請(qǐng)看示例 4）。
示例 1：
輸入：rains = [1,2,3,4] 輸出：[-1,-1,-1,-1] 解釋：第一天后，裝滿水的湖泊包括 [1] 第二天后，裝滿水的湖泊包括 [1,2] 第三天后，裝滿水的湖泊包括 [1,2,3] 第四天后，裝滿水的湖泊包括 [1,2,3,4] 沒有哪一天你可以抽干任何湖泊的水，也沒有湖泊會(huì)發(fā)生洪水。示例 2：
輸入：rains = [1,2,0,0,2,1] 輸出：[-1,-1,2,1,-1,-1] 解釋：第一天后，裝滿水的湖泊包括 [1] 第二天后，裝滿水的湖泊包括 [1,2] 第三天后，我們抽干湖泊 2 。所以剩下裝滿水的湖泊包括 [1] 第四天后，我們抽干湖泊 1 。所以暫時(shí)沒有裝滿水的湖泊了。 第五天后，裝滿水的湖泊包括 [2]。 第六天后，裝滿水的湖泊包括 [1,2]。 可以看出，這個(gè)方案下不會(huì)有洪水發(fā)生。同時(shí)， [-1,-1,1,2,-1,-1] 也是另一個(gè)可行的沒有洪水的方案。示例 3：
輸入：rains = [1,2,0,1,2] 輸出：[] 解釋：第二天后，裝滿水的湖泊包括 [1,2]。我們可以在第三天抽干一個(gè)湖泊的水。 但第三天后，湖泊 1 和 2 都會(huì)再次下雨，所以不管我們第三天抽干哪個(gè)湖泊的水，另一個(gè)湖泊都會(huì)發(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示例 5：
輸入：rains = [10,20,20] 輸出：[] 解釋：由于湖泊 20 會(huì)連續(xù)下 2 天的雨，所以沒有沒有辦法阻止洪水。提示：
- 1 <= rains.length <= 10^5
- 0 <= rains[i] <= 10^9
Solution3
優(yōu)先隊(duì)列+貪心，每次抽干最近要下雨的湖
class Solution {public int[] avoidFlood(int[] rains) {int n = rains.length;int[] ans = new int[n];int[] next = new int[n];//記錄每個(gè)湖下一次的下雨時(shí)間Arrays.fill(next, n+1);Map<Integer, Integer> tm = new HashMap<>();//每個(gè)湖最早下雨的時(shí)間 湖-天數(shù)for(int i = n-1; i >= 0; i--){int r = rains[i];if(r > 0){if(tm.containsKey(r)){next[i] = tm.get(r);}tm.put(r, i); //更新第r個(gè)湖下雨的時(shí)間}}Map<Integer, Boolean> st = new HashMap<>();//湖泊的狀態(tài)PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>((o1, o2) -> o1.getKey()-o2.getKey());//小根堆,value-湖泊編號(hào)，key-這個(gè)湖泊下一次最早哪天下雨for(int i = 0; i < n; i++){int r = rains[i];if(r > 0){// 如果這天下雨了if(st.getOrDefault(r, false) == true){//如果這個(gè)湖泊之前已經(jīng)有水了，則洪水發(fā)生return new int[]{};}st.put(r, true);pq.offer(new Pair(next[i], r));ans[i] = -1;}else{// 如果這天沒有下雨，要抽水if(pq.isEmpty()){ans[i] = 1;//如果堆是空的，則抽第一個(gè)湖}else{//取出最近要下雨的，這個(gè)湖抽水的需求最迫切。也就是堆的key最小的Pair<Integer, Integer> t = pq.poll();st.put(t.getValue(), false);ans[i] = t.getValue();}}}return ans;} }參考：
- https://www.bilibili.com/video/BV1ja4y1Y7nk
- https://leetcode-cn.com/problems/avoid-flood-in-the-city/solution/you-xian-ji-dui-lie-tan-xin-mei-ci-xian-chou-gan-z/
1489. 找到最小生成樹里的關(guān)鍵邊和偽關(guān)鍵邊
題目描述4
給你一個(gè) n 個(gè)點(diǎn)的帶權(quán)無向連通圖，節(jié)點(diǎn)編號(hào)為 0 到 n-1 ，同時(shí)還有一個(gè)數(shù)組 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 節(jié)點(diǎn)之間有一條帶權(quán)無向邊。最小生成樹 (MST) 是給定圖中邊的一個(gè)子集，它連接了所有節(jié)點(diǎn)且沒有環(huán)，而且這些邊的權(quán)值和最小。
請(qǐng)你找到給定圖中最小生成樹的所有關(guān)鍵邊和偽關(guān)鍵邊。如果從圖中刪去某條邊，會(huì)導(dǎo)致最小生成樹的權(quán)值和增加，那么我們就說它是一條關(guān)鍵邊。偽關(guān)鍵邊則是可能會(huì)出現(xiàn)在某些最小生成樹中但不會(huì)出現(xiàn)在所有最小生成樹中的邊。
請(qǐng)注意，你可以分別以任意順序返回關(guān)鍵邊的下標(biāo)和偽關(guān)鍵邊的下標(biāo)。
提示：
- 2 <= n <= 100
- 1 <= edges.length <= min(200, n * (n - 1) / 2)
- edges[i].length == 3
- 0 <= fromi < toi < n
- 1 <= weighti <= 1000
- 所有 (fromi, toi) 數(shù)對(duì)都是互不相同的。
Solution4
最小生成樹：構(gòu)造最小生成樹的算法主要有：克魯斯卡爾（Kruskal）算法和普利姆（Prim）算法
class Solution {/** 思路詳解：* 1. 整體思路：* a. 通過Kruska算法（加邊法）可以計(jì)算出最小生成樹MST的最小權(quán)值minCost* b. 遍歷所有的邊:* i. 如果去掉這個(gè)邊，MST的最小權(quán)值 > minCost，說明這個(gè)邊是一個(gè)關(guān)鍵邊* ii. 否則，說明如果去掉這個(gè)邊，MST的最小權(quán)值 == minCost，這個(gè)又分為兩種情況* 1) 如果包含這個(gè)邊的MST的最小權(quán)值 == minCost, 說明這個(gè)邊是一個(gè)偽關(guān)鍵邊* 2) 否則，說明包含這個(gè)邊的MST的最小權(quán)值 > minCost，說明這個(gè)邊一定不是關(guān)鍵邊* 2. getMSTExclude / getMSTInclude 算法：* a. 初始化ends數(shù)組，值為-1，表示每個(gè)節(jié)點(diǎn)都是樹的終點(diǎn)* b. newEdges是按照權(quán)值從小到大排列的有序數(shù)組，遍歷數(shù)組，對(duì)于每條邊的兩個(gè)節(jié)點(diǎn)，如果他們不連通，則連接這兩個(gè)節(jié)點(diǎn)對(duì)應(yīng)的兩顆樹* c. 最終的結(jié)果有兩種可能，通過n-1條邊把樹連通為一顆樹（返回邊權(quán)值），或者最終不足以連通為一顆樹(返回最大整數(shù))*/public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {int height = edges.length;int[][] newEdges = new int[height][4];for(int i = 0; i < height; i++){newEdges[i][0] = edges[i][0];newEdges[i][1] = edges[i][1];newEdges[i][2] = edges[i][2];newEdges[i][3] = i;}Arrays.sort(newEdges, new Comparator<int[]>(){@Overridepublic int compare(int[] o1, int[] o2){return o1[2] - o2[2];}});List<Integer> realCri = new ArrayList<>();List<Integer> fakeCri = new ArrayList<>();int minCost = getMSTExclude(n, newEdges, -1);for(int i = 0; i < height; i++){if(getMSTExclude(n, newEdges, i) > minCost){realCri.add(i);}else if(getMSTInclude(n, newEdges, i) == minCost){fakeCri.add(i);}}List<List<Integer>> ans = new ArrayList<>();ans.add(realCri);ans.add(fakeCri);return ans;}//不包含邊edge的MSTprivate int getMSTExclude(int n, int[][] edges, int edge){int height = edges.length;int[] ends = new int[n];//記錄每個(gè)節(jié)點(diǎn)指向的終點(diǎn)Arrays.fill(ends, -1);//-1代表指向自己int cost = 0;int counter = 0;for(int[] e : edges){if(e[3] == edge){//排除edge邊continue;}int end1 = getEnd(ends, e[0]);int end2 = getEnd(ends, e[1]);if(end1 != end2){//連接兩條邊ends[end1] = end2;cost += e[2];counter++;}}return counter == n - 1 ? cost : Integer.MAX_VALUE;}//包含邊edge的MSTprivate int getMSTInclude(int n, int[][] edges, int edge){int height = edges.length;int[] ends = new int[n];//記錄每個(gè)節(jié)點(diǎn)指向的終點(diǎn)Arrays.fill(ends, -1);//-1代表指向自己int cost = 0;int counter = 0;//連接edge邊for(int[] e : edges){if(e[3] == edge){ends[e[0]] = e[1];cost += e[2];counter++;}}for(int[] e : edges){int end1 = getEnd(ends, e[0]);int end2 = getEnd(ends, e[1]);if(end1 != end2){//連接兩條邊ends[end1] = end2;cost += e[2];counter++;}}return counter == n - 1 ? cost : Integer.MAX_VALUE;}//值為-1的才是樹的終點(diǎn)private int getEnd(int[] ends, int node){if(ends[node] == -1){return node;}else{ends[node] = getEnd(ends, ends[node]);return ends[node];}} }參考鏈接：https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solution/kruskasuan-fa-by-xiao-hei-34/
我的公眾號(hào):GitKid
暫時(shí)每日分享LeetCode，我在不斷學(xué)習(xí)的過程中，公眾號(hào)也在不斷充實(shí)，歡迎大家掃碼關(guān)注。
TODO:《劍指offer》系列
總結(jié)
以上是生活随笔為你收集整理的[算法]LeetCode第194场周赛202006021的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Typescript(一)
- 下一篇： 【解决方案】严防夏天溺水，开启EasyD