資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告