最佳觀光組合
Dec 30, 2024 am 02:46 AM1014。最佳觀光配對
難度:中
主題:數組,動態規劃
給你一個整數數組values,其中values[i]代表第i個個景點的值。兩個景點 i 和 j 之間的距離為 j - i。
一對(i
回傳一對遊覽點的最高分。
範例1:
- 輸入: 值 = [8,1,5,2,6]
- 輸出: 11
- 解釋: i = 0, j = 2, 值[i] 值[j] i - j = 8 5 0 - 2 = 11
範例2:
- 輸入:值= [1,2]
- 輸出: 2
約束:
- 2 4
- 1
提示:
- 你能一次說出最好的觀光景點嗎(即,當你迭代輸入時?)當我們迭代執行此操作時,我們應該存儲或跟踪什麼?
解:
我們可以使用線性時間複雜度的單遍方法O(n)。這個想法是在我們迭代數組時跟踪最好的可能值[i] i。這使我們能夠最大化每個有效對 (i, j) 的分數[i]值[j] i - j。
讓我們用 PHP 實作這個解:1014。最佳觀光配對
<?php /** * @param Integer[] $values * @return Integer */ function maxScoreSightseeingPair($values) { ... ... ... /** * go to ./solution.php */ } // Example usage: $values1 = [8, 1, 5, 2, 6]; echo maxScoreSightseeingPair($values1); // Output: 11 $values2 = [1, 2]; echo maxScoreSightseeingPair($values2); // Output: 2 ?>
登入後複製
解釋:
-
初始化:
- maxI 被初始化為values[0],因為我們從索引1開始評估對。
- maxScore 初始化為 0 以追蹤最高分數。
-
迭代數組:
- 對於從 1 開始的每個索引 j,使用以下公式計算 (i, j) 對的分數: 分數 = maxI 值[j] - j
- 用所得的最大值更新 maxScore。
-
更新 maxI:
- 更新 maxI 以追蹤下一次迭代的 value[i] i 的最大可能值。
-
回傳最高分數:
- 迭代數組後,maxScore 將包含任何對的最大分數。
複雜:
- 時間複雜度: O(n) 因為我們循環遍歷數組一次。
- 空間複雜度: O(1),因為我們使用恆定的空間量。
該解決方案在遵守約束的同時有效計算最大分數,並針對大輸入進行了最佳化。
聯絡連結
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
- 領英
- GitHub
以上是最佳觀光組合的詳細內容。更多資訊請關注PHP中文網其他相關文章!
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱門文章
擊敗分裂小說需要多長時間?
3 週前
By DDD
倉庫:如何復興隊友
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
公眾號網頁更新緩存難題:如何避免版本更新後舊緩存影響用戶體驗?
3 週前
By 王林
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前
By 尊渡假赌尊渡假赌尊渡假赌

熱門文章
擊敗分裂小說需要多長時間?
3 週前
By DDD
倉庫:如何復興隊友
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
公眾號網頁更新緩存難題:如何避免版本更新後舊緩存影響用戶體驗?
3 週前
By 王林
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前
By 尊渡假赌尊渡假赌尊渡假赌

熱門文章標籤

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)