Интервью Вопрос: обрезать несколько последовательных пробелов из строки

Question

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

input  = "I    Like    StackOverflow a      lot"
output = "I Like StackOverflow a lot"

Строковые функции недопустимы, так как это вопрос интервью.Ищем алгоритмическое решение задачи.

Answer 1

Может ли использование <algorithm> квалифицироваться как "алгоритмическое решение"?

#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
struct BothAre
{
    char c;
    BothAre(char r) : c(r) {}
    bool operator()(char l, char r) const
    {
            return r == c && l == c;
    }
};
int main()
{
    std::string str = "I    Like    StackOverflow a      lot";
    std::string::iterator i = unique(str.begin(), str.end(), BothAre(' '));
    std::copy(str.begin(), i, std::ostream_iterator<char>(std::cout, ""));
    std::cout << '\n';
}

тестовый прогон: https://ideone.com/ITqxB

Answer 2

C ++ 0x - решение, использующее лямбду вместо обычного объекта функции.Сравните с решением Кубби.

#include <string>
#include <algorithm>

int main()
{
    std::string str = "I    Like    StackOverflow a      lot";

    str.erase(std::unique(str.begin(), str.end(),
      [](char a, char b) { return a == ' ' && b == ' '; } ), str.end() );  
}

Answer 3

Сохраните два индекса: следующее доступное место для ввода буквы (скажем, i) и текущий индекс, который вы исследуете (скажем, j).

Просто переберите всесимволы с j, и всякий раз, когда вы видите букву, копируйте ее в индекс i, затем увеличивайте i.Если вы видите пробел, которому не предшествовал пробел, также скопируйте пробел.

I думаю, это будет работать на месте ...

Answer 4

Я бы просто пошел с этим:

int main(int argc, char* argv[])
{
    char *f, *b, arr[] = "  This        is    a test.                ";
    f = b = arr;

    if (f) do
    {
        while(*f == ' ' && *(f+1) == ' ') f++;
    } while (*b++ = *f++);

    printf("%s", arr);

    return 0;
}

Answer 5

Я бы предложил небольшой конечный автомат (простой оператор switch). Потому что, если интервьюер похож на меня, первое улучшение, которое они попросят вас сделать, это полностью обрезать все начальные или конечные пробелы, чтобы:

"    leading and    trailing    "

преобразуется в:

"leading and trailing"

вместо:

" leading and trailing "

Это действительно простая модификация конструкции конечного автомата, и мне кажется, что проще понять логику конечного автомата в целом по «прямому» кодированному циклу, даже если для этого требуется еще несколько строк код, чем прямой цикл.

И если вы утверждаете, что изменения в прямом цикле не будут слишком плохими (что можно обоснованно аргументировать), то я (как интервьюер) добавлю, что я также хочу, чтобы начальные нули из чисел были обрезается.

С другой стороны, многим интервьюерам может на самом деле не нравиться решение с автоматом состояний как «неоптимальное». Я думаю, это зависит от того, что вы пытаетесь оптимизировать.

Answer 6

Это очень простая реализация удаления лишних пробелов.

#include <iostream>
std::string trimExtraWhiteSpaces(std::string &str);
int main(){
    std::string str = "  Apple    is a     fruit  and I like     it   .  ";
    str = trimExtraWhiteSpaces(str);
    std::cout<<str;
}
std::string trimExtraWhiteSpaces(std::string &str){
    std::string s;
    bool first = true;
    bool space = false;
    std::string::iterator iter;
    for(iter = str.begin(); iter != str.end(); ++iter){
        if(*iter == ' '){
            if(first == false){
                space = true;
            }
        }else{
            if(*iter != ',' && *iter != '.'){
                if(space){
                    s.push_back(' ');
                }
            }
            s.push_back(*iter);
            space = false;
            first = false;
        }
    }
    return s;
}

Answer 7

Функциональный вариант в Haskell:

import Data.List (intercalate)

trimSpaces :: String -> String
trimSpaces =  intercalate " " . words

Алгоритм следующий:

1. разбивает строку на список слов, разделенных пробелом
2. объединить список, вставив один пробел между каждым элементом в списке

Answer 8

void trimspaces(char * str){
    int i = 0;
    while(str[i]!='\0'){
        if(str[i]==' '){
            for(int j = i + 1; j<strlen(str);j++){
                if(str[j]!=' '){
                    memmove(str + i + 1, str + j, strlen(str)-j+1);
                    break;
                }
            }
        }
        i++;
    }
}

Answer 9

int j = 0;
int k=0;
char str[] = "I    Like    StackOverflow a      lot"; 
int length = strlen(str);
char str2[38];
for (int i = 0; i < length; i++) 
{ 
    if (str[i] == ' ' && str[i+1] == ' ') 
     continue; 
    str2[j] = str[i];
    j++;
} 

str2[j] =NULL;

cout<<str2;

Answer 10

Обрезка нескольких пробелов также означает, что за пробелом всегда должен следовать непробельный символ.

int pack = 0;
char str[] = "I    Like    StackOverflow a      lot";
for (int iter = 1; iter < strlen(str); iter++)
{
    if (str[pack] == ' ' && str[iter] == ' ')
        continue;
    str[++pack] = str[iter];
}
str[++pack] = NULL;