算法-加油站問題

hello 大家好!今天開寫一個新章節,每一天一道算法題。讓我們一起來學習算法思維吧!

在這里插入圖片描述

function canCompleteCircuit(gas, cost) {// 加油站的總數const n = gas.length;// 記錄總剩余油量,若總剩余油量小于 0,說明無法繞環路行駛一周let totalSurplus = 0;// 記錄當前從起始點出發累計的剩余油量let currentSurplus = 0;// 記錄可能的起始加油站編號,初始設為 0let start = 0;// 遍歷每一個加油站for (let i = 0; i < n; i++) {// 計算從當前加油站出發到下一個加油站的剩余油量const surplus = gas[i] - cost[i];// 累加每一個加油站的剩余油量到總剩余油量中totalSurplus += surplus;// 累加從當前起始點出發到當前加油站的剩余油量currentSurplus += surplus;// 如果當前從起始點出發累計的剩余油量小于 0,說明從當前 start 出發無法繼續行駛if (currentSurplus < 0) {// 則更新起始點為下一個加油站start = i + 1;// 并將當前累計的剩余油量重置為 0,準備從新的起始點開始計算currentSurplus = 0;}}// 如果總剩余油量小于 0,說明整體的汽油量不足以支持繞環路行駛一周if (totalSurplus < 0) {return -1;}// 否則,返回記錄的起始加油站編號return start;
}// 示例測試
const gas = [1, 2, 3, 4, 5];
const cost = [3, 4, 5, 1, 2];
console.log(canCompleteCircuit(gas, cost));

代碼思路解釋

初始化部分:
n:獲取加油站的總數,用于后續的循環遍歷。
totalSurplus:用來統計所有加油站的汽油量減去行駛消耗后的總剩余油量。如果這個值小于 0,說明無論從哪個加油站出發,都無法繞環路行駛一周。
currentSurplus:記錄從當前假設的起始加油站出發,到當前遍歷到的加油站時累計的剩余油量。
start:表示可能的起始加油站編號,初始從 0 號加油站開始嘗試。

遍歷加油站:
在循環中,對于每一個加油站,計算從該加油站出發到下一個加油站的剩余油量 surplus,即 gas[i] - cost[i]。
將這個剩余油量累加到 totalSurplus 中,以統計總的剩余油量情況。
同時也將其累加到 currentSurplus 中,以跟蹤從當前假設的起始點出發的剩余油量變化。
若 currentSurplus 小于 0,意味著從當前假設的 start 出發無法到達下一個加油站,所以更新 start 為下一個加油站的編號 i + 1,并將 currentSurplus 重置為 0,重新開始從新的起始點計算剩余油量。

結果判斷:
循環結束后,檢查 totalSurplus 的值。如果它小于 0,說明整體汽油量不夠繞環路行駛,返回 -1。
若 totalSurplus 大于等于 0,說明存在一個起始點可以繞環路行駛一周,返回記錄的 start 編號。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/67188.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/67188.shtml
英文地址,請注明出處:http://en.pswp.cn/web/67188.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

訊飛繪鏡(ai生成視頻)技術淺析(二):大模型

1.訊飛星火大模型的基礎架構 2.自然語言處理(NLP)技術的具體實現 3.腳本生成的具體過程與模型公式 4.分鏡生成的具體過程與模型公式 5.視頻生成與編輯的技術細節 6.關鍵技術公式的詳細推導與解釋 一、訊飛星火大模型的基礎架構 訊飛星火大模型是基于Transformer架構的深…

【機器學習】深入探索SVM:支持向量機的原理與應用

目錄 &#x1f354; SVM引入 1.1什么是SVM? 1.2支持向量機分類 1.3 線性可分、線性和非線性的區分 &#x1f354; 小結 學習目標 知道SVM的概念 &#x1f354; SVM引入 1.1什么是SVM? 看一個故事&#xff0c;故事是這樣子的&#xff1a; 在很久以前的情人節&#xf…

pycharm 運行遠程環境問題 Error:Failed to prepare environment.

問題排查 拿到更詳細的報錯信息&#xff1a; Help > Diagnostic Tools > Debug Log Settings section: 添加下面的配置 com.intellij.execution.configurations.GeneralCommandLine 重顯報錯&#xff0c;我這里是再次運行代碼打開 Help | Collect Logs and Diagnosti…

一組開源、免費、Metro風格的 WPF UI 控件庫

前言 今天大姚給大家分享一個開源、免費、Metro風格的 WPF UI 控件庫&#xff1a;MahApps.Metro。 項目介紹 MahApps.Metro 是一個開源、免費、Metro風格的 WPF UI 控件庫&#xff0c;提供了現代化、平滑和美觀的控件和樣式&#xff0c;幫助開發人員輕松創建具有現代感的 Win…

讀寫和解析簡單的 nc 文件

NetCDF 文件格式在氣象數據工程領域占據著舉足輕重的地位&#xff0c;其結構靈活、強兼容性等優勢使其成為該領域的一個標準。無論是從事學術研究還是工程實踐&#xff0c;掌握這種數據格式變得越發重要。其次&#xff0c;我注意到目前社區中氣象編程大多數課程都聚焦于某個特定…

Mac m1,m2,m3芯片使用nvm安裝node14報錯

使用nvm安裝了node 12/16/18都沒有問題&#xff0c;到14就報錯了。第一次看到這個報錯有點懵&#xff0c;查詢資料發現是Mac芯片的問題。 Issue上提供了兩個方案&#xff1a; 1、為了在arm64的Mac上安裝node 14&#xff0c;需要使用Rosseta&#xff0c;可以通過以下命令安裝 …

【計算機網絡】host文件

host文件的主要功能&#xff1a; 域名解析 本地映射&#xff1a;host文件的主要功能是將**域名映射到相應的 IP 地址**。當計算機需要訪問一個網站或服務時&#xff0c;它會首先在 host文件中查找該域名對應的 IP 地址。如果在 host文件中找到了匹配的域名和 IP 地址映射&…

vue3中customRef的用法以及使用場景

1. 基本概念 customRef 是 Vue3 提供的用于創建自定義響應式引用的 API&#xff0c;允許顯式地控制依賴追蹤和觸發響應。它返回一個帶有 get 和 set 函數的工廠函數來自定義 ref 的行為。 1.1 基本語法 import { customRef } from vuefunction createCustomRef(value) {retu…

周末總結(2024/01/25)

工作 人際關系核心實踐&#xff1a; 要學會隨時回應別人的善意&#xff0c;執行時間控制在5分鐘以內 堅持每天早會打招呼 遇到接不住的話題時拉低自己&#xff0c;抬高別人(無陰陽氣息) 朋友圈點贊控制在5min以內&#xff0c;職場社交不要放在5min以外 職場的人際關系在面對利…

C++和Python實現SQL Server數據庫導出數據到S3并導入Redshift數據倉庫

用C實現高性能數據處理&#xff0c;Python實現操作Redshift導入數據文件。 在Visual Studio 2022中用C和ODBC API導出SQL Server數據庫中張表中的所有表的數據為CSV文件格式的數據流&#xff0c;用逗號作為分隔符&#xff0c;用雙引號包裹每個數據&#xff0c;字符串類型的數據…

基于OpenCV實現的答題卡自動判卷系統

一、圖像預處理 ?? 二、查找答題卡輪廓 ?? 三、透視變換 ?? 四、判卷與評分 ?? 五、主函數 六、完整代碼+測試圖像集 總結 ?? 在這篇博客中,我將分享如何使用Python結合OpenCV庫開發一個答題卡自動判卷系統。這個系統能夠自動從掃描的答題卡中提取信…

Android AOP:aspectjx

加入引用 在整個項目的 build.gradle 中&#xff0c;添加 classpath "com.hujiang.aspectjx:gradle-android-plugin-aspectjx:2.0.10" 可以看到測試demo的 gradle 版本是很低的。 基于 github 上的文檔&#xff0c;可以看到原版只支持到 gradle 4.4 。后續需要使…

第84期 | GPTSecurity周報

GPTSecurity是一個涵蓋了前沿學術研究和實踐經驗分享的社區&#xff0c;集成了生成預訓練Transformer&#xff08;GPT&#xff09;、人工智能生成內容&#xff08;AIGC&#xff09;以及大語言模型&#xff08;LLM&#xff09;等安全領域應用的知識。在這里&#xff0c;您可以找…

TCP/IP 協議:互聯網通信的基石

TCP/IP 協議:互聯網通信的基石 引言 TCP/IP協議,全稱為傳輸控制協議/互聯網協議,是互聯網上應用最為廣泛的通信協議。它定義了數據如何在網絡上傳輸,是構建現代互聯網的基礎。本文將深入探討TCP/IP協議的原理、結構、應用以及其在互聯網通信中的重要性。 TCP/IP 協議概述…

蛇年特別版貪吃蛇H5小游戲

該作者的原創文章目錄: 生產制造執行MES系統的需求設計和實現 企業后勤管理系統的需求設計和實現 行政辦公管理系統的需求設計和實現 人力資源管理HR系統的需求設計和實現 企業財務管理系統的需求設計和實現 董事會辦公管理系統的需求設計和實現 公司組織架構圖設計工具 庫存管…

MapReduce,Yarn,Spark理解與執行流程

MapReduce的API理解 Mapper 如果是單詞計數&#xff1a;hello&#xff1a;1&#xff0c; hello&#xff1a;1&#xff0c; world&#xff1a;1 public void map(Object key, // 首字符偏移量Text value, // 文件的一行內容Context context) // Mapper端的上下文&#xff0c;…

如何將xps文件轉換為txt文件?xps轉為pdf,pdf轉為txt,提取pdf表格并轉為txt

文章目錄 xps轉txt方法一方法二 pdf轉txt整頁轉txt提取pdf表格&#xff0c;并轉為txt 總結另外參考XPS文件轉換為TXT文件XPS文件轉換為PDF文件PDF文件轉換為TXT文件提取PDF表格并轉為TXT示例代碼&#xff08;部分&#xff09; 本文測試代碼已上傳&#xff0c;路徑如下&#xff…

Day26-【13003】短文,什么是順序表?順序表和數組、內存地址的關系?順序表的插入、刪除操作如何實現?操作的時間復雜度是多少?

文章目錄 第二節&#xff0c;線性表的順序存儲及實現概覽什么是順序表和鏈表&#xff1f;順序存儲的叫順序表順序表和數組還有內存地址的關系&#xff1f;順序表的基本操作如何實現&#xff1f;1、插入操作如何實現&#xff1f;2、刪除操作如何實現&#xff1f;3、賦值和查找操…

【含開題報告+文檔+PPT+源碼】基于SpringBoot的校園跑腿管理系統

開題報告 本文旨在探討校園跑腿系統的設計與實現&#xff0c;通過深入研究與分析&#xff0c;實現了一套包含用戶管理、發布跑腿單、跑腿搶單、跑腿單評論、在線留言以及用戶在線充值等功能的綜合性系統。該系統以提高校園內物品跑腿與配送效率為核心目標&#xff0c;為廣大學…

zookeeper的介紹和簡單使用

1 zookerper介紹 zookeeper是一個開源的分布式協調服務&#xff0c;由Apache軟件基金會提供&#xff0c;主要用于解決分布式應用中的數據管理、狀態同步和集群協調等問題。通過提供一個高性能、高可用的協調服務&#xff0c;幫助構建可靠的分布式系統。 Zookeeper的特點和功能…