文章目錄

• • 1. 比賽結果
  • 2. 題目
  • • 1. LeetCode 5479. 千位分隔數 easy
    • 2. LeetCode 5480. 可以到達所有點的最少點數目 medium
    • 3. LeetCode 5481. 得到目標數組的最少函數調用次數 medium
    • 4. LeetCode 5482. 二維網格圖中探測環 hard

1. 比賽結果

題目比較簡單，全部做出來了。繼續加油！

全國排名： 511 / 3304，15.5%；全球排名： 1626 / 11366，14.3%

2. 題目

1. LeetCode 5479. 千位分隔數 easy

題目鏈接

給你一個整數 n，請你每隔三位添加點（即 "." 符號）作為千位分隔符，并將結果以字符串格式返回。

示例 1： 輸入：n = 987 輸出："987"示例 2： 輸入：n = 1234 輸出："1.234"示例 3： 輸入：n = 123456789 輸出："123.456.789"示例 4： 輸入：n = 0 輸出："0"提示： 0 <= n < 2^31

---

解題：

• 按題意模擬即可

class Solution { public:string thousandSeparator(int n) {string num = to_string(n), ans;int k = 3;for(int i = int(num.size())-1; i >= 0; i--){if(k == 0){ans = "." + ans;//3位到了，加點k = 3;//重置3i++;//該位還需要再次訪問}else{ans = num[i] + ans;//沒到三次，加字符k--;}}return ans;} };

0 ms 5.9 MB

2. LeetCode 5480. 可以到達所有點的最少點數目 medium

題目鏈接

給你一個 有向無環圖 ， n 個節點編號為 0 到 n-1 ，以及一個邊數組 edges ，其中 edges[i] = [fromi, toi] 表示一條從點 fromi 到點 toi 的有向邊。

找到最小的點集使得從這些點出發能到達圖中所有點。題目保證解存在且唯一。

你可以以任意順序返回這些節點編號。

示例 1：

輸入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] 輸出：[0,3] 解釋：從單個節點出發無法到達所有節點。 從 0 出發我們可以到達 [0,1,2,5] 。 從 3 出發我們可以到達 [3,4,2,5] 。 所以我們輸出 [0,3] 。

示例 2：

輸入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] 輸出：[0,2,3] 解釋：注意到節點 0，3 和 2 無法從其他節點到達， 所以我們必須將它們包含在結果點集中，這些點都能到達節點 1 和 4 。提示： 2 <= n <= 10^5 1 <= edges.length <= min(10^5, n * (n - 1) / 2) edges[i].length == 2 0 <= fromi, toi < n 所有點對 (fromi, toi) 互不相同。

---

解題：

• 檢查入度為0的節點

class Solution { public:vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {vector<int> indegree(n, 0), ans;for(auto& e : edges) {indegree[e[1]]++;}for(int i = 0; i < n; i++){if(indegree[i] == 0)ans.push_back(i);}return ans;} };

696 ms 94.5 MB

3. LeetCode 5481. 得到目標數組的最少函數調用次數 medium

題目鏈接

給你一個與 nums 大小相同 且 初始值 全為 0 的數組 arr ，請你調用以上函數得到整數數組 nums 。

請你返回將 arr 變成 nums 的最少函數調用次數。

答案保證在 32 位有符號整數以內。

示例 1： 輸入：nums = [1,5] 輸出：5 解釋：給第二個數加 1 ：[0, 0] 變成 [0, 1] （1 次操作）。 將所有數字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。 給兩個數字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。 總操作次數為：1 + 2 + 2 = 5 。示例 2： 輸入：nums = [2,2] 輸出：3 解釋：給兩個數字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。 將所有數字乘以 2 ： [1, 1] -> [2, 2] （1 次操作）。 總操作次數為： 2 + 1 = 3 。示例 3： 輸入：nums = [4,2,5] 輸出：6 解釋：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5] （nums 數組）。示例 4： 輸入：nums = [3,2,2,4] 輸出：7示例 5： 輸入：nums = [2,4,8,16] 輸出：8提示： 1 <= nums.length <= 10^5 0 <= nums[i] <= 10^9

---

解題：

• 數組要乘以2的次數是最大的那個數，可以被2除的次數
• 然后每個數不能被2整除時，就 -1，調用次數 +1

class Solution { public:int minOperations(vector<int>& nums) {int s = 0, maxn = 0;for(int i = 0; i < nums.size(); ++i){maxn = max(maxn, nums[i]);}for(int i = 0; i < nums.size(); ++i){while(nums[i]){if(nums[i]&1)//不能整除{s++;//調用nums[i]--;}else{nums[i] /= 2;}}}while(maxn>1)//大于1時{maxn /= 2;//最大的數能被2除的次數s++;}return s;} };

188 ms 25.5 MB

4. LeetCode 5482. 二維網格圖中探測環 hard

題目鏈接

給你一個二維字符網格數組 grid ，大小為 m x n ，你需要檢查 grid 中是否存在 相同值 形成的環。

一個環是一條開始和結束于同一個格子的長度 大于等于 4 的路徑。對于一個給定的格子，你可以移動到它上、下、左、右四個方向相鄰的格子之一，可以移動的前提是這兩個格子有 相同的值 。

同時，你也不能回到上一次移動時所在的格子。比方說，環 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因為從 (1, 2) 移動到 (1, 1) 回到了上一次移動時的格子。

如果 grid 中有相同值形成的環，請你返回 true ，否則返回 false 。

示例 1：

輸入：grid = [ ["a","a","a","a"], ["a","b","b","a"], ["a","b","b","a"], ["a","a","a","a"]] 輸出：true 解釋：如下圖所示，有 2 個用不同顏色標出來的環：

示例 2：

輸入：grid = [ ["c","c","c","a"], ["c","d","c","c"], ["c","c","e","c"], ["f","c","c","c"]] 輸出：true 解釋：如下圖所示，只有高亮所示的一個合法環：

示例 3：

輸入：grid = [ ["a","b","b"], ["b","z","b"], ["b","b","a"]] 輸出：false提示： m == grid.length n == grid[i].length 1 <= m <= 500 1 <= n <= 500 grid 只包含小寫英文字母。

---

解題：

• dfs 記錄訪問標記，以及走過的 steps

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};bool found = false;int m, n; public:bool containsCycle(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();int i, j, k, x, y;vector<vector<bool>> visited(m, vector<bool>(n, false));vector<vector<int>> step(m, vector<int>(n, 0));for(i = 0; i < m; ++i) {for(j = 0; j < n; ++j){if(found) return found;if(visited[i][j])continue;visited[i][j] = true;step[i][j] = 1;//走過的步數dfs(i,j,step,visited,grid);}}return found;}void dfs(int i, int j,vector<vector<int>> &step, vector<vector<bool>> &visited, vector<vector<char>>& grid){int x,y,k;if(found) return;for(k = 0; k < 4; k++){x = i + dir[k][0];y = j + dir[k][1];if(x >= 0 && x < m && y >= 0 && y < n){if(grid[x][y] != grid[i][j])continue;//不相同的值，不行if(!visited[x][y])//沒有訪問{visited[x][y] = true;step[x][y] = step[i][j]+1;//步數+1dfs(x, y, step, visited, grid);}else{ //訪問過了，且當前步數跟其步數差滿足條件if(step[i][j]-step[x][y]+1 >= 4){found = true;return;}}}}} };

724 ms 100.8 MB

---

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

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

總結

以上是生活随笔為你收集整理的LeetCode 第 33 场双周赛（511/3304，前15.5%，第4次全部通过）的全部內容，希望文章能夠幫你解決所遇到的問題。

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