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;//假设我们第一次能跳跃到的最远位置为end
while(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;
}
}