45. Jump Game II

这是一个被自己蠢哭的故事。。。

思路1 - 回溯

最近做了很多回溯的题目，比如数独问题和八皇后问题，所以看到这道题目也是先想用回溯把所有可能的解法列出来，然后求出最小的步数。其实就是暴力算法，结果是毫无疑问的TLE。

public class Solution {
    private int minStep = Integer.MAX_VALUE;

    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        if (nums.length == 2)
            return 1;
        // 要到达index，有哪些点可以一步到达？
        // 注意value list要是有序的
        // 这时一个类似“建索引”的过程
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

        for (int i = 0; i < nums.length; i++) {
            // 当前点可以一步到达哪些点？
            for (int j = 1; j <= nums[i]; j++) {
                // 从点i可以一步到达点target，都是数组下标
                int target = i + j;
                if (target >= nums.length)
                    break;
                // 有点类似倒排索引的概念
                if (map.containsKey(target)) {
                    map.get(target).add(i);
                } else {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(i);
                    map.put(target, list);
                }
            }
        }
        //System.out.println(map);

        minStep = Integer.MAX_VALUE;
        // 从最后一个点开始回溯
        tryStep(map, 0, nums.length - 1);
        return minStep;
    }

    // 下一步要走到nextIndex
    private void tryStep(Map<Integer, List<Integer>> map, int currentStep, int nextIndex) {
        // 不存在一步走到0的情况，递归终止
        if (nextIndex == 0) {
            minStep = Integer.min(minStep, currentStep);
            return;
        }
        // 如果当前的步数已经大于等于minStep了，继续找下去肯定会更大，递归终止
        if (currentStep >= minStep) {
            return;
        }
        // 有哪些点可以一步到达nextIndex？
        for (int i : map.get(nextIndex)) {
            tryStep(map, currentStep + 1, i);
        }
    }
}

理论上这段程序可以列出所有可能的解法，当然也就能求出minStep，但也是很低效。构造map的过程就是O(N^2)了，数据量一大，还没开始tryStep就会TLE。

思路2 - 伪DP

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        if (nums.length == 2)
            return 1;
        // 要到达index，有哪些点可以一步到达？
        // 注意value list要是有序的
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

        for (int i = 0; i < nums.length; i++) {
            // 当前点可以一步到达哪些点？
            for (int j = 1; j <= nums[i]; j++) {
                // 从点i可以一步到达点target，都是数组下标
                int target = i + j;
                if (target >= nums.length)
                    break;
                if (map.containsKey(target)) {
                    map.get(target).add(i);
                } else {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(i);
                    map.put(target, list);
                }
            }
        }

        // dp[i]表示从0到i所需要的最小步数
        int[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = 1;   // 题目保证一定有解，所以dp[1]必定是1
        for (int i = 2; i < dp.length; i++) {
            List<Integer> oneStepList = map.get(i);  // 从哪些点可以一步走到i？
            int min = Integer.MAX_VALUE;
            // 这个for是不是能想办法优化掉
            for (int j : oneStepList) {
                min = Integer.min(min, dp[j]);
            }
            dp[i] = min + 1;
        }
        return dp[nums.length - 1];
    }
}

可以看出这不是真正的dp，因为当前状态不是依赖于有限的历史状态，结果就是求dp[i]时还要一个for循环。。。而且构造map的过程没啥改进，数据量一大，构造map时还是会TLE。

思路3 - greedy

思路其实和之前差不多，首先要知道有哪些点可以一步跳到end。但是这些点里我只要关心最左端的点就可以了，其他的点都不用关心，假设这个点是A。然后再计算有哪些点可以一步跳到A，同样找到最左端的点B。重复这个过程直到第0个元素。

这里有个很重要的规律：如果i<j<k，从i跳到j需要的最小步数是a，从i跳到k需要最小步数b，则有a<=b，仔细想想就能明白。

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        if (nums.length == 2)
            return 1;
        // 从第一个元素跳到最后一个元素
        return innerJump(nums, 0, nums.length - 1);
    }
    // 求出从begin跳到end需要的最小步数
    private int innerJump(int[] nums, int begin, int end) {
        if (begin == end) {
            return 0;
        }
        // greedy
        // 有哪些点可以一步跳到end，从这些点中取出最左侧的那个
        int left = leftmostIndex(nums, begin, end);
        return innerJump(nums, begin, left) + 1;
    }

    private int leftmostIndex(int[] nums, int begin, int end) {
        // 最左端，哪个点能一步跳到end？
        for (int i = begin; i < end; i++) {
            int target = i + nums[i];
            if (target >= end) {
                return i;
            }
        }
        // 不可能返回-1，因为题目说一定有解
        return -1;
    }
}

这个解法理论上是正确的，但还是TLE。。。因为在计算leftmostIndex时，还是一个for循环去遍历。总的复杂度还是O(N^2)。leetcode有一个特殊的test case是[1,1,1,...,1]，总共2.5w个1。。。碰到这个case这个解法必定TLE啊。。。而且由于数据量很大，递归的嵌套层次也很深，还容易StackOverflow。。。

思路4 - greedy + 线段树

思路3的解法其实是正确的，关键应该怎样提高求leftmost的效率？我想到了线段树。

对于输入[3,3,2,1,1,1]，0号元素是3，可以从0号元素一步跳到[1,3]中的任意一个元素，表示为0->[1,3]，同理有1->[2,4]，但是对index in (1,2,3)的情况下，已经有0号元素可以跳到了，而0号元素明显在1号元素左边，所以实际上是1->[4,4]。我们可以为所有元素都计算出这样一个映射关系，映射到一个线段上，这个过程是O(N)的。

求leftmost时，我们只要快速计算出给定的index在哪个线段中，然后就能反向找出leftmost了。既然是区间相关的问题，自然就想到了线段树。

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        if (nums.length == 2)
            return 1;

        // 构造线段树的过程
        LineTree head = null;
        for (int i = 0; i < nums.length - 1; i++) {
            // 因为有0的存在，其实这不是一个完整的线段树，比如父节点是[0,10]，子节点可能是[0,4]和[7,10]
            // 但不影响本题，因为我们用线段树是为了加速查找leftmost的过程
            // 我们不会寻找一个为0的元素的leftmost
            if (nums[i] == 0)
                continue;
            // 从当前元素i，可以一步达到哪些元素？
            int begin = i + 1, end = i + nums[i];
            if (end >= nums.length) // 注意end的边界
                end = nums.length - 1;
            if (begin <= end) {
                if (head == null) {
                    head = new LineTree(begin, end, i);
                } else {
                    // 插入一个节点，注意这里的逻辑
                    // 如果当前的[begin,end]完全包括在head的[begin,end]里，就不用做任何事
                    // 如果二者有重合的部分，才需要新增一个节点
                    // 由于这道题目的特殊性，重合的部分只可能是右侧，而且插入节点必定创建一个新的head
                    if (head.begin <= begin && end <= head.end) {
                        // do nothing
                        continue;
                    }
                    LineTree newHead = new LineTree(head.begin, end, -1);
                    LineTree right = null;
                    if (head.end < begin) {
                        right = new LineTree(begin, end, i);
                    } else {
                        right = new LineTree(head.end + 1, end, i);
                    }
                    newHead.left = head;
                    newHead.right = right;
                    head = newHead;
                }
            }
        }
        // 从第一个元素跳到最后一个元素
        return innerJump(nums, 0, nums.length - 1, head);
    }

    // 计算从begin跳到end的最小步数
    private int innerJump(int[] nums, int begin, int end, LineTree head) {
        // 把尾递归优化掉了，避免StackOverFlow
        int count = 0;
        while (begin < end) {
            // greedy。从left跳到end只需要1，所以我们只要计算从begin跳到left的最小步数再加1就好了
            int left = leftmostIndex(nums, end, head);
            count++;
            end = left;
        }
        return count;
    }

    private int leftmostIndex(int[] nums, int end, LineTree head) {
        LineTree cur = head;
        // 最左端，哪个点能一步跳到end？
        while (cur.contains(end)) {
            if (cur.isLeaf())
                return cur.value;
            if (cur.left != null && cur.left.contains(end))
                cur = cur.left;
            else
                cur = cur.right;
        }
        // 不可能返回-1，上面的while也不可能死循环或NPE，因为题目说一定有解
        return -1;
    }
}

class LineTree {
    // 线段树，包括begin和end，inclusive
    int begin = 0, end = 0;
    int value = 0;
    LineTree left, right;

    public LineTree(int begin, int end, int value) {
        this.begin = begin;
        this.end = end;
        this.value = value;
    }

    public boolean isLeaf() {
        return left == null && right == null;
    }

    public String toString() {
        return begin + "," + end + ":" + value;
    }

    public boolean contains(int x) {
        return x >= begin && x <= end;
    }
}

但这个解法还是TLE。。。因为[1,1,1,1...1]这种case，对应的映射关系是0->[1,1], 1->[2,2], 2->[3,3], 3->[4,4] ...，线段树会退化为一颗“点树”，由于数据都在叶子节点，所以数据量大时查找会很慢。

思路5 - greedy + TreeMap

还是在思路4的基础上优化。线段树退化为“点树”，查找很慢，部分原因是因为数据都在叶子节点上。如果改成非叶节点也能存数据，类似于二叉树的形式，是不是会好很多？

但转念一想不对啊，即使是二叉树，这种情况下也会退化为list，因为输入是有序的：0->[1,1], 1->[2,2], 2->[3,3], 3->[4,4] ...，查找性能肯定还是很差。一般应对这种情况会用到AVL树，难道要我写个AVL版的二叉线段树？AVL树实在很复杂，我估计我写不来。。。

于是考虑使用新的数据结构，最好是能在O(1)时间内找到leftmost。看到O(1)就会想到map，有没有线段map？突然想到guava中有个RangeMap，看了下API，卧槽这就是我要的啊。虽然它本质上是用红黑树存储数据的（红黑树本身就是平衡的），查找是O(logN)，不是O(1)。最关键的是leetcode中不能用guava啊。。。

于是去google，找找jdk中有没有类似RangeMap的工具，找到了这个：http://stackoverflow.com/questions/1314650/using-java-map-for-range-searches。原来TreeMap也可以做到类似的功能，它的内部也是个红黑树。。。以前都不知道TreeMap可以做范围查询，还是自己用的不熟啊。。。

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        if (nums.length == 2)
            return 1;

        // build index
        // 用TreeMap去模拟范围查询
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        int curEnd = -1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0)
                continue;
            // 从当前元素i，可以一步达到哪些元素？
            int begin = i + 1, end = i + nums[i];
            if (end >= nums.length) // 注意end的边界
                end = nums.length - 1;
            if (begin <= end) {
                if (curEnd == -1) {
                    map.put(begin, i);
                    curEnd = end;
                    continue;
                }
                if (end <= curEnd) {
                    // do nothing
                    continue;
                }

                if (begin > curEnd) {
                    map.put(begin, i);
                } else {
                    map.put(curEnd + 1, i);
                }
                curEnd = end;
            }
        }
        // 从第一个元素跳到最后一个元素
        return innerJump(nums, 0, nums.length - 1, map);
    }

    // 计算从begin跳到end的最小步数
    private int innerJump(int[] nums, int begin, int end, TreeMap<Integer, Integer> map) {
        int count = 0;
        while (begin < end) {
            // greedy。从left跳到end只需要1，所以我们只要计算从begin跳到left的最小步数再加1就好了
            int left = leftmostIndex(nums, end, map);
            count++;
            end = left;
        }
        return count;
    }
    // 注意这个求leftmost的过程
    private int leftmostIndex(int[] nums, int end, TreeMap<Integer, Integer> map) {
        return map.floorEntry(end).getValue();
    }
}

整体的算法复杂度应该是O(NlogN)吧。这个算法终于AC了，但是还是比较慢，只能beat 1.7%。。。

思路6 - 另一种greedy

看了其他人的解法，发现其实解法可以很简单。。。20行代码以内就可以解决。。。而且是O(N)的解法。顿时觉得自己之前考虑那么多，纠结那么久好蠢啊。。。

本质还是greedy，但却跟我是不一样的思路：

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        if (nums.length == 2)
            return 1;

        int count = 0;
        // 走n步最多可以走到last，走n+1步最多可以走到now
        // 这个过程要仔细想想
        int now = 0, last = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] + i > now)
                now = nums[i] + i;
            if (last == i) {
                last = now;
                count++;
            }
        }

        return last >= nums.length - 1 ? count : count + 1;
    }
}

这个解法的思路是“正向”的，计算走n步最多能走到哪里。而我的思路是“反向”的，计算要走到end，上一步应该走哪里。所以即使是相同步数下，我们给出的解法可能也不同，比如对于输入[3,100,200,4,5,6]，我的解是3->100>6，而另一种解法是3->200->6。

只能呵呵了。。。