2023-05-31：给定一个整数数组 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）

那么该索引就会被认为是好的起始索引。

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

输入：[2,3,1,1,4]。

输出：3。

答案2023-05-31：

大体步骤如下：

1.对于数组中的每个元素，使用有序表（treemap）分别找到奇数规则和偶数规则下的下一步位置。

2.奇数规则下要寻找第一个大于等于当前值的位置，而偶数规则下要寻找第一个小于等于当前值的位置。

3.使用动态规划方法，从后往前遍历数组，对于每个位置分别判断是否能够到达数组的末尾。

4.定义 dp[i][0] 表示当来到 i 位置，且在奇数规则下，最终能否到达数组末尾。同理，dp[i][1] 表示当来到 i 位置，且在偶数规则下，最终能否到达数组末尾。

5.对于每个位置 i，如果奇数规则下可以跳到下一个位置 odd[i]，则 dp[i][0] = dp[odd[i]][1]。同理，如果偶数规则下可以跳到下一个位置 even[i]，则 dp[i][1] = dp[even[i]][0]。

6.初始化 dp[n-1][0] 和 dp[n-1][1] 为 true，表示从数组末尾出发，无论是奇数规则还是偶数规则，都可以到达该位置。

7.遍历数组，对于每个位置 i，如果 dp[i][0] = true，则说明从该位置出发遵循奇数规则可以到达数组末尾，答案加 1。

8.返回答案。

时间复杂度：在该算法中，使用了一次 treemap 的查询操作和一次 treemap 的插入操作，这两种操作的时间复杂度均为 O(log n)，对于遍历整个数组以及动态规划的过程，其时间复杂度均为 O(n)，因此总的时间复杂度为 O(n log n)。

空间复杂度：算法中使用三个数组以及一个有序表。其中 odd 和 even 数组的长度为 n，dp 数组的大小为 n * 2，而有序表需要存储 n 个元素，因此算法的空间复杂度为 O(n)。

go语言完整代码如下：

package mainimport ("fmt""github.com/emirpasic/gods/maps/treemap")func oddEvenJumps(arr []int) int {n := len(arr)// 来到了i位置，如果要遵循奇数规则，应该去哪？odd[i]odd := make([]int, n)// 来到了i位置，如果要遵循偶数规则，应该去哪？even[i]even := make([]int, n)// 有序表，// key : 某个值// value : key这个值，出现的最左位置// >= key 且最小// <= key 且最大orderMap := treemap.NewWithIntComparator()for i := n - 1; i >= 0; i-- {// i位置，arr[i]，奇数规则，>= arr[i]且最小的！to, to2 := orderMap.Ceiling(arr[i])if to != nil {odd[i] = to2.(int)} else {odd[i] = -1}// i位置，arr[i]，偶数规则，<= arr[i]且最大的！to, to2 = orderMap.Floor(arr[i])if to != nil {even[i] = to2.(int)} else {even[i] = -1}orderMap.Put(arr[i], i)}// dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾？// dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾？dp := make([][]bool, n)for i := range dp {dp[i] = make([]bool, 2)}dp[n-1][0] = truedp[n-1][1] = trueans := 1for i := n - 2; i >= 0; i-- {// dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾// odd[i] -> 右走！ -1if odd[i] != -1 {dp[i][0] = dp[odd[i]][1]}// dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾if even[i] != -1 {dp[i][1] = dp[even[i]][0]}if dp[i][0] {ans++}}return ans}func main() {arr := []int{2, 3, 1, 1, 4}result := oddEvenJumps(arr)fmt.Println(result)}

rust语言完整代码如下：

use std::collections::BTreeMap;fn odd_even_jumps(arr: Vec) -> i32 {    let n = arr.len();    // 来到了i位置，如果要遵循奇数规则，应该去哪？odd[i]    let mut odd = vec![0; n];    // 来到了i位置，如果要遵循偶数规则，应该去哪？even[i]    let mut even = vec![0; n];    // 有序表，    // key : 某个值    // value : key这个值，出现的最左位置    // >= key 且最小    // <= key 且最大    let mut order_map = BTreeMap::new();    let mut i = n as i32 - 1;    while i >= 0 {        // i位置，arr[i]，奇数规则，>= arr[i]且最小的！        if let Some((&_to, &to2)) = order_map.range(arr[i as usize]..).next() {            odd[i as usize] = to2;        } else {            odd[i as usize] = -1;        }        // i位置，arr[i]，偶数规则，<= arr[i]且最大的！        if let Some((&_to, &to2)) = order_map.range(..=arr[i as usize]).rev().next() {            even[i as usize] = to2;        } else {            even[i as usize] = -1;        }        order_map.insert(arr[i as usize], i);        i -= 1;    }    // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾？    // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾？    let mut dp = vec![vec![false; 2]; n];    dp[n - 1][0] = true;    dp[n - 1][1] = true;    let mut ans = 1;    let mut i = n as i32 - 2;    while i >= 0 {        // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾        // odd[i] -> 右走！ -1        dp[i as usize][0] = odd[i as usize] != -1 && dp[odd[i as usize] as usize][1];        // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾        dp[i as usize][1] = even[i as usize] != -1 && dp[even[i as usize] as usize][0];        ans += if dp[i as usize][0] { 1 } else { 0 };        i -= 1;    }    ans}fn main() {    let arr = vec![2,3,1,1,4];    let result = odd_even_jumps(arr);    println!("{}", result);}

c++完整代码如下：

#include #include #include 

c语言完整代码如下：

#include #include #include struct BTreeNode {    int key;    int value;    struct BTreeNode* left;    struct BTreeNode* right;};struct BTreeMap {    struct BTreeNode* root;};struct BTreeNode* createNode(int key, int value) {    struct BTreeNode* node = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));    node->key = key;    node->value = value;    node->left = NULL;    node->right = NULL;    return node;}struct BTreeNode* insertNode(struct BTreeNode* node, int key, int value) {    if (node == NULL) {        return createNode(key, value);    }    if (key < node->key) {        node->left = insertNode(node->left, key, value);    }    else if (key > node->key) {        node->right = insertNode(node->right, key, value);    }    else {        node->value = value;    }    return node;}struct BTreeNode* findCeiling(struct BTreeNode* node, int target) {    if (node == NULL) {        return NULL;    }    if (node->key == target) {        return node;    }    if (node->key < target) {        return findCeiling(node->right, target);    }    struct BTreeNode* leftNode = findCeiling(node->left, target);    if (leftNode != NULL) {        return leftNode;    }    return node;}struct BTreeNode* findFloor(struct BTreeNode* node, int target) {    if (node == NULL) {        return NULL;    }    if (node->key == target) {        return node;    }    if (node->key > target) {        return findFloor(node->left, target);    }    struct BTreeNode* rightNode = findFloor(node->right, target);    if (rightNode != NULL) {        return rightNode;    }    return node;}struct BTreeMap* createMap() {    struct BTreeMap* map = (struct BTreeMap*)malloc(sizeof(struct BTreeMap));    map->root = NULL;    return map;}void insert(struct BTreeMap* map, int key, int value) {    map->root = insertNode(map->root, key, value);}int getCeiling(struct BTreeMap* map, int target) {    struct BTreeNode* ceilingNode = findCeiling(map->root, target);    if (ceilingNode == NULL) {        return -1;    }    return ceilingNode->value;}int getFloor(struct BTreeMap* map, int target) {    struct BTreeNode* floorNode = findFloor(map->root, target);    if (floorNode == NULL) {        return -1;    }    return floorNode->value;}void destroyNode(struct BTreeNode* node) {    if (node == NULL) {        return;    }    destroyNode(node->left);    destroyNode(node->right);    free(node);}void destroyMap(struct BTreeMap* map) {    destroyNode(map->root);    free(map);}int oddEvenJumps(int* arr, int arrSize) {    int n = arrSize;    // 来到了i位置，如果要遵循奇数规则，应该去哪？odd[i]    int* odd = (int*)malloc(n * sizeof(int));    // 来到了i位置，如果要遵循偶数规则，应该去哪？even[i]    int* even = (int*)malloc(n * sizeof(int));    // 有序表，    // key : 某个值    // value : key这个值，出现的最左位置    // >= key 且最小    // <= key 且最大    struct BTreeMap* orderMap = createMap();    for (int i = n - 1; i >= 0; --i) {        // i位置，arr[i]，奇数规则，>= arr[i]且最小的！        int to2 = getCeiling(orderMap, arr[i]);        if (to2 == -1) {            odd[i] = -1;        }        else {            odd[i] = to2;        }        // i位置，arr[i]，偶数规则，<= arr[i]且最大的！        to2 = getFloor(orderMap, arr[i]);        if (to2 == -1) {            even[i] = -1;        }        else {            even[i] = to2;        }        insert(orderMap, arr[i], i);    }    destroyMap(orderMap);    // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾？    // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾？    bool** dp = (bool**)malloc(n * sizeof(bool*));    for (int i = 0; i < n; ++i) {        dp[i] = (bool*)malloc(2 * sizeof(bool));        dp[i][0] = false;        dp[i][1] = false;    }    dp[n - 1][0] = true;    dp[n - 1][1] = true;    int ans = 1;    for (int i = n - 2; i >= 0; --i) {        // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾        // odd[i] -> 右走！ -1        if (odd[i] != -1) {            dp[i][0] = dp[odd[i]][1];        }        // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾        if (even[i] != -1) {            dp[i][1] = dp[even[i]][0];        }        if (dp[i][0]) {            ++ans;        }    }    // 释放内存    for (int i = 0; i < n; ++i) {        free(dp[i]);    }    free(dp);    free(odd);    free(even);    return ans;}int main() {    int arr[] = { 2,3,1,1,4 };    int arrSize = sizeof(arr) / sizeof(int);    int result = oddEvenJumps(arr, arrSize);    printf("%d\n", result);     return 0;}

标签：