C++에서 연속적으로 같은 차이가 있는 숫자

모든 연속 숫자 사이의 절대 차이가 K가 되도록 길이가 N인 모든 음이 아닌 정수를 찾아야 한다고 가정합니다. 답의 모든 숫자는 숫자 0 자체를 제외하고 선행 0이 없어야 함을 명심해야 합니다. 어떤 순서로든 답변을 반환할 수 있습니다. 따라서 N =3이고 K =7이면 출력은 [181,292,707,818,929]가 됩니다. 여기서 070은 선행 0이 하나 있기 때문에 유효한 숫자가 아님을 알 수 있습니다.

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

• dp라는 행렬 하나를 만들고 크기는 n + 1이 되고 1에서 9까지를 dp[1]

  에 채웁니다.

• 1 ~ N – 1 범위의 i에 대해

  • 방문 세트 정의

  • 범위 0에서 dp[i]

    까지의 j에 대해

    • x :=dp[i,j]

    • lastNum :=x의 마지막 숫자

    • 숫자 :=lastNum + k

    • 숫자가 0에서 9 사이이고 (x*10 + 숫자)를 방문하지 않으면

      • dp[i + 1]

        에 (10*x + 숫자)를 삽입합니다.

      • 방문 배열에 10*x + 숫자 삽입

    • 숫자 :=lastNum – K

    • 숫자가 0에서 9 사이이고 (x*10 + 숫자)를 방문하지 않으면

      • dp[i + 1]

        에 (10*x + 숫자)를 삽입합니다.

      • 방문 배열에 10*x + 숫자 삽입

• N이 1이면 dp[N]

  에 0을 삽입합니다.

• 반환 dp[N]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> numsSameConsecDiff(int N, int K) {
      vector <int> dp[N + 1];
      for(int i = 1; i <= 9; i++){
         dp[1].push_back(i);
      }
      for(int i = 1; i < N; i++){
         set <int> visited;
         for(int j = 0; j < dp[i].size(); j++){
            int x = dp[i][j];
            int lastNum = x % 10;
            int digit = lastNum + K;
            if(digit >= 0 && digit <= 9 && !visited.count(x * 10 + digit)){
               dp[i + 1].push_back(x * 10 + digit);
               visited.insert(x * 10 + digit);
            }
            digit = lastNum - K;
            if(digit >= 0 && digit <= 9 && !visited.count(x * 10 + digit)){
               dp[i + 1].push_back(x * 10 + digit);
               visited.insert(x * 10 + digit);
            }
         }
      }
      if(N == 1){
         dp[N].push_back(0);
      }
      return dp[N];
   }
};
main(){
   Solution ob;
   print_vector(ob.numsSameConsecDiff(3,7));
}

입력

3
7

출력

[181,292,707,818,929]