跳转到主内容
趣航编程网 - 趣学编程,启航技术之路!

LeetCode Day 贪心算法 第 2 部分

122. 买卖股票的最佳时机 II 给你一个整数数组prices,其中prices[i]是给定股票在第i天的价格。 每天,您都可以决定购买和/或出售股票。您在任何时候最多只能持有一股股票。但是,您可以购买并在同一天立即出售。 找到并返还你能获得的最大利润。 示例1: 输入:价格 = [7,1,5,3,6,4] 输出:7 说明:第 2 天买入(价格 = 1),第 3 天卖出(价格 = 5),利润 = 5-1 = 4。 然后在第4天买入(价格=3)并在第5天卖出(价格=6),利润=6-3=3. 总利润为 4 + 3 = 7. 示例2: 输入:价格 = [1,2,3,4,5] 输出:4 说明:第 1 天买入(价格 = 1),第 5 天卖出(价格 = 5),利润 = 5-1 = 4。 总利润为4. 示例3: 输入:价格 = [7,6,4,3,1] 输出:0 说明:没有办法赚取正利润,所以我们从来不买股票来实现最大利润0。 限制: 1 0 原始页面 错误代码
public int maxProfit(int[] 价格) { 利润= 0; int 购买 = Integer.MAX_VALUE; 整数总和=0; int 窥视 = 0; for(int i=0; i 购买 && num > 看){ 利润 = num - 购买; 窥视=数字; } else if((num>购买 && num
我初始化购买到 int MAX_VALUE 并忘记更新这可能会导致一些错误。 修复此问题并截断代码 精细代码
public int maxProfit(int[] 价格) { if(prices.length <1){ 返回0; } 利润= 0; int 购买 = 价格[0]; 整数总和=0; int peek = 价格[0]; for(int i=0; i 窥视){ 利润 = num - 购买; 窥视=数字; } 否则 if(num
1005. K 个否定后数组的和最大化 给定一个整数数组 nums 和一个整数 k,按以下方式修改该数组: 选择一个索引 i 并将 nums[i] 替换为 -nums[i]。 您应该准确应用此过程 k 次。您可以多次选择相同的索引 i。 这样修改后返回数组可能的最大和。 示例1: 输入:nums = [4,2,3], k = 1 输出:5 解释:选择索引 1,nums 变为 [4,-2,3]。 示例2: 输入:nums = [3,-1,0,2], k = 3 输出:6 解释:选择索引 (1, 2, 2),nums 变为 [3,1,0,2]。 示例3: 输入:nums = [2,-3,-1,5,-4], k = 2 输出:13 解释:选择索引 (1, 4),nums 变为 [2,3,-1,5,4]。 限制: 1 -100 1 原始页面
public int MaximumSumAfterKNegations(int[] nums, int k) { Arrays.sort(nums); int 变化 = nums[nums.length-1] >=0?0:nums.length-1; 整数总和=0; for(int i=0; i0){ 总和 -= nums[i]; k——; }别的{ 总和 += nums[i]; } // 找到交叉点 if(i>0 && nums[i-1]<=0 && nums[i]>0){ if(-nums[i-1]>nums[i]){ 改变=我; }别的{ 变化=i-1; } } } // k>nums.length 所以我们需要用完这些 k 如果(k>0){ 如果(k%2!=0){ //找到最小绝对值 sum -= 2*Math.abs(nums[变化]); } } 返回总和; }
55. 跳跃游戏 给你一个整数数组 nums。您最初位于数组的第一个索引处,数组中的每个元素代表您在该位置的最大跳跃长度。 如果可以到达最后一个索引,则返回 true,否则返回 false。 示例1: 输入:nums = [2,3,1,1,4] 输出:true 说明:从索引 0 跳 1 步到 1,然后跳 3 步到最后一个索引。 示例2: 输入:nums = [3,2,1,0,4] 输出:假 说明:无论如何,你总是会到达索引 3。它的最大跳转长度为0,这使得它无法到达最后一个索引。 限制: 1 0 错误代码
public boolean canJump(int[] nums) { //判断是否到达最后一个元素,这样我们只能看到是否到达倒数第二个元素 for(int i=0; i= nums.length){ 返回真; } //查找当前步中的最大步数 for(int j=0; j<=size; j++){ // 计算索引和值的最大值 if(i+j+nums[i+j]>下一个){ 下一个 = i+j+nums[i+j]; } } 我=下一个; } 返回真; }
错误代码2
public boolean canJump(int[] nums) { if(nums.length==1){ 返回真; } if(nums[0] == 0){ 返回假; } for(int i=0; i=nums.length-1){ 返回真; } } 返回假; }
public boolean canJump(int[] nums) { if(nums.length==1){ 返回真; } 整数范围=0; for(int i=0; i<=范围; i++){ 范围 = Math.max(范围, i+nums[i]); if(范围 >= nums.length-1){ 返回真; } } 返回假; }
45. 跳跃游戏二 给你一个 0 索引的长度为 n 的整数 nums 数组。您最初位于 nums[0]. 每个元素nums[i]代表从索引i向前跳转的最大长度。换句话说,如果你在 nums[i],你可以跳转到任何 nums[i + j],其中: 0 i + j 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以达到 nums[n - 1]。 示例1: 输入:nums = [2,3,1,1,4] 输出:2 说明:到达最后一个索引的最小跳转次数为 2。从索引 0 到 1 跳转 1 步,然后跳转 3 步到最后一个索引。 示例2: 输入:nums = [2,3,0,1,4] 输出:2 限制: 1 0 保证你能达到nums[n - 1].
公共 int 跳转(int[] nums) { if(nums.length == 1){ 返回0; } 整数步=0; 整数范围=0; int 预设范围 = 0; for(int i=0; i= nums.length-1){ 步骤++; 休息; } if(i == preRange){ 预范围=范围; 步骤++; } } 返回步骤; }

相关文章