Các số có sự khác biệt liên tiếp giống nhau trong C ++

Giả sử chúng ta phải tìm tất cả các số nguyên không âm có độ dài N sao cho hiệu số tuyệt đối giữa mọi chữ số liên tiếp là K. Chúng tôi có thể trả lại câu trả lời theo bất kỳ thứ tự nào. Vì vậy, nếu N =3 và K =7, thì đầu ra sẽ là [181,292.707,818,929], Ở đây chúng ta có thể thấy 070 không phải là một số hợp lệ, vì nó có một số 0 ở đầu.

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

• Tạo một ma trận gọi là dp và kích thước của nó sẽ là n + 1, điền từ 1 đến 9 vào dp [1]

• cho tôi trong phạm vi từ 1 đến N - 1

  • Xác định một tập hợp được gọi là đã truy cập

  • cho j trong phạm vi 0 đến kích thước của dp [i]

    • x:=dp [i, j]

    • lastNum:=chữ số cuối cùng của x

    • chữ số:=lastNum + k

    • nếu chữ số nằm trong phạm vi từ 0 đến 9 và (x * 10 + chữ số) không được truy cập, thì

      • chèn (10 * x + chữ số) vào dp [i + 1]

      • chèn chữ số 10 * x + vào mảng đã truy cập

    • chữ số:=lastNum - K

    • nếu chữ số nằm trong phạm vi từ 0 đến 9 và (x * 10 + chữ số) không được truy cập, thì

      • chèn (10 * x + chữ số) vào dp [i + 1]

      • chèn chữ số 10 * x + vào mảng đã truy cập

• nếu N là 1, thì chèn 0 vào dp [N]

• trả về dp [N]

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;
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));
}

Đầu vào

3
7

Đầu ra

[181,292,707,818,929]