Hot100之贪心算法

121买股票的最佳时机

题目

思路解析

有两种解法,DP和维护第i天最小值

维护第i天前的最小值

从左到右枚举卖出价格 prices[i

那么要想获得最大利润，我们需要知道第 i 天之前股票价格的最小值是什么

也就是从 prices[0] 到 prices[i−1] 的最小值，把它作为买入价格，这可以用一个变量 minPrice 维护。

请注意，minPrice 维护的是 prices[i] 左侧元素的最小值。

由于只能买卖一次，所以在遍历中，维护 prices[i]−minPrice 的最大值，就是答案。

DP

我们弄一个二维的dp【】数组

dp【i】【0】指的是下标为i这天结束的时候，持股，手上拥有的最大现金

dp【i】【1】指的是下标为i这天结束的时候，不持股，手上拥有的最大现金

所以我们一开始初始化的时候是这样初始化的

第一天买股了和第一天卖股了

//初始化
dp[0][0]=-prices[0];
dp[0][1]=0;

有了这个逻辑，所以我们的dp逻辑就出来了

买股我们就减去当天的price

卖股我们就加上当天的price

for(int i=1;i<prices.length;i++)
{// dp[i][0] 下标为 i 这天结束的时候，持股，手上拥有的最大现金数// dp[i][1] 下标为 i 这天结束的时候，不持股，手上拥有的最大现金数//可以看成如果我们今天买股消耗的钱更少,我们就要选消耗钱更少的dp[i][0]=Math.max(dp[i-1][0],0-prices[i]);//保证第i天及以前卖股的最大值dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}

dp【i】【0】存储第i天以及第i天之前，我们买股票的消耗钱最小值

dp【i】【1】存储第i天以及第i天之前，我们卖股票的最大值

从前往后递推

我们就能记录第i天以及第i天之前，我们遇到的最低价钱的股票，和卖股票能钻到钱的最大值

代码

维护第i天前的最小值

class Solution {public int maxProfit(int[] prices) {int ans = 0;int minPrice = prices[0];for (int p : prices) {ans = Math.max(ans, p - minPrice);minPrice = Math.min(minPrice, p);}return ans;}
}

DP

class Solution {public int maxProfit(int[] prices) {int dp[][]=new int[prices.length][2];
//初始化
dp[0][0]=-prices[0];
dp[0][1]=0;for(int i=1;i<prices.length;i++)
{// dp[i][0] 下标为 i 这天结束的时候，持股，手上拥有的最大现金数// dp[i][1] 下标为 i 这天结束的时候，不持股，手上拥有的最大现金数//可以看成如果我们今天买股消耗的钱更少,我们就要选消耗钱更少的dp[i][0]=Math.max(dp[i-1][0],0-prices[i]);//保证第i天及以前卖股的最大值dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);}
}

55跳跃游戏

题目

是否能跳跃到最后一个位置

思路解析

我们for循环从左往右遍历

每次都找能跳跃到的最大下标

然后我们还有个i<=most,意思是我们的最远距离可以跳跃到或者大于i这个距离

我们的下标才能继续往下判断是否能继续跳跃

跳不到的话就不做行为，相当于结束了

如果遍历完之后，我们的most还是小于数组长度，那说明跳跃不到最后一个节点

代码

class Solution {public boolean canJump(int[] nums) {int length=nums.length;
int most=0;for(int i=0;i<length;i++)
{
if(i<=most)
{most=Math.max(most, i + nums[i]);
}if(most>=length-1)
return true;}return false;}
}

45跳跃游戏2

题目

跳跃到最后一个位置的最小跳跃次数

思路解析

我们要找到跳跃到的最远位置时能走的最短距离

首先我们要关注不能漏跳的问题和一些小点

例如【2，3，0，1，4】

我们肯定是 2，3，4这样跳到最后

而不是2，0这样子跳

也不是2，3，1，4这样子跳

首先我们不能漏跳

其次我们要跳的次数最少

所以我们有个start节点记录每次跳跃的开始位置，有个end节点，记录每次跳跃时能跳跃到的最远位置

我们for循环

//找到我们能跳跃到的最远位置end
for(int i=start;i<end;i++)
{maxpos=Math.max(maxpos,i+nums[i]);
}

i为起点，end-1为终点，然后for循环遍历，更新我们的能跳到的最远处

这样子就不会漏节点了

代码

class Solution {public int jump(int[] nums) {int ans=0;
int start=0;
int end=1;//假设我们第一次能跳跃到的最远位置为endwhile(end<nums.length)
{int maxpos=0;//找到我们能跳跃到的最远位置end
for(int i=start;i<end;i++)
{maxpos=Math.max(maxpos,i+nums[i]);
}//start变成上一次能跳跃到的最远位置
start=end;
//end变成for循环中我们能找到的新的能跳到的最远位置
end=maxpos+1;ans++;}
return ans;}
}

763划分字母区间

题目

思路解析

存字母的最远下标

//存对应字母的最远下标
for(int i=0;i<s.length();i++)
{arr[Crr[i]-'a']=i;}

我们遍历的时候不断更新当前遍历的字符串中字符的最远下标

然后当最远下标和当前下标匹配时，说明这个点就是最远的点了，我们收集答案

//遍历的时候,记录遍历的这段字母中的最远下标
right=Math.max(right,arr[Crr[i]-'a']);//当匹配到字符串中字母的最远下标，我们就记录个数
if(right==i)
{list.add(right-left);
left=right;}

代码

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> list=new LinkedList<>();int [] arr=new int[26];
char [] Crr=s.toCharArray();
int right=0;
int left=-1;//存对应字母的最远下标
for(int i=0;i<s.length();i++)
{arr[Crr[i]-'a']=i;}for(int i=0;i<s.length();i++)
{//遍历的时候,记录遍历的这段字母中的最远下标
right=Math.max(right,arr[Crr[i]-'a']);//当匹配到字符串中字母的最远下标，我们就记录个数
if(right==i)
{list.add(right-left);
left=right;}}return list;}
}