数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中给定数字集最多为 N 的数字
假设我们有一个排序好的数字集合 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，当 i < sz，更新 (i 加 1)，执行：
ret := ret + (D 的大小)^i
对于初始化 i := 0，当 i < sz，更新 (i 加 1)，执行：
hasSameNum := false
对于 D 中的每个字符串 x：
如果 x[0] < n[i]，则：
ret := ret + (D 的大小)^(sz - i - 1)
否则，如果 x[0] 与 n[i] 相同，则：
hasSameNum := true
如果 hasSameNum 为假，则：
返回 ret
返回 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
更新于：2020年6月4日
138 次浏览
广告