LeetCode 第 206 场周赛（733/4491，前16.3%）
生活随笔
收集整理的這篇文章主要介紹了
LeetCode 第 206 场周赛（733/4491，前16.3%）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 1. 比賽結果
- 2. 題目
- 1. LeetCode 5511. 二進制矩陣中的特殊位置 easy
- 2. LeetCode 5512. 統計不開心的朋友 medium
- 3. LeetCode 5513. 連接所有點的最小費用 medium
- 4. LeetCode 5514. 檢查字符串是否可以通過排序子字符串得到另一個字符串 hard
1. 比賽結果
做出來3題。繼續加油！
全國排名： 733 / 4491，16.3%；全球排名： 2140 / 13291，16.1%
2. 題目
1. LeetCode 5511. 二進制矩陣中的特殊位置 easy
題目鏈接
給你一個大小為 rows x cols 的矩陣 mat，其中 mat[i][j] 是 0 或 1，請返回 矩陣 mat 中特殊位置的數目 。
特殊位置 定義：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均為 0（行和列的下標均 從 0 開始 ），則位置 (i, j) 被稱為特殊位置。
示例 1： 輸入：mat = [[1,0,0],[0,0,1],[1,0,0]] 輸出：1 解釋：(1,2) 是一個特殊位置， 因為 mat[1][2] == 1 且所處的行和列上所有其他元素都是 0示例 2： 輸入：mat = [[1,0,0],[0,1,0],[0,0,1]] 輸出：3 解釋：(0,0), (1,1) 和 (2,2) 都是特殊位置示例 3： 輸入：mat = [[0,0,0,1],[1,0,0,0],[0,1,1,0],[0,0,0,0]] 輸出：2示例 4： 輸入：mat = [[0,0,0,0,0],[1,0,0,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]] 輸出：3提示： rows == mat.length cols == mat[i].length 1 <= rows, cols <= 100 mat[i][j] 是 0 或 1解題：
- 先計算出每行，每列 1的個數
- 再次遍歷矩陣，數字為1，且行列1的個數均為1
48 ms 13.1 MB
2. LeetCode 5512. 統計不開心的朋友 medium
題目鏈接
給你一份 n 位朋友的親近程度列表，其中 n 總是 偶數 。
對每位朋友 i，preferences[i] 包含一份 按親近程度從高到低排列 的朋友列表。
換句話說，排在列表前面的朋友與 i 的親近程度比排在列表后面的朋友更高。
每個列表中的朋友均以 0 到 n-1 之間的整數表示。
所有的朋友被分成幾對，配對情況以列表 pairs 給出，其中 pairs[i] = [xi, yi] 表示 xi 與 yi 配對，且 yi 與 xi 配對。
但是，這樣的配對情況可能會是其中部分朋友感到不開心。
在 x 與 y 配對 且 u 與 v 配對的情況下，如果同時滿足下述兩個條件，x 就會不開心：
- x 與 u 的親近程度勝過 x 與 y，且
- u 與 x 的親近程度勝過 u 與 v
返回 不開心的朋友的數目 。
示例 1： 輸入：n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]] 輸出：2 解釋： 朋友 1 不開心，因為： - 1 與 0 配對，但 1 與 3 的親近程度比 1 與 0 高，且 - 3 與 1 的親近程度比 3 與 2 高。 朋友 3 不開心，因為： - 3 與 2 配對，但 3 與 1 的親近程度比 3 與 2 高，且 - 1 與 3 的親近程度比 1 與 0 高。 朋友 0 和 2 都是開心的。示例 2： 輸入：n = 2, preferences = [[1], [0]], pairs = [[1, 0]] 輸出：0 解釋：朋友 0 和 1 都開心。示例 3： 輸入：n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]] 輸出：4 提示： 2 <= n <= 500 n 是偶數 preferences.length == n preferences[i].length == n - 1 0 <= preferences[i][j] <= n - 1 preferences[i] 不包含 i preferences[i] 中的所有值都是獨一無二的 pairs.length == n/2 pairs[i].length == 2 xi != yi 0 <= xi, yi <= n - 1 每位朋友都 恰好 被包含在一對中解題：
- 先預處理出，每個人的列表里的關系值大小 rela
- 然后按題意模擬
144 ms 26.2 MB
3. LeetCode 5513. 連接所有點的最小費用 medium
題目鏈接
給你一個points 數組，表示 2D 平面上的一些點，其中 points[i] = [xi, yi] 。
連接點 [xi, yi] 和點 [xj, yj] 的費用為它們之間的 曼哈頓距離 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的絕對值。
請你返回將所有點連接的最小總費用。
只有任意兩點之間 有且僅有 一條簡單路徑時，才認為所有點都已連接。
示例 1：
輸入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 輸出：20 解釋： 我們可以按照上圖所示連接所有點得到最小總費用，總費用為 20 。 注意到任意兩個點之間只有唯一一條路徑互相到達。 示例 2： 輸入：points = [[3,12],[-2,5],[-4,1]] 輸出：18示例 3： 輸入：points = [[0,0],[1,1],[1,0],[-1,1]] 輸出：4示例 4： 輸入：points = [[-1000000,-1000000],[1000000,1000000]] 輸出：4000000示例 5： 輸入：points = [[0,0]] 輸出：0提示： 1 <= points.length <= 1000 -106 <= xi, yi <= 106 所有點 (xi, yi) 兩兩不同。解題：
- 類似題目：LeetCode 1135. 最低成本聯通所有城市（最小生成樹+排序+并查集）
prim算法：vis標記點，把該點相連的邊全部加入優先隊列，取出最小的邊，邊的另一端點的所有邊加入隊列
struct cmp {bool operator()(const pair<int,int>& a, const pair<int,int>& b) const{return a.second > b.second;//小頂堆, 距離小的優先} }; class Solution { public:int minCostConnectPoints(vector<vector<int>>& points) {int n = points.size();if(n == 1) return 0;vector<bool> vis(n, false);vector<vector<pair<int,int>>> edges(n,vector<pair<int,int>>());for(int i = 0, j, d; i < n; i++){for(j = i+1; j < n; j++){d = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]);edges[i].push_back({j,d});edges[j].push_back({i,d});}}priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> q;int to, distance, total = 0, edge_num = 0;vis[0] = true;for(auto& e : edges[0])q.push(e); while(!q.empty()){to = q.top().first;distance = q.top().second;q.pop();if(!vis[to]){vis[to] = true;total += distance;edge_num++;if(edge_num == n-1)return total;for(auto& e : edges[to])q.push(e); }}return -1;} };1288 ms 162.2 MB
kruskal 算法：對所有的邊排序，短的優先，用并查集檢查邊的兩個端點是否屬于一個集合（不屬于的話，加入邊，合并兩個端點）
class dsu{ public:vector<int> f;dsu(int n){f.resize(n);for (int i = 0; i < n; ++i)f[i] = i;}void merge(int a, int b){int fa = find(a), fb = find(b);f[fa] = fb;}int find(int a){if(a == f[a])return a;return f[a] = find(f[a]);} }; struct edge{int d;int p1, p2;edge(int dis, int a, int b){d = dis, p1 = a, p2 = b;} }; class Solution { public:int minCostConnectPoints(vector<vector<int>>& points) {int n = points.size();if(n == 1) return 0;dsu u(n);vector<edge> e(n*(n-1)/2, edge(0,0,0));for(int i = 0, k = 0, j, d; i < n; i++){for(j = i+1; j < n; j++){d = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]);e[k++] = edge(d,i,j);}}sort(e.begin(), e.end(),[&](auto& a, auto& b){return a.d < b.d;});int N = n-1, p1, p2, d, ans = 0, f1, f2;for(int i = 0; i < e.size(); ++i){p1 = e[i].p1, p2 = e[i].p2;d = e[i].d;f1 = u.find(p1), f2 = u.find(p2);if(f1 == f2)continue;ans += d;u.f[f1] = f2;if(--N == 0)break;}return ans;} };1184 ms 31.6 MB
4. LeetCode 5514. 檢查字符串是否可以通過排序子字符串得到另一個字符串 hard
題目鏈接
給你兩個字符串 s 和 t ，請你通過若干次以下操作將字符串 s 轉化成字符串 t ：
- 選擇 s 中一個 非空 子字符串并將它包含的字符就地 升序 排序。
比方說，對下劃線所示的子字符串進行操作可以由 “1423 4” 得到 “12344” 。
如果可以將字符串 s 變成 t ，返回 true 。否則，返回 false 。
一個 子字符串 定義為一個字符串中連續的若干字符。
示例 1： 輸入：s = "84532", t = "34852" 輸出：true 解釋：你可以按以下操作將 s 轉變為 t ： "84532" （從下標 2 到下標 3）-> "84352" "84352" （從下標 0 到下標 2） -> "34852"示例 2： 輸入：s = "34521", t = "23415" 輸出：true 解釋：你可以按以下操作將 s 轉變為 t ： "34521" -> "23451" "23451" -> "23415"示例 3： 輸入：s = "12345", t = "12435" 輸出：false示例 4： 輸入：s = "1", t = "2" 輸出：false提示： s.length == t.length 1 <= s.length <= 105 s 和 t 都只包含數字字符，即 '0' 到 '9' 。解題：
參考zerotrac2 大佬的題解
class Solution { public:bool isTransformable(string s, string t) {int n = s.size();vector<queue<int>> pos(10);for(int i = 0; i < n; ++i) pos[s[i]-'0'].push(i);for(int i = 0; i < n; ++i){if(pos[t[i]-'0'].empty())return false;//字符內容對不上for(int d = 0; d < t[i]-'0'; ++d){if(!pos[d].empty() && pos[d].front() < pos[t[i]-'0'].front())//前面有數字比我小的，升序不可能做到return false;}pos[t[i]-'0'].pop();}return true;} };168 ms 16.9 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 第 206 场周赛（733/4491，前16.3%）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： LeetCode MySQL 1527.
- 下一篇： 阿里云 超级码力在线编程大赛初赛 第2场