-1

重複の可能性：
異なる桁を含む整数の総数を見つけるC++プログラム

私が符号なし整数を持っていると仮定して、それをlowと呼び、お互いにhigh>lowのようにhighと呼びます。問題は、この範囲で異なる数字を含む整数を見つけることです。たとえば、lowが1で、highが10の場合、答えは10です。これは、この範囲のすべての数値に個別の数字が含まれているためです。低が1で高が12であるとすると、11には同じ数字が含まれているため、答えは10になります。例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のすべての数字を使用する代わりに、「5」を省略して9つの異なる数字を使用します。すべての数値に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-line は配列エントリをゼロに設定します。数字が 2 回発生した場合は、XORを参照してください。そしてisValidNumber、それが実際にあなたにとって有効な番号であるかどうかを知らせます。ところで: この例では、C++11 が必要ですstd::to_string。

このアルゴリズムを使用すると、最初の無効な数値を検出し、それを使用して範囲を設定できます。

于 2012-11-10T19:09:34.607 に答える