Сдвиг строки C / C ++ к определенному элементу - наименьшие возможные шаги - PullRequest
Новая
       40

Сдвиг строки C / C ++ к определенному элементу - наименьшие возможные шаги

1 голос
/ 31 января 2012

вот моя дилемма.

У меня есть, например, эта строка:

"1 2 3 4 5 ..... 100", но может быть любой длины (обычно намного, намного больше, говоря о четырехзначных числах).

Что мне нужно сделать: переупорядочить элементы строки, основываясь на известной возможности. Например: рассматриваемая позиция - 70. Мне нужно иметь следующий вывод: "70 71 .... 100 1 2 3 ... 69"

Условия:

  1. Я знаю ключ: например, вышеприведенное «70». Может быть также 500, 5000, зависит от длины строки.
  2. Я не могу использовать строковые буферы или функции управления строками.
  3. Памяти практически нет.
  4. Доступны два 1-байтовых буфера.
  5. Операция должна выполняться с наименьшим количеством возможных шагов (критично ко времени).

Я пытался найти хороший алгоритм, который не зависел бы от положения ключа в строке. В основном, сдвиг влево / вправо в зависимости от того, какая половина я все еще делаю для большого количества операций чтения / записи, и я этого не хочу.

Большое спасибо!

Ответы [ 4 ]

4 голосов
/ 31 января 2012 
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());
2 голосов
/ 31 января 2012

Это 3 * обратный метод, который я упоминал в комментариях. Просто 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
2 голосов
/ 31 января 2012

этот код подходит для вашего описания, но вы достаточно расплывчаты, поэтому я сомневаюсь, что он делает то, что вы хотите ... 

#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

0 голосов
/ 31 января 2012

Если вы хотите реализовать это самостоятельно с нуля, подсказка заключается в том, что, меняя пары байтов, вы можете организовать перемещение фрагмента строки в нужное место (либо начало, либо конец в зависимости от ситуации), оставляяболее короткая длина нити, которую еще нужно повернуть на место.В конце концов вам не хватит строки для вращения.

...