2023-05-31：給定一個整數(shù)數(shù)組 A，你可以從某一起始索引出發(fā)，跳躍一定次數(shù) 在你跳躍
2023-05-31：給定一個整數(shù)數(shù)組 A，你可以從某一起始索引出發(fā)，跳躍一定次數(shù)
在你跳躍的過程中，第 1、3、5... 次跳躍稱為奇數(shù)跳躍
而第 2、4、6... 次跳躍稱為偶數(shù)跳躍
你可以按以下方式從索引 i 向后跳轉(zhuǎn)到索引 j（其中 i < j）：
在進行奇數(shù)跳躍時（如，第 1，3，5... 次跳躍），你將會跳到索引 j
使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多個這樣的索引 j
你只能跳到滿足要求的最小索引 j 上。
在進行偶數(shù)跳躍時（如，第 2，4，6... 次跳躍）
你將會跳到索引 j，使得 A[i] >= A[j]，A[j] 是可能的最大值
如果存在多個這樣的索引 j，你只能跳到滿足要求的最小索引 j 上。
（對于某些索引 i，可能無法進行合乎要求的跳躍。）
如果從某一索引開始跳躍一定次數(shù)（可能是 0 次或多次）
就可以到達數(shù)組的末尾（索引 A.length - 1）
那么該索引就會被認為是好的起始索引。
返回好的起始索引的數(shù)量。
輸入：[2,3,1,1,4]。
輸出：3。
答案2023-05-31：
大體步驟如下：
1.對于數(shù)組中的每個元素，使用有序表（treemap）分別找到奇數(shù)規(guī)則和偶數(shù)規(guī)則下的下一步位置。
2.奇數(shù)規(guī)則下要尋找第一個大于等于當前值的位置，而偶數(shù)規(guī)則下要尋找第一個小于等于當前值的位置。
3.使用動態(tài)規(guī)劃方法，從后往前遍歷數(shù)組，對于每個位置分別判斷是否能夠到達數(shù)組的末尾。
4.定義 dp[i][0] 表示當來到 i 位置，且在奇數(shù)規(guī)則下，最終能否到達數(shù)組末尾。同理，dp[i][1] 表示當來到 i 位置，且在偶數(shù)規(guī)則下，最終能否到達數(shù)組末尾。
5.對于每個位置 i，如果奇數(shù)規(guī)則下可以跳到下一個位置 odd[i]，則 dp[i][0] = dp[odd[i]][1]。同理，如果偶數(shù)規(guī)則下可以跳到下一個位置 even[i]，則 dp[i][1] = dp[even[i]][0]。
6.初始化 dp[n-1][0] 和 dp[n-1][1] 為 true，表示從數(shù)組末尾出發(fā)，無論是奇數(shù)規(guī)則還是偶數(shù)規(guī)則，都可以到達該位置。
7.遍歷數(shù)組，對于每個位置 i，如果 dp[i][0] = true，則說明從該位置出發(fā)遵循奇數(shù)規(guī)則可以到達數(shù)組末尾，答案加 1。
8.返回答案。
時間復雜度：在該算法中，使用了一次 treemap 的查詢操作和一次 treemap 的插入操作，這兩種操作的時間復雜度均為 O(log n)，對于遍歷整個數(shù)組以及動態(tài)規(guī)劃的過程，其時間復雜度均為 O(n)，因此總的時間復雜度為 O(n log n)。
空間復雜度：算法中使用三個數(shù)組以及一個有序表。其中 odd 和 even 數(shù)組的長度為 n，dp 數(shù)組的大小為 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位置，如果要遵循奇數(shù)規(guī)則，應(yīng)該去哪？odd[i]
????odd?:=?make([]int,?n)
????//?來到了i位置，如果要遵循偶數(shù)規(guī)則，應(yīng)該去哪？even[i]
????even?:=?make([]int,?n)
????//?有序表，
????//?key?:?某個值
????//?value?:?key這個值，出現(xiàn)的最左位置
????//?>=?key?且最小
????//?<=?key?且最大
????orderMap?:=?treemap.NewWithIntComparator()
????for?i?:=?n?-?1;?i?>=?0;?i--?{
????????//?i位置，arr[i]，奇數(shù)規(guī)則，>=?arr[i]且最小的！
????????to,?to2?:=?orderMap.Ceiling(arr[i])
????????if?to?!=?nil?{
????????????odd[i]?=?to2.(int)
????????}?else?{
????????????odd[i]?=?-1
????????}
????????//?i位置，arr[i]，偶數(shù)規(guī)則，<=?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位置，且在奇數(shù)規(guī)則下，最終能不能到結(jié)尾？
????//?dp[i][1]?:?當來到i位置，且在偶數(shù)規(guī)則下，最終能不能到結(jié)尾？
????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位置，且在奇數(shù)規(guī)則下，最終能不能到結(jié)尾
????????//?odd[i]?->?右走！?-1
????????if?odd[i]?!=?-1?{
????????????dp[i][0]?=?dp[odd[i]][1]
????????}
????????//?dp[i][1]?:?當來到i位置，且在偶數(shù)規(guī)則下，最終能不能到結(jié)尾
????????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位置，如果要遵循奇數(shù)規(guī)則，應(yīng)該去哪？odd[i]
????let?mut?odd?=?vec![0;?n];
????//?來到了i位置，如果要遵循偶數(shù)規(guī)則，應(yīng)該去哪？even[i]
????let?mut?even?=?vec![0;?n];
????//?有序表，
????//?key?:?某個值
????//?value?:?key這個值，出現(xiàn)的最左位置
????//?>=?key?且最小
????//?<=?key?且最大
????let?mut?order_map?=?BTreeMap::new();
????let?mut?i?=?n?as?i32?-?1;
????while?i?>=?0?{
????????//?i位置，arr[i]，奇數(shù)規(guī)則，>=?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]，偶數(shù)規(guī)則，<=?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位置，且在奇數(shù)規(guī)則下，最終能不能到結(jié)尾？
????//?dp[i][1]?:?當來到i位置，且在偶數(shù)規(guī)則下，最終能不能到結(jié)尾？
????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位置，且在奇數(shù)規(guī)則下，最終能不能到結(jié)尾
????????//?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位置，且在偶數(shù)規(guī)則下，最終能不能到結(jié)尾
????????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++完整代碼如下：
using?namespace?std;
int?oddEvenJumps(vector<int>&?arr)?{
????int?n?=?arr.size();
????//?來到了i位置，如果要遵循奇數(shù)規(guī)則，應(yīng)該去哪？odd[i]
????vector<int>?odd(n);
????//?來到了i位置，如果要遵循偶數(shù)規(guī)則，應(yīng)該去哪？even[i]
????vector<int>?even(n);
????//?有序表，
????//?key?:?某個值
????//?value?:?key這個值，出現(xiàn)的最左位置
????//?>=?key?且最小
????//?<=?key?且最大
????map<int,?int>?orderMap;
????for?(int?i?=?n?-?1;?i?>=?0;?--i)?{
????????//?i位置，arr[i]，奇數(shù)規(guī)則，>=?arr[i]且最小的！
????????auto?it?=?orderMap.lower_bound(arr[i]);
????????if?(it?!=?orderMap.end())?{
????????????odd[i]?=?it->second;
????????}
????????else?{
????????????odd[i]?=?-1;
????????}
????????//?i位置，arr[i]，偶數(shù)規(guī)則，<=?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位置，且在奇數(shù)規(guī)則下，最終能不能到結(jié)尾？
????//?dp[i][1]?:?當來到i位置，且在偶數(shù)規(guī)則下，最終能不能到結(jié)尾？
????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位置，且在奇數(shù)規(guī)則下，最終能不能到結(jié)尾
????????//?odd[i]?->?右走！?-1
????????if?(odd[i]?!=?-1)?{
????????????dp[i][0]?=?dp[odd[i]][1];
????????}
????????//?dp[i][1]?:?當來到i位置，且在偶數(shù)規(guī)則下，最終能不能到結(jié)尾
????????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語言完整代碼如下：
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位置，如果要遵循奇數(shù)規(guī)則，應(yīng)該去哪？odd[i]
????int*?odd?=?(int*)malloc(n?*?sizeof(int));
????//?來到了i位置，如果要遵循偶數(shù)規(guī)則，應(yīng)該去哪？even[i]
????int*?even?=?(int*)malloc(n?*?sizeof(int));
????//?有序表，
????//?key?:?某個值
????//?value?:?key這個值，出現(xiàn)的最左位置
????//?>=?key?且最小
????//?<=?key?且最大
????struct?BTreeMap*?orderMap?=?createMap();
????for?(int?i?=?n?-?1;?i?>=?0;?--i)?{
????????//?i位置，arr[i]，奇數(shù)規(guī)則，>=?arr[i]且最小的！
????????int?to2?=?getCeiling(orderMap,?arr[i]);
????????if?(to2?==?-1)?{
????????????odd[i]?=?-1;
????????}
????????else?{
????????????odd[i]?=?to2;
????????}
????????//?i位置，arr[i]，偶數(shù)規(guī)則，<=?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位置，且在奇數(shù)規(guī)則下，最終能不能到結(jié)尾？
????//?dp[i][1]?:?當來到i位置，且在偶數(shù)規(guī)則下，最終能不能到結(jié)尾？
????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位置，且在奇數(shù)規(guī)則下，最終能不能到結(jié)尾
????????//?odd[i]?->?右走！?-1
????????if?(odd[i]?!=?-1)?{
????????????dp[i][0]?=?dp[odd[i]][1];
????????}
????????//?dp[i][1]?:?當來到i位置，且在偶數(shù)規(guī)則下，最終能不能到結(jié)尾
????????if?(even[i]?!=?-1)?{
????????????dp[i][1]?=?dp[even[i]][0];
????????}
????????if?(dp[i][0])?{
????????????++ans;
????????}
????}
????//?釋放內(nèi)存
????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;
}
