資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
