奇偶题库
奇偶跳
给定一个整数数组 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）出发，通过一定数量的跳跃到达数组末尾。
方案 动态规划与红黑树
思路: 采用逆向思维，从数组末尾出发，求能到达的下标总数即可。在逆向处理的过程中，我们只要找到之前遍历过的数组中，满足奇数跳跃或者偶数跳跃的最接近当前val的元素，就是这次跳跃到达的目标点。
-
状态定义:
-
odd[i]: 从索引 i 出发奇数次跳跃是否能到达数组末尾。只要这个位置能跳到终点，那么从别的位置跳到这个位置，一样也能抵达终点。
-
even[i]: 从索引 i 出发偶数次跳跃是否能到达数组末尾。只要这个位置能跳到终点，那么从别的位置跳到这个位置，一样也能抵达终点。
-
-
状态转移方程:从
i = N-2到i = 0的遍历过程中-
odd[i]=even[当前元素在红黑树中的后继节点的 value] -
even[i]=odd[当前元素在红黑树中的前去节点的 value]
-
-
初始化状态:
-
通过红黑树，逆序维护 nums 中的元素
-
odd[i]初始都为false，由于是逆序遍历，odd[len-1]初始为true -
even[i]初始都为false,由于是逆序遍历，even[len-1]初始为true
-
-
问题答案: 统计 odd 中为 true的元素个数即可
class Node {
data;
color = "red";
left = null;
right = null;
parent = null;
constructor(data) {
this.data = data;
}
}
class RedBlackTree {
root = null;
leftRotate(rotateNode) {
if (!rotateNode) {
console.log("请传入旋转节点");
return;
}
let rightNode = rotateNode.right;
rotateNode.right = rightNode.left;
if (rightNode.left) {
rightNode.left.parent = rotateNode;
}
rightNode.parent = rotateNode.parent;
if (!rotateNode.parent) {
this.root = rightNode;
} else if (rotateNode.data.key < rotateNode.parent.data.key) {
rotateNode.parent.left = rightNode;
} else {
rotateNode.parent.right = rightNode;
}
rightNode.left = rotateNode;
rotateNode.parent = rightNode;
}
rightRotate(rotateNode) {
if (!rotateNode) {
console.log("请传入旋转节点");
return;
}
let leftNode = rotateNode.left;
rotateNode.left = leftNode.right;
if (leftNode.right) {
leftNode.right.parent = rotateNode;
}
leftNode.parent = rotateNode.parent;
if (!rotateNode.parent) {
this.root = leftNode;
} else if (rotateNode.data.key < rotateNode.parent.data.key) {
rotateNode.parent.left = leftNode;
} else {
rotateNode.parent.right = leftNode;
}
leftNode.right = rotateNode;
rotateNode.parent = leftNode;
}
insert(data) {
let newNode = new Node(data);
if (!this.root) {
this.root = newNode;
this.root.color = "black";
return;
} else {
let currentNode = this.root;
while (currentNode) {
if (data.key < currentNode.data.key) {
if (!currentNode.left) {
newNode.parent = currentNode;
currentNode.left = newNode;
this.fixInsert(newNode);
break;
}
currentNode = currentNode.left;
} else if (data.key > currentNode.data.key) {
if (!currentNode.right) {
newNode.parent = currentNode;
currentNode.right = newNode;
this.fixInsert(newNode);
break;
}
currentNode = currentNode.right;
} else {
currentNode.data.value=data.value;
break;
}
}
}
}
fixInsert(node) {
let currentNode = node;
while (
currentNode &&
currentNode != this.root &&
currentNode.parent.color == "red"
) {
if (currentNode.parent.data.key < currentNode.parent.parent.data.key) {
let uncleNode = currentNode.parent.parent.right;
if (uncleNode && uncleNode.color == "red") {
currentNode.parent.color = "black";
uncleNode.color = "black";
currentNode.parent.parent.color = "red";
currentNode = currentNode.parent.parent;
} else {
if (currentNode.data.key > currentNode.parent.data.key) {
currentNode = currentNode.parent;
this.leftRotate(currentNode);
}
currentNode.parent.color = "black";
currentNode.parent.parent.color = "red";
this.rightRotate(currentNode.parent.parent);
}
} else {
let uncleNode = currentNode.parent.parent.left;
if (uncleNode && uncleNode.color == "red") {
currentNode.parent.color = "black";
uncleNode.color = "black";
currentNode.parent.parent.color = "red";
currentNode = currentNode.parent.parent;
} else {
if (currentNode.data.key < currentNode.parent.data.key) {
currentNode = currentNode.parent;
this.rightRotate(currentNode);
}
currentNode.parent.color = "black";
currentNode.parent.parent.color = "red";
this.leftRotate(currentNode.parent.parent);
}
}
}
this.root.color = "black";
}
find(key) {
let currentNode = this.root;
while (currentNode) {
if (key < currentNode.data.key) {
currentNode = currentNode.left;
} else if (key > currentNode.data.key) {
currentNode = currentNode.right;
} else {
return currentNode;
}
}
return null;
}
getPredecessor(key) {
let current=this.root;
while(current){
if(key>current.data.key){
if(current.right){
current=current.right;
}else{
return current;
}
}else{
if(current.left){
current=current.left;
}else{
let parent=current.parent;
let temp=current;
while(parent&&temp==parent.left){
temp=parent;
parent=parent.parent;
}
return parent;
}
}
}
return null
}
getSucceed(key) {
let current=this.root;
while(current){
if(key<current.data.key){
if(current.left){
current=current.left;
}else{
return current;
}
}else{
if(current.right){
current=current.right;
}else{
let parent=current.parent;
let temp=current;
while(parent&&temp==parent.right){
temp=parent;
parent=parent.parent;
}
return parent;
}
}
}
return null;
}
}
function oddEvenJumps(nums) {
let len=nums.length;
if(len<=1){
return len;
}
let odd=new Array(len).fill(false);
let even=new Array(len).fill(false);
odd[len-1]=true;
even[len-1]=true;
let rbTree=new RedBlackTree();
rbTree.insert({key:nums[len-1],value:len-1});
for(let i=len-2;i>=0;i--){
let node=rbTree.find(nums[i]);
if(node){
odd[i]=even[node.data.value];
even[i]=odd[node.data.value];
}else{
let lowerNode=rbTree.getPredecessor(nums[i]);
let hightNode=rbTree.getSucceed(nums[i]);
if(lowerNode){
even[i]=odd[lowerNode.data.value];
}
if(hightNode){
odd[i]=even[hightNode.data.value];
}
}
rbTree.insert({key:nums[i],value:i});
}
let result=0;
for(let item of odd){
if(item){
result++
}
}
return result;
};
性能分析:
- 时间复杂度：O(NlogN)，其中 N 是数组 A 的长度。
- 空间复杂度：O(N)。