零、买卖股票的最佳时机
每次持股一股,只能买卖一次
- 计算利润 price - cost
- 日期是不断推进的
- cost(花费) min 选取最小的股价
- profit利润,max(profit, price - cost)
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for(int price:prices){
//取买的时候价格最低
cost = Math.min(cost, price);
//取 当天减去最低价格 与 profit相比较最大卖出
profit = Math.max(profit,price - cost);
}
return profit;
}
}
一、买卖股票的最佳时机2
每次持股1股,可多次买卖
计算每天相对于上一天利润是上升还是下降,将所有上升的利润叠加,下降的不交易
class Solution {
public int maxProfit(int[] prices) {
// i - (i - 1) 为上升序列 叠加利润, 下降序列不交易
int profit = 0;
for(int i = 1; i < prices.length; i++){
int tmp = prices[i] - prices[i - 1];
if(tmp > 0) profit += tmp;
}
return profit;
}
}
跳跃游戏
class Solution {
public boolean canJump(int[] nums) {
if(nums == null || nums.length==0){
return true;
}
int n = nums.length;
int ans = 0;
//遍历数组所有元素,求整体能达到的最远的位置
for(int i=0;i<n;++i){
if(ans>=i){
ans = Math.max(ans,i+nums[i]);
}
}
//如果ans已经大于数组末尾,直接返回true即可
if(ans>=n-1){
return true;
}
return false;
}
}
跳跃游戏2
相对于跳跃游戏增加了遇到跳跃到末尾就记录 到当前节点需要的步数
class Solution {
public int jump(int[] nums) {
int end = 0;
int maxPosition = 0;
int steps = 0;
for(int i = 0; i < nums.length - 1; i++){
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[i] + i);
if(i == end){ //遇到边界,就更新边界,并且步数加一
//end表示 i位置所能到达的最远处(nums[i] + i);在遍历i到达end时,step++表示需要再次进行跳跃
end = maxPosition;
steps++;
}
}
return steps;
}
}