Снова и снова

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

Как всегда, перед началом два оговорки:

  • Эти задачи предоставляет замечательный информационный бюллетень 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 управляет такими операциями внутри. Если вы знаете больше об этом, пожалуйста, дайте мне знать!

Тогда вот мои решения! Что вы о них думаете? Вы знаете или используете какой-либо из этих языков? Дайте мне знать, похлопав в ладоши или ответив на статью с вашим шансом решить эту проблему!

Если вам понравился пост, спасибо за чтение: не забудьте подписаться на блог, я буду публиковать материалы, связанные с ИТ и программированием, каждый раз, когда смогу. И если вы этого не сделали, все равно спасибо, что дочитали до конца: дайте мне знать, как улучшить!

Как всегда, спасибо за чтение.

Никола