home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Odd Even Jump ใน C++

คำอธิบายโจทย์

อาร์เรย์ A กระโดดจาก i ไป j (i

ตัวอย่าง

A = [10,13,12,14,15] → Output: 2 (index 3 และ 4)

วิธีแก้ปัญหา

Monotonic Map + DP:

  1. คำนวณ nextGreaterEqual[i] และ nextSmallerEqual[i] ด้วย map (BST) วนจากขวาไปซ้าย
  2. DP: v[i][1] = สามารถถึงปลายจาก i ด้วย odd jump, v[i][0] = even jump
  3. v[n-1][0]=v[n-1][1]=true
  4. v[i][1] = v[nextGreaterEqual[i]][0], v[i][0] = v[nextSmallerEqual[i]][1]
  5. นับ v[i][1] ที่เป็น true

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int oddEvenJumps(vector<int>& A) {
        int ret = 1, n = A.size();
        vector<int> nextGE(n, -1), nextSE(n, -1);
        map<int, int> st; // value -> index
        
        for(int i=n-1; i>=0; i--) {
            auto it = st.lower_bound(A[i]);
            nextGE[i] = (it != st.end()) ? it->second : -1;
            if(it != st.end() && it->first == A[i]) it++;
            nextSE[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(nextGE[i] != -1) v[i][1] = v[nextGE[i]][0];
            if(nextSE[i] != -1) v[i][0] = v[nextSE[i]][1];
            if(v[i][1]) ret++;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {10,13,12,14,15};
    cout << ob.oddEvenJumps(v);
    return 0;
}

อินพุต

{10,13,12,14,15}

เอาต์พุต

2