Leetcode 975 Odd Even Jump

发表于 |

给定一个整数数组 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 上。
（对于某些索引 i，可能无法进行合乎要求的跳跃。）
如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 A.length - 1），那么该索引就会被认为是好的起始索引。

返回好的起始索引的数量。

示例 1：
输入：[10,13,12,14,15]
输出：2
解释：
从起始索引 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 不是好的起始索引。
类似地，我们可以推断：
从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

示例 3：
输入：[5,1,3,4,2]
输出：3
解释：
我们可以从起始索引 1，2，4 出发到达数组末尾。

提示：

  1. 1 <= A.length <= 20000
  2. 0 <= A[i] < 100000

题意分析：
现在给定一个数组，让你从某个数开始向右移动，当前位置为i，移动规则如下：

  1. 第1,3,5,7…，次移动时，移动到所有不小于A[i]的数中的最小的数的位置
  2. 第2,4,6,8…，次移动时，移动到所有不大于A[i]的数中的最大的数的位置
  3. 若有多个位置满足，移动到最小index处。

思路分析：
对于任意一个位置i，这里使用odd[i]表示奇数次跳跃时下一个可以跳跃的位置，even[i]表示偶数次跳跃时下一个可以跳跃的位置。若无法跳跃，则值默认为-1。

可以保证，odd[i]和even[i]都是可以计算出来的某个确定的值，不存在能同时跳两个位置。我们先思考这样一个问题，假设我们已经把odd数组和even数组计算出来了，如何去找最后的结果呢？我们直接使用dfs去找，如果当前值为-1（代表已经无法跳跃），那么我们判断当前的index是否为终点。如果dfs返回true，则说明该位置是一个good starting index。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = len(A)
def dfs(u, flag):
    # flag = 1表示现在是奇数次跳跃
    if flag == 1:
        if odd[u] == -1:
            return u == n-1
        v = dfs(odd[u], 0)
    elif flag == 0:
        if even[u] == -1:
            return u == n-1
        v = dfs(even[u], 1)
    return v

res = 0
for i in range(n-1, -1, -1):
    if dfs(i, 1):
        res += 1
print(res)

但我们又注意到，如果这样计算dfs的时候会有大量重复计算，因为可能某个状态(u, flag)在之前的dfs中已经判断出来是否能到达终点，应该使用记忆化的思想去直接返回已经计算的结果。
所以上面的代码改成

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
n = len(A)
ok = set()
notok = set()
def dfs(u, flag):
    if (u, flag) in ok: return True
    if (u, flag) in notok: return False
    if flag == 1:
        if odd[u] == -1:
            return u == n-1
        v = dfs(odd[u], 0)
    elif flag == 0:
        if even[u] == -1:
            return u == n-1
        v = dfs(even[u], 1)
    if v:
        ok.add((u, flag))
    else:
        notok.add((u, flag))
    return v

res = 0
for i in range(n-1, -1, -1):
    if dfs(i, 1):
        res += 1
print(res)

那么我们现在只要将odd和even计算出来即可，这里采用bisect方法去找结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = len(A)
stack = [A[n-1]]
index = {A[n-1]: n-1} # 用来记录已经出现的值的最小index
odd = [-1] * n
even = [-1] * n
for i in range(n-2, -1, -1):
    if A[i] not in index:
        index[A[i]] = i
        idx = bisect.bisect(stack, A[i])
        if idx < len(stack):
            odd[i] = index[stack[idx]]
        if idx > 0:
            even[i] = index[stack[idx-1]]
        bisect.insort(stack, A[i])
    else:
        odd[i] = index[A[i]]
        even[i] = index[A[i]]
        index[A[i]] = i

你可能会好奇，bisect.insort()方法应该是O(n)复杂度，这样下来整个循环就是O(n^2)复杂度，为什么不会超时呢？你可以阅读一下这位大神的解释，并且希望你能把这个当成结论来用，explanation

最后完整代码如下：

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
class Solution(object):
    def oddEvenJumps(self, A):
        n = len(A)
        stack = [A[n-1]]
        index = {A[n-1]: n-1}
        odd = [-1] * n
        even = [-1] * n
        for i in range(n-2, -1, -1):
            if A[i] not in index:
                index[A[i]] = i
                idx = bisect.bisect(stack, A[i])
                if idx < len(stack):
                    odd[i] = index[stack[idx]]
                if idx > 0:
                    even[i] = index[stack[idx-1]]
                bisect.insort(stack, A[i])
            else:
                odd[i] = index[A[i]]
                even[i] = index[A[i]]
                index[A[i]] = i

        ok = set()
        notok = set()
        def dfs(u, flag):
            if (u, flag) in ok: return True
            if (u, flag) in notok: return False
            if flag == 1:
                if odd[u] == -1:
                    return u == n-1
                v = dfs(odd[u], 0)
            elif flag == 0:
                if even[u] == -1:
                    return u == n-1
                v = dfs(even[u], 1)
            if v:
                ok.add((u, flag))
            else:
                notok.add((u, flag))
            return v

        res = 0
        for i in range(n-1, -1, -1):
            if dfs(i, 1):
                res += 1
        return res
# 64 / 64 test cases passed.
# difficulty: hard
# Runtime: 692 ms