Nhảy chẵn lẻ trong C ++

Giả sử chúng ta có một mảng A. Từ chỉ mục bắt đầu nào đó, chúng ta có thể thực hiện một loạt các bước nhảy. Các bước nhảy vị trí (1, 3, 5, ...) trong chuỗi được gọi là bước nhảy số lẻ và các bước nhảy vị trí (2, 4, 6, ...) trong chuỗi được gọi là bước nhảy số chẵn.

Bây giờ chúng ta có thể từ chỉ mục tôi chuyển tiếp sang chỉ mục j (với i

Trong các bước nhảy số lẻ, chúng ta có thể nhảy đến chỉ số j sao cho A [i] <=A [j] và A [j] là giá trị nhỏ nhất có thể. Khi có nhiều chỉ mục j như vậy, chúng ta chỉ có thể chuyển đến chỉ mục j nhỏ nhất.
Trong các bước nhảy số chẵn, chúng ta có thể nhảy đến chỉ số j sao cho A [i]> =A [j] và A [j] là giá trị lớn nhất có thể. Khi có nhiều chỉ mục j như vậy, chúng ta chỉ có thể chuyển đến chỉ mục j nhỏ nhất.
Có thể xảy ra trường hợp đối với một số chỉ mục i, không có bước nhảy hợp pháp nào.

Bây giờ, một chỉ mục bắt đầu được gọi là tốt khi, bắt đầu từ chỉ mục đó, chúng ta có thể đến cuối mảng bằng cách nhảy một số lần.

Chúng ta phải tìm số lượng chỉ mục khởi đầu tốt.

Vì vậy, nếu đầu vào giống như [10,13,12,14,15], thì đầu ra sẽ là 2, vì có hai chỉ số vị trí 3 và 4 từ nơi chúng ta có thể đạt được ở cuối.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

ret:=1
n:=kích thước của A
Xác định một mảng nextGreaterEqual có kích thước n điền vào giá trị này bằng -1
Xác định một mảng nextSmallerEqual có kích thước n điền vào giá trị này bằng -1
Xác định một bản đồ st
để khởi tạo i:=n - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
- if:=Cặp khóa-giá trị có giá trị không lớn hơn A [i]
- nextGreaterEqual [i]:=if (it) không phải là phần tử cuối cùng, thì giá trị của nó, nếu không thì -1
- nếu nó không bằng phần tử cuối cùng của st và phần tử đầu tiên của nó giống với A [i], thì -
  - (tăng nó lên 1)
- nextSmallerEqual [i]:=nếu (nó) không phải là phần tử đầu tiên, thì giá trị của phần tử trước đó, nếu không thì -1
- st [A [i]]:=i
Xác định một mảng 2D v có kích thước n x 2 và điền vào mảng này bằng false
v [n - 1, 0] =v [n - 1, 1] =true
để khởi tạo i:=n - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
- nếu nextGreaterEqual [i] không bằng -1, thì -
  - v [i, 1]:=v [nextGreaterEqual [i], 0]
- nếu nextSmallerEqual [i] không bằng -1, thì -
  - v [i, 0]:=v [nextSmallerEqual [i], 1]
- nếu v [i, 1] khác 0 thì -
  - (tăng ret lên 1)
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{10,13,12,14,15}

Nhảy chẵn lẻ trong C ++

Ví dụ

Đầu vào

Đầu ra