Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

산술 조각 II - C++의 하위 시퀀스

<시간/>

N개의 숫자가 있는 배열 A가 있다고 가정합니다. 해당 배열의 하위 시퀀스 슬라이스는 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] ], [2,4,6,8,10],

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • ret :=0
  • 한 지도 dp 다른 지도 cnt 정의
  • A에서 요소를 가져와서 하나의 세트 정의
  • n :=A의 크기
  • 초기화 i :=1의 경우, i
  • j 초기화의 경우 :=i - 1, j>=0일 때 업데이트(j를 1만큼 감소), −
    • 차이 :=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] + 온도 + 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