文章目錄

• • 1. 比賽結果
  • 2. 題目
  • • 1. LeetCode 5460. 好數對的數目 easy
    • 2. LeetCode 5461. 僅含 1 的子串數 medium
    • 3. LeetCode 5211. 概率最大的路徑 medium（Dijkstra）
    • 4. LeetCode 5463. 服務中心的最佳位置 hard（最優化退火算法）

1. 比賽結果

第三題一個地方的數組長度寫錯，浪費了好多時間，成績應該可以再往前靠一下的，第四題數學最優化問題，不會。這是目前最好成績 8.88%，繼續加油！

全國排名： 468 / 5273，8.88%；全球排名： 1828 / 13984，13.1%

2. 題目

1. LeetCode 5460. 好數對的數目 easy

題目鏈接

給你一個整數數組 nums 。

如果一組數字 (i,j) 滿足 nums[i] == nums[j] 且 i < j ，就可以認為這是一組 好數對 。

返回好數對的數目。

示例 1： 輸入：nums = [1,2,3,1,1,3] 輸出：4 解釋：有 4 組好數對，分別是 (0,3), (0,4), (3,4), (2,5) ，下標從 0 開始示例 2： 輸入：nums = [1,1,1,1] 輸出：6 解釋：數組中的每組數字都是好數對示例 3： 輸入：nums = [1,2,3] 輸出：0提示： 1 <= nums.length <= 100 1 <= nums[i] <= 100

---

解題：

• 直接暴力模擬

class Solution { public:int numIdenticalPairs(vector<int>& nums) {int n = nums.size(), i, j, sum = 0;for(int i = 0; i < n; ++i){for(j = i+1; j < n; ++j)if(nums[i] == nums[j])sum++;}return sum;} };

2. LeetCode 5461. 僅含 1 的子串數 medium

題目鏈接

給你一個二進制字符串 s（僅由 ‘0’ 和 ‘1’ 組成的字符串）。

返回所有字符都為 1 的子字符串的數目。

由于答案可能很大，請你將它對 10^9 + 7 取模后返回。

示例 1： 輸入：s = "0110111" 輸出：9 解釋：共有 9 個子字符串僅由 '1' 組成 "1" -> 5 次 "11" -> 3 次 "111" -> 1 次示例 2： 輸入：s = "101" 輸出：2 解釋：子字符串 "1" 在 s 中共出現 2 次示例 3： 輸入：s = "111111" 輸出：21 解釋：每個子字符串都僅由 '1' 組成示例 4： 輸入：s = "000" 輸出：0提示： s[i] == '0' 或 s[i] == '1' 1 <= s.length <= 10^5

---

解題：

• 找到連續為1的個數，該區間內的符合要求的子串個數為 $n?(n+1)/2$

class Solution { public:int numSub(string s) {int i,j,n=s.size(),sum = 0, mod = int(1e9+7);for(i = 0; i < n; ++i){if(s[i]=='1'){j = i;while(j < n && s[j]=='1'){j++; }long long n = j-i;sum = (sum+((n*(n+1)/2)%mod))%mod;i = j-1;}}return sum%mod;} };

3. LeetCode 5211. 概率最大的路徑 medium（Dijkstra）

題目鏈接

給你一個由 n 個節點（下標從 0 開始）組成的無向加權圖，該圖由一個描述邊的列表組成，
其中 edges[i] = [a, b] 表示連接節點 a 和 b 的一條無向邊，且該邊遍歷成功的概率為 succProb[i] 。

指定兩個節點分別作為起點 start 和終點 end ，請你找出從起點到終點成功概率最大的路徑，并返回其成功概率。

如果不存在從 start 到 end 的路徑，請 返回 0 。
只要答案與標準答案的誤差不超過 1e-5 ，就會被視作正確答案。

示例 1：

輸入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 輸出：0.25000 解釋：從起點到終點有兩條路徑，其中一條的成功概率為 0.2 ， 而另一條為 0.5 * 0.5 = 0.25

示例 2：

輸入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2 輸出：0.30000

示例 3：

輸入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 輸出：0.00000 解釋：節點 0 和 節點 2 之間不存在路徑提示： 2 <= n <= 10^4 0 <= start, end < n start != end 0 <= a, b < n a != b 0 <= succProb.length == edges.length <= 2*10^4 0 <= succProb[i] <= 1 每兩個節點之間最多有一條邊

---

解題：

• 迪杰斯特拉 最短路徑+優先隊列優化

struct cmp {bool operator()(const pair<int,double>& a, const pair<int,double>& b)const{return a.second < b.second;//概率大的優先} }; class Solution { public:double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {unordered_map<int,unordered_map<int,double>> m;for(int i = 0; i < edges.size(); ++i){m[edges[i][0]][edges[i][1]] = succProb[i];m[edges[i][1]][edges[i][0]] = succProb[i];}vector<double> prob(n,0.0);prob[start] = 1.0;priority_queue<pair<int,double>,vector<pair<int,double>>,cmp> q;q.push({start, 1.0});while(!q.empty()){int i = q.top().first, j;double p = q.top().second, pij;q.pop();for(auto it = m[i].begin(); it != m[i].end(); ++it){j = it->first;pij = it->second;if(p*pij > prob[j]){prob[j] = p*pij;q.push({j, prob[j]});}}}return prob[end];} };

4. LeetCode 5463. 服務中心的最佳位置 hard（最優化退火算法）

題目鏈接

一家快遞公司希望在新城市建立新的服務中心。
公司統計了該城市所有客戶在二維地圖上的坐標，并希望能夠以此為依據為新的服務中心選址：使服務中心 到所有客戶的歐幾里得距離的總和最小 。

給你一個數組 positions ，其中 positions[i] = [xi, yi] 表示第 i 個客戶在二維地圖上的位置，返回到所有客戶的 歐幾里得距離的最小總和 。

換句話說，請你為服務中心選址，該位置的坐標 [xcentre, ycentre] 需要使下面的公式取到最小值：

$$\sum _{i=0}^{n?1}\sqrt{{\left(x_{\text{centre}}?x_i\right)}^2+{\left(y_{\text{centre}}?y_i\right)}^2}$$

與真實值誤差在 10^-5 之內的答案將被視作正確答案。

示例 1：

輸入：positions = [[0,1],[1,0],[1,2],[2,1]] 輸出：4.00000 解釋：如圖所示，你可以選 [xcentre, ycentre] = [1, 1] 作為新中心的位置， 這樣一來到每個客戶的距離就都是 1，所有距離之和為 4 ，這也是可以找到的最小值。

示例 2：

輸入：positions = [[1,1],[3,3]] 輸出：2.82843 解釋：歐幾里得距離可能的最小總和為 sqrt(2) + sqrt(2) = 2.82843示例 3： 輸入：positions = [[1,1]] 輸出：0.00000示例 4： 輸入：positions = [[1,1],[0,0],[2,0]] 輸出：2.73205 解釋：乍一看，你可能會將中心定在 [1, 0] 并期待能夠得到最小總和， 但是如果選址在 [1, 0] 距離總和為 3 如果將位置選在 [1.0, 0.5773502711] ，距離總和將會變為 2.73205 當心精度問題！示例 5： 輸入：positions = [[0,1],[3,2],[4,5],[7,6],[8,9],[11,1],[2,12]] 輸出：32.94036 解釋：你可以用 [4.3460852395, 4.9813795505] 作為新中心的位置提示： 1 <= positions.length <= 50 positions[i].length == 2 0 <= positions[i][0], positions[i][1] <= 100

---

解題：

• 參考第二名大佬的答案寫的
• 大家說是退火算法，動態調整下一次迭代的步長，又有證明目標是凸函數，局部最小值就是全局最小值

class Solution { public:double getMinDistSum(vector<vector<int>>& positions) {int n = positions.size(), k;double x0, y0, xi = 0, yi = 0, nx, ny;for(int i = 0; i < n; ++i){xi += positions[i][0];yi += positions[i][1];}x0 = xi/n;y0 = yi/n;//均值作為初始值vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};double eps = 1e-6, step = 100, d, dis = calSumDis(x0,y0,positions);while(step > eps){bool down = false;for(k = 0; k < 4; ++k){nx = x0 + dir[k][0]*step;ny = y0 + dir[k][1]*step;d = calSumDis(nx, ny, positions);if(d < dis){dis = d;x0 = nx;y0 = ny;down = true;break;}}if(!down)//沒有降低，說明步長太大step /= 2.0;}return dis;}double calSumDis(double x0, double y0, vector<vector<int>>& p){double d = 0.0;for(auto& pi : p)d += sqrt((x0-pi[0])*(x0-pi[0])+(y0-pi[1])*(y0-pi[1]));return d;} };

20 ms 7.8 MB

while(step > eps){for(k = 0; k < 4; ++k){nx = x0 + dir[k][0]*step;ny = y0 + dir[k][1]*step;d = calSumDis(nx, ny, positions);if(d < dis){dis = d;x0 = nx;y0 = ny;}}step *= 0.95;//或者直接每次都慢慢降低步長}

60 ms 8.1 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 第 197 场周赛（468/5273，前8.88%）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。