สมมติว่าเราต้องหาจำนวนเต็มที่ไม่ติดลบที่มีความยาว N โดยที่ผลต่างที่แน่นอนระหว่างทุก ๆ ตัวเลขสองหลักที่ต่อเนื่องกันคือ K เราต้องจำไว้ว่าทุกตัวเลขในคำตอบจะต้องไม่มีศูนย์นำหน้า ยกเว้นตัวเลข 0 เอง เราอาจส่งคืนคำตอบในลำดับใดก็ได้ ดังนั้นหาก N =3 และ K =7 ผลลัพธ์จะเป็น [181,292,707,818,929] เราจะเห็นว่า 070 ไม่ใช่ตัวเลขที่ถูกต้อง เพราะมันมีศูนย์นำหน้าหนึ่งตัว
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างเมทริกซ์หนึ่งชื่อ dp และขนาดจะเป็น n + 1 เติม 1 ถึง 9 ลงใน dp[1]
-
สำหรับผมอยู่ในช่วง 1 ถึง N – 1
-
กำหนดชุดที่เรียกว่าเยี่ยมชม
-
สำหรับ j ในช่วง 0 ถึงขนาดของ dp[i]
-
x :=dp[i, j]
-
lastNum :=หลักสุดท้ายของ x
-
หลัก :=lastNum + k
-
หากตัวเลขอยู่ในช่วง 0 ถึง 9 และไม่ได้เข้าชม (x*10 + หลัก)
-
แทรก (10*x + หลัก) ลงใน dp[i + 1]
-
แทรก 10*x + หลักลงในอาร์เรย์ที่เข้าชม
-
-
หลัก :=lastNum – K
-
หากตัวเลขอยู่ในช่วง 0 ถึง 9 และไม่ได้เข้าชม (x*10 + หลัก)
-
แทรก (10*x + หลัก) ลงใน dp[i + 1]
-
แทรก 10*x + หลักลงในอาร์เรย์ที่เข้าชม
-
-
-
-
ถ้า N คือ 1 ให้ใส่ 0 ลงใน dp[N]
-
กลับ 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]
