Снова и снова
Добро пожаловать обратно с еще одной проблемой, чтобы решить! Сегодня мы столкнулись с довольно простой и быстрой задачей, поэтому я подумал, что было бы интересно взглянуть на ее реализацию не только на языке.
Как всегда, перед началом два оговорки:
- Эти задачи предоставляет замечательный информационный бюллетень Daily Coding Problem, подписаться на который можно здесь. Проверьте это и попробуйте решить свои проблемы тоже!
- Я не опытный программист, а просто парень, который любит делиться своими лучшими попытками (и неудачами), пытаясь решить эти проблемы.
Без лишних слов, давайте посмотрим на сегодняшнюю проблему:
Учитывая массив и число
k
, которое меньше длины массива, поверните массив вправо наk
элементов на месте.
Вот мой взгляд на проблему. Начнем с массива, который можно повернуть вправо. Давайте представим полосу с написанными на ней символами, что-то вроде ..., E, A, B, C, D, E, A, B, C, D, E, ...
. Возьмем его кусочек, для простоты ..., A, B, C, D, E, ...
и смахнем вправо. То, что мы получим, будет ..., E, A, B, C, D, ...
. Если мы повторим задачу k
раз, скажем, k=3
раз, то получим что-то вроде этого:
Однако, если мы посмотрим внимательнее, то увидим, что 3-кратный свайп вправо означает замену последних трех элементов массива и размещение их на первых местах, в то время как первые два элемента принудительно помещаются в его конец.
Это означает, что мы можем реализовать более простой процесс, который помещает первые буквы в конец массива и удаляет их с исходного места.
Тогда задача довольно проста. Для простоты возьмем в качестве примера этот массив из пяти символов a,b,c,d,e
и коэффициент k
, равный 3. Давайте посмотрим, как это сделать на трех разных языках.
питон
Начнем с Python. Этот язык хорошо известен своей простотой в работе и поддерживается огромным сообществом профессионалов и энтузиастов, которые работали над ним с момента его рождения в 1991 году. интерпретируемый язык, поэтому ему не хватает скорости компилируемого кода. Кроме того, это динамически типизированный язык, а это означает, что нам не нужно объявлять, с какими типами переменных мы работаем. Это означает меньше работы для нас, но больше работы для переводчика. Естественно, эти проблемы заметны только в больших проектах и программах: мы можем разрабатывать эти простые алгоритмы, не думая о проблеме скорости выполнения.
Вот решение на Python:
for n in range(len(array)-k): array.append(array[0]) array = array[1:]
По сути, мы меняем первые len(array)-k
элементов массива на конец массива и после каждого цикла вырезаем первый элемент, чтобы избавиться от него.
Но мы можем больше! Python настолько прост в написании, что мы могли бы дать однострочное решение этой проблемы. Вот как:
array = array[k-1:] + array[0:k-1]
Мы просто переопределяем массив как композицию двух частей предыдущего. Первая часть состоит из элементов от k-1
до конца, а вторая часть состоит из элементов от начала до элемента с индексом k-1
.
GO
GO, также известный как Golang, это довольно молодой язык, полностью разработанный Google, который стал очень популярным за последние несколько лет. Целью Go было объединение скорости таких языков, как C и C++, с простым синтаксисом таких языков, как Python. Это привело к появлению нового языка, на котором очень быстро и просто писать. Язык статически типизирован, а это означает, что нам необходимо определить типы, с которыми мы работаем. Основным недостатком использования этих языков является отсутствие встроенных инструментов: он настолько сосредоточен на производительности, что оставляет разработчику реализацию всего, что дает ему возможность разработать все наилучшим образом. возможно… если он сможет.
Вот решение в GO.
func rotator (v []string, k int) []string { for i:=0;i<len(v)-k;i++ { v = append(v,v[0]) v = v[1:] } }
Идея остается прежней: мы делаем цикл по массиву и добавляем каждый найденный элемент в конец массива до элемента len(v)-k
. После этого мы разрезаем массив.
Котлин
Kotlin — действительно хороший язык, разработанный JetBrains, который стремится стать надежной альтернативой Java. Его цель — быть более быстрой, простой и менее раздутой версией Java, и по этой причине пару лет назад он также был официально принят Google в качестве основного языка разработки Android. Он также межъязыковый: поскольку он компилируется в байт-код Java, можно объединять код Kotlin и Java в одних и тех же проектах, используя функции и библиотеки без каких-либо ограничений друг от друга. Однако есть и проблемы: он немного сбивает с толку из-за множества встроенных функций и ключевых слов. Кроме того, для того, кто только начинает программировать, изучение Kotlin, на мой взгляд, является настоящим кошмаром из-за необходимости значительного количества времени, чтобы понять среду Java и все необходимые инструменты для построения, а также отличить, что такое Java и что такое Котлин.
Во всяком случае, вот решение на языке Kotlin.
fun rotator (array :MutableList<String>, k :Int) :MutableList<String> { for (n in 0 until array.size-k) { array.add(array[n]) } return array.subList(k-1,array.size) }
Идея та же, что и раньше: мы просто добавляем array.size — k
раз элемент nth
, а затем возвращаем subList(k-1,array.size)
.
Временная сложность
Как всегда, краткий обзор временной сложности задачи. Три алгоритма выполняются за время O(n): есть только цикл for, замедляющий выполнение, и он выполняется len(array)-len(array)-k
раз, а это означает, что время его выполнения зависит от длины массива и выбранного нами коэффициента k
.
Я не очень уверен в том, что Python one liner: на мой взгляд, он должен выполняться за время O(1), так как эта строка кода должна просто «вырезать» массив по k-му адресу памяти и поместить его с отдых в правильном месте. Однако я не совсем уверен в этом, так как не знаю, как Python управляет такими операциями внутри. Если вы знаете больше об этом, пожалуйста, дайте мне знать!
Тогда вот мои решения! Что вы о них думаете? Вы знаете или используете какой-либо из этих языков? Дайте мне знать, похлопав в ладоши или ответив на статью с вашим шансом решить эту проблему!
Если вам понравился пост, спасибо за чтение: не забудьте подписаться на блог, я буду публиковать материалы, связанные с ИТ и программированием, каждый раз, когда смогу. И если вы этого не сделали, все равно спасибо, что дочитали до конца: дайте мне знать, как улучшить!
Как всегда, спасибо за чтение.
Никола