数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的奇偶跳跃
假设我们有一个数组 A。从某个起始索引开始，我们可以进行一系列跳跃。序列中的位置 (1, 3, 5, ...) 被称为奇数跳跃，序列中的位置 (2, 4, 6, ...) 被称为偶数跳跃。
现在，我们可以从索引 i 跳到索引 j（其中 i < j）的方式如下：
在奇数跳跃中，我们可以跳到索引 j，使得 A[i] <= A[j] 且 A[j] 是尽可能小的值。当有多个这样的索引 j 时，我们只能跳到最小的索引 j。
在偶数跳跃中，我们可以跳到索引 j，使得 A[i] >= A[j] 且 A[j] 是尽可能大的值。当有多个这样的索引 j 时，我们只能跳到最小的索引 j。
对于某些索引 i，可能不存在合法的跳跃。
现在，当从某个起始索引开始，我们可以通过跳跃若干次到达数组的末尾时，该起始索引被称为良好的。
我们需要找到良好的起始索引的数量。
因此，如果输入类似于 [10,13,12,14,15]，则输出将为 2，因为有两个位置索引 3 和 4，我们可以从它们到达末尾。
为了解决这个问题，我们将遵循以下步骤：
ret := 1
n := A 的大小
定义一个大小为 n 的数组 nextGreaterEqual，并将其填充为 -1
定义一个大小为 n 的数组 nextSmallerEqual，并将其填充为 -1
定义一个 map st
对于初始化 i := n - 1，当 i >= 0 时，更新（将 i 减 1），执行：
if := 值不大于 A[i] 的键值对
nextGreaterEqual[i] := 如果 (it) 不是最后一个元素，则为 it 的值，否则为 -1
如果它不等于 st 的最后一个元素，并且 it 的第一个元素与 A[i] 相同，则：
(将 it 增加 1)
nextSmallerEqual[i] := 如果 (it) 不是第一个元素，则为 it 的前一个元素的值，否则为 -1
st[A[i]] := i
定义一个大小为 n x 2 的二维数组 v，并将其填充为 false
v[n - 1, 0] = v[n - 1, 1] = true
对于初始化 i := n - 2，当 i >= 0 时，更新（将 i 减 1），执行：
如果 nextGreaterEqual[i] 不等于 -1，则：
v[i, 1] := v[nextGreaterEqual[i], 0]
如果 nextSmallerEqual[i] 不等于 -1，则：
v[i, 0] := v[nextSmallerEqual[i], 1]
如果 v[i, 1] 不为零，则：
(将 ret 增加 1)
返回 ret
让我们看看以下实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int oddEvenJumps(vector<int>& A){
int ret = 1;
int n = A.size();
vector<int> nextGreaterEqual(n, -1);
vector<int> nextSmallerEqual(n, -1);
map<int, int> st;
for (int i = n - 1; i >= 0; i--) {
map<int, int>::iterator it = st.lower_bound(A[i]);
nextGreaterEqual[i] = (it != st.end()) ? it->second : -1;
if (it != st.end() && it->first == A[i])
it++;
nextSmallerEqual[i] = it != st.begin() ? prev(it)->second
: -1;
st[A[i]] = i;
}
vector<vector<bool> > v(n, vector<bool>(2, false));
v[n - 1][0] = v[n - 1][1] = true;
for (int i = n - 2; i >= 0; i--) {
if (nextGreaterEqual[i] != -1) {
v[i][1] = v[nextGreaterEqual[i]][0];
}
if (nextSmallerEqual[i] != -1) {
v[i][0] = v[nextSmallerEqual[i]][1];
}
if (v[i][1])
ret++;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {10,13,12,14,15};
cout << (ob.oddEvenJumps(v));
}输入
{10,13,12,14,15}输出
2
511 次浏览
