网站建设模板源码,海城百度公司 海城网站建设,杭州百度,南宁网站建设外包贪心算法 买卖股票的最佳时机买卖股票的最佳时机II跳跃游戏跳跃游戏II划分字母区间 买卖股票的最佳时机
给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一个不同的… 贪心算法 买卖股票的最佳时机买卖股票的最佳时机II跳跃游戏跳跃游戏II划分字母区间 买卖股票的最佳时机
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 示例 1 输入[7,1,5,3,6,4] 输出5 解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。 注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。
思路 如果第 i i i 天卖出股票则最大利润为(该天的股价-前面天数中最小的股价)然后与已知的最大利润比较如果大于则更新当前最大利润的值。
代码
class Solution {public int maxProfit(int[] prices) {int cost Integer.MAX_VALUE, profit 0;for (int i 0; i prices.length; i) {cost Math.min(cost, prices[i]);profit Math.max(profit, prices[i] - cost);}return profit;}
}买卖股票的最佳时机II
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。 在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。 返回 你能获得的 最大 利润 。 示例 1 输入prices [7,1,5,3,6,4] 输出7 解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。 随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3。 最大总利润为 4 3 7 。
思路 分解成每天都买卖但是只在最后的结果中加入正的局部最优-全局最优。
代码 注意 i 从 1 开始
class Solution {public int maxProfit(int[] prices) {int profit 0;for (int i 1; i prices.length; i) {profit Math.max(prices[i] - prices[i-1], 0);}return profit;}
}跳跃游戏
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。 示例 1 输入nums [2,3,1,1,4] 输出true 解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 示例 2 输入nums [3,2,1,0,4] 输出false 解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。
思路 确定从第一个位置开始能够跳跃到的范围有多少如果这个范围能够覆盖到数组的最后一个位置那么就可以范围true。
代码
class Solution {public boolean canJump(int[] nums) {int cover 0; // 覆盖范围// 遍历的范围是cover内for (int i 0; i cover; i) {// 遍历到一个位置就从上一个cover和该位置能够到达的最远位置取最大值cover Math.max(cover, i nums[i]);if (cover nums.length - 1) {// 如果能够覆盖到数组的最后一个位置return true;}}return false;}
}跳跃游戏II
在上一题的基础上要求返回最少跳跃次数。 示例 1: 输入: nums [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。
思路 代码
class Solution {public int jump(int[] nums) {int curRight 0; // 已经造桥的右端点int nextRight 0; // 下一步造桥最远的端点int ans 0; // 答案// for 循环中 i nums.length - 1// 因为开始的时候边界时第0个位置ans已经加过一次1了最后末尾的时候不用计算步数了for (int i 0; i nums.length - 1; i) {nextRight Math.max(nextRight, i nums[i]);if (i curRight) { // 到达已建造的桥的右端点curRight nextRight; // 建造桥ans;}}return ans;}
}划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。 注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。 示例 1 输入s “ababcbacadefegdehijhklij” 输出[9,7,8] 解释 划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的因为划分的片段数较少。 示例 2 输入s “eccbbbbdec” 输出[10]
思路 先用一个hash数组把字符串中每一个字母出现的最远位置下标存储在hash数组中。 遍历字符串更新当前要划分的区间的最远距离当前最远距离与该位置字母的最远位置下标取最大值 然后判断此时的最远位置是否是当前位置如果是说明已经找到了一个划分的区间。 结合代码随项目的思路来解题
代码
class Solution {public ListInteger partitionLabels(String s) {int[] hash new int[26];for (int i 0; i s.length(); i) {// 求某个字母的最远位置使用hash来记录// s.charAt(i) - a是字母的索引i是这个字母目前的最远位置hash[s.charAt(i) - a] i;}int left 0, right 0;ListInteger ans new ArrayList();for (int i 0; i s.length(); i) {// 现有的右边界和当前位置字母的最远出现位置求maxright Math.max(right, hash[s.charAt(i) - a]);// i right 说明找到了一个分割点if (i right) {ans.add(right - left 1);left right 1; } }return ans;}
}
