'lintcode 奇偶跳'

Posted on | In

描述

给定一个整数数组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），那么这是一个有效的起始索引。

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

样例

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) 我们可以跳跃至末尾

思路

建立一个数组res来存放可以跳跃到末尾的编号，遍历每一个数，如果这个数不在res数组中就开始跳跃，跳跃过程中所有奇数跳的编号都要记录下来，如果能跳跃到末尾的话，奇数跳的编号都存在res当中，最后返回res数组的长度即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    /**
     * @param A: An integer array A
     * @return: Return the number of good starting indexes
     */
    int jump(vector<int> &A, int start, int times) {
        if (start == A.size() - 1)
            return start;
        int res = -1;
        if (times % 2 == 0) {
            int max = INT_MIN;
            for (int i = start+1; i < A.size(); i++) {
                if (A[i] <= A[start] && A[i] > max) {
                    res = i;
                    max = A[i];
                }
            }
        }
        else {
            int min = INT_MAX;
            for (int i = start+1; i < A.size(); i++) {
                if (A[i] >= A[start] && A[i] < min){
                    min = A[i];
                    res = i;
                }
            }
        }
        return res;
    }

    bool isFind(vector<int>& A, int tar){
        for (int i = 0; i < A.size(); i++ )
            if (A[i] == tar)
                return true;

        return false;
    }

    int oddEvenJumps(vector<int> &A) {
        // Write your code here

        //奇数跳： 大于等于A[i]的最小A[j]
        //偶数跳： 小于等于A[i]的最大A[j]


        vector<int> res;
        for (int i = 0; i < A.size(); i++) {
            vector<int> temp;
            if (isFind(res, i))
                continue;
            temp.push_back(i);
            int times = 1;
            int start = i;
            while (jump(A, start, times) != -1 && start != A.size() - 1){
                start = jump(A, start, times);
                times++;
                if (times % 2 == 1 && !isFind(res, start))
                    temp.push_back(start);
            }
            if (start == A.size() - 1) {
                for (int j = 0; j < temp.size(); j++)
                    res.push_back(temp[j]);
            }
        }

        return res.size();
    }
};
-------------end of filethanks for reading-------------