一、问题描述
一只青蛙从数组(A)的每一个元素向数组尾部跳动。跳动规则如下：
- 当奇数跳的时候，就是第1、3、5、7....次进行移动时候，移动规则A[i] <= A[j], 并且A[j] = min(A[i+1], A[A.length-1])； 并且i < j，下同； 若A[j] = A[i]则返回最小的j索引，下同。
- 当偶数跳的时候，就是第2、4、6、8....次进行移动的时候，移动规则A[i] >= A[j]，并且A[j] = max(A[i+1], A[A.length-1])
问，能从起点跳到终点的次数有多少个？
二、思想
两种。
1、从前往后计算。
- 每次如果能完成从前往后的计算，那么记录奇数跳和偶数跳过的位置。
- 如果奇数跳或者偶数跳经过的地方能到达终点，则直接结果进行+1
2、从后向前计算。
- 由于可以从任一点出发，因此更好的做法是从后向前计算。
- 其它的整体思路和从前向后计算差不多
三、Code
从前向后计算和从后向前计算的Code都写过，但是从后向前的效果更好些。因此只贴出从后向前的代码。主要是掌握思想。
package algorithm;
import java.util.HashMap;
import java.util.TreeSet;
public class OddEvenJump {
public int oddEvenJump(int[] A) {
int res = 0, n = A.length;
boolean[] odd = new boolean[n];
boolean[] even = new boolean[n];
odd[n - 1] = true;
even[n - 1] = true;
TreeSet<Integer> set = new TreeSet<>();
HashMap<Integer, Integer> map = new HashMap<>();
set.add(A[n - 1]);
map.put(A[n - 1], n - 1);
for (int i = n - 2; i >= 0; i--) {
Integer oddJump = set.ceiling(A[i]);
if (oddJump != null) {
odd[i] = even[map.get(oddJump)];
if (odd[i]) res++;
}
Integer evenJump = set.floor(A[i]);
if (evenJump != null) {
even[i] = odd[map.get(evenJump)];
}
set.add(A[i]);
map.put(A[i], i);
}
return res;
}
}