leetcode------贪心算法2

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode------贪心算法2，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2370字，纯文字阅读大概需要4分钟。

内容图文

一、(55)跳跃游戏

**题目：**给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game

思路：
1、如果处于i位置的时候，最远可以跳到j位置，那么在i位置可以调到i->j中的任意位置，所以我们要求是否能跳到最后一个位置，只需要求出最远能到的位置是否大于数组长度-1，即最后一个元素的index；
2、定义一个变量max_value来保存每一个位置元素所能到达的最远位置，例如：第0个元素2，最远到达0+2=2;同理，第1个元素3，最远到达1+3=4；即每个元素最远到达的位置=index+nums[index];
3、在遍历过程中，如果值大于max_value，则刷新max_value,知道遍历到倒数第二个元素结束，判断max_value是否大于nums.length-1;

class Solution {
    public boolean canJump(int[] nums) {
        int max_value=0;
        for(int i=0;i<nums.length-1;i++){
            if(max_value<i){
                return false;
            }
            if(nums[i]+i>max_value){
                max_value = nums[i]+i;
            }
        }
        if(max_value>=nums.length-1){
            return true;
        }
        return false;
    }
}

二、(402)移掉K位数字

**题目：**给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
eg:
输入: num = “1432219”, k = 3
输出: “1219”
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

思路:
1、从最高位一次向下判断，如果下一位的值大于当前位，则不删除，继续向下判断，如果下一位的值小于当前位，则删除当前位，继续向下判断；该思路可以使用栈实现，将字符串按顺序push到栈中，push之前先判断栈顶的元素是否大于要push的值，如果大于，则将栈中元素pop出来，并继续比较栈顶元素。每一次pop都需要将k值–；当k<0则结束循环，然后将剩余元素push进去。
2、需要考虑2个特殊情况：
2.1、当所有元素都push完，但是k仍然>0,例如：12345，k=2；此种情况直接从栈中弹出剩余k个元素；
2.2、当高位存在无效零：0200，此时应该去掉高位0改为200；此种情况在stack.push是判断，如果栈为空，并且需要push的值为0，则不push跳过。

class Solution {
    public String removeKdigits(String num, int k) {
        char [] ch = num.toCharArray();
        String result="";
        Stack<Character> stack = new Stack<Character>();
        
        for(int i=0;i<ch.length;i++){
            while(!stack.isEmpty()&&k>0&&ch[i]<stack.peek()){
                stack.pop();
                k--;
            }
            if(stack.isEmpty()&&ch[i] == '0'){

            }else{
                stack.push(ch[i]);
            }
        }
        while(k>0&&!stack.isEmpty()){
            stack.pop();
            k--;
        }  
        while(!stack.isEmpty()){
            result = stack.peek()+result;
            stack.pop();
        }
        if(result ==""){
            return  "0";
        }
        return result;
    }
}

内容总结

以上是互联网集市为您收集整理的leetcode------贪心算法2全部内容，希望文章能够帮你解决leetcode------贪心算法2所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---