{'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과 같으면 숫자가 2, 3, 4, 7, 22, 23, 24, 27일 수 있으므로 출력은 20이 됩니다. , 32, 33, 34, 37, 42, 43, 44, 47, 72, 73, 74, 77. 다른 모든 숫자는 100보다 큽니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=N을 문자열로 변환
-
sz :=n의 크기, ret :=0
-
initialize i :=1의 경우, i
-
ret :=ret + (D의 크기)^i
-
-
initialize i :=0의 경우, i
-
hasSameNum :=거짓
-
D −
의 각 문자열 x에 대해-
x[0]
-
ret :=ret + (D의 크기)^(sz - i - 1)
-
-
그렇지 않으면 x[0]이 n[i]와 같을 때 -
-
hasSameNum :=참
-
-
-
hasSameNum이 0이 아닌 경우 -
-
리턴 렛
-
-
-
ret + 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