中级农民
- 积分
- 112
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2018-11-14
- 最后登录
- 1970-1-1
|
975. Odd Even Jump
这题要求我们找出一个int数组中good starting index(gsi)的数量,这里的gsi的定义是说:一个数从奇数次跳是选择后面数中大于它本身的最小的数,欧数次跳是选择后面数中小于它本身中最大的数,如果能够经过奇偶跳最终抵达最后一个数的话,最开始的starting index就算做gsi。当我们在草稿纸上手动跑一下过程就可以get到两个规律。首先,最后一个数永远是gsi。第二,index i 的奇数跳 如果是gsi,那么index i - 1的偶数跳也是。同样的,如果index i 的偶数跳 如果是gsi,那么index i - 1的奇数跳也是gsi。第一条和第二条规律让我们能够构建出一个dp。为了能够快速选择奇偶跳的下一个数,我们可以时候用treemap的ceilingkey和floorKey。
- class Solution {
- public int oddEvenJumps(int[] A) {
- if(A == null || A.length == 0) return 0;
-
- TreeMap<Integer, Integer> map = new TreeMap<>();
-
- int n = A.length;
- int res = 1;
- boolean[][] dp = new boolean[n][2];
-
- dp[n-1][0] = true;
- dp[n-1][1] = true;
-
- map.put(A[n-1], n-1);
-
- for(int i = n - 2; i >= 0; i--) {
- Integer nextOddJumpNum = map.ceilingKey(A[i]);
- if(nextOddJumpNum != null) {
- dp[i][0] = dp[map.get(nextOddJumpNum)][1];
- }
- Integer nextEvenJumpNum = map.floorKey(A[i]);
- if(nextEvenJumpNum != null) {
- dp[i][1] = dp[map.get(nextEvenJumpNum)][0];
- }
- map.put(A[i], i);
- if(dp[i][0] == true)
- res++;
- }
-
-
-
- return res;
- }
- }
复制代码
|
|