-1

可能重复：
c ++程序查找包含不同数字的整数总数

假设我有一个无符号整数，称它为低，另一个称它为高，这样高>低。问题是找到包含此范围内不同数字的整数。例如，假设 low 为 1，high 为 10，则答案为 10，因为此范围内的所有数字都包含不同的数字。如果假设 low 是 1，high 是 12，那么答案是 10，因为 11 包含相同的数字。例如 123,234,4567 是有效数字，但 121,2342,4546 是无效数字。我不是在寻找暴力算法。如果任何人都有比通常的蛮力方法更好的解决方案，请告诉..

4

2 回答 2

0

我将推导出一个算法来确定从 0-n 中这些数字的数量，然后您可以简单地计算（有效数字的数量 0-高）-（有效数字的数量 0-低）。要获取有效数字 0-n，请查看您的数字中的位数：例如，如果 n 有 5 位数字，则每个有效的 1、2、3 和 4 位数字都在您的结果集中。因此，对于一个 4 位数字，您计算该 4 位数字中所有可能的数字组合：1234、1235、1236...5678、5789 和 6789。然后计算排列数（1234 也可以是 1243， 1324、1342...等），并乘以（排列的数量）x（您在上一步中导出的不同序列的数量）。然后你就有了所有 4 位数字的答案。对每一组做同样的事情，并为你的上一组想出更具体的东西；如果高是5500，您需要介于 5000-5100 之间的有效数字。您可以应用类似的算法，但不是使用所有数字 0-9，而是使用 9 个不同的数字，省略“5”。请注意，所有数字也可以有一个 0，但不是在开头，因此算法也需要考虑这一点。

于 2012-11-10T19:06:55.943 回答
0

只需将您的数字转换为字符串，然后在检查给定字符是否已在您的字符串中出现的同时运行它。例如：

#include <string>

int main()
{
    std::string s = std::to_string(12345);
    bool occuredCheck[10] = {0}; //automatically fills with zeros. 10 values for the 10 numbers
    bool isValidNumber = true;

    for(int i=s.length()-1; i>=0; ++i)
        if(occuredCheck[s[i] - '0'] ^ true == 0) isValidNumber = false;
}

如果数字出现两次，则 if 行将数组条目设置为零，请参阅XOR。并isValidNumber让您知道它是否真的是您的有效号码。顺便说一句：这个例子需要 C++11 用于std::to_string.

使用此算法，您可以检测到第一个无效数字，然后使用它设置您的范围。

于 2012-11-10T19:09:34.607 回答