คำอธิบายปัญหา
หาจำนวนเต็มบวกทั้งหมดที่มีความยาว N หลัก โดยความต่างสัมบูรณ์ระหว่างหลักติดกันทุกคู่เท่ากับ K ไม่อนุญาตให้มี leading zeros (ยกเว้นตัวเลข 0 เอง)
ตัวอย่าง: N=3, K=7 → [181,292,707,818,929] (070 ไม่ได้เพราะ leading zero)
วิธีแก้ปัญหา (DP / BFS)
- เริ่มจากหลักแรก 1-9 (ไม่สามารถเป็น 0 ได้)
- สร้างตัวเลขยาวขึ้นทีละหลัก: เพิ่มหลักใหม่ = หลักสุดท้าย ± K (ถ้าอยู่ใน 0-9)
- ใช้ set ป้องกันซ้ำ
- ทำซ้ำ N-1 รอบ
- กรณี N=1 เพิ่ม 0 เข้าไป
ตัวอย่างโค้ด C++
#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] << (i+1 < v.size() ? ", " : "");
}
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 x : dp[i]) {
int last = x % 10;
for(int d : {last + K, last - K}) {
if(d >= 0 && d <= 9 && !visited.count(x * 10 + d)) {
dp[i+1].push_back(x * 10 + d);
visited.insert(x * 10 + d);
}
}
}
}
if(N == 1) dp[N].push_back(0);
return dp[N];
}
};
int main() {
Solution ob;
print_vector(ob.numsSameConsecDiff(3, 7));
return 0;
}
อินพุต
3 7
เอาต์พุต
[181, 292, 707, 818, 929]
