สมมติว่าเรามีอาร์เรย์ 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