Разбор задач

Задача 1.

Дан связный список. Нужно написать функцию swapNodes, которая будет менять местами каждые два соседних узла и возвращать голову списка.

Пример 1:

Дан связный список 1 —> 2 —> 3 —> 4

Ответ в этом случае такой: 2 —> 1 — > 4 —> 3

Пример 2:

Дан связный список a —> b —> c

Ответ: b — > a — > c

Узел будем представлять таким образом:

Скопировать кодJSX
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

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

Рассмотрим алгоритм подробнее:

Заведем переменную tmp. Присвоим полю next этой переменной значение head. В конце работы алгоритма вернем его из функции.

Присвоим переменной cur значение head, prev - tmp.

Пока cur не равно None, и cur.next не равно None, будем в цикле выполнять такие действия:

Присвоим переменной cur_next значение поля next переменной cur.
Переменной next_tmp
- значение поля next переменной cur_next.
Запишем в поле next переменной prev значение cur_next.
В поле next переменной cur_next
- значение cur.
В поле next переменной cur
- значение next_tmp.
Присвоим переменной prev значение cur.
Переменной cur
- значение next_tmp.

После завершения цикла вернем из функции tmp.next, то есть голову списка.

Код алгоритма:

Скопировать кодJSX
def swapNodes(head):
    cur = head
    tmp = Node('-1')
    tmp.next = head
    prev = tmp
    while cur is not None and cur.next is not None:
        cur_next = cur.next
        next_tmp = cur_next.next
        prev.next = cur_next
        cur_next.next = cur
        cur.next = next_tmp
        prev = cur
        cur = next_tmp
    return tmp.next

Попробуем посмотреть, что вернет функция для первого примера:

Скопировать кодJSX
node = Node(1, Node(2, Node(3, Node(4))))
node = swapNodes(node)

while node:
    print(node.value)
    node = node.next
# 2
# 1
# 4
# 3

Задача 2.

Дана закодированная строка, нужно её декодировать. Кодирование производится так: n[symbol] значит, что символ повторяется n раз.

Пример 1:

Входная строка: "2[a]3[bc]1[d]" Ответ: 'aabcbcbcd'

Пример 2:

Входная строка: "3[a2[b]]" Ответ: 'abbabbabb'

Решать задачу будем с использованием стека. Комментарии представлены в коде для простоты его понимания.

Скопировать кодJSX
def transformString(input_string):
    stack = []
    result = ''
      tmp = ''
    # Пройдем по всем символам строки
    for symbol in input_string:
        if stack:
            # Если стек не пуст
            if symbol != ']':
                # Если число больше 9, то нужно соединить цифры в число
                if stack[-1].isdigit() and symbol.isdigit():
                    # Если на верхушке стека цифра, прибавляем текущее значение
                    stack[-1] += symbol
                else:
                    # Добавляем символ в стек
                    stack.append(symbol)
            else:
                # Если текущий символ ']' извлекаем из стека элементы, пока не дойдем до '[' 
                while stack[-1] != '[':
                    tmp = stack.pop() + tmp
                stack.pop() # Извлекаем '['
                multiplier = stack.pop() # Извлекаем число необходимых повторений 
                tmp *= int(multiplier)
                # Если стек пуст, текущая итерация завершена, можно изменить переменную result
                if not stack:
                    result += tmp
                else:
                    # Иначе снова положим tmp в стек 
                    stack.append(tmp)
                tmp = '' # Присвоим переменной tmp пустую строку
        elif symbol.isalpha():
            # Если стек пуст, и текущий символ - буква, добавим ее к результату
            result += symbol
        else:
            # Иначе положим символ в стек
            stack.append(symbol)      
    return result

Рассмотрим работу алгоритма на примере "2[a]3[bc]".

На вход приходит символ 2, добавляем его в стек.
Далее добавляем в стек скобку '['
Затем добавляем букву 'a'.
Следующий входной символ - закрывающаяся скобка ']'. Извлекаем элементы из стека, пока не пойдем до открывающейся скобки. Переменная tmp становится равной 'a'.
Извлекаем открывающуюся скобку из стека.
Затем извлекаем 2. Именно это число раз следует сконкатенировать значение tmp. Получаем 'aa'. Добавляем полученное значение в переменную result.
Далее кладем в стек число 3.
Затем открывающуюся скобку '['.
Следом 'b', и далее 'c'.
Далее приходит закрывающаяся скобка ']'.
Извлекаем элементы из стека, пока не встретим '[', и добавляем символ в переменную tmp слева. Значение tmp станет равным 'bc'.
Извлечем открывающуюся скобку '['.
Возьмем из вершины стека число 3, которое означает, сколько раз нужно сконкатенировать значение tmp. Получим, что tmp = 'bcbcbc'.
Добавим к переменной result значение tmp.
В результате получим ответ 'aabcbcbc'.