[LeetCode] 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 -1.

Note:
The solution is guaranteed to be unique.

思路：

这题要想清楚不容易，尽管想清楚后代码写起来很简单。

I.  显然当gas[i]<cost[i]时，i不能作为起点。

II. 当对所有加油站求和：sum(gas[i] - cost[i]) <0时，无法环绕一圈。反之，则一定能环绕一圈。

问题是如果可以环绕一圈，如何找起点？

性质1. 对于任意一个加油站i，假如从i出发可以环绕一圈，则i一定可以到达任何一个加油站。显而易见。

性质2. 如果这样的i是唯一的，则必然不存在j!=i， 从j出发可以到达i。

反证法：如果存在这样的j，则必然存在j->i->i的路径，而这个路径会覆盖j->j一周的路径。那么j也将是一个符合条件的起点。与唯一解的限制条件矛盾。

性质3. 假如i是最后的解，则由1可知，从0 ~ i-1出发无法达到i。而从i出发可以到达i+1 ~ n-1。

结合以上三条性质，得出解决的思路：

0. 如果对所有加油站的sum(gas[i] - cost[i])<0，则无解。否则进入1。

1. 从0开始计算sum(gas[i] - cost[i])，当遇到i1使sum<0时，说明从0出发无法到达i1。根据性质1，0不是起始点。而由于从0出发已经到达了1 ~ i1-1。根据性质2，1 ~ i1-1一定不是正确的起始点。此时i1为起始点的候选。

2. 将sum清0，并从i1出发，假如又遇到i2使sum(gas[i] - cost[i]) < 0 时，说明i1出发无法绕一圈，更具性质1，排除i1。又因为i1+1 ~ i2-1都能从i1出发到达,。根据性质2，它们也必然不是起始点。此时i2为起始点的候选。

3. 以此类推，直到遇到ik，使从ik出发可以到达ik+1 ~ n-1。

其中步骤0可以合并到1~3的扫描中，一个pass来得到解。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int start = 0, netGasSum = 0, curGasSum = 0; for(int i=0; i<cost.size(); i++) { netGasSum += gas[i] - cost[i]; curGasSum += gas[i] - cost[i]; if(curGasSum<0) { start = i+1; curGasSum = 0; } } if(netGasSum < 0) return -1; return start; } };

[LeetCode] Best Time to Buy and Sell Stock I, II, II

Best Time to Buy and Sell Stock I

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

思路：Best Time to Buy and Sell Stock I

I限制了只能买卖一次。于是要尽可能在最低点买入最高点抛出。这里的一个隐含的限制是抛出的时间必须在买入的时间之后。所以找整个数组的最大最小值之差的方法未必有效，因为很可能最大值出现在最小值之前。但是可以利用类似思路，在扫描数组的同时来更新一个当前最小值minPrice。这样能保证当扫到i时，minPrices必然是i之前的最小值。当扫到i时：

如果prices[i] < minPrice，则更新minPrice = prices[i]。并且该天不应该卖出。

如果prices[i] >= minPrice，则该天可能是最好的卖出时间，计算prices[i] - minPrice，并与当前的单笔最大利润比较更新。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int maxProfit(vector<int> &prices) { if(prices.empty()) return 0; int ret = 0, minPrice = prices[0]; for(int i=1; i<prices.size(); i++) { if(prices[i]<minPrice) minPrice = prices[i]; else ret = max(prices[i]-minPrice,ret); } return ret; } };

思路：Best Time to Buy and Sell Stock II

II并没有限制总的买卖次数，只限制了当天只能买或卖。所以可以采用greedy的方法，来获得所有可能的正利润。以如下序列说明：

2 1 3 4 5 4 2 8 7

只要prices[i] - prices[i-1]>0，我们就在第i-1天买入，第i天抛出。这样可以包括所有可能赚取利润的区间。

1 2 3 4 5 6 7 8 9 10

class Solution { public: int maxProfit(vector<int> &prices) { int ret = 0; for(int i=1; i<prices.size(); i++) { ret += prices[i]>prices[i-1] ? prices[i]-prices[i-1] : 0; } return ret; } };

思路：Best Time to Buy and Sell Stock III

III是这三题中最难的。允许两次买卖，但同一时间只允许持有一支股票。也就意味着这两次买卖在时间跨度上不能有重叠（当然第一次的卖出时间和第二次的买入时间可以是同一天）。既然不能有重叠可以将整个序列以任意坐标i为分割点，分割成两部分：

prices[0:n-1] => prices[0:i] + prices[i:n-1]

对于这个特定分割来说，最大收益为两段的最大收益之和。每一段的最大收益当然可以用I的解法来做。而III的解一定是对所有0<=i<=n-1的分割的最大收益中取一个最大值。为了增加计算效率，考虑采用dp来做bookkeeping。目标是对每个坐标i：

1. 计算A[0:i]的收益最大值：用minPrice记录i左边的最低价格，用maxLeftProfit记录左侧最大收益

2. 计算A[i:n-1]的收益最大值：用maxPrices记录i右边的最高价格，用maxRightProfit记录右侧最大收益。

3. 最后这两个收益之和便是以i为分割的最大收益。将序列从左向右扫一遍可以获取1，从右向左扫一遍可以获取2。相加后取最大值即为答案。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: int maxProfit(vector<int> &prices) { if(prices.empty()) return 0; int n = prices.size(); vector<int> leftProfit(n,0); int maxLeftProfit = 0, minPrice = prices[0]; for(int i=1; i<n; i++) { if(prices[i]<minPrice) minPrice = prices[i]; else maxLeftProfit = max(maxLeftProfit, prices[i]-minPrice); leftProfit[i] = maxLeftProfit; } int ret = leftProfit[n-1]; int maxRightProfit = 0, maxPrice = prices[n-1]; for(int i=n-2; i>=0; i--) { if(prices[i]>maxPrice) maxPrice = prices[i]; else maxRightProfit = max(maxRightProfit, maxPrice-prices[i]); ret = max(ret, maxRightProfit + leftProfit[i]); } return ret; } };

[LeetCode] Jump Game I, II

Jump Game I

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

思路：Jump Game I

注意题目中A[i]表示的是在位置i，“最大”的跳跃距离，而并不是指在位置i只能跳A[i]的距离。所以当跳到位置i后，能达到的最大的距离至少是i+A[i]。用greedy来解，记录一个当前能达到的最远距离maxIndex：

1. 能跳到位置i的条件：i<=maxIndex。

2. 一旦跳到i，则maxIndex = max(maxIndex, i+A[i])。

3. 能跳到最后一个位置n-1的条件是：maxIndex >= n-1

1 2 3 4 5 6 7 8 9 10 11

class Solution { public: bool canJump(int A[], int n) { int maxIndex = 0; for(int i=0; i<n; i++) { if(i>maxIndex || maxIndex>=(n-1)) break; maxIndex = max(maxIndex, i+A[i]); } return maxIndex>=(n-1) ? true : false; } };

思路：Jump Game II

同样可以用greedy解决。与I不同的是，求的不是对每个i，从A[0:i]能跳到的最远距离；而是计算跳了k次后能达到的最远距离，这里的通项公式为：

d[k] = max(i+A[i])     d[k-2] < i <= d[k-1]

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int jump(int A[], int n) { int curMax = 0, njumps = 0, i = 0; while(curMax<n-1) { int lastMax = curMax; for(; i<=lastMax; i++) curMax = max(curMax,i+A[i]); njumps++; if(lastMax == curMax) return -1; } return njumps; } };