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

Arnab Chakraborty

更新于：2020-12-26

145 次浏览

开启你的职业生涯

完成课程获得认证

开始学习