পাটিগণিতের স্লাইস II - C++ এর পরবর্তী অংশ

ধরুন আমাদের একটি অ্যারে আছে, যেখানে N সংখ্যা রয়েছে। সেই অ্যারের একটি পরবর্তী স্লাইস হল (K0, K1, K2, … Kn) এর মতো পূর্ণসংখ্যার যেকোন ক্রম যাতে 0 <=K0 =2। তাই আমাদের পাটিগণিত স্লাইসের সংখ্যা ফেরত দিতে হবে।

সুতরাং যদি ইনপুটটি [2,4,6,8,10] এর মত হয়, তাহলে উত্তর হবে 7, যেহেতু 7টি গাণিতিক স্লাইস রয়েছে। [2,4,6], [2,4,10], [4,6,8], [6,8,10], [2,4,6,8], [4,6,8,10 ], [২,৪,৬,৮,১০],

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ret :=0
• এক মানচিত্র dp অন্য মানচিত্র cnt সংজ্ঞায়িত করুন
• A থেকে উপাদান নিয়ে একটি সেট s সংজ্ঞায়িত করুন
• n :=A এর আকার
• আরম্ভ করার জন্য i :=1, যখন i করুন
• j শুরু করার জন্য :=i - 1, যখন j>=0, আপডেট করুন (j 1 দ্বারা কম করুন), −
  করুন
  • diff :=A[i] - A[j]
  • যদি diff <=-inf বা diff> inf, তারপর −
    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
  • temp :=dp[j, diff] যখন diff মানচিত্রে থাকে dp[j], অন্যথায় 0
  • ret :=ret + temp
  • যদি (A[i] + diff) s থাকে, তাহলে −
    • dp[i, diff] :=dp[i, diff] + temp + 1

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int numberOfArithmeticSlices(vector<int>& A) {
      int ret = 0;
      unordered_map <lli, unordered_map <lli, lli> > dp, cnt;
      unordered_set <int> s (A.begin(), A.end());
      int n = A.size();
      for(int i = 1; i < n; i++){
         for(int j = i - 1; j >= 0; j--){
            lli diff = (lli)A[i] - (lli)A[j];
            if(diff <= INT_MIN || diff > INT_MAX) continue;
            int temp = dp[j].count(diff) ? dp[j][diff] : 0;
            ret += temp;
            if(s.count(A[i] + diff))dp[i][diff] += temp + 1;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,4,6,8,10};
   cout << (ob.numberOfArithmeticSlices(v));
}

ইনপুট

{2,4,6,8,10}

আউটপুট

7