Computer >> Máy Tính >  >> Lập trình >> C ++

Arithmetic Slices II - Chuỗi con trong C ++

Giả sử chúng ta có một mảng A, trong đó N số có mặt. Một lát con của mảng đó là bất kỳ chuỗi số nguyên nào như (K0, K1, K2,… Kn) sao cho 0 <=K0 =2. Vì vậy ta phải trả về số lát cắt cấp số cộng.

Vì vậy, nếu đầu vào là [2,4,6,8,10], thì câu trả lời sẽ là 7, vì có 7 lát số học. [2,4,6], [2,4,10], [4,6,8], [6,8,10], [2,4,6,8], [4,6,8,10 ], [2,4,6,8,10],

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

  • ret:=0
  • Xác định một bản đồ dp một bản đồ khác cnt
  • Xác định một tập hợp s bằng cách lấy các phần tử từ A
  • n:=kích thước của A
  • để khởi tạo i:=1, khi i
  • để khởi tạo j:=i - 1, khi j> =0, cập nhật (giảm j đi 1), thực hiện -
    • diff:=A [i] - A [j]
    • nếu diff <=-inf hoặc diff> inf, thì -
      • Bỏ qua phần sau, chuyển sang phần lặp tiếp theo
    • temp:=dp [j, diff] khi khác biệt nằm trong bản đồ dp [j], nếu không thì 0
    • ret:=ret + temp
    • nếu (A [i] + diff) có trong s, thì -
      • dp [i, diff]:=dp [i, diff] + temp + 1
  • trả lời lại
  • 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;
    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));
    }

    Đầu vào

    {2,4,6,8,10}

    Đầu ra

    7