121
這道題的思路是貪心：題目的意思是只買賣一次股票载绿，買賣不能是同一天粥诫。遍歷過程中更新買入價(jià)格的最小值、利潤的最大值崭庸，這樣就可以保證賣出一定是在買入后面怀浆。
55
這道題的思路是不斷更新能到達(dá)的最長范圍，如果最長范圍大于等于數(shù)組長度冀自，那么就可以到達(dá)終點(diǎn)揉稚，否則不能。在每一個(gè)點(diǎn)處如何去更新最長范圍熬粗？用len當(dāng)作最長范圍搀玖，一開始len是當(dāng)前節(jié)點(diǎn)的值。以len作為for循環(huán)的終止條件驻呐，這個(gè)len可以在便利的時(shí)候不斷更新灌诅。
class Solution {
public:
? ? bool canJump(vector<int>& nums) {
? ? ? ? int len=0;
? ? ? ? for(int i=0;i<=len;i++)
? ? ? ? {
? ? ? ? ? ? len=max(len,nums[i]+i);
? ? ? ? ? ? if(len>=nums.size()-1) return true;
? ? ? ? }
? ? ? ? return false;
? ? }
};
45
這道題的思路是為了獲得最少的跳躍步數(shù)，每一步都跳的最大含末，每一步最大又是由上一步在它的范圍內(nèi)遍歷得到猜拾。
class Solution {
public:
? ? int jump(vector<int>& nums) {
? ? ? ? int ans=0;
? ? ? ? int current=0;
? ? ? ? int next=0;
? ? ? ? if (nums.size() == 1) return 0;
? ? ? ? for(int i=0;i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? next=max(next,nums[i]+i);
? ? ? ? ? ? if(i==current)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ans++;
? ? ? ? ? ? ? ? current=next;
? ? ? ? ? ? ? ? if(next>=nums.size()-1) break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return ans;
? ? }
};
