首頁 後端開發 php教程 最佳觀光組合

最佳觀光組合

Dec 30, 2024 am 02:46 AM

Best Sightseeing Pair

1014。最佳觀光配對

難度:

主題:數組,動態規劃

給你一個整數數組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

提示:

  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
?>
登入後複製

解釋:

  1. 初始化:

    • maxI 被初始化為values[0],因為我們從索引1開始評估對。
    • maxScore 初始化為 0 以追蹤最高分數。
  2. 迭代數組:

    • 對於從 1 開始的每個索引 j,使用以下公式計算 (i, j) 對的分數: 分數 = maxI 值[j] - j
    • 用所得的最大值更新 maxScore。
  3. 更新 maxI:

    • 更新 maxI 以追蹤下一次迭代的 value[i] i 的最大可能值。
  4. 回傳最高分數:

    • 迭代數組後,maxScore 將包含任何對的最大分數。

複雜:

  • 時間複雜度: O(n) 因為我們循環遍歷數組一次。
  • 空間複雜度: O(1),因為我們使用恆定的空間量。

該解決方案在遵守約束的同時有效計算最大分數,並針對大輸入進行了最佳化。

聯絡連結

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

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

  • 領英
  • GitHub

以上是最佳觀光組合的詳細內容。更多資訊請關注PHP中文網其他相關文章!

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

熱門文章

倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章

倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章標籤

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

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

11個最佳PHP URL縮短腳本(免費和高級) 11個最佳PHP URL縮短腳本(免費和高級) Mar 03, 2025 am 10:49 AM

11個最佳PHP URL縮短腳本(免費和高級)

在Laravel中使用Flash會話數據 在Laravel中使用Flash會話數據 Mar 12, 2025 pm 05:08 PM

在Laravel中使用Flash會話數據

簡化的HTTP響應在Laravel測試中模擬了 簡化的HTTP響應在Laravel測試中模擬了 Mar 12, 2025 pm 05:09 PM

簡化的HTTP響應在Laravel測試中模擬了

Instagram API簡介 Instagram API簡介 Mar 02, 2025 am 09:32 AM

Instagram API簡介

構建具有Laravel後端的React應用程序:第2部分,React 構建具有Laravel後端的React應用程序:第2部分,React Mar 04, 2025 am 09:33 AM

構建具有Laravel後端的React應用程序:第2部分,React

php中的捲曲:如何在REST API中使用PHP捲曲擴展 php中的捲曲:如何在REST API中使用PHP捲曲擴展 Mar 14, 2025 am 11:42 AM

php中的捲曲:如何在REST API中使用PHP捲曲擴展

在Codecanyon上的12個最佳PHP聊天腳本 在Codecanyon上的12個最佳PHP聊天腳本 Mar 13, 2025 pm 12:08 PM

在Codecanyon上的12個最佳PHP聊天腳本

宣布 2025 年 PHP 形勢調查 宣布 2025 年 PHP 形勢調查 Mar 03, 2025 pm 04:20 PM

宣布 2025 年 PHP 形勢調查

See all articles