Есть ли способ, если строка повторяется, чтобы вернуть только повторные буквы один раз?

Question

Я сделал код, который будет для строки «aabbcc» возвращать «abc», но в тех случаях, когда больше букв, таких как «aaa», он возвращает «aa» вместо одной.

Вот кодЯ сделал.

void Ponavljanje(char *s, char *p) {
  int i, j = 0, k = 0, br = 0, m = 0;
  for (i = 0; i < strlen(s) - 1; i++) {
    for (j = i + 1; j < strlen(s); j++) {
      if (s[i] == s[j]) {
        br++;
        if (br == 1) {
          p[k++] = s[i];
        }
      }

    }
    br = 0;
  }
  p[k] = '\0';
  puts(p);
}

Для "112233" вывод должен быть "123" или для "11122333" это также должно быть "123".

Answer 1

• Избегайте повторных вызовов на strlen(s).Слабый компилятор может не видеть, что s не изменяется и вызывать strlen(s) много раз, каждый вызов страхует затраты на n операции - что совершенно неэффективно.@arkku.¹ Вместо этого просто прекратите итерацию, когда обнаружен нулевой символ .

• Инициализируйте логический список флаговдля всех char в ложь.Когда персонаж встречается, установите флаг, чтобы предотвратить последующее использование.Будьте осторожны, когда индексирование этого списка как char может быть отрицательным.

• Использование const char *s обеспечивает более широкое распределение и помогает оптимизации компилятора.

Пример:

#include <stdbool.h>
#include <limits.h>

void Ponavljanje(const char *s, char *p) {
  const char *p_original = p;
  bool occurred[CHAR_MAX - CHAR_MIN + 1] = { 0 }; // all values set to 0 (false)
  while (*s) {
    if (!occurred[*s - CHAR_MIN]) {
      occurred[*s - CHAR_MIN] = true;
      *p++ = *s;
    }
    s++; 
  }
  *p = '\0';
  puts(p_original);
}

---

¹ @ неправильный4you комментирует, что многие компиляторы могут предположить, что строка не изменилась, и оптимизировать повторяющиеся strlen() вызов.Совместимый компилятор не может сделать это, хотя без restrict, если только не известно , что во всех вызовах s и p не перекрываются.В противном случае компилятор должен предположить, что p может повлиять на s и гарантировать повторный вызов strlen().

Answer 2

Если вы хотите удалить только последовательные двойные буквы, тогда этой функции будет достаточно, и примеры, приведенные в вопросе, подойдут:

#include <stdio.h>
void Ponavljanje(char *s,char *p)
{
  char dd = '\0';
  char *r;
  if(s == NULL || p == NULL)
    return;
  r = p;
  while(*s){
    if(*s != dd){
      *r = *s;
      dd = *s;
      r++;
    }
    s++;
  }
  *r = '\0';
  puts(p);
}
int main(void)
{
  char s[20] = "1111332222";
  char p[20];
  Ponavljanje(s,p);
}

Answer 3

выполняет работу со сложностью O (n) Полагаю, программирование может дать rmg

void Ponavljanje(char *s,char *p)
{
  char n[256] = {0};
  int i = 0;

  while (*s) {
    switch (n[(unsigned char) *s]) {
    case 0:
      n[(unsigned char) *s] = 1;
      break;
    case 1:
      p[i++] = *s;
      n[(unsigned char) *s] = 2;
    }    
    s += 1;
  }

  p[i] = 0;

  puts(p);
}

Answer 4

Вот кое-что, что работает независимо от порядка:

#include <stdio.h>
#include <string.h>

void
repeat(char *s, char *p)
{
    int slen;
    int sidx;
    int pidx;
    int plen;
    int schr;

    slen = strlen(s);
    plen = 0;

    for (sidx = 0; sidx < slen; ++sidx) {
        schr = s[sidx];

        // look for duplicate char
        int dupflg = 0;
        for (pidx = 0;  pidx < plen;  ++pidx) {
            if (p[pidx] == schr) {
                dupflg = 1;
                break;
            }
        }

        // skip duplicate chars
        if (dupflg)
            continue;

        p[plen++] = schr;
    }

    p[plen] = 0;

    puts(p);
}

int
main(void)
{
    char p[100];

    repeat("112233",p);
    repeat("123123",p);

    return 0;
}

Примечание: Как уже упоминалось, strlen не следует помещать в условие условия цикла в for [потому что длина s инвариантна].Сохраните strlen(s) в отдельной переменной и выполните цикл до этого предела

---

Вот другая / более быстрая версия, которая использует гистограмму, поэтому требуется только один цикл:

#include <stdio.h>
#include <string.h>

void
repeat(char *s, char *p)
{
    char dups[256] = { 0 };
    int slen;
    int sidx;
    int pidx;
    int plen;
    int schr;

    slen = strlen(s);

    sidx = 0;
    plen = 0;

    for (sidx = 0; sidx < slen; ++sidx) {
        schr = s[sidx] & 0xFF;

        // look for duplicate char
        if (dups[schr])
            continue;
        dups[schr] = 1;

        p[plen++] = schr;
    }

    p[plen] = 0;

    puts(p);
}

int
main(void)
{
    char p[100];

    repeat("112233",p);
    repeat("123123",p);

    return 0;
}

---

ОБНОВЛЕНИЕ № 2:

Я бы предложил выполнить итерацию до завершающего байта NUL

Хорошо, вот полная версия указателя, котораятак быстро, как я знаю, как это сделать:

#include <stdio.h>
#include <string.h>

void
repeat(char *s, char *p)
{
    char dups[256] = { 0 };
    char *pp;
    int schr;

    pp = p;

    for (schr = *s++;  schr != 0;  schr = *s++) {
        schr &= 0xFF;

        // look for duplicate char
        if (dups[schr])
            continue;
        dups[schr] = 1;

        *pp++ = schr;
    }

    *pp = 0;

    puts(p);
}

int
main(void)
{
    char p[100];

    repeat("112233",p);
    repeat("123123",p);

    return 0;
}

Answer 5

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

С aaa в качестве входа, и первый, и второй a вызывают внутренний циклчтобы найти повторение, давая вам aa.Фактически, вы всегда получаете на одно вхождение меньше каждого символа на выходе, чем на входе, что означает, что он работает только для 1 или 2 вхождений на входе (что приводит к 0 и 1 вхождениям соответственно на выходе).