1

这是我的困境。

我有例如这个字符串：

"1 2 3 4 5 ..... 100" ，但它可以是任意长度（通常要大得多，指的是 4 位数字）。

我需要做的：根据已知位置重新排列字符串的元素。例如：有问题的位置是 70。我需要有以下输出：“70 71 ....100 1 2 3 ...69”

条件：

  1. 我知道关键：例如上面的“70”。也可以是500、5000，取决于字符串的长度。
  2. 我不能使用任何字符串缓冲区或字符串管理功能。
  3. 几乎没有可用的内存。
  4. 有两个可用的 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*reverse 方法。只是普通的 C，没有花哨的字符串类。交换只需要一个存储元素。

#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 回答