LC122. 买卖股票的最佳时机Ⅱ
一旦遇到相比于昨天降价的，就抛出，就购入低价的，直到又遇到下一个滑坡点，又立即抛出，计算收益
贪心算法表现在：总是在降价前抛出，获取收益，总是在降价当前抛出
这道题的另一个思考角度是，对原数组如[7,1,5,3,6,4]，除第一天外求取利润数组，即[-6, 4, -2, 3, -2]，对所有正数相加求和即可。
int maxProfit(vector<int>& prices)
{
////因为0 <= prices[i] <= 10^4，在最后加多虚拟的一天，
////保证循环不变量，能够处理到最后一天，如例子[1, 2, 3, 4, 5]
prices.emplace_back(-1);
int sum = 0;
int purchase = prices[0]; //当前所持股票
for (int i = 1; i < prices.size(); ++i)
{
//一旦遇到相比于昨天降价的，就抛出，就购入低价的
if (prices[i] < prices[i - 1])
{
sum += (prices[i - 1] - purchase); //计算换股票前赚的
purchase = prices[i];
}
//else //若升价，按兵不动
}
return sum;
}
LC55. 跳跃游戏
根据第一个数，设定初始右边界。对边界内的数，逐个找到可能存在的最右的边界，若能达到等于或超过最后一个元素的下标，即为true。
bool canJump(vector<int>& nums)
{
if (nums.size() == 1)
{
return true;
}
int size = nums.size();
int bound = nums[0];
int pos = 1;
while (pos <= bound)
{
if ((pos + nums[pos]) >= size - 1)
{
return true;
}
else if ((pos + nums[pos]) > bound)
{
bound = (pos + nums[pos]);
}
++pos;
}
return false;
}
LC45. 跳跃游戏Ⅱ
跟上一题在大体逻辑上是一致的，如bound的划定和更新。但也要区分开来：
- 上一题问的是是否可达，所以用while (pos <= bound)。本题说明一定可达nums[n - 1]，求最小步数。所以只需while (pos <= size - 1)。
本题的关键，在于既然要计算最小步数，就要想清楚什么时候步数才一定要加一。
- 开始我的处理方式是，在上一题的基础上，加多一个loop_bound，标记当前step的最远覆盖范围，只有超过该值，才更新一次(loop_bound = bound;)，同时step_inc_flag标志位保证pos在当前step的最远覆盖范围增加时，只step++一次。
- 导致我辅助变量如此多的原因在于，变量的初始不应该从原数组的第二个元素算起，这样子在while内的处理能够更加地统一
int jump(vector<int>& nums)
{
int size = nums.size();
int bound = nums[0];
int loop_bound = nums[0]; //记录这一step的最远覆盖范围
bool step_inc_flag = 1;
int pos = 1;
int step = 1;
int min_step = INT32_MAX;
if (size == 1) //如果只有一个元素，即已达终点
{
return 0;
}
if (bound >= size - 1)
{
return 1;
}
while (pos <= min(bound, size - 1))
{
if (pos <= loop_bound && step_inc_flag == 1)
{
++step;
step_inc_flag = 0;
}
else if (pos > loop_bound)
{
loop_bound = bound;
step_inc_flag = 1;
continue;
}
if ((pos + nums[pos]) >= size - 1 && step < min_step)
{
min_step = step;
}
if ((pos + nums[pos]) > bound)
{
bound = (pos + nums[pos]);
}
++pos;
}
return min_step;
}
简短优化（参考Carl哥思路）：
- 初始pos、bound设立为0
- 循环不变量，设定step = 1，如例子[1, 2]，在循环内如果step不用增加，即达终点
int jump(vector<int>& nums)
{
int size = nums.size();
int bound = 0;
int loop_bound = 0; //记录这一step的最远覆盖范围
int pos = 0;
int step = 1;
if (size == 1) //如果只有一个元素，即已达终点
{
return 0;
}
while (pos <= size - 1)
{
if (pos > loop_bound) //超过当前step的最远覆盖范围，才增加步数
{
step++;
loop_bound = bound;
}
if ((pos + nums[pos]) > bound) //检测是否更新最远覆盖范围
{
bound = (pos + nums[pos]);
}
if (bound >= size - 1) //若最远覆盖范围，覆盖了终点，直接结束
{
break;
}
++pos;
}
return step;
}