C/C++字符串转移到特定元素 - 最少可能的步骤

Question

这是我的困境。

例如，我有这个字符串：

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

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

条件：

1. 我知道关键：例如上面的“70”。也可以是 500、5000，取决于字符串长度。
2. 我无法使用任何字符串缓冲区或字符串管理函数。
3. 可用内存很少甚至没有。
4. 有两个 1 字节缓冲区可用。
5. 操作应以尽可能少的步骤完成（时间关键）。

我一直在尝试找到一种不依赖于字符串中键的位置的好的算法。基本上，根据我的一半左右移动，仍然可以进行大量读/写，但我不希望这样。

多谢！

Answer 1

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());

Answer 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 应该同样有效

Answer 3

这就是我在评论中提到的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

Answer 4

如果您想自己从头开始实现这一点，线索是通过交换字节对，您可以安排将字符串的一部分移动到正确的位置（适当的开头或结尾），从而留下较短的长度仍需要旋转到位的字符串。最终你会用完绳子来旋转。