[leetcode/lintcode 题解] Google 面试题：奇偶跳

[hakunamatata11]

给定一个整数数组 A 。从某一些起始索引，你可以做一系列的跳跃。其中的（第 1，第 3，第 5 ......）跳跃称为奇数跳跃，（第 2，第 4，第 6 ......）跳跃称为偶数跳跃。

你可以从索引 i 以下列方式跳转到索引 j （ i <j ）：

在奇数跳跃（即跳跃 1,3,5，...）期间，跳转到索引 j，使得 A [i] <= A [j]并且 A [j]是可能的最小值。如果有多个这样的索引 j，则只能跳转到最小的索引 j 。 在偶数跳跃（即跳跃 2,4,6，...）期间，跳转到索引 j，使得 A [i]> = A [j]，A [j]是最大的可能值。如果有多个这样的索引 j，则只能跳转到最小的索引 j 。（可能存在某些索引，不存在合法的跳跃）

如果从该索引开始，您可以通过跳转一些次数（大于等于 0 次）到达数组的末尾（索引 A.length - 1 ），那么这是一个有效的起始索引。

返回有效的起始索引的个数。

• <= A.length <= 20000
• 0 <= A[i] < 100000

在线评测地址：https://www.lintcode.com/problem/odd-even-jump/?utm_source=sc-v2ex-fks

样例 1:

输入: [10,13,12,14,15]
输出: 2
解析: 
从 index i = 0 开始，我们可以跳跃至 i = 2 (因为 A[2] 是 A[1], A[2], A[3], A[4] 中 >= A[0]最小的), 然后我们就无法再继续跳跃了
从 i = 1 和 i = 2 开始, 我们可以跳跃至 i = 3, 然后无法再继续跳跃了
从 i = 3 开始, 我们可以跳跃至 i = 4, 因此我们可以到达末尾
从 i = 4 开始, 我们已经在末尾了
综上, 有 2 个有效的索引 (i = 3, i = 4) 我们可以经过一系列的跳跃达到末尾

样例 2:

输入: [2,3,1,1,4]
输出: 3
解析: 
从 i = 0 开始, 我们可以跳跃至 i = 1, i = 2, i = 3:

在我们的第一次跳跃 (奇数跳), 我们先跳跃至 i = 1, 因为 A[1] 是 (A[1], A[2], A[3], A[4] >= A[0]) 当中最小的，

在我们的第二次跳跃 (偶数跳), 我们从 i = 1 跳到 i = 2 因为 A[2] 是 (A[2], A[3], A[4] <= A[1])当中最大的.  A[3] 也是最大的, 但是 2 是更小的索引, 所以我们跳到 i = 2 而不是 i = 3.

在我们的第三次跳跃 (奇数跳),我们从 i = 2 跳到 i = 3 因为 A[3] 是 (A[3], A[4] >= A[2])当中最小的

我们不能从 i = 3 跳跃 i = 4, 因此起始索引 i = 0 是无效的

根据同样的规则，我们可以求出：
存在 3 个有效的起始索引 (i = 1, i = 3, i = 4) 我们可以跳跃至末尾

[题解] 使用 Java 中的 TreeMap 用于高效查找当前 index 之后的相对的最小值和最大值。 定义两个 boolean 数组记录当前 index 是否可以奇数跳以及偶数眺到达末尾。 逆推的思维找到有效的起始索引。

public class Solution {
    /**
     * @param A: An integer array A
     * @return: Return the number of good starting indexes
     */
    public int oddEvenJumps(int[] A){
        int res = 1, lenA = A.length;
        
        // higher[i] = true 代表从索引 i 奇数跳可以到达末尾
        boolean []higher = new boolean[lenA];
        // lower[i] = true 代表从索引 i 偶数跳可以到达末尾
        boolean []lower = new boolean[lenA];
        // 初始化最后一个位置，无论哪种跳法都是已经在末尾了
        higher[lenA - 1] = lower[lenA - 1] = true;
        // 记录 value - index
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        treeMap.put(A[lenA - 1], lenA - 1);
        for (int i = lenA - 2; i >= 0; i--) {  // 逆推，分两种情况
            // 找到 index = i 之后大于等于 A[i]的最小的数
            Map.Entry high = treeMap.ceilingEntry(A[i]);
            // 找到 index = i 之后小于等于 A[i]的最大的数
            Map.Entry low = treeMap.floorEntry(A[i]);
            
            if (high != null){ // 当前位置进行奇数跳取决于目的地的偶数跳是否能到达终点
                higher[i] = lower[(int)high.getValue()];
            }
            if (low != null){  // 同理
                lower[i] = higher[(int)low.getValue()];
            }
            // 起始点一定是奇数跳
            if (higher[i]){
                res ++;
            }
            treeMap.put(A[i], i);
        }
        return res;
    }
}

更多语言代码参见： https://www.jiuzhang.com/solution/odd-even-jump/?utm_source=sc-v2ex-fks