Поиск палиндромов в связанном списке

Question

Это вопрос интервью (снова).

Учитывая односвязный связанный список, найдите самый большой палиндром в списке.(Вы можете предположить, что длина палиндрома четная)

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

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

Какой-нибудь лучший способ помочь мне?:(

Answer 1

Можно придумать O (n²) -алгоритм с O (1) пространственной сложностью следующим образом:

Рассмотрим f→o→b→a→r→r→a→b:

Пройдите по списку, переворачивая ссылки во время посещения. Начните с x=f и y=f.next:

• набор x.next = null

• f o→b→a→r→r→a→b
  ^ ^
  |  \
  x   y

  и проверьте, сколько ссылок в обоих списках (x и y) равны.
• Теперь продолжайте. (tmp=y.next, y.next=x, x=y, y=tmp) Например. на втором шаге он даст f←o b→a→r→r→a→b с x=o и y=b, теперь вы снова проверяете, является ли это палиндромом, и продолжаете:
• f←o←b a→r→r→a→b
• f←o←b←a r→r→a→b
• f←o←b←a←r r→a→b yay:)
• и т.д.

Если вам нужно восстановить список снова, снова измените его в O (n)

Answer 2

Это хорошо проанализированная проблема с O (N) сложностью времени.

• Вы можете изменить исходную строку (скажем, str и str_reversed)

Затем проблема преобразуется в: найти самую длинную общую подстроку в str и str_reversed.

• Подход O (N) создает дерево суффиксов (O (N)) с постоянным временем поиска наименьшего общего предка.

Answer 3

Если вы копируете списки в массив, может пригодиться следующее: Поскольку мы рассматриваем только палиндромы четной длины, я предполагаю, что это так. Но техника может быть легко расширена для работы с палиндромами странной длины.

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

Рассмотрим слово: aabbabbabab. Мы ищем самый длинный палиндром.

a a b b a b b a b a b (spaces for readability)
°^°                   start at this position and look to the left/right as long as possible,
 1                    we find a palindrome of length 2 (but we store "1")
                      we now have a mismatch so we move the pointer one step further
a a b b a b b a b a b
   ^                  we see that there's no palindrome at this position, 
 1 0                  so we store "0", and move the pointer
a a b b a b b a b a b
  ° °^° °             we have a palindrome of length 4, 
 1 0 2                so we store "2"
                      naively, we would move the pointer one step to the right,
                      but we know that the two letters before pointer were *no*
                      palindrome. This means, the two letters after pointer are
                      *no* palindrome as well. Thus, we can skip this position
a a b b a b b a b a b
         ^            we skipped a position, since we know that there is no palindrome
 1 0 2 0 0            we find no palindrome at this position, so we set "0" and move on
a a b b a b b a b a b
      ° ° °^° ° °     finding a palindrome of length 6,
 1 0 2 0 0 3 0 0      we store "3" and "mirror" the palindrome-length-table
a a b b a b b a b a b
                 ^    due to the fact that the previous two positions hold "0", 
 1 0 2 0 0 3 0 0 0    we can skip 2 pointer-positions and update the table
a a b b a b b a b a b
                   ^  now, we are done
 1 0 2 0 0 3 0 0 0 0

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

Другой пример: aaaaaab

a a a a a a b
°^°
 1

a a a a a a b
° °^° °
 1 2 1        we can fill in the new "1" since we found a palindrome, thus mirroring the
              palindrome-length-table
a a A A a a b (capitals are just for emphasis)
     ^        at this point, we already know that there *must* be a palindrome of length
 1 2 1        at least 1, so we don't compare the two marked A's!, but start at the two 
              lower-case a's

Моя точка зрения такова: как только мы найдем палиндромы, мы сможем отразить (хотя бы часть) таблицы длины палиндрома и, таким образом, вывести информацию о новых персонажах. Таким образом, мы можем сохранить сравнения.

Answer 4

Я сделал это с помощью рекурсии за O (n) время.Я делаю это с помощью

1. . Предположим, у нас есть связанный список источников, теперь скопируйте весь связанный список в другой связанный список, то есть целевой связанный список;
2. теперь обратный целевой объект связанlist;
3. теперь проверяет, равны ли данные в исходном связанном списке и целевом связанном списке, равны ли они палиндрому, в противном случае они не являются палиндромом.
4. теперь освобождает связанную цельсписок.

Код:

#include<stdio.h>
#include<malloc.h>

struct node {
    int data;
    struct node *link;
};

int append_source(struct node **source,int num) {
    struct node *temp,*r;
    temp = *source;
    if(temp == NULL) {
        temp = (struct node *) malloc(sizeof(struct node));
        temp->data = num;
        temp->link = NULL;
        *source = temp;
        return 0;
    }
    while(temp->link != NULL) 
        temp = temp->link;
    r = (struct node *) malloc(sizeof(struct node));
    r->data = num;
    temp->link = r;
    r->link = NULL;
    return 0;
}

int display(struct node *source) {
    struct node *temp = source;
    while(temp != NULL) {
        printf("list data = %d\n",temp->data);
        temp = temp->link;
    }
    return 0;
}

int copy_list(struct node **source, struct node **target) {
    struct node *sou = *source,*temp = *target,*r;
    while(sou != NULL) {
        if(temp == NULL) {
            temp = (struct node *) malloc(sizeof(struct node));
            temp->data = sou->data;
            temp->link = NULL;
            *target = temp;
        }
        else {
            while(temp->link != NULL) 
                temp = temp->link;
            r = (struct node *) malloc(sizeof(struct node));
            r->data = sou->data;
            temp->link = r;
            r->link = NULL;
        }
        sou = sou->link;
    }
    return 0;
}

int reverse_list(struct node **target) {
    struct node *head = *target,*next,*cursor = NULL;
    while(head != NULL) {
        next = head->link;
        head->link = cursor;
        cursor = head;
        head = next;
    }
    (*target) = cursor;
    return 0;
}

int check_pal(struct node **source, struct node **target) {
    struct node *sou = *source,*tar = *target;
    while( (sou) && (tar) ) {
        if(sou->data != tar->data) {
            printf("given linked list not a palindrome\n");
            return 0;
        }
        sou = sou->link;
        tar = tar->link;
    }
    printf("given string is a palindrome\n");
    return 0;
}

int remove_list(struct node *target) {
    struct node *temp;
    while(target != NULL) {
        temp = target;
        target = target->link;
        free(temp);
    }
    return 0;
}

int main()
{
    struct node *source = NULL, *target = NULL;
    append_source(&source,1);
    append_source(&source,2);
    append_source(&source,1);
    display(source);
    copy_list(&source, &target);
    display(target);
    reverse_list(&target);
    printf("list reversed\n");
    display(target);
    check_pal(&source,&target); 
    remove_list(target);
    return 0;
}

Answer 5

Сначала найдите среднюю точку связанного списка, для этого прохождения через связанный список и посчитайте количество узлов.

Допустим, количество узлов равно N, средняя точка будет равна N / 2.

Теперь перейдите к узлу средней точки и начните переворачивать связанный список до конца, что можно сделать на месте со сложностью O (n).

Затем сравните элементы от начала до середины с элементами от середины до конца, если они все равны, строка - палиндром, в противном случае - разрыв.

Сложность времени: - O (n)

Сложность пространства: - O (1)

Answer 6

Вот алгоритм O (n ^ 2):

1. Преобразование списка в двусвязный список

2. Чтобы иметь четныйПри длине палиндрома у вас должны быть две одинаковые буквы рядом друг с другом.Поэтому итерируйте по каждой паре соседних букв (n-1 из них) и на каждой итерации, если буквы идентичны, найдите самый большой палиндром, средние буквы которого - эти две.