Giả sử chúng ta có độ dài n. Chúng ta phải tìm tất cả các số nét vẽ có độ dài n.
Như chúng ta biết rằng số nét vẽ là số trông giống nhau khi xoay 180 độ.
Vì vậy, nếu đầu vào là n =2, thì đầu ra sẽ là ["11", "69", "88", "96"]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định ret mảng
-
nếu n là số lẻ thì -
-
chèn "0" vào cuối ret
-
chèn "1" vào cuối ret
-
chèn "8" vào cuối ret
-
-
Nếu không
-
chèn chuỗi trống vào cuối ret
-
-
cho n> 1, cập nhật n:=n - 2, do -
-
Xác định tạm thời mảng
-
để khởi tạo i:=0, khi tôi
-
s:=ret [i]
-
nếu n> 3, thì -
-
chèn "0" concatenate s nối "0" vào cuối tạm thời
-
-
chèn "1" concatenate s nối "1" vào cuối tạm thời
-
chèn "8" concatenate s nối "8" vào cuối tạm thời
-
chèn "6" concatenate s nối "9" vào cuối tạm thời
-
insert "9" concatenate s concatenate "6" vào cuối temp
-
-
ret:=temp
-
-
trả lại ret
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string< findStrobogrammatic(int n) {
vector<string< ret;
if (n & 1) {
ret.push_back("0");
ret.push_back("1");
ret.push_back("8");
}
else {
ret.push_back("");
}
for (; n > 1; n -= 2) {
vector<string< temp;
for (int i = 0; i < ret.size(); i++) {
string s = ret[i];
if (n > 3) {
temp.push_back("0" + s + "0");
}
temp.push_back("1" + s + "1");
temp.push_back("8" + s + "8");
temp.push_back("6" + s + "9");
temp.push_back("9" + s + "6");
}
ret = temp;
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.findStrobogrammatic(3));
} Đầu vào
3
Đầu ra
[101, 808, 609, 906, 111, 818, 619, 916, 181, 888, 689, 986, ]