Как я выясняю наименьшее количество количества символов для создания палиндрома?

Просто переопределите установщик кнопки и попробуйте установить свойство contentHorizontAlignment в установщике:

-(UIButton *)yourButton {
      [_yourButton setContentHorizontalAlignment:UIControlContentHorizontalAlignmentLeft];

    return _yourButton;
}
15
задан eeerahul 18 October 2011 в 17:18
поделиться

5 ответов

Только алгоритмы, поскольку это, вероятно, домашнее задание [Извинения Рэймонду, это вопрос интервью, а не домашнее задание, как ясно показывают его правки / комментарии. Однако алгоритмы и добавленный псевдокод все еще пригодны для этой цели, и я добавил немного кода C. в конце]

Вам нужно найти самый длинный палиндром в конце строки. Алгоритм определения того, является ли строка палиндромом, можно создать, просто запустив один указатель с начала строки и один с конца, проверяя идентичность символов, на которые они ссылаются, до тех пор, пока они не встретятся в середине. Что-то вроде:

function isPalindrome(s):
    i1 = 0
    i2 = s.length() - 1
    while i2 > i1:
        if s.char_at(i1) not equal to s.char_at(i2):
            return false
        increment i1
        decrement i2
    return true

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

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

Лучшее случай - если исходная строка была палиндромом, и в этом случае стек будет пустым. В худшем случае остается один символ (односимвольная строка автоматически становится палиндромом) и все остальные в стеке.

Количество символов, которое вам нужно добавить в конец исходной строки, - это количество символов в стек.

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

Примеры:

String      Palindrome  Stack  Notes
------      ----------  -----  -----
ABBA            Y       -      no characters needed.

String      Palindrome  Stack  Notes
------      ----------  -----  -----
ABB             N       -
BB              Y       A      one character needed.
ABBA            Y       -      start popping, finished.

String      Palindrome  Stack  Notes
------      ----------  -----  -----
FAE             N       -
AE              N       F
E               Y       AF     two characters needed.
AEA             Y       F      start popping.
FAEAF           Y       -      finished.

String      Palindrome  Stack  Notes
------      ----------  -----  -----
FOO             N       -
OO              Y       F      one character needed.
FOOF            Y       -      start popping, finished.

String      Palindrome  Stack  Notes
------      ----------  -----  -----
HAVANNA         N       -
AVANNA          N       H
VANNA           N       AH
ANNA            Y       VAH    three characters needed.
VANNAV          Y       AH     start popping.
AVANNAVA        Y       H
HAVANNAVAH      Y       -      finished.

String          Palindrome   Stack      Notes
------          ----------   --------   -----
deoxyribo           N        -
eoxyribo            N        d
oxyribo             N        ed
:                   :        :
bo                  N        iryxoed
o                   Y        biryxoed   eight chars needed.
bob                 Y        iryxoed    start popping.
ibobi               Y        ryxoed
:                   :        :
oxyribobiryxo       Y        ed
eoxyribobiryxoe     Y        d
deoxyribobiryxoed   Y        -          finished.

Преобразование этого метода в «код»:

function evalString(s):
    stack = ""
    while not isPalindrome(s):
        stack = s.char_at(0) + stack
        s = s.substring(1)
    print "Need " + s.length() + " character(s) to make palindrome."
    while stack not equal to "":
        s = stack.char_at(0) + s + stack.char_at(0)
        stack = stack.substring(1)
    print "Palindrome is " + s + "."

Для тех, кто меньше интересующийся псевдокодом, вот тестовая программа на языке C, которая делает свое дело.

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

static char *chkMem (char *chkStr) {
    if (chkStr == NULL) {
        fprintf (stderr, "Out of memory.\n");
        exit (1);
    }
    return chkStr;
}

static char *makeStr (char *oldStr) {
    char *newStr = chkMem (malloc (strlen (oldStr) + 1));
    return strcpy (newStr, oldStr);
}

static char *stripFirst (char *oldStr) {
    char *newStr = chkMem (malloc (strlen (oldStr)));
    strcpy (newStr, &(oldStr[1]));
    free (oldStr);
    return newStr;
}

static char *addFront (char *oldStr, char addChr) {
    char *newStr = chkMem (malloc (strlen (oldStr) + 2));
    sprintf (newStr, "%c%s", addChr, oldStr);
    free (oldStr);
    return newStr;
}

static char *addBoth (char *oldStr, char addChr) {
    char *newStr = chkMem (malloc (strlen (oldStr) + 3));
    sprintf (newStr, "%c%s%c", addChr, oldStr, addChr);
    free (oldStr);
    return newStr;
}

static int isPalindrome (char *chkStr) {
    int i1 = 0;
    int i2 = strlen (chkStr) - 1;
    while (i2 > i1)
        if (chkStr[i1++] != chkStr[i2--])
            return 0;
    return 1;
}

static void evalString (char *chkStr) {
    char * stack = makeStr ("");
    char * word = makeStr (chkStr);

    while (!isPalindrome (word)) {
        printf ("%s: no, ", word);
        stack = addFront (stack, *word);
        word = stripFirst (word);
        printf ("stack <- %s, word <- %s\n", stack, word);
    }
    printf ("%s: yes, need %d character(s)\n", word, strlen (stack));

    printf ("----------------------------------------\n");
    printf ("Adjusting to make palindrome:\n");
    while (strlen (stack) > 0) {
        printf ("   %s, stack <- %s\n", word, stack);
    word = addBoth (word, *stack);
    stack = stripFirst (stack);
    }
    printf ("   %s\n", word);
    printf ("========================================\n");

    free (word);
    free (stack);
}

int main (int argc, char *argv[]) {
    int i;
    for (i = 1; i < argc; i++) evalString (argv[i]);
    return 0;
}

Выполнение этого с:

mkpalin abb abba fae foo deoxyribo

дает результат:

abb: no, stack <- a, word <- bb
bb: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
   bb, stack <- a
   abba
========================================

abba: yes, need 0 character(s)
----------------------------------------
Adjusting to make palindrome:
   abba
========================================

fae: no, stack <- f, word <- ae
ae: no, stack <- af, word <- e
e: yes, need 2 character(s)
----------------------------------------
Adjusting to make palindrome:
   e, stack <- af
   aea, stack <- f
   faeaf
========================================

foo: no, stack <- f, word <- oo
oo: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
   oo, stack <- f
   foof
========================================

deoxyribo: no, stack <- d, word <- eoxyribo
eoxyribo: no, stack <- ed, word <- oxyribo
oxyribo: no, stack <- oed, word <- xyribo
xyribo: no, stack <- xoed, word <- yribo
yribo: no, stack <- yxoed, word <- ribo
ribo: no, stack <- ryxoed, word <- ibo
ibo: no, stack <- iryxoed, word <- bo
bo: no, stack <- biryxoed, word <- o
o: yes, need 8 character(s)
----------------------------------------
Adjusting to make palindrome:
   o, stack <- biryxoed
   bob, stack <- iryxoed
   ibobi, stack <- ryxoed
   ribobir, stack <- yxoed
   yribobiry, stack <- xoed
   xyribobiryx, stack <- oed
   oxyribobiryxo, stack <- ed
   eoxyribobiryxoe, stack <- d
   deoxyribobiryxoed
========================================
48
ответ дан 1 December 2019 в 00:10
поделиться

просто

static int GetNumForPalindrome(string str)
    {
        int count = 0;
        for (int start = 0, end = str.Length - 1; start < end; ++start)
        {
            if (str[start] != str[end])
                ++count;
            else --end;
        }
        return count;
    }
    static void Main(string[] args)
    {
        while (true)
        {
            Console.WriteLine(GetNumForPalindrome(Console.ReadLine()).ToString());

        }

    }
1
ответ дан 1 December 2019 в 00:10
поделиться

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

Используя этот алгоритм, вы можете решить проблему в O (n ^ 2) .

1
ответ дан 1 December 2019 в 00:10
поделиться

В дополнение к ответу Пакса. Вы можете использовать алгоритм Манахера линейного времени, описанный в «Драгоценностях стрингологии», для вычисления радиусов палиндромов в тексте. Используя это, вы можете легко вычислить длину самого длинного палиндрома в конце текста за линейное время. Я думаю, что это ускоряет алгоритм Пакса до линейного времени.

РЕДАКТИРОВАТЬ:

Алгоритм Пакса работает при условии, что вы можете добавлять символы только в конец строки. Попробуйте с помощью BAAABAAB, вы получите BAAABAABAAAB, но вы можете превратить его в BAABABAAB с помощью одной вставки или BAABAAABAAB, если вы можете добавить только в конце или в начале.

1
ответ дан 1 December 2019 в 00:10
поделиться

создайте функцию, которая принимает строку и число n, а затем пытается преобразовать строку в палиндром, добавляя n дополнительных символов ..
для n = 0 .. ничего не делать
для n = 1 ... добавить первый символ ... и так далее
запустить эту функцию от n = 0 до длины исходной строки ..
первое число n, для которого он возвращает успех .. это ваш ответ

0
ответ дан 1 December 2019 в 00:10
поделиться
Другие вопросы по тегам:

Похожие вопросы: