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 main
import ( "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] = true dp[n-1][1] = true ans := 1 for 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++ } } 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>) -> 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 <iostream>#include <vector>#include <map>using namespace std;
int oddEvenJumps(vector<int>& arr) { int n = arr.size(); // 来到了i位置，如果要遵循奇数规则，应该去哪？odd[i] vector<int> odd(n); // 来到了i位置，如果要遵循偶数规则，应该去哪？even[i] vector<int> even(n); // 有序表， // key : 某个值 // value : key这个值，出现的最左位置 // >= key 且最小 // <= key 且最大 map<int, int> orderMap; for (int i = n - 1; i >= 0; --i) { // i位置，arr[i]，奇数规则，>= arr[i]且最小的！ auto it = orderMap.lower_bound(arr[i]); if (it != orderMap.end()) { odd[i] = it->second; } else { odd[i] = -1; } // i位置，arr[i]，偶数规则，<= arr[i]且最大的！ it = orderMap.upper_bound(arr[i]); if (it != orderMap.begin()) { even[i] = (--it)->second; } else { even[i] = -1; } orderMap[arr[i]] = i; } // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾？ // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾？ vector<vector<bool>> dp(n, vector<bool>(2)); 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; } } return ans;}
int main() { vector<int> arr = { 2,3,1,1,4 }; int result = oddEvenJumps(arr); cout << result << endl; return 0;}
复制代码
c 语言完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>
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;}
复制代码
评论