一.买卖股票的最佳时机问题概述给定一个数组prices它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回0。思路我站在每天的角度去看总是拿历史到现在最低的价格买入我看看今天的价格卖出是不是比之前的历史的都要赚如果都要赚我就卖如果不是我就不卖。代码class Solution { public int maxProfit(int[] prices) { int minpriceInteger.MAX_VALUE; int maxProfit0; for(int price:prices){ minpriceMath.min(price,minprice); maxProfitMath.max(maxProfit,price-minprice); } return maxProfit; } }二.跳跃游戏问题概述给你一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回true否则返回false。思路012342311424348第一个数最大能跳到索引2那索引2之前的最大数为4那他最大再变更为4那44已经含盖了最后个索引所以为true.012343210433334第一个数最大能跳到索引3那索引3之前的最大数还是3那他跳不到4.为false那我们就从第一个数开始遍历每次跳1格计算当前能跳到的最远位置当遍历的数当前最远位置那就没法跳了就返回false。如果当前跳到的最远位置已经大于等于最后个位置所以已经具备了跳到最后的能力直接返回false。代码最后一个return true永远不会执行但不写会编译错误。代码class Solution { public boolean canJump(int[] nums) { int maxReach0; int nnums.length; for(int i0;in;i){ if(imaxReach){ return false; } maxReachMath.max(maxReach,nums[i]i); if(maxReachn-1){ return true; } } return true; } }三.跳跃游戏II问题概述上一题问能不能跳到最后现在问的是能跳到最后最少只要跳几次。题目保证一定能跳到最后思路倒着推从左往右找第一个能跳到最后那个索引位置记作pos1,step。再以pos1为目标位置从左到右找第一个能跳到pos1的下一个pos2step,依次类推有几个pos就是最少跳跃次数。那可能你会有疑惑有木有可能跳不到pos1呢其实你可以结合上题它是从第一个数开始遍历的能到最后那期间的那些数都是可以跳的那题目保证了从0能跳到最后n,那0到n这个区间一定包括pos1,那pos1左边必有能到它的数那有人问呢那pos2呢这不就是n取pos1嘛那不也就跳的到嘛。代码class Solution { public int jump(int[] nums) { int posnums.length-1; int step0; while(pos0){ for(int i0;ipos;i){ if(nums[i]ipos){ posi; step; break; } } } return step; } }四.划分字母区间问题概述给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串ababcc能够被分为[abab, cc]但类似[aba, bcc]划分是非法的,因为b在两个字符串都出现了。思路如果a出现的位置为2810那是不是包含a的片段一定得分割到10那前面如果有b,位置为311那是不是就又得切到11这个位置。那我们就可以想到先把每个字母最后的位置记录下来一个一个位置切下去看到哪才能断。代码class Solution { public ListInteger partitionLabels(String s) { ListInteger resnew ArrayListInteger(); int start0,end0; int[] lastnew int[26]; for(int i0;is.length();i){ last[s.charAt(i)-a]i; } for(int i0;is.length();i){ endMath.max(end,last[s.charAt(i)-a]); if(iend){ res.add(end-start1); starti1; } } return res; } }