資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢小於n且包含多個相同數字的整數
假設我們有一個整數n，我們需要找到小於或等於n的正整數個數，其中這些整數至少有一個數字出現多次。
例如，如果輸入是n = 200，則輸出為38
為了解決這個問題，我們將遵循以下步驟：
定義一個數組a
初始化x := n，當x不為零時，更新x := x / 10，執行：
將x mod 10插入到a的末尾
反轉陣列a
ret := n
初始化w := 1，d := 1，當w < a的大小，更新(w增加1)，執行：
d := d * min(9, 10 − w + 1)
ret := ret − d
定義一個函式go()。它不接受任何引數。
b := (1左移10位) − 1
初始化i := 0，當i < a的大小，更新(i增加1)，執行：
初始化d := i < 1，當d < a[i]，更新(d增加1)，執行：
ret := ret − x
如果((1左移a[i]位) 與 b進行按位與)不為零，則
b := b XOR (1左移a[i]位)
否則
返回
(ret減1)
呼叫函式go()
返回ret
讓我們來看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
vector<int> a;
for (int x = n; x; x /= 10) a.push_back(x % 10);
reverse(a.begin(), a.end());
int ret = n;
for (int w = 1, d = 1; w < a.size(); ++w) {
d *= min(9, 10 − w + 1);
ret −= d;
}
auto go = [&]() {
int b = (1 << 10) − 1;
for (int i = 0; i < a.size(); ++i) {
for (int d = (i < 1); d < a[i]; ++d) {
int x = 0;
if ((1 << d) & b) ++x;
for (int j = i + 1; j < a.size(); ++j) x *= 10 − j;
ret −= x;
}
if ((1 << a[i]) & b)
b ^= (1 << a[i]);
else
return;
}
−−ret;
};
go();
return ret;
}
int main(){
cout << solve(200) << endl;
return 0;
}輸入
200
輸出
38
更新於：2020-12-26
145 次瀏覽
廣告