1

これが私のジレンマです。

たとえば、次の文字列があります。

"1 2 3 4 5 ..... 100" ですが、任意の長さにすることができます (通常は、4 桁の数字について話す、はるかに大きなもの)。

私がする必要があるのは、既知の位置に基づいて文字列の要素を再配置することです。例: 問題の位置は 70 です。次の出力が必要です: "70 71 ....100 1 2 3 ...69"

条件：

  1. 私は鍵を知っています：例えば上記の「70」。文字列の長さによっては、500、5000 の場合もあります。
  2. 文字列バッファまたは文字列管理関数を使用できません。
  3. 利用可能なメモリがほとんどまたはまったくありません。
  4. 2 つの 1 バイト バッファが利用可能です。
  5. 操作は可能な限り最小限の手順で実行する必要があります (タイム クリティカル)。

文字列内のキーの位置に依存しない優れたアルゴリズムを見つけようとしています。基本的に、自分の半分に応じて左/右にシフトすると、多くの読み取り/書き込みが可能になり、それは望ましくありません。

どうもありがとう！

4

4 に答える 4

4 
std::vector<std::string> numbers((std::istream_iterator<std::string>(std::cin)),
                                 std::istream_iterator<std::string>());
std::rotate(numbers.begin(), numbers.begin() + 70, numbers.end());
于 2012-01-30T21:45:42.490 に答える
2

このコードはあなたの説明に合っていますが、あなたは漠然としているので、あなたが望むことをしているとは思えません...

#include <string>
#include <iostream>
#include <cmath>
#include <cassert>
#include <stdint.h>

int main() {
    int n = 15;
    std::string s = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  ";

    uint16_t index;
    switch((int)log10(n)) {
    case 0: // 0 - 9 
        // -2 to account for lack of "0" in the list which would have occupied 2 chars..
        index = (2 * (n)) + -2;
        break;
    case 1: // 10 - 99
        index = (3 * (n % 10)) + (10 * 2 - 2);
        break;
    case 2: // 100 - 999
        index = (4 * (n % 100)) + (90 * 3) + (10 * 2 - 2);
        break;
    case 3: // 1000 - 9999
        index = (5 * (n % 1000)) + (900 * 4) + (90 * 3) + (10 * 2 - 2);
        break;
    }

    std::string::iterator first  = s.begin();
    std::string::iterator middle = s.begin() + index;
    std::string::iterator last   = s.end();

    std::string::iterator next = middle;
    while(first != next) {

        char temp1;
        temp1 = *first;
        *first = *next;
        *next = temp1;

        ++first;
        ++next;

        if (next == last) {
            next = middle;
        } else if (first == middle) {
            middle = next;
        }
    }

    std::cout << s << std::endl;
}

次の出力が生成されます。

$ ./test 
15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14

しかし、シーケンスまでずっと同じように動作するはずです9999

于 2012-01-30T21:54:33.487 に答える
2

これは、コメントで言及した 3*逆の方法です。シンプルな C で、派手な文字列クラスはありません。スワップに必要なストレージ要素は 1 つだけです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int array[] = { 0, 1,2,3,4,5,6,7,8,9} ;
#define COUNT (sizeof array / sizeof array[0])

void reverse(int *arr, size_t siz);
void doprint(int *arr, size_t siz);
int main(int argc, char **argv)
{
unsigned pos = 3;

if (argc >1 && argv[1]) sscanf(argv[1], "%u", &pos);
if (pos >= COUNT) exit(1);

doprint(array, COUNT);
reverse(array,COUNT);
reverse(array,pos);
reverse(array+pos,COUNT-pos);
doprint(array, COUNT);
return 0;
}

void doprint(int *arr, size_t siz)
{
while( siz--) {
        printf(" %d", *arr++);
        }
printf("\n");
}

void reverse(int *arr, size_t siz)
{
int * end;
for (end= arr+siz-1; end > arr; end--,arr++) {
        int tmp;
        tmp = *arr;
        *arr = *end;
        *end = tmp;
        }
}

信じられない人のために、結果は次のとおりです。

$ ./a.out 3
 0 1 2 3 4 5 6 7 8 9
 7 8 9 0 1 2 3 4 5 6
于 2012-01-31T10:17:22.353 に答える
0

これを自分で最初から実装したい場合、手がかりは、バイトのペアを交換することで、文字列のセクションを適切な場所 (必要に応じて開始または終了のいずれか) に移動するように手配できることです。まだ所定の位置に回転する必要がある文字列。最終的には、回転する文字列が不足します。

于 2012-01-30T22:08:52.147 に答える