最高峰地圖-php教程-PHP中文網

首頁

後端開發

php教程

最高峰地圖

Barbara Streisand

Jan 23, 2025 am 02:23 AM

1765。最高峰地圖

難度：中

主題：陣列、廣度優先搜尋、矩陣

給定一個大小為 m x n 的整數矩陣 isWater，它表示 land 和 water 單元格的地圖。

如果 isWater[i][j] == 0，則單元格 (i, j) 是陸地單元格。
如果 isWater[i][j] == 1，則單元格 (i, j) 是水單元格。

您必須依照下列規則為每個儲存格指派高度：

每個單元格的高度必須為非負數。
如果單元格是水單元格，則其高度必須為 0。
任何兩個相鄰單元格的絕對高度差必須最多 1。如果一個單元格位於另一個單元格的正北、東、南或西方向，則該單元格與另一個單元格相鄰（即，他們的側面接觸）。

找出一個高度分配，使得矩陣中的最大高度為最大化.

傳回大小為 m x n 的整數矩陣高度，其中 height[i][j] 是單元格 (i, j) 的高度。如果有多個解決方案，則傳回其中任何。

範例1：

最高峰地圖

輸入： isWater = [[0,1],[0,0]]
輸出： [[1,0],[2,1]]
說明： 影像顯示了每個單元格的指定高度。
- 藍色單元格是水單元格，綠色單元格是陸地單元格。

範例2：

最高峰地圖

輸入： isWater = [[0,0,1],[1,0,0],[0,0,0]]
輸出： [[1,1,0],[0,1,1],[1,2,2]]
解釋： 高度 2 是任何分配的最大可能高度。
- 任何最大高度為 2 且仍符合規則的高度分配也將被接受。

範例 3：

輸入： isWater = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0, 0,0,1,1,0, 0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0 ,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0 ,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0, 0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1, 0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0 ,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0 ,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0, 0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0 ,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1 ,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0, 0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1, 0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1 ,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0 ,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1, 1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0, 0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1 ,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0, 1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0] ,[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1 ,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0 ,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0, 0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0, 0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1 ,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0 ,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0, 1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1, 0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1 ,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1 ,0,1,1,0,0,0,0,1,0,1,0,0],...]
輸出： [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1, 1,0,0,1, 2,1,1,2,2,1,0 ,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1 ,1,2,1,0,1,2, 3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0 ,1,2,1,0,0,1, 2,1,0,1,1,0,1 ,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0, 1,0,1,1,1,0,1 ,1,0,1,1,2,1, 0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0, 1,1,0,1,0,1,0 ,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2, 3,2,2,2,2,2,2 ,3,2,3,3,2,1, 0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2 ,1,0,1,2,1,1, 0,1,1,0,1,2], [0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1 ,0,0,1,1,0,0, 1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1 ,0,1,0,1,1,0, 0,1,2,1,0,1,2 ,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1, 2,3,2,1,1,0,1 ,1,1,1,0,1,0, 1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0,0, 1,1,1,0,1,0,1 ,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1, 0,1,1,1,1,0,1 ,0,0,1,1,1,0, 0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2 ,1,1,1,1,1,1, 2,1,2,3,3,2,1 ,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0 ,1,2,1,2,3],[ 1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1 ,0,1,1,0,1,2, 1,1,0,1,1,1,1 ,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1, 0,1,1,2,1,0,1 ,2,1,...]]

約束：

m == isWater.length
n == isWater[i].length
1
isWater[i][j] 是 0 或 1。
至少有一個個水細胞。

提示：

將每個水單元設定為 0。每個單元的高度受其最近的水單元的限制。
以所有水細胞為源執行多源 BFS。

註：本題與542.01矩陣相同

解：

我們可以使用廣度優先搜尋（BFS）方法。以下是我們如何逐步實現它：

問題分解：

水細胞：帶有1的細胞代表水細胞，其高度始終為0。
陸地單元：帶有 0 的單元代表陸地單元，其高度應指定為使得相鄰陸地單元的高度差最多為 1。

方法：

BFS 初始化:
- 我們首先將所有水單元格（值為 1 的單元格）標記為 BFS 中的起點，並將它們的高度指定為 0。
- 然後我們處理鄰近的陸地單元（值為 0 的單元）以分配高度。
BFS 遍歷:
- 從每個水單元開始，我們向外擴展，將每個相鄰的陸地單元的高度增加 1，確保相鄰單元之間的高度差永遠不會超過 1。
- 我們繼續這個過程，直到訪問完所有單元格。
結果：結果將是遵循給定規則的高度矩陣，其中高度值最大化。

讓我們用 PHP 實作這個解：1765。最高峰地圖

<?php /**
 * @param Integer[][] $isWater
 * @return Integer[][]
 */
function highestPeak($isWater) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$$isWater1 = [[0,1],[0,0]];
$$isWater2 = [[0,0,1],[1,0,0],[0,0,0]];
$$isWater3 = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0],[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0],...];

echo highestPeak($$isWater1) . "\n"; // Output: [[1,0],[2,1]]
echo highestPeak($$isWater2) . "\n"; // Output: [[1,1,0],[0,1,1],[1,2,2]]
echo highestPeak($$isWater3) . "\n"; // Output: [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1,1,0,0,1,2,1,1,2,2,1,0,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1,1,2,1,0,1,2,3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0,1,2,1,0,0,1,2,1,0,1,1,0,1,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,0,1,1,2,1,0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2,3,2,2,2,2,2,2,3,2,3,3,2,1,0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2,1,0,1,2,1,1,0,1,1,0,1,2],[0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1,0,1,0,1,1,0,0,1,2,1,0,1,2,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1,2,3,2,1,1,0,1,1,1,1,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,1,1,0,1,0,1,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,0,1,1,1,0,0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2,1,1,1,1,1,1,2,1,2,3,3,2,1,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0,1,2,1,2,3],[1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1,0,1,1,0,1,2,1,1,0,1,1,1,1,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1,0,1,1,2,1,0,1,2,1,...]]
?>

解釋：

初始化:
- 我們將所有單元格的高度矩陣初始化為 -1。水細胞立即設定為 0。
- 水細胞被排入 BFS 隊列。
BFS:
- 我們透過使每個單元出列來處理隊列，並且對於其每個相鄰單元，我們檢查它是否在邊界內並且未被訪問。
- 如果它是有效的陸地單元（未訪問過），我們會為其分配比當前單元高度大一的高度，並將其排隊以進行進一步處理。
結果：
- BFS 完成後，高度矩陣將包含每個單元格的最高可能高度，尊重給定的限制。

時間複雜度：

O(m * n) 其中 m 是行數，n 是列數。這是因為在 BFS 遍歷過程中每個單元最多被處理一次。

此解決方案確保矩陣填滿正確的高度，並且 BFS 保證每個單元格的最大高度，同時保持相鄰單元格之間的高度差約束。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

領英
GitHub

以上是最高峰地圖的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

PHP與Python：了解差異Apr 11, 2025 am 12:15 AM

PHP和Python各有優勢，選擇應基於項目需求。 1.PHP適合web開發，語法簡單，執行效率高。 2.Python適用於數據科學和機器學習，語法簡潔，庫豐富。

php：死亡還是簡單地適應？Apr 11, 2025 am 12:13 AM

PHP不是在消亡，而是在不斷適應和進化。 1)PHP從1994年起經歷多次版本迭代，適應新技術趨勢。 2)目前廣泛應用於電子商務、內容管理系統等領域。 3)PHP8引入JIT編譯器等功能，提升性能和現代化。 4)使用OPcache和遵循PSR-12標準可優化性能和代碼質量。

PHP的未來：改編和創新Apr 11, 2025 am 12:01 AM

PHP的未來將通過適應新技術趨勢和引入創新特性來實現：1)適應云計算、容器化和微服務架構，支持Docker和Kubernetes；2)引入JIT編譯器和枚舉類型，提升性能和數據處理效率；3)持續優化性能和推廣最佳實踐。

您什麼時候使用特質與PHP中的抽像類或接口？Apr 10, 2025 am 09:39 AM

在PHP中，trait適用於需要方法復用但不適合使用繼承的情況。 1)trait允許在類中復用方法，避免多重繼承複雜性。 2)使用trait時需注意方法衝突，可通過insteadof和as關鍵字解決。 3)應避免過度使用trait，保持其單一職責，以優化性能和提高代碼可維護性。

什麼是依賴性注入容器（DIC），為什麼在PHP中使用一個？Apr 10, 2025 am 09:38 AM

依賴注入容器（DIC）是一種管理和提供對象依賴關係的工具，用於PHP項目中。 DIC的主要好處包括：1.解耦，使組件獨立，代碼易維護和測試；2.靈活性，易替換或修改依賴關係；3.可測試性，方便注入mock對象進行單元測試。

與常規PHP陣列相比，解釋SPL SplfixedArray及其性能特徵。Apr 10, 2025 am 09:37 AM

SplFixedArray在PHP中是一種固定大小的數組，適用於需要高性能和低內存使用量的場景。 1)它在創建時需指定大小，避免動態調整帶來的開銷。 2)基於C語言數組，直接操作內存，訪問速度快。 3)適合大規模數據處理和內存敏感環境，但需謹慎使用，因其大小固定。

PHP如何安全地上載文件？Apr 10, 2025 am 09:37 AM

PHP通過$\_FILES變量處理文件上傳，確保安全性的方法包括：1.檢查上傳錯誤，2.驗證文件類型和大小，3.防止文件覆蓋，4.移動文件到永久存儲位置。

什麼是無效的合併操作員（??）和無效分配運算符（?? =）？Apr 10, 2025 am 09:33 AM

JavaScript中處理空值可以使用NullCoalescingOperator(??)和NullCoalescingAssignmentOperator(??=)。 1.??返回第一個非null或非undefined的操作數。 2.??=將變量賦值為右操作數的值，但前提是該變量為null或undefined。這些操作符簡化了代碼邏輯，提高了可讀性和性能。

See all articles