首页 > Java > java教程 > 正文

LeetCode Day 贪心算法 第 2 部分

WBOY
发布: 2024-07-09 18:16:21
转载
660人浏览过

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<prices.length; i++){
            int num = 价格[i];
            if(num > 购买 && num > 看){
                利润 = num - 购买;
                窥视=数字;
            }
            else if((num>购买 && num<peek) || num < 购买){
                总和+=利润;
                利润=0;
                购买=数量;
                窥视=数字;
            }

        }

        返还金额+利润;
    }
登录后复制

我初始化购买到 int MAX_VALUE 并忘记更新这可能会导致一些错误。

修复此问题并截断代码

精细代码

 public int maxProfit(int[] 价格) {
        if(prices.length <1){
            返回0;
        }
        利润= 0;
        int 购买 = 价格[0];
        整数总和=0;
        int peek = 价格[0];

        for(int i=0; i<prices.length; i++){
            int num = 价格[i];
            if( 数字 > 窥视){
                利润 = num - 购买;
                窥视=数字;
            }
            否则 if(num<peek){
                总和+=利润;
                利润=0;
                购买=数量;
                窥视=数字;
            }

        }
        总和+=利润;
        返回总和;
    }
登录后复制

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; i<nums.length; i++){
            if(nums[i] < 0 && k>0){

                总和 -= 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-1;){
            int 大小 = nums[i];
            整数下一个 = 0;
            int 下一个值 = 0;
            如果(大小== 0){
                返回假;
            }
            if(i+size >= 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; i++){
            if(i+nums[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; i++){
            范围 = Math.max(范围, i+nums[i]);
            if(范围 >= nums.length-1){
                步骤++;
                休息;
            }
            if(i == preRange){
                预范围=范围;
                步骤++;
            }

        }
        返回步骤;

    }
登录后复制

以上就是LeetCode Day 贪心算法 第 2 部分的详细内容,更多请关注php中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
相关标签:
来源:dev.to网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号