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語言完整代碼如下：
```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語言完整代碼如下：
```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++完整代碼如下：
```cpp
#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語言完整代碼如下：
```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;
}
```
