findingsea's Studio.

Jump Game II@LeetCode

LeetCode
Word count: 207 / Reading time: 1 min
2015/04/06 Share

Jump Game II

比较典型的贪心。维护一个区间，区间表示第i步所能到达的索引范围。递推的方法为：每次都遍历一遍当前区间内的所有元素，从一个元素出发的最远可达距离是index+array[index]，那么下一个区间的左端点就是当前区间的右端点+1，下一个区间的右端点就是当前区间的max(index+array[index])，以此类推，直到区间包含了终点，统计当前步数即可。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int jump(int[] A) {
        if (A.length == 1)
            return 0;
        int max = 0, count = 1, begin = 0, end = A[0];
        while (end < A.length - 1) {
            count++;
            int index = begin;
            for (; index <= end; index++) {
                max = Math.max(max, index + A[index]);
            }
            begin = index;
            end = max;
        }
        return count;
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/04/06/jump-game-ii/

发表日期: April 6th 2015, 11:05:00 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 100
2020
2019
2018
2017
2015
2014
2013
Octopress GitHub Python Django 吐槽 Reading ACM 项目总结 JavaScript 日志 Java LeetCode Interview Algorithm Life Windows ffmpeg life Go c++ essay review