Удалить каждый символ в одной строке, которая соответствует любому символу в другом


Я пытаюсь решить это упражнение, в котором мне дана следующая функция:

/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
 int i, j;

 for (i = j = 0; s[i] != '\0'; i++)
     if (s[i] != c)
       s[j++] = s[i];
 s[j] = '\0';
} 

упражнение:

Написать альтернативную версию выжать(С1,С2), который удаляет все символ в S1, что соответствует любому символу в строке S2.

Я пришел с этой:

#define COPY   1
#define NOCOPY 0

void multisqueeze(char s[], char f[])
{
int i, j,k, state;
i = j = k = 0;
state = COPY;
while (s[i] != '\0')
{
    state = COPY;
    while (f[k] != '\0' && state == COPY)
    {

        printf("s is %c, f is %c\n", s[i], f[k]); 
        if (tolower(f[k]) == tolower(s[i]))
        {
            state = NOCOPY;
            printf("Nocopy set \n");
        }
        k++;
    }
    k=0;

    if (state == COPY)
    {
        printf("Copying a character, %c\n", s[i]);
        s[j++] = s[i];
    }
    i++;
}
printf("Loop ended, s is %c\n", s[i]);
s[j] = '\0';
}

Это похоже на действительное решение проблемы и выдает правильный ответ. Но мне сказали, что реализация грязный и не читаемый из-за использования переменной состояния и что есть более элегантные способы сделать это. Я пытался обернуть мою голову вокруг него в течение некоторого времени, и я просто не могу видеть способ, чтобы не использовать переменную состояния на всех. Я думаю, что это упражнение из языка C Брайан Керниган и Деннис Ритчи.



3701
3
задан 5 августа 2011 в 10:08 Источник Поделиться
Комментарии
5 ответов

Что у вас есть о(N^2) решение.

Но давайте посмотрим на приведение его в первую очередь:


  1. Вам действительно нужны эти макросы.
    Если вы должны иметь их, то почему бы не назвать переменную копировать и использовать макросы истина/ложь

#define COPY   1
#define NOCOPY 0


  1. Объявление переменных через запятую ленив и считается плохой практикой, но вы также должны использовать более описательные имена переменных. я/Дж/K не объяснить, что они используются для. Также если вы работаете больше и вы должны изменить его ищу все вхождения переменной " я " может занять некоторое время, потому что все ложные срабатывания на поиск столь ремонт, это тоже плохая идея.
    Есть пару пограничные случаи, в которых декларация может пойти не так. Так что в целом это просто лучше держаться подальше.

int i, j,k, state;


  1. Вы используете в цикле while (). Но для(;;) цикл был бы аккуратнее. Это позволяет проверить инициализацию и приращение в этом же заявлении. Это ставит всю работу по переменной k в том же месте.

    while (f[k] != '\0' && state == COPY)


  1. Вы уверены, что действительно хотите сделать этот тест?

        if (tolower(f[k]) == tolower(s[i]))


  1. ОК. Суть проблемы. Использование переменной состояния.
    Причина, по которой вы этот тест, чтобы вырваться из этого цикла while, а затем не делает фактическую работу в следующем цикле. У вас уже есть неудачные государственной информационной неявно место, где вы находитесь в цикле while тестирования, поэтому все, что вам нужно сделать, это выйти из текущего цикла. Вам не нужно делать явную проверку в состоянии, но просто использовать оператор break.

            state = NOCOPY;


  1. Так что, если мы повторно пишу свой вариант с учетом моих замечаний мы получим:

void multisqueeze(char s[], char f[])
{
int i = 0; // Iterate over s[]
int j = 0; // Iterate over s[] as elements are copied (this is the dst)

for(i = 0; s[i] != '\0'; ++i)
{
int k = 0; // Iterate over f[]
for(k = 0; f[k] != '\0'; ++k)
{
if (tolower(f[k]) == tolower(s[i]))
{
break;
}
}

if (f[k] != '\0') // Then we never reached the end of the loop
{ // This means we found a match in the f[] array
s[j++] = s[i];
}
}
s[j] = '\0';
}

Но есть решение за o(n) времени.
Что вам нужно сделать, это преобразовать поисках второй строки в единое сравнение.

Поскольку char является ограниченный диапазон (0-255), мы можем поменять пространство для времени.
Выделить массив, который представляет каждый символ возможный характер. Затем мы можем использовать это как способ, чтобы поискать существования персонажа.

Поэтому вместо того, чтобы делать это:

        for(k = 0; f[k] != '\0'; ++k)
{
if (tolower(f[k]) == tolower(s[i]))
{
break;
}
}

для каждой итерации с[]. Что вы хотите сделать, это перебрать ф[] Один раз и сохранить состояние каждого персонажа. Так что вы можете просто найти ответ на один шаг, а не итерации. Для этого мы поднимем этот цикл из внутреннего цикла и выделить массив для всех возможных значений типа char, затем отметьте любым мы находим в F[] как актуально в наше выделенный массив.

Это то, что моя будет выглядеть (на самом деле моя будет выглядеть несколько иначе, как я бы написал в стиле C++, но я перевел на C, чтобы сделать его совместимым с вопросом).

void squeeze(char s[], char f[])
{
int loopF;
int loopS;
int squeeze = 0;
int test[256] = {0}; // One for each character. Default to false.
// I would use bool here. But C does not have bool
// Could use char to save space but that can be confusing
// as not everybody considers a char as an integer type.

for(loopF = 0; f[loopF] != '\0'; ++loopF)
{ test[tolower(f[loopF])] = 1; // Mark every character in test that is in f as true.
test[toupper(f[loopF])] = 1; // Thus we can test for existence just by looking it up
}

for(int loopS=0; s[loopS]; ++loopS)
{
if (test[s[loopS]]) // Test to see if the character in s is also marked true in test.
{ squeeze++;
continue;
}
// move characters down the squeezed amount
s[loopS-squeeze] = s[loopS];
}
}

8
ответ дан 6 августа 2011 в 06:08 Источник Поделиться

Я могу предложить альтернативное решение. Он не использует какой-либо переменной состояния.

void multisqueeze(char s[], char f[]) {
char *from = s, *to = s, *p;
for( ; *from; from++ ) {
for ( p = f; *p; p++ )
if ( *from == *p )
break;
if ( !*p ) {
*to = *from;
to++;
}
}
*to = '\0';
}

2
ответ дан 5 августа 2011 в 10:08 Источник Поделиться

Хотя есть несколько способов сделать это, я думаю, представляют собой "набор" символов, которые должны быть пропущены как массив "логическое"С ... который представляет собой целое число для каждого возможного персонажа, говорите ли скопировать этот персонаж или нет:

char copy[CHAR_MAX];

// by default, we copy all characters:
memset(copy, 1, sizeof(copy));

// but we don't copy any that are contained in f:
while (*f)
copy[*f++] = 0;

Тогда я хожу по строке примерно как в оригинальной функции, но для каждого персонажа, вместо проверки того, что равна С, я хотел проверить, есть ли этот пункт в копию массива присвоено значение 0 или 1. Скопируйте каждый символ, если и только если это место в скопировать имеет значение 1 (или, по крайней мере, что это не 0 -- имейте в виду, что 0 принимает значение false, а все остальное оценивается как истинное).

1
ответ дан 6 августа 2011 в 01:08 Источник Поделиться

Очень хорошее решение было дано с учетом того, что там всего 256 символов в C и с помощью массива конечных и приемлемый размер для выполнения сравнения в O(1). Но если бы мы были в Java (или другой язык Юникода), или если проблема связана ИНЦ или тоскует вместо символов, представляющих все возможные значения в массиве может стать нецелесообразным. Чтобы сохранить алгоритм как можно быстрее, хеш-таблица может быть использована, сохраняя сравнения в O(1), но требует больше памяти. Если у вас мало памяти, этот алгоритм за o(Н*лог(Н)) время и сложность в o(n) по памяти:


  1. Вроде как входных, сохраняя исходный индекс данных в темп массивов,

  2. Удалить соответствующие данные,

  3. Сортировать обратно по индексу.

1
ответ дан 6 августа 2011 в 12:08 Источник Поделиться

для длительного отбросить строку создать поиск

#include <string.h>

void multisqueeze(char *s, char *f)
{
char mapping[256];
bzero(mapping, 256);
for(; *f != '\0'; f++) mapping[*f] = 1;
char* w = s;
while (*s != '\0') {
if (! mapping[*s])
*w++ = *s;
s++;
}
*w = '\0';
}

1
ответ дан 5 августа 2011 в 10:08 Источник Поделиться