《Java算法》贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法的经典案例：

跳跃游戏：

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

例如：[2,3,1,1,4,2,2,1] 很明显最短路线：2跳到3的位置，再跳到4的位置，然后就可以跳到最后。

算法思路：（绿色圈表示当前位置，橙色表示能够达到的最远距离）

从第一个数字2开始，能达到橙色1的位置。能达到的最远位置变更。

走到绿色3的位置，这个位置能达到的最远位置变成橙色4的位置，最远位置变更，步数加一。

继续走到绿色1的位置，这个位置能达到的最远位置不如橙色4的位置，最远位置没有变化，步数不变。

继续走到绿色4的位置，这个位置能达到的最远位置为橙色1的位置，最远位置变化，步数加一，且已经到达终点，循环结束。

该算法：

时间复杂度：O(n)O(n)。

空间复杂度：O(1)O(1)。

代码如下：

public class Subject92 {

    public static void main(String[] args) {

        int[] arrInt = new int[]{2,3,1,1,4,2,1};

        System.out.println(new Subject92().jump(arrInt));

    }

    public int jump(int[] nums) {

        //小于等于1的都不需要跳

        int lengths = nums.length;

        if(lengths <= 1){

            return 0;

        }

        int reach = 0;  //当前能走的最远距离

        int nextreach = nums[0];

        int step = 0;  //需要步数

        for(int i = 0;i<lengths;i++){

            //贪心算法核心：这一步是不是可以比上一步得到更多步数，可以则取最新的路线。

            nextreach = Math.max(i+nums[i],nextreach);

            if(nextreach >= lengths-1) return (step+1);

            if(i == reach){

                step++;

                reach = nextreach;

            }

        }

        return step;

    }

}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

巴特西

《Java算法》贪心算法

最新文章

热门文章