日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內(nèi)最全I(xiàn)T社區(qū)平臺 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁 > php開源 > php教程 > 【Leetcode】Gas Station

【Leetcode】Gas Station

來源:程序員人生   發(fā)布時間:2016-06-25 16:11:12 閱讀次數(shù):2505次

題目鏈接:https://leetcode.com/problems/gas-station/
題目:

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return ⑴.

Note:
The solution is guaranteed to be unique.

思路:

看了tag發(fā)現(xiàn)是貪心,想起老師上課說貪心實現(xiàn)起來是最簡單的,最難的是證明貪心策略的正確性。這里主要為了AC,多嘗試幾次可能的策略懶得證明了(寶寶TM不會證明啊!!)。很自然想到的策略有:1、從gas最多的station開始 2、從cost最少的station開始 3、從剩余(gas-cost)最少的開始。

嘗試了幾次發(fā)現(xiàn)第2種是對的,但要注意如果有多個站點cost相同,要判斷這些站點是不是能完成環(huán)圈旅行。

算法:

public int canCompleteCircuit(int[] gas, int[] cost) { int index = 0; for (int i = 1; i < cost.length; i++) { if (cost[i]<cost[index]) { index = i; } } for(int i=0;i<cost.length;i++){ if(cost[i]==cost[index]){ if(isValid(cost, gas, i)!=⑴){ return i; } } } return ⑴; } public int isValid(int[]cost,int[] gas,int index){ int tankGas = 0; for(int i=index;i<gas.length;i++){ tankGas+=gas[i]-cost[i]; if(tankGas<0){ return ⑴; } } for(int i=0;i<index;i++){ tankGas+=gas[i]-cost[i]; if(tankGas<0){ return ⑴; } } return index; }


生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 日本精品一区二区三区四区的功能 | 中文字幕福利片 | 91高清在线观看 | 国产精品18hdxxxⅹ在线 | 久久免费99精品久久久久久 | 91精品久久久久久久蜜月 | 日韩小视频 | 成人av在线网站 | 国产福利网站 | 欧美成人资源 | 国产精品视频999 | 成人h视频在线观看 | 精品国产乱码久久久久久影片 | 国产男女免费完整视频 | 男女上床网站 | 在线免费观看av网站 | 亚洲天堂婷婷 | 天堂网亚洲 | 99久久精品国产一区二区三区 | 天堂一区二区三区 | 久久国产精品首页 | 亚洲精品综合 | 日韩精品视频在线播放 | 久久精品国产v日韩v亚洲 | 亚洲精品久久久久久久久久久久久 | 国产精品18久久久久久久久久久久 | 日韩成人在线免费观看 | 可以免费看的av网站 | 久久久久久免费精品一区二区三区 | 91先生在线观看 | 国产一区二区久久精品 | 国产综合精品一区二区三区 | 黄网址在线观看 | 一区二区在线观看视频 | 久久久久久久久成人 | 国产成人一区二区 | 一二三在线视频 | 国产精品久久久久久久av大片 | 国产精品久久久一区二区三区 | 一级视频在线 | 黄色av电影在线观看 |