Удаление повторяющихся символов с помощью Python

1656647646 udalenie povtoryayushhihsya simvolov s pomoshhyu python

Энтони Систилли

u5BpGYgfdJJ1t5cWj5McotcvNXiV375fUFQp
Автор фотографии Tim Gouw из Pexels

Сейчас интервью у Google в моде. Но иногда собеседования могут получить самое лучшее для нас. Особенно если это для позиции мы действительно хотят.

Я имел удовольствие проходить собеседование во многих ведущих компаниях, будучи студентом, и устроился на работу инженера-программиста в Силиконовой долине.

Моя цель – помочь ты получить работу мечты, о которой ты всегда мечтал!

Мы собираемся рассмотреть классический вопрос, который может появиться на следующем собеседовании Google.

Предупреждение: если вы ветеран программирования, вы, вероятно, уже знаете, как решить этот вопрос!

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

ВОПРОС: если ввести строку, удалите все повторяющиеся символы и поверните новую строку.

Если вы хотите видео для объяснения вопроса, я сделал его здесь.

vv17teBZkBcz1N9YYWbuSuDrjToPBRKECOs9

Как мы видим из приведенного выше примера, результатом будет «abc», поскольку мы удаляем вторые «a», «b» и «c».

Прежде всего, давайте настроим нашу функцию в Python 2.7.

def deleteReoccurringCharacters(string):

Для ответа на этот вопрос мы собираемся использовать специальную структуру данных под названием HashSet.

LcEjXtDtuirkkf-VWJ5VNDes95irHF-8K89D
Набор

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

  1. Это совершенно неупорядоченно
  2. Он не может содержать дубликатов

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

Давайте настроим обе эти вещи.

def deleteReoccurringCharacters(string):    seenCharacters = set()    outputString = ''

Теперь, когда мы настроили нужные структуры данных, давайте поговорим о нашем алгоритме.

Поскольку набор работает в памяти, он имеет сложность времени поиска 0(1).

Это значит, что мы можем использовать его, чтобы проверить, посещали ли мы персонажа!

Наш алгоритм

Просмотрите все символы в начальной строке и выполните следующие действия.

Шаг 1. Проверьте, есть ли персонаж уже в нашем наборе

Шаг 2. Если его нет в наборе, добавьте его в набор и добавьте в строку

Давайте посмотрим, как это будет выглядеть в коде?

for char in string:    if char not in seenCharacters:        seenCharacters.add(char)        outputString += char

Нам не нужно беспокоиться о регистре «другое», потому что мы ничего не делаем с самым повторяющимся символом.

Теперь все, что осталось сделать это вернуть outputString.

Вот как выглядит готовый код:

def deleteReoccurringCharacters(string):    seenCharacters = set()    outputString = ''    for char in string:        if char not in seenCharacters:            seenCharacters.add(char)            outputString += char    return outputString

И вот оно!

Будь это собеседование, ваш рекрутер спросил бы вас о временной и пространственной сложности.

Давайте проделаем небольшой анализ.

Временная сложность

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

Для каждого из этих символов мы должны проверить, видели ли мы… Однако, поскольку время поиска HashSet равно O(1), это не влияет на нашу временную сложность.

Покидая нас с окончательной временной сложностью O(n).

Космическая сложность

В худшем случае мы получим строчку со всеми уникальными символами. Например, «abcdef».

В таком случае мы сохраняем все п элементов в нашей строке и наборе.

Однако мы также ограничены размером английского алфавита.

Это хороший шанс спросить нашего интервьюера, какой тип символов считается уникальным в строке (большие/нижние/цифры/символы).

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

Оставляя нам самый плохой сценарий космической сложности O(1).

Теперь вы знаете, как решить вопрос на собеседовании Google!

Этот вопрос, скорее всего, возникнет на ранних этапах собеседования из-за его откровенности… Как онлайн тест или первый телефонный звонок.

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

Я также опубликовал здесь готовый код Github.

Спасибо за просмотр и желаем удачи!

.a #33

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *