คี่คู่กระโดดใน C++

สมมติว่าเรามีอาร์เรย์ A จากดัชนีเริ่มต้น เราสร้างชุดของการข้ามได้ ตำแหน่ง (1, 3, 5, ...) การกระโดดในชุดเรียกว่าการกระโดดเลขคี่ และตำแหน่ง (2, 4, 6, ...) การกระโดดในชุดจะเรียกว่าการกระโดดเลขคู่

ตอนนี้เราอาจจากดัชนี i กระโดดไปข้างหน้าไปยังดัชนี j (ด้วย i

• ในระหว่างการกระโดดด้วยเลขคี่ เราสามารถข้ามไปที่ดัชนี 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 เนื่องจากมีดัชนีตำแหน่ง 2 ตำแหน่ง 3 และ 4 จากตำแหน่งที่เราสามารถเข้าถึงได้ในตอนท้าย

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยกเลิก :=1

• n :=ขนาดของ A

• กำหนดอาร์เรย์ nextGreaterEqual ของขนาด n เติมด้วย -1

• กำหนดอาร์เรย์ nextSmallerEqual ของขนาด n เติมด้วย -1

• กำหนดหนึ่งแผนที่ st

• สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • ถ้า :=คู่คีย์-ค่าที่มีค่าไม่เกิน A[i]

  • nextGreaterEqual[i] :=ถ้า (it) ไม่ใช่องค์ประกอบสุดท้าย ก็ให้ค่าของมัน มิฉะนั้น -1

  • ถ้ามันไม่เท่ากับองค์ประกอบสุดท้ายของ st และองค์ประกอบแรกเหมือนกับ A[i] ดังนั้น −

    • (เพิ่มขึ้นอีก 1)

  • nextSmallerEqual[i] :=if (it) ไม่ใช่องค์ประกอบแรก ดังนั้นค่าของค่าก่อนหน้าของมัน มิฉะนั้น -1

  • st[A[i]] :=ฉัน

• กำหนดอาร์เรย์ 2 มิติ v ขนาด n x 2 หนึ่งรายการ และเติมค่านี้ด้วยค่าเท็จ

• v[n - 1, 0] =v[n - 1, 1] =จริง

• สำหรับการเริ่มต้น 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] ไม่ใช่ศูนย์ ดังนั้น −

    • (เพิ่มการถอยกลับโดย 1)

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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