<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 1334. 閾值距離內鄰居最少的城市 # 題目地址(1334. 閾值距離內鄰居最少的城市) <https://leetcode-cn.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/> ## 題目描述 ``` <pre class="calibre18">``` 有 n 個城市,按從 0 到 n-1 編號。給你一個邊數組 edges,其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 兩個城市之間的雙向加權邊,距離閾值是一個整數 distanceThreshold。 返回能通過某些路徑到達其他城市數目最少、且路徑距離 最大 為 distanceThreshold 的城市。如果有多個這樣的城市,則返回編號最大的城市。 注意,連接城市 i 和 j 的路徑的距離等于沿該路徑的所有邊的權重之和。 示例 1: ``` ``` ![](https://img.kancloud.cn/71/2f/712fd0b69de8737cdd68fc0440eb2ce4_960x720.jpg) ``` <pre class="calibre18">``` 輸入:n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 輸出:3 解釋:城市分布圖如上。 每個城市閾值距離 distanceThreshold = 4 內的鄰居城市分別是: 城市 0 -> [城市 1, 城市 2] 城市 1 -> [城市 0, 城市 2, 城市 3] 城市 2 -> [城市 0, 城市 1, 城市 3] 城市 3 -> [城市 1, 城市 2] 城市 0 和 3 在閾值距離 4 以內都有 2 個鄰居城市,但是我們必須返回城市 3,因為它的編號最大。 示例 2: ``` ``` ![](https://img.kancloud.cn/b7/bf/b7bf5a43ae30be1c18b11d32e3559ca3_960x720.jpg) ``` <pre class="calibre18">``` 輸入:n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 輸出:0 解釋:城市分布圖如上。 每個城市閾值距離 distanceThreshold = 2 內的鄰居城市分別是: 城市 0 -> [城市 1] 城市 1 -> [城市 0, 城市 4] 城市 2 -> [城市 3, 城市 4] 城市 3 -> [城市 2, 城市 4] 城市 4 -> [城市 1, 城市 2, 城市 3] 城市 0 在閾值距離 4 以內只有 1 個鄰居城市。 提示: 2 <= n <= 100 1 <= edges.length <= n * (n - 1) / 2 edges[i].length == 3 0 <= fromi < toi < n 1 <= weighti, distanceThreshold <= 10^4 所有 (fromi, toi) 都是不同的。 ``` ``` ## 前置知識 - 動態規劃 - Floyd-Warshall ## 公司 - 暫無 ## 思路 這道題的本質就是: 1. 在一個無向圖中尋找每兩個城鎮的最小距離,我們使用 Floyd-Warshall 算法(英語:Floyd-Warshall algorithm),中文亦稱弗洛伊德算法,是解決任意兩點間的最短路徑的一種算法。 2. 篩選最小距離不大于 distanceThreshold 的城鎮。 3. 統計每個城鎮,其滿足條件的城鎮有多少個 4. 我們找出最少的即可 Floyd-Warshall 算法的時間復雜度和空間復雜度都是O(N3)O(N^3)O(N3), 而空間復雜度可以優化到O(N2)O(N^2)O(N2)。Floyd-Warshall 的基本思想是對于每兩個點之間的最小距離,要么經過中間節點 k,要么不經過,我們取兩者的最小值,這是一種動態規劃思想,詳細的解法可以參考[Floyd-Warshall 算法(wikipedia)](https://zh.wikipedia.org/wiki/Floyd-Warshall%E7%AE%97%E6%B3%95) ## 代碼 代碼支持:Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findTheCity</span><span class="hljs-params">(self, n: int, edges: List[List[int]], distanceThreshold: int)</span> -> int:</span> <span class="hljs-title"># 構建dist矩陣</span> dist = [[float(<span class="hljs-string">'inf'</span>)] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n)] <span class="hljs-keyword">for</span> i, j, w <span class="hljs-keyword">in</span> edges: dist[i][j] = w dist[j][i] = w <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): dist[i][i] = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) <span class="hljs-title"># 過濾</span> res = <span class="hljs-params">0</span> minCnt = float(<span class="hljs-string">'inf'</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): cnt = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> d <span class="hljs-keyword">in</span> dist[i]: <span class="hljs-keyword">if</span> d <= distanceThreshold: cnt += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> cnt <= minCnt: minCnt = cnt res = i <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度:O(N3)O(N^3)O(N3) - 空間復雜度:O(N2)O(N^2)O(N2) ## 關鍵點解析 - Floyd-Warshall 算法 - 你可以將本文給的 Floyd-Warshall 算法當成一種解題模板使用 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看