สมมติว่าเรามีชุดของตัวเลข D หนึ่งชุด ซึ่งเป็นชุดย่อยที่ไม่ว่างเป็น {'1', '2', '3', '4', '5', '6', '7', '8', ' 9'} ยกเว้น 0 ตอนนี้ เราจะเขียนตัวเลขบางตัวโดยใช้ตัวเลขเหล่านี้ โดยใช้แต่ละหลักกี่ครั้งก็ได้ตามต้องการ ดังนั้น ถ้า D ={'2','3','7'} เราอาจเขียนตัวเลขเช่น '23', '771', '2372327'
ตอนนี้เราต้องหาจำนวนเต็มบวกที่สามารถเขียนได้ซึ่งน้อยกว่าหรือเท่ากับ N
ดังนั้นหากอินพุตเป็น D =[2,3,4,7], N =100 เอาต์พุตจะเป็น 20 เนื่องจากตัวเลขสามารถเป็น 2, 3, 4, 7, 22, 23, 24, 27 , 32, 33, 34, 37, 42, 43, 44, 47, 72, 73, 74, 77. ตัวเลขอื่นๆ ทั้งหมดมีค่ามากกว่า 100
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=แปลง N เป็นสตริง
-
sz :=ขนาดของ n, ret :=0
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
-
ret :=ret + (ขนาด D)^i
-
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน
-
hasSameNum :=เท็จ
-
สำหรับแต่ละสตริง x ใน D -
-
ถ้า x[0]
-
ret :=ret + (ขนาด D)^(sz - i - 1)
-
-
มิฉะนั้นเมื่อ x[0] เหมือนกับ n[i] แล้ว −
-
hasSameNum :=จริง
-
-
-
ถ้าไม่ใช่ hasSameNum จะไม่ใช่ศูนย์ ดังนั้น −
-
รีเทิร์น
-
-
-
รีเทิร์น + 1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int atMostNGivenDigitSet(vector<string> &D, int N) {
string n = to_string(N);
int sz = n.size();
int ret = 0;
for (int i = 1; i < sz; i++) {
ret += pow(D.size(), i);
}
for (int i = 0; i < sz; i++) {
bool hasSameNum = false;
for (string &x : D) {
if (x[0] < n[i]) {
ret += pow(D.size(), sz - i - 1);
} else if (x[0] == n[i]) {
hasSameNum = true;
}
}
if (!hasSameNum)
return ret;
}
return ret + 1;
}
};
main(){
Solution ob;
vector<string> v = {"2","3","4","7",};
cout << (ob.atMostNGivenDigitSet(v, 100));
} อินพุต
{"2","3","4","7"}, 100 ผลลัพธ์
20
