数据结构
网络
关系数据库管理系统 (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 次浏览
广告