狗家奇偶跳思路

狗家奇偶跳有标准解答了么，看到讨论说用dp做，没想通

这题可以稍微形式化地描述一下，理解起来应该是比较容易的

给定长度为n的数组A，首先根据题目定义位置J元素的奇数后继和偶数后继（如果没有后继的话可以取值-1）：
--
SuccessorOdd(J) = min { K | J < K 且 A[J] < A[K] 且 A[K] - A[J]在所有满足条件的K中是最小的 }

SuccessorEven(J) = min { K | J < K 且 A[J] > A[K] 且 A[J] - A[K]在所有满足条件的K中是最小的 }
--

现在先假定SuccessorOdd(J)和SuccessorOdd(K)是两个已知数组，我们后面再考虑怎么计算它们。

然后，定义
--
ReachableOdd(I) = 从位置I跨出奇数步时，是否可以到达最后位置

ReachableEven(I) = 从位置I跨出偶数步时，是否可以到达最后位置
--

容易写出递归表达式
--
ReachableOdd(I) = ReachableEven(SuccessorOdd(I))
边界条件：ReachableOdd(-1) = false

ReachableEven(I) = ReachableOdd(SuccessorEven(I)
边界条件：ReachableEven(-1) = false
--
这个表达式可以用TopDown + Memo或者BottomUp的方式用O(n)时间计算出来（也就是DP）。

最后，我们考虑如何求解SuccessorOdd和SuccessorEven。这个问题本质上是一维的nearest neighbor（NN），经典索引结构就是平衡树（C++ map，Java TreeMap等等）。在数据量比较大以及数据分布skew不严重的时候，网格化（hash）方法一般会有更好的性能。

具体来说，就是从后往前扫一遍数组，并维护一个NN的索引结构（例如平衡树）映射数组中每一个值到其位置。对于每一个元素A[J]，先在当前索引中寻找取值离A[J]最近的元素（Odd是向上最近，Even是向下最近）。这个可以使用C++ map的upper_bound/lower_bound，或者Java TreeMap的higherEntry/lowerEntry，在O(log(n))时间做到。然后将A[J]到J的映射也添加到索引中。

总时间复杂度就是O(n log(n))（用hash方法可以expected O(n)，如果没有skew的话）


补充内容 (2019-1-13 14:32):
递归表达式的边界条件还要加两条：ReachableOdd(n-1) = true；ReachableEven(n-1) = true

你说的是 975， 昨天的Leetcode contest 的题目？
https://leetcode.com/contest/weekly-contest-119/problems/odd-even-jump/

You are given an integer array A.  From some starting index, you can make a series of jumps.  The (1st, 3rd, 5th, ...) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:

During odd numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value.  If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, ...), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value.  If there are multiple such indexes j, you can only jump to the smallest such index j.
(It may be the case that for some index i, there are no legal jumps.)
A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

1. class Solution {
   
2.     public int oddEvenJumps(int[] A) {
   
3.         int n = A.length;
   
4.         TreeMap<Integer, Integer> nextGreater = new TreeMap<>((i, j) -> A[i] == A[j] ? i - j : Integer.compare(A[i], A[j]));
   
5.         initTreeMap(A, nextGreater);
   
6.         TreeMap<Integer, Integer> nextSmaller = new TreeMap<>((i, j) -> A[i] == A[j] ? i - j : -Integer.compare(A[i], A[j]));
   
7.         initTreeMap(A, nextSmaller);
   
8.         Map<Integer, Set<Integer>> oddJumpFrom = getJumpFrom(nextGreater);
   
9.         Map<Integer, Set<Integer>> evenJumpFrom = getJumpFrom(nextSmaller);
   
10.         boolean[] canStartFromOddJump = new boolean[n];
    
11.         boolean[] canStartFromEvenJump = new boolean[n];
    
12.         canStartFromOddJump[n - 1] = true;
    
13.         Set<Integer> odds = oddJumpFrom.getOrDefault(n - 1, new HashSet<Integer>());
    
14.         Set<Integer> evens = evenJumpFrom.getOrDefault(n - 1, new HashSet<Integer>());
    
15.         while(!odds.isEmpty() || !evens.isEmpty()) {
    
16.             Set<Integer> newOdds = new HashSet<>();
    
17.             Set<Integer> newEvens = new HashSet<>();
    
18.             for (Integer odd: odds) {
    
19.                 canStartFromOddJump[odd] = true;
    
20.                 for (Integer even: evenJumpFrom.getOrDefault(odd, new HashSet<Integer>())) {
    
21.                     if (!canStartFromEvenJump[even]) newEvens.add(even);
    
22.                 }
    
23.             }
    
24.             for (Integer even: evens) {
    
25.                 canStartFromEvenJump[even] = true;
    
26.                 for (Integer odd: oddJumpFrom.getOrDefault(even, new HashSet<Integer>())) {
    
27.                     if (!canStartFromOddJump[odd]) newOdds.add(odd);
    
28.                 }
    
29.             }
    
30.             odds = newOdds;
    
31.             evens = newEvens;
    
32.         }
    
33.         int result = 0;
    
34.         for (boolean valid: canStartFromOddJump) {
    
35.             if (valid) result++;
    
36.         }
    
37.         return result;
    
38.     }
    
39.    
    
40.     public void initTreeMap(int[] A, TreeMap<Integer, Integer> treeMap) {
    
41.         for (int i = A.length - 1; i >= 0; i--) {
    
42.             Integer next = treeMap.higherKey(i);
    
43.             treeMap.put(i, next);
    
44.         }
    
45.     }
    
46.    
    
47.     public Map<Integer, Set<Integer>> getJumpFrom(TreeMap<Integer, Integer> treeMap) {
    
48.         Map<Integer, Set<Integer>> result = new HashMap<>();
    
49.         for (Map.Entry<Integer, Integer> entry: treeMap.entrySet()) {
    
50.             Integer from = entry.getKey();
    
51.             Integer to = entry.getValue();
    
52.             if (to != null) {
    
53.                 result.putIfAbsent(to, new HashSet<Integer>());
    
54.                 result.get(to).add(from);
    
55.             }
    
56.         }
    
57.         return result;
    
58.     }
    
59. }

复制代码

顶zsszszszsz

吹梦到西洲 发表于 2019-1-13 10:06
有的。

没看到代码啊

magicsets 发表于 2019-1-13 14:31
这题可以稍微形式化地描述一下，理解起来应该是比较容易的

给定长度为n的数组A，首先根据题目定义位置J ...

看了这个解析，感觉好可怕。。。这种问题即使是onsite想写出来也很麻烦。。。现在面试都这么难了么。

同意magicsets的思路，我的解法有一点小的区别
1. 先创建两个Map，算出对每个起始点，它的 next odd jump 和 next even jump的位置，没有则为null. 具体实现上可以用Java里的TreeMap.higherKey
2. 再创建两个Map，算出对每一个位置做为终止点，它可以从哪些位置跳过来。
3. 从最后一个位置，算出它可以从哪些位置跳过来，从这些位置又可以从哪些位置跳过来，注意ood jump， even jump 交替。用boolean array 去重
4. 所有可以先开始odd jump最后到达最后一个位置的都是合法的。

同在准备google OA